[자료구조] C - 연결리스트(linkedlist) - 3. 이중연결리스트

오늘은 이중연결리스트에 대해 다루어 볼 것이다. 

 

단순연결리스트와 원형 연결리스트에 대해서는 이전 포스팅을 참고하자.

https://mobuk.tistory.com/8?category=1076684 

[자료구조] C - 연결리스트(linkedlist) - 1. 단순연결리스트

 

https://mobuk.tistory.com/14?category=1076684 

[자료구조] C - 연결리스트(linkedlist) - 2. 원형연결리스트

 

 

이중 연결 리스트의 구조

 

단순연결리스트는 노드의 화살표가 단방향으로만 이루어져 있다. 그래서 역방향으로 진행할 때에는 굉장히 어려움이 있다. 바로 앞 노드를 탐색하기 위해서는 처음부터 탐색하거나 한바퀴 돌아 탐색을 해야한다. 여기서 이중연결리스트의 아이디어가 시작되었다. 화살표가 뒤쪽, 앞쪽 2개가 존재하면 데이터가 앞에 있던 뒤에 있던 이동이 자유로울 것이다. 이중 연결리스트는 아래 그림과 같이 링크가 왼쪽, 오른쪽 두 개가 있는 노드가 연결된 것이다. 

이중연결리스트의 구조

이중 연결리스트를 구현할 때 단순 연결리스트와의 가장 큰 차이점은 화살표의 개수이고 또 다른 차이점은 헤드포인터이다. 단순연결리스트는 헤드 포인터로 시작 지점을 나타냈지만, 이중 연결리스트는 헤드 노드를 하나 만들어서 처리한다. 즉, data에 아무것도 담기지 않고 시작 지점만 표시해주는 노드가 하나 삽입되어 있다는 것이다. 

head 노드

왜 이렇게 만드는 것인지에 대한 의문은 구현을 해보다 보면 매우 자연스럽게 알게 된다. 헤드가 노드로 되어 있으면 포인터일 때 보다 삽입이나 삭제 알고리즘이 매우 간단해진다. 그 이유는 head -> rlink = head ->llink -> head 이기 때문이다.

 

이중 연결리스트의 구현

 

0. 자기 참조 구조체로 노드 선언

typedef int element;

typedef struct dlinkedlist {
	element data;
	struct dlinkedlist* llink;
	struct dlinkedlist* rlink;
}Node;

특징은 구조체 내부에 포인터가 2개가 있다는 것이다. 

 

1. init

void* init(Node* h)
{
	h->llink = h;
	h->rlink = h;
}

헤드 노드 만들 때나 그냥 빈 노드 하나 만들 때 사용하면 되는 녀석이다. 꼭 필요한지는 모르겠지만, 일단 만들어봤다.

 

2.  printlist

void printlist(Node* h)
{
	Node* p = h->rlink;
	if (h == NULL)
		return;
	while (p != h)
	{
		printf(" <-|%d|-> ", p->data);
		p = p->rlink;
	}
	printf("\n");
}

 

 

3. insert

void insert(Node* before, element data)
{
	Node* curr = (Node*)malloc(sizeof(Node));
	curr->data = data;
	
	curr->llink = before;
	curr->rlink = before->rlink;
	before->rlink->llink = curr;
	before->rlink = curr;
}

->를 연달아 두번 쓸 수 있다는 사실을 이번에 처음 알았다. 배웠는데 내가 까먹은건지는 모르겠지만, 굉장히 흥미롭고 재미있었다.

 

4. delete

void delete(Node* h, Node* f)
{
	if (h == NULL)
		return;
	f->rlink->llink = f->llink;
	f->llink->rlink = f->rlink;
	free(f);
}

 

출력테스트

#include<stdio.h>
#pragma warning(disable:4996)
#include<stdlib.h>

typedef int element;

typedef struct dlinkedlist {
	element data;
	struct dlinkedlist* llink;
	struct dlinkedlist* rlink;
}Node;

void* init(Node* h)
{
	h->llink = h;
	h->rlink = h;
}

void printlist(Node* h)
{
	Node* p = h->rlink;
	if (h == NULL)
		return;
	while (p != h)
	{
		printf(" <-|%d|-> ", p->data);
		p = p->rlink;
	}
	printf("\n");
}

void insert(Node* before, element data)
{
	Node* curr = (Node*)malloc(sizeof(Node));
	curr->data = data;
	
	curr->llink = before;
	curr->rlink = before->rlink;
	before->rlink->llink = curr;
	before->rlink = curr;
}

void delete(Node* h, Node* f)
{
	if (h == NULL)
		return;
	f->rlink->llink = f->llink;
	f->llink->rlink = f->rlink;
	free(f);
}

int main(void)
{
	Node *h =(Node*)malloc(sizeof(Node));
	init(h);
	for (int i = 0; i < 5; i++)
	{
		insert(h, i, h);
		printlist(h);
	}
	for (int i = 0; i < 5; i++)
	{
		delete(h, h->rlink);
		printlist(h);
	}
	free(h);
	return 0;
}

 

정상적으로 출력이 잘 되었다.

 

 

 

[소감]

원형연결리스트보다 오히려 조금 더 쉬운 느낌이 든다. 기분탓인지는 모르겠지만 쉬웠다. 하지만, 코드가 복잡해지면 어렵겠지?? 요즘 자료구조를 계속 공부하다보니 얼른 이걸 써먹고 싶다는 생각이 자주 든다. 

비하인드지만 처음에는 출력이 오류나서.. 계속 찾아도 안보였는데 알고보니 printlist에서 p->rlist를 오른쪽 왼쪽 헷갈려서 p->llist로 적어서 그랬다는 ㅠㅠ 디버깅만  10분 했네.. 문제도 아니고 기본 출력 디버깅을 10분이상 쓴게 처음이었다.