[자료구조] 이중 연결리스트 Doubly linked list

이중 연결리스트

이중 연결리스트는 각 노드가 선행 노드와 후속 노드에 대한 링크를 가지는 리스트입니다.

아래 그림처럼 노드의 왼쪽 링크(left link)와 오른쪽 링크(right link)가 각각 다른 노드의 오른쪽 링크와 왼쪽 링크를 연결짓고 있으며 특별하게 헤드도 노드로 이루어져 있습니다.

 

 

헤드노드

헤드노드는 데이터를 가지지 않고 오로지 삽입, 삭제 코드를 간단하게 할 목적으로 만들어진 노드입니다. 따라서 헤드 포인터와의 구별이 필요하며 리스트가 공백상태라면 헤드 노드만 존재하는 상태입니다. 이때 헤드노드의 left link는 right link를 가리키며 right link는 left link를 가리키는 상태입니다.

 

삽입 연산

new_node를 before의 앞쪽에 삽입하는 연산입니다.

 

 

 

(1)은 new_node의 llink가 before를 가리키게 합니다.

(2)는 new_node의 rlink가 before의 rlink를 가리키게 합니다.

(3)은 before의 rlink의 llink가 new_node를 가리키게 합니다.

(4)는 before의 rlink가 new_node를 가리키게 합니다.

 

이상적인 실행순서는 (1) -> (2) -> (3) -> (4) 이지만 순서마다 경우의 차이가 있을 수 있습니다.

(1)의 경우 순서의 상관없이 아무 때나 실행해도 됩니다.

(2)의 경우 반드시 (4)보다는 먼저 실행되어야 합니다.

(3)의 경우 반드시 (4)보다는 먼저 실행되어야 합니다.

(4)의 경우 반드시 (2)와 (3)보다 먼저 실행되어서는 안되며 절대 첫 순서로 실행되어서는 안됩니다.

 

삭제 연산

삭제하려는 노드를 removed 변수로 받아서 삭제 연산을 수행합니다. 기본적으로 삭제할 노드의 이중 연결을 해제하는 형식입니다.

 

(1)은 removed의 llink의 rlink가 removed의 rlink를 가리키게 합니다.

(2)는 removed의 rlink의 llink가 removed의 llink를 가리키게 합니다.

 

 

알고리즘

#include <stdio.h>
#include <stdlib.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 print_dlist(DListNode* phead) {
	DListNode* p;
	for (p = phead->rlink; p != phead; p = p->rlink) {
		printf("<-| |%d| |-> ", p->data);
	}
	printf("\n");
}
// 새로운 데이터를 노드 before의 오른쪽에 삽입
void dinsert(DListNode* before, element data) {
	DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));
	newnode->data = data;
	newnode->llink = before;
	newnode->rlink = before->rlink;
	before->rlink->llink = newnode;
	before->rlink = newnode;
}
// 노드 removed를 삭제
void ddelete(DListNode* head, DListNode* removed) {
	if (removed == head) return;
	head->rlink = removed->rlink;
	removed->rlink->llink = removed->llink;
	free(removed);
}
// 메인
int main(void) {
	DListNode* head = (DListNode*)malloc(sizeof(DListNode));
	init(head);
	printf("추가 단계\n");
	for (int i = 0; i < 5; i++) {
		dinsert(head, i);
		printDlist(head);
	}
	printf("\n삭제 단계\n");
	for (int i = 0; i < 5; i++) {
		printDlist(head);
		ddelete(head, head->rlink);
	}
	free(head);
	return 0;
}

/* 실행결과
삽입 단계
<-| |0| |->
<-| |1| |-> <-| |0| |->
<-| |2| |-> <-| |1| |-> <-| |0| |->
<-| |3| |-> <-| |2| |-> <-| |1| |-> <-| |0| |->
<-| |4| |-> <-| |3| |-> <-| |2| |-> <-| |1| |-> <-| |0| |->

삭제 단계
<-| |4| |-> <-| |3| |-> <-| |2| |-> <-| |1| |-> <-| |0| |->
<-| |3| |-> <-| |2| |-> <-| |1| |-> <-| |0| |->
<-| |2| |-> <-| |1| |-> <-| |0| |->
<-| |1| |-> <-| |0| |->
<-| |0| |->
*/

 

 

연습문제

이중 연결 리스트에 저장된 데이터의 개수를 반환하는 함수를 작성하라

int get_size(DlistNode *head)

// 저장된 데이터의 개수를 반환
int get_size(DListNode* head)
{
	DListNode* p;
	int count = 0;
	for (p = head->rlink; p != head; p = p->rlink) {
		count++;
	}
	return count;
}

 

이중 연결 리스트에서 특정한 값을 탐색하는 함수를 작성하라

DListNode *search(DListNode *head, element data)

// 특정한 값을 탐색
DListNode* search(DListNode* head, element data)
{
	DListNode* p;
	for (p = head->rlink; p != head; p = p->rlink) {
		if (p->data == data) return p;  
	}
	return NULL;
}

 

이중 연결 리스트를 역순으로 순회하면서 저장된 데이터 값을 출력하는 함수를 작성하라

void print_dlist_reverse(DlistNode *head)

// 역순으로 순회하면서 저장된 데이터 값을 출력
void print_dlist_reverse(DListNode* head)
{
	DListNode* p;
	for (p = head->llink; p != head; p = p->llink) {
		printf("<-| |%d| |-> ", p->data);
	}
	printf("\n");
}

 

현재 순서를 나타내는 이중 연결리스트를 이용한 프로그램을 작성하라. 만약, A노드, B노드, C노드가 존재할 때, 현재 순서가 B라면 기호 #을 이용하여 리스트를 다음과 같이 출력한다.

<-| A |-> <-| #B#|-> <-| C|->