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

1. 이중 연결 리스트 특징

• 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트

2. 이중 연결 리스트 구조

• 두 개의 링크 필드와 한 개의 데이터 필드로 구성
• llink(Left link) 필드 : 왼쪽 노드와 연결하는 포인터
• rlink(Right link) 필드 : 오른쪽 노드와 연결하는 포인터

1) C언어 구조체

 - C언어 구조체로 본 이중 연결 리스트의 기본구조

 

struct Dnode{
	struct Dnode *llink;
	int data;
	struct Dnode *rlink;
};

 

2) 이중 연결리스트의 구조

head	llink	Data	rlink	llink	Data	rlink	llink	Data	rlink
→	NULL	10	→	←	20	→	←	30	NULL
	node1			node2			node3

 

3) 이중 원형 연결리스트(Doubly Circular linkde list)의 구조

	↓			←			←
head	llink	Data	rlink	llink	Data	rlink	llink	Data	rlink
→	↓	10	→	←	20	→	←	30	↑
	→			→			↑
	node1			node2			node3

 

 - 기본 구조에서는 첫 시작 노드 llink와 마지막 노드의 rlink에 NULL이 들어가지만, 이중 원형 연결리스트에서는 첫 시작 노드 llink가 마지막 rlink를 가리키고 마지막 노드 rlink가 첫 시작 노드 llink를 가리키는 구조다.

 

3. 이중 연결 리스트 생성

1) C언어 실습

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

typedef struct DNODE{	// 구조체 정의
	int data;
	struct DNODE *prev;	// 앞의 링크
	struct DNODE *next;	// 뒤의 링크
}NODE;

NODE *head, *tail;

NODE *makenode(int data) {	// 노드 생성
	NODE *p = (NODE *)malloc(sizeof(NODE));
	p -> data = data;
	p -> next = NULL;
	p -> prev = NULL;
	return p;
}

void print() {	// 역방향 출력
	NODE *p;
	p = tail;
	while (p -> prev != head) {
		printf(" %d-->", p -> data);
		p = p -> prev;
	}
	printf(" %d ", p -> data); puts("출력 끝");
}

void init() {	// head, tail 초기화
	head = (NODE *)malloc(sizeof(NODE));
	tail = (NODE *)malloc(sizeof(NODE));
	head -> data = 0;
	tail -> data = 0;

	head -> next = tail;
	head -> prev = head;
	tail -> prev = head;
	tail -> next = tail;
}

void main() {
	init();
	print();
}

 

이중 연결 리스트 생성

 

4. 이중 연결 리스트 삽입

1. 삽입할 노드를 가져온다.
2. 새 노드의 데이터 필드에 값을 저장
3. 새 노드의 왼쪽 노드의 오른쪽 링크(rlink)를 새 노드의 오른쪽 링크(rlink)에 저장
4. 왼쪽 노드의 오른쪽 링크(rlink)에 새 노드의 주소를 저장
5. 새 노드의 오른쪽 노드의 왼쪽 링크(llink)를 새 노드의 왼쪽 링크(llink)에 저장
6. 오른쪽 노드의 왼쪽 링크(llink)에 새 노드의 주소를 저장

1) 순서

1. NEW.rlink ← pre.rlink;
    - 노드 pre의 rlink를 노드 NEW의 rlink에 저장하여 노드 pre의 오른쪽 노드를 삽입할 노드 NEW의 오른쪽 노드로 연결
2. pre.rlink ← NEW;
    - 새 노드 NEW의 주소를 노드 pre의 rlink에 저장하여 노드 NEW를 노드 pre의 오른쪽 노드로 연결
3. NEW.llink ← pre;
    - 포인터 pre의 값을 삽입할 노드 NEW의 llink에 저장하여 노드 pre를 노드 NEW의 왼쪽 노드로 연결
4. NEW.rlink.llink ← NEW;
    - 포인터 NEW의 값을 노드 NEW의 오른쪽 노드(NEW.rlink)의 llink에 저장하여 노드 NEW의 오른쪽 노드의 왼쪽 노드로 노드 NEW를 연결

2) C언어 실습

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

typedef struct DNODE{	// 구조체 정의
	int data;
	struct DNODE *prev;	// 앞의 링크
	struct DNODE *next;	// 뒤의 링크
}NODE;

NODE *head, *tail;

NODE *makenode(int data) {	// 노드 생성
	NODE *p = (NODE *)malloc(sizeof(NODE));
	p -> data = data;
	p -> next = NULL;
	p -> prev = NULL;
	return p;
}

void print() {	// 출력
	NODE *p;
	p = head;
	while (p -> next != tail){
		printf(" %d-->", p -> data);
		p = p -> next;
	}
	printf(" %d ", p -> data); puts("출력 끝");
}

void init() {	// head, tail 초기화
	head = (NODE *)malloc(sizeof(NODE));
	tail = (NODE *)malloc(sizeof(NODE));
	head -> data = 0;
	tail -> data = 0;

	head -> next = tail;
	head -> prev = head;
	tail -> prev = head;
	tail -> next = tail;
}

void push_back(int data){	// 노드 삽입
	NODE *newnode = makenode(data);
	NODE *p;
	p = tail;
	p -> prev -> next = newnode;
	newnode -> prev = p -> prev;
	p -> prev = newnode;
	newnode -> next = p;
}

void main() {
	init();
	push_back(10);
	push_back(20);
	push_back(30);
	print();
}

 

push_back에서 이해하기 어렵다. 특히 p -> prev -> next = newnode; 이 부분이다. 

 

(1) 삽입 전

 

llink	Data	rlink				llink	Data	rlink
	0	→				←	0
head						tail = p
			llink	Data	rlink
			NULL	10	NULL
			newnode

 

p의 prev(llink)의 next(rlink)가 newnode다. 즉, p의 prev가 가리키는 head의 rlink를 말하는 것이다. 그래서 head의 rlink는 newnode를 가리키게 된다. 

newnode의 llink는 p의 prev이므로 head를 가리키게 된다.

이것은 head를 push_back에서 선언하지 않아서 tail만을 이용해 상대적으로 위치를 알아낸다고 생각하면 쉽다.

 

(2) 삽입 후

 

llink	Data	rlink				llink	Data	rlink
	0	↘				↙	0
head						tail = p
			llink	Data	rlink
			↖	10	↗
			newnode

 

5. 이중 연결 리스트 삭제

1) 순서

1. 삭제할 노드의 오른쪽 노드의 주소(old.rlink)를 삭제할 노드의 왼쪽 노드(old.llink)의 오른쪽 링크(rlink)에 저장
    - old.llink.rlink <- lod.rlink;
2. 삭제할 노드의 왼쪽 노드의 주소(old.llink)를 삭제할 노드의 오른쪽 노드(old.rlink)의 왼쪽 링크(llink)에 저장
    - old.rlink.llink <- old.llink;
3. 삭제한 노드를 자유 공간 리스트에 반환
    - returnNode(old);

2) C언어 실습

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

typedef struct DNODE{	// 구조체 정의
	int data;
	struct DNODE *prev;	// 앞의 링크
	struct DNODE *next;	// 뒤의 링크
}NODE;

NODE *head, *tail;

NODE *makenode(int data) {	// 노드 생성
	NODE *p = (NODE *)malloc(sizeof(NODE));
	p -> data = data;
	p -> next = NULL;
	p -> prev = NULL;
	return p;
}

void print() {	// 출력
	NODE *p;
	p = head;
	while (p -> next != tail){
		printf(" %d-->", p -> data);
		p = p -> next;
	}
	printf(" %d ", p -> data); puts("출력 끝");
}

void init() {	// head, tail 초기화
	head = (NODE *)malloc(sizeof(NODE));
	tail = (NODE *)malloc(sizeof(NODE));
	head -> data = 0;
	tail -> data = 0;

	head -> next = tail;
	head -> prev = head;
	tail -> prev = head;
	tail -> next = tail;
}

void push_back(int data){	// 노드 삽입
	NODE *newnode = makenode(data);
	NODE *p;
	p = tail;
	p -> prev -> next = newnode;
	newnode -> prev = p -> prev;
	p -> prev = newnode;
	newnode -> next = p;
}

void removeat(int val){	// 삭제
	NODE *p;
	p = head -> next;
	while(p -> next != tail){
		if(p -> data == val){
			p -> next -> prev = p -> prev;
			p -> prev -> next = p -> next;
			free(p);
			return;
		}
		p = p -> next;
	}
}

void main() {
	init();
	push_back(10);
	push_back(20);
	push_back(30);
	puts(" - 삭제 전 -");
	print();
	puts(" - 삭제 후 -");
	removeat(20);
	print();
}

 

이중 연결 리스트 삭제