[C/C++]연결리스트 - 이중연결리스트 DLL

자료구조

이중연결리스트는 앞에 두 연결리스트와 차이가 두드러집니다.

 

link가 후속링크, 선행링크로 나뉘어 있고, 노드의 진행방향이 양방향으로 확장됩니다. 이렇게 됨에 따라 공간적인 낭비는 심해지겠지만 그만큼 시간적인 부분에서 성능을 높일 수 있습니다.

 

이중연결 리스트 Doubly Linked List

typedef int element;
typedef struct DListNode {
	element data;
	struct DListNode* llink;//선행노드를 가리키는 포인터
	struct DListNode* rlink;//후속노드를 가리키는 포인터
}DListNode;

단순연결리스트, 원형연결리스트와 다르게 link포인터가 2개 입니다. 위에서 말했듯이 각각 선행노드, 후속노드를 가리킵니다.

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

못보던 함수입니다. 이중연결리스트에서 삽입, 삭제를 용이하게 하기 위해서 만드는 특별한 노ㄷ, 헤드노드를 위해 존재하는 함수입니다.

 

헤드 노드는 헤드포인터와는 다른 것입니다. 헤드노드는 데이터를 갖지않는 빈 노드이고, 헤드포인터는 리스트의 첫번째 노드를 가리키고 있는 포인터입니다.

DListNode* head = (DListNode*)malloc(sizeof(DListNode));
init(head);

이렇게 헤드노드를 만듭니다. 헤드노드가 있으면 앞 뒤로 어디든지 접근을 시작할 수 있어서 삽입, 삭제가 간편해집니다.

 

이중연결리스트의 삽입, 삭제에 들어가기 전에 미리 정리해야될 내용이 있습니다.

 

포인터가 2개인 만큼, 그 표현도 복잡해지는데, 아래와 같습니다.

p = p->llink->rlink = p->rlink->link
p->llink는 선행노드, p->rlink는 후속노드 

이게 생각보다 눈을 복잡하게 하기 때문에 미리 알고 가는 겁니다.

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

	node->llink = pre;
	node->rlink = pre->rlink;
	pre->rlink->llink = node;
	pre->rlink = node;
}

삽입함수입니다. 선행노드를 알아야하죠.

 

• 삽입할 노드가 선행노드를 가리키게합니다.
• 선행노드가 원래 가리키고 있던 것을 삽입할 노드도 가리키게 합니다.
• 삽입할 노드의 후속노드가 될, 즉 원래 선행노드가 가리키던 노드의 llink를 삽입할 노드에 연결합니다.
• 삽입할 노드가 후속노드를 가리키게합니다.

아래 네 줄을 쭉 풀어봤습니다.

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

삭제함수는 단순연결리스트와 조금 차이가 있습니다.

 

단순연결리스트에서는 removed 포인터를 만들어서 temp변수처럼 사용했지만 이번에는 삭제할 노드를 직접 removed로 사용합니다.

 

여기서도

p = p->llink->rlink = p->rlink->link
p->llink는 선행노드, p->rlink는 후속노드 

이 개념을 꼭 기억하셔야 헷갈리지 않습니다.

 

removed를 기준으로 진행하게됩니다. 매개변수로 가져왔던 head는 공백리스트가 될 지만 확인하는 것으로 사용됩니다.

 

링크의 이동이 끝난 removed노드는 free(removed)를 통해 메모리에서 해제해줍니다.

 

삭제함수는 간단하죠.

 

전체코드를 올리고 마치도록하겠습니다.

#include <stdio.h>

typedef int element;
typedef struct DListNode {
	element data;
	struct DListNode* llink;//선행노드를 가리키는 포인터
	struct DListNode* rlink;//후속노드를 가리키는 포인터
}DListNode;

void print_list(DListNode* phead) {
	DListNode* p;
	for (p = phead->rlink; p != phead; p = p->rlink) {
		printf("<-| |%d| |-> ", p->data);
	}
	printf("\n");
}

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

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

	node->llink = pre;
	node->rlink = pre->rlink;
	pre->rlink->llink = node;
	pre->rlink = node;
}

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

int main() {
	DListNode* head = (DListNode*)malloc(sizeof(DListNode));
	init(head);
	
	for (int i = 0; i < 5; i++) {
		dinsert(head, i);
		print_list(head);
	}
	printf("-------\n");
	for (int i = 0; i < 5; i++) {
		ddelete(head, head->rlink);
		print_list(head);
	}
	free(head);

	return 0;
}

"댓글, 공감 버튼 한 번씩 누르고 가주시면 큰 힘이 됩니다"