IT, FIRE, License and Daily life

<이중 연결 리스트 삭제 연산>

1. 삭제할 노드의 오른쪽 노드의 주소(old.rlink)를 삭제할 노드의 왼쪽 노드(old.llink)의 오른쪽 링크에 저장한다.

2. 삭제할 노드의 왼쪽 노드의 주소(old.llink)를 삭제할 노드의 오른쪽 노드(old.rlink)의 왼쪽 링크(llink)에 저장한다.

3. 삭제할 노드를 자유공간리스트에 반환

① old.llink.rlink ← old.rlink;

삭제할 노드의 오른쪽 노드의 주소를 노드 old의 왼쪽노드의 rlink에 저장한다.

② old.rlink.llink ← old.llink;

삭제할 노드의 왼쪽 노드의 주소를 노드 old의 오른쪽 노드의 llink에 저장한다.

Copyrightⓒ2014 By 한빛아카데미(주)

<이중 연결 리스트 삽입 연산>

1. 삽입할 노드를 가져옴

2. 새 노드의 데이터 필드에 값 저장

3. 새 노드의 왼쪽 노드의 오른쪽 링크(rlink)를 새 노드의 오른쪽 링크(rlink)에 저장

4. 왼쪽 노드의 오른쪽 링크(rlink)에 새 노드의 주소를 저장

5. 새 노드의 오른쪽 노드의 왼쪽 링크(llink)를 새 노드의 왼쪽 링크(llink)에 저장

6. 오른쪽 노드의 왼쪽 링크(llink)에 새 노드의 주소를 저장

① new.rlink ← pre.rlink;

노드 pre(이전노드)의 rlink를 노드 new의 rlink에 저장한다.

② pre.rlink ← new;

새 노드 new의 주소를 노드 pre(이전노드)의 rlink에 저장한다.

③ new.llink ← pre;

포인터 pre의 값을 삽입할 노드 new의 llink에 저장한다.

④ new.rlink.llink ← new;

포인터 new의 값을 노드 new의 오른쪽노드의 llink에 저장한다.

Copyrightⓒ2014 By 한빛아카데미(주)

<이중 연결 리스트>

양쪽 방향으로 순회할 수 있도록 노드를 연결할 리스트이다.

[이중 연결 리스트의 노드 구조]

llink(left link) 필드 : 왼쪽 노드와 연결하는 포인터

rlink(right link) 필드 : 오른쪽 노드와 연결하는 포인터

[노드 구조에 대한 구조체]

typedef struct Dnode {

   struct Dnode *llink;

   char data[5];

   struct Dnode *rlink;

}

[이중 연결 리스트의 표현]

[이중 연결 리스트의 원형 리스트]

Copyrightⓒ2014 By 한빛아카데미(주)

<원형 연결 리스트 삭제 연산>

원형 연결 리스트 CL에서 포인터 pre가 가리키는 노드의 다음 노드를 삭제하고 삭제한 노드는 자유 공간 리스트에 반환하는 연산이다.

1. if (CL = null) then error;

공백 리스트일 경우 삭제할 노드가 없기 때문에 에러

2. else {                         

      old ← pre.link;            // ①

      pre.link ← old.link;      // ②

      if(old = CL) then          // ③ - 1

         CL ← old.link;         // ③ - 2

      returnNode(old);         // ④

   }

① old ← pre.link;

이전 노드(pre)의 다음 노드를 삭제할 노드로 지정

② pre.link ← old.link;

이전 노드(pre)의 다음 노드를 old.link인 삭제할 노드의 다음 노드로 지정

한마디로 old를 건너뛴다는 의미

③ - 1 if(old = CL) then

삭제할 노드가 원형 리스트의 첫 번째 노드일 경우

③ - 2 CL ← old.link;

CL(리스트 포인터)가 old.link인 첫번째 노드를 가리키게 한다.

두번째 노드가 리스트의 첫 번째 노드를 가리키게 한다.

Copyrightⓒ2014 By 한빛아카데미(주)

<원형 연결 리스트>

단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 연결 리스트를 원형 연결 리스트라고 한다.

링크를 따라 계속 순회하면 이전 노드에 접근이 가능하다.

<원형 연결 리스트 삽입>

[첫 번째 노드로 삽입하기]

1. if (CL = null) then {

      CL ← new;          // ①

      new.link ← new;  // ②

   }

원형리스트가 공백 리스트인 경우에는 삽입하는 노드 new는 리스트의 첫 번째 노드이자 마지막 노드가 된다.

① CL ← new;

원형 리스트의 시작을 가리키는 CL포인터가 new를 가리키게 한다.

② new.link ← new;

노드 new가 자기자신을 가리키게 한다. 첫번째 노드이자 마지막 노드이기 때문

2. else {

      temp ← CL;                       // ①

      while (temp.link ≠ CL) do   // ②

         temp ← temp.link;

      new.link ← temp.link;         // ③

      temp.link ← new;               // ④

      CL ← new;                      // ⑤

   }

원형 리스트가 공백이 아닌 경우에는 첫 번째 노드의 주소를 임시 순회 포인터(temp)에 저장하여 노드 순회의 시작점을 정한다.

① temp ← CL;

② while (temp.link ≠ CL) do

         temp ← temp.link;

temp를 링크를 따라 마지막 노드까지 이동한다.

③ new.link ← temp.link;

리스트의 마지막 노드의 링크 값을 노드 new의 링크에 저장하여, 노드 new가 노드 temp의 다음 노드(이 노드가 처음 노드임)를 가리키게 한다. (왜? 마지막 노드의 다음 노드는 리스트의 첫 번째 노드가 되기 때문에)

④ temp.link ← new;

포인터 new의 값을 포인터 temp의 마지막 노드 링크에 저장하여, 리스트의 마지막 노드가 노드 new를 가리키게 한다. 즉, 첫번째로 노드를 삽입해 주었으면 마지막 노드가 그 첫번째 노드를 가리키게 해주는 작업을 하는 것이다.

⑤ CL ← new;

노드 new의 값을 CL에 저장하여 노드 new가 리스트이 첫 번째 노드가 되도록 지정한다.

​[중간 노드로 삽입하기]

1. if (CL = null) then {

      CL ← new;

      new.link ← new;

   }

"[첫 번째 노드로 삽입하기]"의 공백 리스트일 경우와 같다.

​

2. ​else {

      new.link ← pre.link;   // ①

      pre.link ← new;     // ②

   }

​공백 리스트가 아닐 경우

① new.link ← pre.link;

​new노드의 링크에 노드(pre)의 다음노드를 연결한다.

② pre.link ← new;

​노드 new를 노드 pre의 링크(pre.link)에 저장하여 pre가 노드 new를 가리키게 한다

Copyrightⓒ2014 By 한빛아카데미(주)

<단순 연결리스트의 탐색>

1. temp ← L;

리스트의 시작주소를 temp라는 임시 포인터변수에 저장한다.

2. while (temp ≠ null) do { 

    // 시작주소가 null일 때 까지(마지막 노드일 때 까지) 반복

        if (temp.data = x) then return temp;

        // 처음 노드부터 비교하면서 temp.data가 x인지를 검사. 참이라면 temp 노드를 반환

        temp ← temp.link;

        // temp에 temp.link를 저장한다 (노드 이동)

  }

Copyrightⓒ2014 By 한빛아카데미(주)

<단순 연결 리스트의 삭제>

1. 공백 리스트인 경우

삭제할 노드가 없어 error로 표시하였다.

2. 공백 리스트가 아닌경우

① old ←pre.link;

노드 pre의 다음노드의 주소(pre.link)를 포인터 old에 저장하여, 포인터 old가 다음 노드를 가리키게 한다.

② if (old = null) then return;

만약 노드 pre가 리스트의 마지막 노드였다면 pre.link값은 null이므로 old의 값은 null이 된다.

즉, pre 뒤에 삭제할 노드가 없다는 의미이다. return으로 종료

③ pre.link ← old.link;

삭제할 노드 old의 다음 노드(old.link)를 노드 pre의 다음 노드(pre.link)로 연결한다.

④ returnNode(old);

삭제할 노드를 반환한다.

Copyrightⓒ2014 By 한빛아카데미(주)

<단순 연결 리스트의 삽입>

 삽입의 알고리즘은 첫 번째 노드로 삽입하는 경우, 중간 노드로 삽입하는 경우, 마지막 노드로 삽입하는 경우로 나뉜다.

1. 첫 번째 노드로 삽입하는 경우

① new ← getNode();
삽입할 노드를 자유 공간리스트에서 할당받는다.

② new.data ← x;
새 노드의 데이터 필드에 x를 저장

③ new.link ← L;
삽입할 노드를 연결하기 위해서 리스트의 첫 번째 노드 주소(L)를 삽입할 새 노드 new의 링크 필드(new.link)에 저장하여, 새 노드 new가 리스트의 첫 번째 노드를 가리키게 한다.

④ L ← new;
리스트의 첫 번째 노드 주소를 저장하고 있는 포인터 L에, 새 노드의 주소 new를 저장하여, 포인터 L이 새 노드를 첫 번째 노드로 가리키도록 지정

2. 중간 노드로 삽입하는 경우

중간에 노드를 삽입하기 위해서는 삽입할 위치의 앞에 있는 선행자 노드를 알려주는 포인터 pre가 필요하다. 공백 리스트일 경우와 공백 리스트가 아닐 경우로 나뉜다.

3. 마지막 노드로 삽입하는 경우

마지막에 노드를 삽입하기 위해서는 먼저 마지막 노드를 찾아야 한다. 링크 필드가 null인 노드가 마지막 노드이다. 마지막 노드를 찾기 위해서는 리스트의 노드들을 순회하는 임시 포인터 temp가 필요하다. 공백 리스트일 경우와 공백 리스트가 아닐 경우로 나뉜다.

[공백 리스트일 경우]

① L ← new;
리스트 포인터 L에 새 노드 new의 주소를 저장하여, 새 노드 new가 리스트의 첫 번째 노드가 되도록 한다.

② new.link ← null;
리스트의 마지막 노드인 new의 링크 필드에 null을 저장하여 마지막 노드임을 표시한다.

[공백 리스트가 아닐 경우]

① new.link ← pre.link;
노드 pre의 링크 필드 값을 노드 new의 링크 필드에 저장하여, 새 노드 new가 노드 pre의 다음 노드를 가리키도록 한다.

② pre.link ← new;
포인터 new의 값을 노드 pre의 링크 필드에 저장하여, 노드 pre가 새 노드 new를 다음 노드로 가리키도록 한다.

3. 마지막 노드로 삽입하는 경우

마지막에 노드를 삽입하기 위해서는 먼저 마지막 노드를 찾아야 한다. 링크 필드가 null인 노드가 마지막 노드이다. 마지막 노드를 찾기 위해서는 리스트의 노드들을 순회하는 임시 포인터 temp가 필요하다. 공백 리스트일 경우와 공백 리스트가 아닐 경우로 나뉜다.

[공백 리스트일 경우]

① L ← new;

​리스트 포인터 L에 새 노드 new의 주소를 저장하여, 새 노드 new가 리스트의 첫 번째 노드가 되도록 한다.

② temp ← L;
현재 리스트 L의 마지막 노드를 찾기 위해서 노드를 순회할 임시포인터 temp에 리스트의 첫 번째 노드의 주소(L)를 지정​

순차 자료구조의 문제점은 삽입연산이나 삭제연산 후에 연속적인 물리 주소를 유지하기 위해서 원소들을 이동시키는 추가적인 작업과 시간 소요의 낭비가 있다. 원소들의 이동 작업으로 인한 오버헤드는 원소의 개수가 많고 삽입・삭제 연산이 많이 발생하는 경우에 성능상의 문제가 발생한다.
순차 자료구조에서의 연산 시간에 대한 문제와 저장 공간에 대한 문제를 개선한 자료 표현 방법이 필요한데 그것이 연결 리스트이다.

연결 자료구조(Linked Data Structure)는 자료의 논리적인 순서와 물리적인 순서가 일치하지 않는 자료구조이다.
각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 방식이다. 이 방법은 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않는다. 크기 변경이 유연하고 더 효율적으로 메모리를 사용한다. 

<연결 리스트>

리스트를 연결 자료구조로 표현한 구조이다. 연결하는 방식에 따라 단순 연결 리스트와 원형 연결 리스트, 이중 연결 리스트, 이중 원형 연결 리스트로 나뉜다.

[노드]

<행렬>

행렬이란 행과 열로 구성된 자료구조이다. 행의 개수를 m, 열의 개수를 n개 라고 한다.

m과 n 이 같은 행렬을 정방행렬이라 한다.

<전치 행렬>

행과 열을 서로 교환하여 구성한 행렬을 말한다.

행렬 A의 모든 원소의 위치(i, j)를 (j, i)로 교환하여 m*n행렬을 n*m행렬로 변환한 행렬이다.

<희소 행렬>

원소의 대부분이 0인 행렬의 경우에는 실제 사용하는 공간보다 사용하지 않는 공간이 많아 기억 공간의 활용도가 떨어진다. 이런 행렬을 희소 행렬이라 한다.

희소 행렬에 대한 정보를 저장하기 위해서 <전체 행의 개수, 전체 열의 개수, 0이 아닌 원소의 개수>의 쌍을 즉, <8, 7, 10>을 첫번 째 행으로 저장한다. (희소행렬의 전체적인 정보 값)