[C] 이중 연결 리스트 (Double Linked List) 1. 정의 / 생성 / 소멸

 이중 연결 리스트의 구조는 단순 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

(참고 : http://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8)

 

 이중 연결 리스트는 단순 연결 리스트에서와 같이 꼬리에 꼬리를 무는 방식으로 메모리를 활용하여 데이터를 저장하는 방식이다. 하지만, 단순 연결 리스트와 다른 점은 다음 노드에 대한 주소값 뿐 아니라, 이전 노드에 대한 주소값도 저장하고 있다는 점이다. 이는 이해하는 데에, 그리고 구현하는 데에 약간의 어려움을 주고, 하나의 노드가 생성될 때 마다, 단순 연결 리스트에 비하여 주소값을 저장할 메모리 공간을 더 쓰게 된다는 단점이 된다. 반면, 리스트에서의 삭제 수행 시간이 최대 O(n-1) 에서 O(1) 로 줄어든다는 장점이 있다.

 사용하는 메모리에 모두에 대한 주소값을 저장할 필요없이 가장 첫번째 노드(Head) 에 대한 주소값만 저장하고 있으면, 필요에 따라 꼬리에 꼬리를 물어가며 필요한 데이터를 찾을 수 있다는 점은 단순 연결리스트와 동일하다.

 

 다음은 이중 연결 리스트의 구조체의 선언이다.

 단순 연결 리스트의 구조체와 비슷하지만, 이전 노드를 가리킬 포인터 공간을 추가적으로 가지고 있다. 여기에서는 단순 연결 리스트를 설명할 때와 마찬가지로 자료 공간은 정수형(int) 자료 공간 하나만을 가지고 구현하고, 설명한다.

 

 다음은 노드의 생성 함수, 메모리를 할당한 노드의 사용이 끝났을 때, 해당 메모리를 반환하는 함수, 이중 연결 리스트로 연결된 모든 노드의 메모리를 반환하는 함수이다.

 이중 연결 리스트의 생성, 소멸과 관련된 함수는 단순 연결 리스트와 다른 점이 거의 없다. 이전 노드를 가리킬 포인터 공간에 대해 연산이 필요없기 때문이다. 자세한 설명 및 사용에 관련된 사항은 이전 글 (링크 : [C] 단순 연결 리스트 (Single Linked List) 1. 정의 / 생성 / 소멸) 에서 확인할 수 있다.