원형 연결 리스트, 삽입

<원형 연결 리스트>

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

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

<원형 연결 리스트 삽입>

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

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 한빛아카데미(주)