이중 연결 리스트

단순 연결 리스트에서의 어떤 노드에서 후속 노드를 찾기는 쉽지만, 선행 노드를 찾으려면 구조상 아주 어렵다.

단순 연결 리스트의 경우에는 헤드 포인터부터 시작해서 탐색을 하여야 한다.

원형 연결 리스트라고 하더라도 거의 전체의 노드를 거쳐서 돌아와야 한다.

따라서 응용 프로그램에서의 특정 노드에서 양방향으로 자유롭게 움직일 필요가 있다면 단순 연결 리스트나 원형 연결 리스트 구조는 부적합하다.

이중 연결 리스트는 이러한 문제점을 해결하기 위하여 만들어진 자료 구조이다.

이중 연결 리스트는 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트이다.

링크가 양방향이므로 양방향으로 검색이 가능하지만 공간을 많이 차지하고 코드가 복잡해진다는 단점이 있다.

그러나 그럼에도 불구하고 여러 가지 장점이 존재하기 때문에 널리 쓰인다.

실제 응용에서는 위 그림처럼 이중 연결 리스트와 원형 연결 리스트를 혼합한 형태가 많이 사용된다.

또한 헤드 노드(Head node)라는 특별한 노드를 추가하는 경우가 많다.

헤드 포인터와는 구별하여야 한다. 헤드 포인터는 리스트의 첫 번째 노드를 가리키는 포인터이고 헤드 노드는 데이터를 가지고 있지 않은 특별한 노드이다.

"헤드 노드가 존재하게 되면 삽입, 삭제 알고리즘이 간편해진다."

헤드 노드의 데이터 필드는 아무런 정보도 담고 있지 않다.

이중 연결 리스트 구현

이중 연결 리스트를 구현해보자. 먼저 노드의 구조를 정의해야 할 것이다.

이중 연결 리스트에서의 노드는 3개의 필드(왼쪽 링크 필드, 데이터 필드, 오른쪽 링크 필드)로 이루어져 있다.

링크 필드는 포인터가 저장된다.

이중 연결 리스트에서 임의의 노드를 가리키는 포인터를 p라고 하면, 다음의 관계가 항상 성립한다.

p == p->llink->rlink == p->rlink->llink

즉, 앞뒤로 똑같이 이동할 수 있음을 나타낸다.

이러한 관계는 공백 리스트에서도 성립한다. 즉, 헤드 노드가 존재하기 때문에 공백 리스트의 경우에는 다음과 같은 상태가 된다.

노드의 구조를 구조체를 이용하여 정의해보면 다음과 같다.

각 노드의 왼쪽 링크 필드는 선행 노드를 가리키며, 오른쪽 링크 필드는 후속 노드를 가리킨다.

typedef int element;
typedef struct DlistNode {
	element data;
	struct DlistNode* llink;
	struct DlistNode* rlink;
}DlistNode;

삽입 연산

삽입 연산에서는 위의 순서대로 링크 필드의 값을 바꾸면 된다.

새로 만들어진 노드의 링크를 먼저 바꾸는 것을 알 수 있다.

새로 만들어진 노드의 링크를 아무런 정보도 가지고 있지 않기 때문에 변경하여도 안전하기 때문이다.

void dinsert_node(DlistNode* before, DlistNode* new_node) {
	new_node->llink = before;
	new_node->rlink = before->rlink;
	before->rlink->llink = new_node;
	before->rlink = new_node;
}

삭제 연산

삭제 연산은 위의 순서대로 링크들의 값을 변화시키면 된다.

void dremove_node(DlistNode* phead_node, DlistNode* removed) {
	if (removed == phead_node)return;
	removed->llink->rlink = removed->rlink;
	removed->rlink->llink = removed->llink;
	free(removed);
}

완전한 프로그램

다음 프로그램은 이중 연결 리스트를 사용한 간단한 프로그램이다.

한 가지 주의할 것은 이중 연결 리스트에서는 헤드 노드가 존재하므로 단순 연결 리스트처럼 헤드 포인터가 필요없다.

즉, 헤드 노드만 알고 있으면 어떤 노드로도 접근할 수 있다.

헤드 노드는 main 함수 안에 변수로 head_node라는 이름으로 생성되어 있다.

head_node는 포인터 변수가 아니고 구조체 변수임을 유의해야 한다.

이중 연결 리스트는 사용하기 전에 반드시 초기화를 해야 된다는 점을 유의하라.

즉, 헤더 노드의 링크 필드들이 자기 자신을 가리키도록 초기화를 해야 한다.

#include <stdio.h>

typedef int element;
typedef struct DlistNode {
	element data;
	struct DlistNode* llink;
	struct DlistNode* rlink;
}DlistNode;

void init(DlistNode* phead) {
	phead->llink = phead;
	phead->rlink = phead;
}

void display(DlistNode* phead) {
	DlistNode* p;
	for (p = phead->rlink; p != phead; p = p->rlink) {
		printf("<--- | %x | %d | %x | --->\n", p->llink, p->data, p->rlink);
	}
	printf("\n");
}

void dinsert_node(DlistNode* before, DlistNode* new_node) {
	new_node->llink = before;
	new_node->rlink = before->rlink;
	before->rlink->llink = new_node;
	before->rlink = new_node;
}

void dremove_node(DlistNode* phead_node, DlistNode* removed) {
	if (removed == phead_node)return;
	removed->llink->rlink = removed->rlink;
	removed->rlink->llink = removed->llink;
	free(removed);
}

int main() {

	DlistNode head_node;
	DlistNode* p[10];

	init(&head_node);
	
	for (int i = 0; i < 5; i++) {
		p[i] = (DlistNode*)malloc(sizeof(DlistNode));
		p[i]->data = i;
		
		dinsert_node(&head_node, p[i]);
	}

	dremove_node(&head_node, p[4]);
	display(&head_node);

	return 0;
}