이중 연결 리스트

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

- 단순 연결 리스트에서는 선행 노드를 찾기 매우 어려움

- 원형 연결 리스트에서도 선행 노드를 찾으려면 거의 전체 노드를 거쳐야 함 

→ 특정 노드에서 양방향으로 움직여야 한다면 단순 연결 리스트 구조는 부적합

- 실제 응용에서는 이중 연결 리스트와 원형 연결 리스트를 혼합

- 헤드 노드(head node)를 추가하는 경우 多

- 헤드 노드는 데이터를 가지고 있지 않고 삽입과 삭제 알고리즘을 간편하게 하기 위해 존재하는 특별한 노드

---

노드 구조 정의

- 이중 연결 리스트에서 노드는 3개의 필드로 이루어짐

- 왼쪽 링크 필드(llink), 데이터 필드, 오른쪽 링크 필드(rlink)

- 링크 필드는 포인터로 이루어짐

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

- 임의의 노드를 가리키는 포인터를 p라 하면 위와 같은 관계가 항상 성립

- 앞뒤로 똑같이 이동할 수 있음을 나타냄

- 공백 리스트의 경우 위와 같은 상태가 됨

//구조체를 이용한 노드 구조 정의
typedef int element;
typedef struct DListNode{
	element data;
	struct DListNode* llink;
	struct DListNode* rlink;
}DListNode;

- 왼쪽 링크 필드(llink)는 선행 노드를 가리킴

- 오른쪽 링크 필드(rlink)는 후속 노드를 가리킴

---

삽입 연산

- 위의 순서대로 링크 필드 값 변경

- 새로 만들어진 노드의 링크는 아직 데이터가 없어 변경해도 안전하므로 이를 먼저 변경

//새로운 데이터를 노드 before의 오른쪽에 삽입
void dinsert(DListNode* before, element data) {
	DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));
	newnode->data = data;
	newnode->llink = before;
	newnode->rlink = before->rlink;	//newnode의 rlink가 before의 rlink가 가리키던 노드(=후행 노드)를 가리키게 변경
	before->rlink->llink = newnode;	//후행 노드의 llink가 newnode를 가리키게 변경
	before->rlink = newnode;	//before의 rlink가 newnode를 가리키게 변경
}

---

삭제 연산

- 위의 순서대로 링크 값 변경

//노드 removed를 삭제
void ddelete(DListNode* head, DListNode* removed) {
	if (removed == head)
		return;
	removed->llink->rlink = removed->rlink;	//removed의 선행 링크가 removed의 후행 링크를 가리키게 변경
	removed->rlink->llink = removed->llink;	//removed의 후행 링크가 removed의 선행 링크를 가리키게 변경
}

---

전체 프로그램

- 이중 연결 리스트에서는 보통 헤드 노드가 존재하므로 단순 연결 리스트처럼 헤드 포인터 필요 x

- 헤드 노드만 알고 있으면 어떤 노드로도 접근 가능

- 헤드 노드는 main 함수에서 생성

- head는 포인터 변수가 아닌 구조체 변수

- 반드시 초기화(헤더 노드의 링크 필드들이 자기 자신을 가리키도록)

#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;
}
//새로운 데이터를 노드 before의 오른쪽에 삽입
void dinsert(DListNode* before, element data) {
	DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));
	newnode->data = data;
	newnode->llink = before;
	newnode->rlink = before->rlink;	//newnode의 rlink가 before의 rlink가 가리키던 노드(=후행 노드)를 가리키게 변경
	before->rlink->llink = newnode;	//후행 노드의 llink가 newnode를 가리키게 변경
	before->rlink = newnode;	//before의 rlink가 newnode를 가리키게 변경
}
//노드 removed를 삭제
void ddelete(DListNode* head, DListNode* removed) {
	if (removed == head)
		return;
	removed->llink->rlink = removed->rlink;	//removed의 선행 링크가 removed의 후행 링크를 가리키게 변경
	removed->rlink->llink = removed->llink;	//removed의 후행 링크가 removed의 선행 링크를 가리키게 변경
}
//리스트 전체 출력
void print_dlist(DListNode* phead) {
	DListNode* p;
	for (p = phead->rlink; p != phead; p = p->rlink) {
		printf("<-|  |%d|  |-> ", p->data);
	}
	printf("\n");
}

int main(void) {
	DListNode* head = (DListNode*)malloc(sizeof(DListNode));
	init(head);
	printf("추가 단계\n");
	for (int i = 0; i < 5; i++) {
		dinsert(head, i);
		print_dlist(head);
	}
	printf("삭제 단계\n");
	for (int i = 0; i < 5; i++) {
		print_dlist(head);
		ddelete(head, head->rlink);
	}
	free(head);
	
	return 0;
}

>>

- 맨 마지막에 삽입된 노드부터 삭제됨