[Data Structure] 이중 연결 리스트

이중 연결 리스트 (Doubly Linked List)

- 링크가 양방향 이기 때문에 양방향 검색이 가능

- 삽입/삭제시 반드시 선행 노드가 필요

- 공간을 많이 차지하고 코드가 복잡하다

- 헤드 노드를 보유

- 헤드 노드 + 이중 연결 리스트 + 원형 연결 리스트로 구현할 예정

 

 

※ 헤드 노드 / 헤드 포인터

헤드 노드

- 데이터 필드에 아무런 정보도 담고 있지 않다 → 데이터를 가지지 않는다

- 단지, 삽입/삭제의 편리함을 위해 구현

- 공백상태에서는 헤드 노드만 존재

헤드 포인터

- 리스트의 첫 번째 노드를 가리키는 포인터

 

※ 항상 성립하는 관계

- 임의의 노드를 가리키는 포인터 p

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

 

 

이중 연결 리스트의 노드 구조

- 1개의 데이터 필드

- 왼쪽 링크 필드 llink : 선행 노드를 가리킨다

- 오른쪽 링크 필드 rlink : 후속 노드를 가리킨다

typedef struct{
    element data;
    struct d_listnode* llink;
    struct d_listnode* rlink;
}d_listnode;

 

 

1. init (초기화)

- 양쪽의 link 필드가 자기 자신을 가리키게 설정

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

 

 

2. 삽입연산

1. 선행 노드(pre) 다음에 new_node 삽입
2. new_node의 llink, rlink를 양쪽 노드에 연결
3. 양쪽에서 new_node에 연결

 

※ 삽입연산 순서

- 이상적인 실행순서 : (1) → (2) → (3) → (4)

- (1) : 아무때나 실행해도 된다

- (2) : 반드시 (4)보다 먼저 실행

- (3) : 반드시 (4)보다 먼저 실행

- (4) : 반드시 (2), (3)보다 뒤에 실행되어야 하고, 절대로 첫 순서에 실행되면 안된다

void insert_node(d_listnode* pre, d_listnode* new_node) {
	// new_node를 pre 다음에 insert하고
	// new_node의 llink, rlink을 양쪽에 연결
	// 양쪽에서 new_node에 연결
	new_node->llink = pre; // (1)
	new_node->rlink = pre->rlink; // (2)
	pre->rlink->llink = new_node; // (3)
	pre->rlink = new_node; // (4)
}

 

 

3. 삭제연산

void delete_node(d_listnode* head, d_listnode* removed) {
	if (removed == head) {
		free(removed);
	}
	else {
		removed->llink->rlink = removed->rlink;
		removed->rlink->llink = removed->llink;
		free(removed);
	}
}

 

 

4. 탐색연산

d_listnode* search(d_listnode* head, int value) {
	d_listnode* p = head->rlink;
	while (p != head) {
		if (p->data == value) return p;
		p = p->rlink;
	}
	return NULL; // 탐색 실패
}

 

 

5. Full Code

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

typedef int element;

typedef struct d_listnode {
	element data;
	struct d_listnode* llink;
	struct d_listnode* rlink;
}d_listnode;

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

void insert_node(d_listnode* pre, d_listnode* new_node) {
	// new_node를 pre 다음에 insert하고
	// new_node의 llink, rlink을 양쪽에 연결
	// 양쪽에서 new_node에 연결
	new_node->llink = pre; // (1)
	new_node->rlink = pre->rlink; // (2)
	pre->rlink->llink = new_node; // (3)
	pre->rlink = new_node; // (4)
}

void delete_node(d_listnode* head, d_listnode* removed) {
	if (removed == head) {
		free(removed);
	}
	else {
		removed->llink->rlink = removed->rlink;
		removed->rlink->llink = removed->llink;
		free(removed);
	}
}

d_listnode* search(d_listnode* head, int value) {
	d_listnode* p = head->rlink;
	while (p != head) {
		if (p->data == value) return p;
		p = p->rlink;
	}
	return NULL; // 탐색 실패
}

void print_list(d_listnode* head) {
	d_listnode* p;
	if (head->rlink == head) {
		fprintf(stderr, "Error : List is empty\n\n");
		return;
	}
	for (p = head->rlink; p != head; p = p->rlink) {
		printf("<- |   | %d |   |->  ", p->data);
	}
	printf("\n\n");
}

int main(void) {
	d_listnode* head = (d_listnode*)malloc(sizeof(d_listnode));
	init(head);
	d_listnode* p1 = (d_listnode*)malloc(sizeof(d_listnode));
	p1->data = 10; init(p1); //p1->llink = p1; p1->rlink = p1;
	d_listnode* p2 = (d_listnode*)malloc(sizeof(d_listnode));
	p2->data = 20; init(p2); //p2->llink = p2; p2->rlink = p2;
	d_listnode* p3 = (d_listnode*)malloc(sizeof(d_listnode));
	p3->data = 30; init(p3); //p3->llink = p3; p3->rlink = p3;

	print_list(head); // (head)
	insert_node(head, p1); // (head) <-> p1(10)
	print_list(head);
	insert_node(p1, p2); // (head) <-> p1(10) <-> p2(20)
	print_list(head);
	insert_node(head, p3); // (head) <-> p3(30) <-> p1(10) <-> p2(20)
	print_list(head);

	if (search(head, 10) != NULL)
		printf("10이 리스트에 있습니다\n\n");
	else
		printf("10이 리스트에 없습니다\n\n");
	if (search(head, 30) != NULL)
		printf("30이 리스트에 있습니다\n\n");
	else
		printf("30이 리스트에 없습니다\n\n");
	if (search(head, 50) != NULL)
		printf("50이 리스트에 있습니다\n\n");
	else
		printf("50이 리스트에 없습니다\n\n");

	delete_node(head, p1); // (head) <-> p3(30) <-> p2(20)
	print_list(head);
	delete_node(head, p2); // (head) <-> p3(30)
	print_list(head);
	delete_node(head, p3); // (head)
	print_list(head);
}