연결리스트의 다양한 구현

원형연결리스트에서 마지막 노드의 링크는 다른 노드들의 링크와 의미가 다르기 때문에 마지막 노드임을 나타내는 정보를 유지하는 것이 필요하다.

 

원형연결리스트는 첫번째 노드에 대한 포인터 대신 마지막 노드에 대한 포인터(clist)를 이용해서 나타내는 것이 일반적이다.

 

이와 같이 하면, 원형연결리스트의 첫 번째 노드는 항상 마지막 노드(clist 노드)의 링크를 통해 접근할 수 있다.

첫 번째 노드로 추가되는 경우에는 노드포인터 clist가 나타내는 마지막 노드의 링크가 변경되는 반면에 마지막 노드로 추가되는 경우에는 노드포인터 clist 자체가 변경된다.

 

이중연결리스트에도 원형연결리스트의 개념을 사용할 수 있다. 이중연결리스트에서 원형연결리스트 개념을 사용한 것을 이중원형연결리스트(doubley circular linked list)라고 한다.

 

이중연결리스트에서는 항상 첫 번째 노드의 before 링크와 마지막 노드의 after 링크가 항상 NULL 이지만 이중원형연결리스트에서는 첫 번째 노드의 before 링크는 마지막 노드를 연결하고, 마지막 노드의 after 링크는 첫 번째 노드를 연결해서 양방향으로 원형연결리스트가 되도록 한다.

 

이중원형연결리스트는 단순원형연결리스트와는 달리 마지막 노드포인터를 유지하지 않고 첫번째 노드포인터를 유지해도 마지막 노드는 첫 번째 노드(clist 노드)의 before 링크를 통해 쉽게 알 수 있다.

 

3.4 연결리스트의 다양한 구현

연결리스트는 공집합 상태의 표현방법과 삭제노드의 메모리 관리 방법등에 따라 구현할 때 추가적으로 고려해야할 사항들이 있다. 다음은 연결리스트의 추가적인 고려사항들에 대해 설명한다.

 

3.4.1 헤드노드를 이용한 연결리스트 구현

지금까지 알아본 연결리스트의 표현에서는 연결리스트가 공집합일때와 아닐 때의 표현이 다르게 된다.

 

연결리스트가 공집합 일 때는 노드가 없기 때문에 연결리스트의 첫 번째 노드를 나타내는 노드포인터는 NULL로 나타내고, 첫 번째 노드의 직전노드를 나타내는 노드포인터도 노드가 존재하지 않기 때문에 NULL로 표현 했는데, 이것은 연결리스트의 추가연산과 삭제연산 함수들을 작성할 때 함수 코드를 복잡하게 하는 원인이 된다.

 

추가노드의 처리방법은 거의 동일함에도 불구하고 첫번째 노드로 추가되는 경우와 그 이외의 경우로 구분해서 함수코드를 if-else 구조로 작성하였는데 이것은 함수의 코드구조를 그 만큼 복잡하게 하고 수행시간도 그만큼 더 많이 들게 한다.

 

그런데 만약 연결리스트를 항상 하나 이상의 노드들을 가진 상태로 표현한다면, 새로운 노드를 첫 번째 노드로 추가하는 경우, 노드포인터 current는 이 노드를 나타내게 하면 되므로 추가함수 코드를 작성할 때 두 경우로 구분할 필요가 없게 된다.

 

연결리스트를 항상 하나 이상의 노드를 가진 상태로 표현하기 위해서는 공집합 여부에 관계없이 항상 연결리스트 포인터가 항상 한 노드를 나타내게 하면 되는데, 이런 목적으로 사용되는 노드를 헤드노드(head node or dummy node)라고 한다. 즉, 헤드노드는 연결리스트의 공집합 상태와 아닌 상태를 동일하게 나타내기 위해 사용되는 맨 앞에 있는 빈 노드이다.

 

헤드노드는 다른 노드들과 같은 구조를 가지고 있지만 자료 필드는 사용하지 않는다. 헤드노드를 이용해서 연결리스트를 표현하면, 공집합 일때는 헤드노드만을 포함하고, 아닐 때는 헤드노드의 링크에 노드들이 연결된다.

 

헤드노드를 사용한 연결리스트에서 새로운 노드를 첫 번째 노드로 추가하려면 새로운 노드를 헤드노드의 링크에 연결하면 되는데, 이것은 노드포인터 current가 헤드노드를 나타내게 하고, current 노드의 직후노드로 새로운 노드를 추가하면 된다.

 

그리고 첫번째 노드를 삭제하려면, 헤드노드의 링크에 연결된 노드를 삭제하면 되는데, 이것은 노드 포인터 current가 헤드노드를 나타내게하고 current 노드의 직후노드를 삭제하면 된다.