단일 연결 리스트에서는 리스트의 마지막 노드의 링크 값이 널(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노드라고 한다.
1. 연결리스트의 정의 연결 리스트는 일정한 순서를 가지는 데이터 항목들을 표현하는 방법중의 하나이다.배열과 같은 순차적 표현 방법과는 달리 데이터 항목들의 논리적인 순서만 유지되고 기억장소 내에서는 각 항목들의 임의의 위치를 가지도록 하는 자료구조이다.
2. 연결리스트의 구조
연결 리스트에서는 각 데이터 항목들이 기억장소내의 어떤 위치에 어떤 항목이 있는 지를 표시해 주어야 한다. 이를 위해 데이터 항목에는 값뿐만아니라 다음 항목의 위치 정보도 함께 저장해둔다. 위치정보의 저장에는 포인터가 사용된다.
3. 연결리스트 에서의 포인터
연결 리스트에서 포인터는 각 항목의 다음 순서인 항목이나 앞 순서인 항목의 위치를 가르키는 지시자이다. 연결 리스트의 마지막 노드에는 다음 순서인 항목이 없고, 첫번째 노드에는 이전 순서인 항목이 없으므로 이들 포인터는 null로 해주어야 한다.
포인터는 연결 리스트의 핵심이다. 연결 리스트에서 공통적인 사항은 데이터 항목 간의 결합이 데이터 항목 자체 내에 포함되어 있는 정보에 의해 포인터의 형식으로 정의된다는 것이다. 이런 사실은 데이터 항목 간의 결합이 배열의 배치와 저장을 기반으로 하는 배열과 링크드 리스트를 분명히 구분하는 기준이다.
위의 그림에서 입력자료는 4칸의 분량인데, 저장장치에 연속된 공간은 최고 3칸밖에 없다. 이럴 경우 배열로는 입력자료를 수용하지 못한다. 그러나 연결리스트를 이용하면 연속되지 않은 빈 공간들을 효율적으로 사용할 수 있다. 다음 그림을 보자.
링크를 통해 데이터의 연결성이 보장된다.
배열과 비교하여 또다른 장점도 있다.
항상 정렬 상태가 유지되어야만 할 어떠한 배열이 있다고 하자. 새 값이 중간에 들어가야 할 경우, 배열은 다음의 모든 데이터를 뒤로 한칸씩 밀어야만 한다. 막대한 낭비가 아닐 수 없다. 소규모의 정보를 다룰 때는 사실 별로 문제가 되지 않을 것이다. 하지만 대용량의 정보를 다룰 때는 문제가 매우 심각해진다. 정부에서 국민의 주민등록정보를 배열로 저장했다고 치자. 누군가가 태어나고 죽을 때마다 움직여야 할 배열의 수는 천문학적일 것이다. 하드는 쓸데없는 자료이동에 대부분의 시간을 소모할 것이고, 막상 데이터를 읽으려면 많은 시간을 기다려야 할 것이고 공무원의 흰머리만 늘어날 것이다.따라서 이러한 것은 연결리스트를 이용하는 것이 훨씬 낫다. (그러나 앞으로 배우게 될 더 나은 자료구조들이 실제로는 이 일에 더 적합하다.)
그러나 단점도 있다. 이러한 링크는 실제적으로 다음 번 저장장소의 주소값인데, 그 값을 저장하기 위해 추가로 저장장소가 필요하게 된다. 따라서 본연의 데이터 외에 추가로 Overhead가 발생한다.
4. 연결리스트의 효율 계산
각 노드는 사용자 데이터와 다음 노드를 가리키는 포인터로 이루어진다. 이 때 효율성을 따져 보아야 한다. 예를 들어 어떤 환경에서 이 포인터가 4 바이트를 차지한다면 데이터는 4보다 훨씬 큰 용량이어야 한다. 예를 들어 데이터의 크기가 2 바이트라면 하나의 노드에 필요한 공간은 최소 6 바이트가 될 것이고, 실제 10 바이트를 저장하기 위해서는 10 / 2 = 5 개의 노드가 필요할 것이며, 이는 메모리 공간을 최소 5 * (2 + 4) = 40 바이트를 필요로 한다. 생각해 볼 필요도 없이 10 바이트를 저장하기 위해 40 바이트를 쓴다는 것은 메모리의 낭비일 것이다. 낭비되는 공간을 퍼센트로 나타내면 30 / 40 * 100 = 75(%)가 된다. 따라서 한 노드에 더 많은 데이터를 저장하여 이러한 손실을 상대적으로 줄일 수 있다. 예를 들어 한 노드에 40 바이트 크기의 데이터를 저장한다면 80 바이트를 저장하기 위한 노드의 개수는 80 / 40 = 2가 될 것이고, 필요한 메모리 공간은 최소 2 * (40 + 4) = 88이 된다. 즉 80 바이트를 저장하기 위해 88 바이트가 필요한 셈이므로 낭비되는 공간은 8 / 88 * 100 = 9(%) 정도이다.
그러나 여기에서는 리스트 구현 방법에 중점을 두고 설명할 것이기 때문에 이러한 효율성은 무시할 것이다.
