[ 자료구조 및 알고리즘 ] 5.연결 자료구조 - 3. 원형 연결 리스트

원형 연결 리스트(circular linked list)

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

• 단순 연결 리스트의 마지막 노드의 링크 필드에 첫 번째 노드의 주소를 저장하여 구성

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

• 선형 기차놀이와 원형 기차놀이 비교

원형 연결 리스트의 삽입 연산

마지막 노드의 링크를 첫 번째 노드로 연결하는 부분만 제외하고는 단순 연결 리스트에서의 삽입 연산과 같은 연산 

 3가지 경우

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

• 중간 노드로 삽입하는 경우

• 마지막 노드로 삽입하는 경우
  − 중간 노드로 삽입하는 경우의 알고리즘 사용 가능

- 첫 번째 노드로 삽입하기

• 원형 연결 리스트 CL에 x 값을 갖는 노드 new를 삽입하는 알고리즘

 

❶<< 원형리스트가 공백 리스트인 경우 >>
• 삽입하는 노드new는 리스트의 첫 번째 노드이자 마지막 노드가 되어야 함

1. CL ← new;
• 포인터 CL이 노드 new를 가리키게 한다.

2. new.link ← new;
• 노드 new가 자기자신을 가리키게 함으로써 노드 new를 첫 번째 노드이자 마지막 노드가 되도록 지정한다.

 

 

❷<< 원형리스트가 공백 리스트가 아닌 경우 >>

 1.  temp ← CL;

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

2.  while (temp.link ≠ CL) do temp ← temp.link;
• while 반복문을 수행하여 순회 포인터 temp를 링크를 따라 마지막 노드까지 이동

3. new.link ← temp.link;

•리스트의 마지막 노드의 링크 값을 노드 new의 링크에 저장하여, 노드 new가 노드 temp의 다음 노드를 가리키게 한다. 리스트 CL은 원형 연결 리스트이므로 마지막 노드의 다음 노드는 리스트의 첫 번째 노드가 된다.

4. temp.link ← new;

• 포인터 new의 값을 포인터 temp가 가리키고 있는 마지막 노드의 링크에 저장 하여, 리스트의 마지막 노드가 노드 new를 가리키게 한다.

5. CL ← new;
• 노드 new의 값을 리스트 포인터CL에 저장하여 노드 new가 리스트의 첫 번째 노드가 되도록 지정

 

알고리즘 5-8 실행 결과

 

 

 

 

 

- 중간 노드로 삽입하기

• 원형 연결 리스트 CL에 x 값을 갖는 노드 new를 포인터 pre가 가리키는 노드의 다음 노드로 삽입하는 알고리즘

❶<< 원형 연결 리스트 CL이 공백 리스트인 경우 >>
• [알고리즘 5-8]에서 공백 리스트에 첫번째 노드를 삽입하는 연산과 같음

❷<< 원형 연결 리스트 CL이 공백 리스트가 아닌 경우 >>

1. new.link ← pre.link;

노드 pre의 다음 노드로 new를 삽입하기 위해서, 먼저 노드 pre의 다음 노드(pre.link)를 new의 다음 노드(new.link)로 연결

2. pre.link ← new;

노드 new의 값(삽입할 노드의 주소)을 노드 pre의 링크에 저장하여, 노드 pre가 노드 new를 가리키도록 한다.

 

 

 

 

원형 연결 리스트의 삭제 연산

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

• 포인터 old는 삭제할 노드 지시

❶ old ← pre.link;

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

 

❷ pre.link ← old.link;
• old의 다음노드(old.link)를 노드 old의 이전노드 pre 노드와 서로 연결

 

❸<<삭제할노드old가원형연결리스트의첫번째노드인경우 >>

1. CL ← old.link;
• 첫 번째 노드를 삭제하는 경우에는 노드 old의 링크 값을 리스트 포인터 CL에 저장하여 두 번째 노드가 리스트의 첫 번째 노드가 되도록 조정

 

원형 연결 리스트의 단점

현재 지점의 이전 노드를 검색하기 위한 비용이 크다