단일 연결 리스트에서는 리스트의 마지막 노드의 링크 값이 널(null:^)이었지만, 환형 연결 리스트(circular linked list)는 마지막 노드의 링크의 링크 값이 널(null:^)이 아닌 리스트의 첫 번째 원소의 주소를 가리키도록 하는 구조로 되어 있다.
환형 연결 리스트의 구조
환형 연결 리스트에서는 노드의 시작과 끝을 구별하지 않음으로써 마지막 노드와 처음 노드가 연결되어 있음으로 임의의 노드에서 다른 모든 노드로의 접근이 가능하여 임의 노드의 검색이 가능하게 된다. 단순 연결 리스트의 경우 정보가 끊어지면 그 다음은 찾을 수가 없는데 환형 연결 리스트는 그것을 극복할 수 있다.
삽입시에 어떠한 변화가 있는지 볼 수 있다.
삽입시에 어떠한 변화가 있는지 볼 수 있다. (다른 예제)
삭제시에 어떠한 변화가 있는지 볼 수 있다.
환상 연결 리스트 L에 새로운 노드 I를 삽입시키는 방법에는 연결 리스트 L 앞에 새로운 노드를 삽입하는 경우와 연결 리스트 L 뒤에 새로운 노드를 삽입하는 방법이 있다. 그림과 같이 구성된 환상 연결 리스트에서 위의 두 가지 방법을 적용해 보면 다음과 같다.
연결 리스트
리스트 앞에 (new)노드를 삽입한 상태
리스트 앞에 노드를 삽입하는 알고리즘
Procedure INSERT_node_FRONT(L, I) if L = 0 then [L ←I; LINK(I) ←L;] else [LINK(I) ← LINK(L); LINK(L) ← I;] end INSERT_node_FRONT
현재 노드가 2개 이상 있으므로 else 쪽의 알고리즘이 동작하게 된다. 동작순서를 살펴보면
연결리스트 L 의 링크값을 연결리스트 I 의 링크값에 넘겨준다.
연결리스트 L은 I를 가르키도록 한다.
가 된다. I 가 추가됨으로서 기존에 L이 가르키고 있던 D0의 주소값을 I 가 물려받게 되고 L은 원래 D0을 가르키고 있었으나, 이제 새로 추가된 I 를 가르키게 되는 것이다.
노드 D를 삭제하기 전의 리스트 상태
노드 D를 삭제한 후의 리스트 상태
Procedure DELETE_node (D, X, Y) if L = 0 then empty; LINK(X) ← LINK(D); if L = D then L ← X; Y ← DATA(D); call RET(D) end DELETE_node
장 점
단 점
임의의 노드로부터 모든 노드로의 접근이 용이하다.
리스트에 노드를 삽입하거나 삭제할 때 노드 수에 관계없이 거의 일정한 시간이 소요되므로, 노드의 삽입과 삭제 연산이 편리하다.
리스트의 결합(combining), 분리(splitting) 작업을 효율적으로 수행할 수 있다.
리스트를 구성하는 특정 노드를 검색하고자 할 때 잘못하면 무한 루프(infinite loop)에 빠질 가능성이 있으므로, 검색을 끝낼 수 있는 노드가 존재하여야 하며 이런 목적으로 추가된 노드를 HEAD노드라고 한다.
