이중 연결리스트는
단순 연결리스트 자료구조를 확장한 형태이다.
단순 연결리스트를 정확히 이해했다면,
이중 연결리스트에 대한 구조 또한 쉽게 이해할 수 있다.
2014/03/20 - [프로그래밍/C언어] - 자료구조 - 연결리스트[linked list] C언어
왼편(단순연결리스트), 오른편(이중연결리스트)의 차이는 prev의 유무다. prev의 역할은 next와 비슷한데 next가 다음 노드(NODE)를 참조하는 것에 반해 prev는 이전 노드(NODE)를 참조한다.
이런 구조적인 차이로 인해 알고리즘도 약간의 변화가 생기게 된다. 단순 연결 리스트의 삽입, 삭제와 이중 연결 리스트의 삽입, 삭제에 대한 비교를 하면 쉽게 이해할 수 있다.
위 그림은 단순 연결리스트의 메모리의 구조를 모식적으로 나타낸 것이다. 그리고 이중연결리스트에 대한 것은 다음과 같다.
prev가 생김으로써 생기는 가장 큰 특징은 특정 노드에 대해서 이전 노드에 대한 정보를 알 수 있다는 것이다. 단순 연결리스트로는 할 수 없는 역으로 출력이 가능하고, 특정 노드의 이전 노드 삭제가능, 특정 노드의 이전에 삽입 가능 등을 할 수 있다.
이중 연결리스트에 대한 자료구조를 설계할 때 몇 가지 주의할 점도 생기게 되는데 모두 prev가 생김으로써 생기는 문제이므로 prev를 주목해서 이해하도록 하면 잊지 않을 수 있다.
삽입 시
1과 2 노드 사이에 9999의 값을 지닌 노드를 삽입하려고한다.
먼저 1노드의 next에 새로운 노드(New노드라하겠다)를 넣고 2노드의 prev에도 New노드를 넣는다.
New노드 의 prev, next도 위와 같은 작업을 한다.
단순연결리스트에서 추가된 부분이다.
단순연결리스트에서 위와 같이 수정만 하면 런타임 에러가 발생할 텐데 다음 두 가지 경우다.
① 리스트에 아무 값도 없는 경우
② 리스트의 맨 마지막에 삽입하려고 할 경우
prev의 관점에서 생각해보면 Right->prev가 위 두 경우에는 Right라는 노드가 존재하지 않기 때문이다.
첫 번째는 head->next값이 NULL이 되고, 두 번째는 마지막 노드->next 값이 NULL이 되기 때문이다.
해결방법
NULL 값 대신 tail이라는 노드를 만들어 리스트의 초기화시에 head->next=tail; 도록 만든다.
이젠 위 코드가 제대로 동작할 것이다.
위와 같이 tail을 설정하면, head와 tail이 마치 거울을 보는 듯한 형상을 한다. 이런 구조상의 특징으로 tail부터 head까지 역순으로 값의 탐색이 가능해진다. 다음은 나머지 코드다.
//추가 와 //수정 부분은 단순연결리스트와 비교하기 위한 주석이다.
사실 이중 연결리스트는 단순 연결리스트를 이해하면 어려운 내용이 아니다. 마치 프라모델을 조립하듯이 삽입과 삭제 시 연결부위를 맞춰 주기만 하면 된다. 실제로 더 많은 기능들은 얼마든지 붙여 넣을 수 있다.