[자료구조] 이중 연결 리스트(Doubly Linked List)의 구조와 구현

 

단순 연결 리스트에서는 선행 노드에 접근하기 어렵다는 점을 개선하여,

원형 연결 리스트에서도 현재 노드의 바로 이전 노드를 접근하려면 전체 리스트를 한 바퀴 순회해야 하는 문제점이 있다.

이를 개선하여 양쪽 방향으로도 순회가 가능한 노드를 연결한 리스트인, '이중 연결 리스트'에 대해 알아보자.

 

 

 

이중 연결 리스트의 구조

 

- 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트

- rlink(right link), llink(left link)

 

 

 

 

 

 

- 헤드 노드(head node): 데이터를 가지고 있지 않은 노드

• rrlink: 첫번째 데이터를 가지고 있는 다음 노드의 주소
• llink: 마지막 데이터를 가지고 있는 노드의 주소

=> 특별한 헤드 노드를 추가함으로써, 첫번째 노드와 마지막 노드의 왼쪽 링크필드, 오른쪽 링크필드를 NULL값이 아닌 노드의 주소를 대입함으로써 원형의 구조를 가져 삽입과 삭제를 용이하게 할 수 있다.

(헤드 노드의 왼쪽 링크 필드는 마지막 노드의 주소를 저장) 

 

 

 

---

 

이중 연결 리스트의 구현

 

 

이중 연결 리스트(Doubly Linked List)의 구조체 DListNode 는 다음과 같다.

왼쪽 노드의 주소, 오른쪽 노드의 주소를 갖는 두 개의 링크 필드 llink와 rlink를 포함한다.

 

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

 

 

 

이중 연결리스트 초기화

 

생성한 헤드 노드를 초기화해준다. 

헤드 노드(구조체)에 대한 메모리를 동적으로 할당받은 후,

init을 호출하여, 각 rrlink, llink 필드에 자신의 노드 주소를 대입하도록 한다.

 

void init(DListNode* head) {
	head->rlink = head;
	head->llink = head;
}
int main() {
	DListNode* head = (DListNode*)malloc(sizeof(DListNode)); // 헤드 노드
	init(head);
}

 

 

 

---

 

이중 연결리스트 삽입

다음은 새로운 노드를 선행 노드인 prev(==before) 다음에 삽입하는 연산이다.

prev - prev->rlink 두 노드 사이에 new를 삽입하여 prev - new - prev->rlink 와 같이 만드는 과정이다.

 

 

먼저 새 노드의 각 링크 필드에 대입을 해준다.

새로운 노드 new의 rlink에는 선행 노드의 rlink를, llink에는 선행 노드의 주소를 대입한다.

 

그리고 나서, 기존 선행 노드의 오른쪽 노드의 llink에는 새 노드의 주소를,

선행 노드의 rlink에는 새 노드의 주소를 대입한다.

 

 

void dinsert(DListNode* prev, element data) {
	DListNode *new = (DListNode*)malloc(sizeof(DListNode));
	new->data = data;

	new->rlink = prev->rlink;
	new->llink = prev;

	prev->rlink->llink = new;
	prev->rlink = new;
}

 

 

 

이중 연결리스트 삭제

 

메모리를 해제하고자 하는 노드의 주소 removed를 삭제하는 ddelete 함수의 구현이다.

 

삭제하고자 하는 노드 removed의 왼쪽 노드의 rlink에는 removed의 오른쪽 노드 주소를,

removed의 오른쪽 노드의 llink에는 removed의 왼쪽 노드 주소를 대입한다.

removed의 양쪽 노드의 왼쪽, 오른쪽 링크필드를 변경 후, 해당 removed 노드의 메모리를 해제해준다.

 

void ddelete(DListNode* head, DListNode* removed) {
	if (removed == head) return;
	else {
		removed->llink->rlink = removed->rlink;
		removed->rlink->llink = removed->llink;
		free(removed);
	}
}

 

전체 메모리 해제

 

헤드 노드의 오른쪽 노드(첫번째 데이터를 가지고 있는 노드) 부터 차례대로 

head 노드에 도달할 때까지의 모든 노드의 메모리를 해제한다.

 

void free_node(DListNode* head) {
	DListNode* p = head->rlink, * next;
	while (p != head) {
		next = p->rlink;
		free(p);
		p = next;
	}
}

 

 

---

 

테스트 프로그램

 

0부터 4까지의 정수를 head 노드의 오른쪽에 삽입하여, 요소 하나를 삽입할 때마다 리스트 전체를 출력한다.

head 노드의 오른쪽 노드를 삭제하기를 반복한다.

 

 

#include <stdio.h>
#include <stdlib.h>

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

void init(DListNode* head) {
	head->rlink = head;
	head->llink = head;
}

void dinsert(DListNode* prev, element data) {
	DListNode *new_node = (DListNode*)malloc(sizeof(DListNode));
	new_node->data = data;

	new_node->rlink = prev->rlink;
	new_node->llink = prev;

	prev->rlink->llink = new_node;
	prev->rlink = new_node;
}

void ddelete(DListNode* head, DListNode* removed) {
	if (removed == head) return; // 삭제할 노드가  head가 같은 경우
	else {
		removed->llink->rlink = removed->rlink;
		removed->rlink->llink = removed->llink;
		free(removed);
	}
}

void free_node(DListNode* head) {
	DListNode* p = head->rlink, * next;
	while (p != head) {
		next = p->rlink;
		free(p);
		p = next;
	}
}

void print_dlist(DListNode* head) {
	DListNode* p = head->rlink; // 첫번째 노드의 주소 대입
	for (;p != head;p = p->rlink)
		printf("%d -> ", p->data);
	printf("\n");
}

int main() {
	DListNode* head = (DListNode*)malloc(sizeof(DListNode)); // 헤드 노드
	init(head);

	printf("insert\n");
	for (int i = 0;i < 5;i++) {
		dinsert(head, i); // 헤드 노드의 오른쪽에 삽입
		print_dlist(head);
	}
	printf("\n\ndelete\n");
	for (int i = 0;i < 5;i++) {
		print_dlist(head);
		ddelete(head, head->rlink); // 헤드 노드의 오른쪽 링크의 노드를 삭제
	}

	free(head);
	return 0;
}

 

main함수에서 요소를 삽입하는 부분을 보면, dinsert(head, i) 가 호출된다.

head 노드가 prev 노드의 인자로 전달되는 것이다.

따라서 첫번째 위치에 노드가 반복되어 삽입되는 것을 확인할 수 있다.

 

노드가 삭제되는 부분을 보면, ddelete(head, head->rlink)가 호출된다. 

헤드의 오른쪽 노드의 주소 head->rlink 가 삭제하고자 하는 노드 removed의 주소의 실인자로 전달된다.

따라서 첫번째에 위치했던 노드들이 하나씩 삭제되는 것을 확인할 수 있다.