Chapter 05. 양방향 연결 리스트

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

'양방향 연결 리스트' 또는 '이중 연결 리스트'라고도 불리는 이 자료구조는 그 이름이 의미하듯 노드가 양쪽 방향으로 연결된 구조의 리스트입니다. 즉, 왼쪽 노드가 오른쪽 노드를 가리킴과 동시에 오른쪽 노드도 왼쪽 노드를 가리키는 구조입니다.

---

양방향 연결 리스트를 이해하기는 어렵지 않습니다. 지금까지 배운 연결 리스트를 크게 세 가지로 분류하자면 다음과 같습니다.

• 단순 연결 리스트
• 더미 노드 연결 리스트
• 원형 연결 리스트

위 세 가지 연결 리스트는 모드 한쪽 방향으로면 연결되는 단방향 연결 리스트입니다. 양방향 연결 리스트는 위 세 가지의 연결 리스트들의 연결 방향이 양쪽으로 되어 있는 것과 같습니다. 이런 점 때문에 보통 양방향 연결 리스트의 구현을 어렵다고 생각하는 사람들이 있습니다. 하지만 이는 잘못된 선입견입니다.

 

양방향 연결 리스트의 구현은 지금까지 해온 단방향 연결 리스트의 구현과 다르지 않습니다. 그리고 단방향 연결 리스트의 경우 before 포인터를 구현해서 사용했지만 양방향 연결 리스트에서는 before 포인터가 전혀 필요하지 않습니다. 어떻게 그렇게 되는 것인지 이제 양방향 연결 리스트를 구현해 보면서 알아보겠습니다.

---

우선은 단순 양방향 연결 리스트를 구현해 볼 것입니다. 이 리스트는 앞서 배운 단순 연결 리스트와 같이 더미 노드가 사용되지 않으며, 원형으로 배치되지도 않은 리스트입니다. 이번 리스트의 구현에서는 LRemove 함수는 구현하지 않겠습니다. 하지만 대신 LPrevious 함수를 구현하게 됩니다. LNext 함수가 오른쪽의 노드를 조회하는 함수라면, Lprevious 함수는 왼쪽의 노드를 조회하는 함수입니다. 이는 각각의 노드가 양방향으로 연결되어 있기 때문에 구현이 가능한 함수입니다. 이제 이를 바탕으로 정의한 헤더 파일을 소개합니다.

//DBLinkedList.h 헤더 파일로 저장
#ifndef DB_LINKEDLIST_H
#define DB_LINKEDLIST_H

#define TRUE 1
#define FALSE 0

typedef int Data;

typedef struct Node
{
	Data data;
	struct Node* next;
	struct Node* prev;
} Node;

typedef struct DLinkedList
{
	Node* head;
	Node* cur;
	int numOfData;
} DBLinkedList;

typedef DBLinkedList List;

void ListInit(List* plist);
void LInsert(List* plist, Data data);
int LFirst(List* plist, Data* pdata);
int LNext(List* plist, Data* pdata);
int LPrevious(List* plist, Data* pdata);
int LCount(List* plist);

#endif

 

 

이제 위 헤더 파일을 바탕으로 각각의 함수들을 구현해 보겠습니다.

먼저, 리스트를 초기화하는 함수인 ListInit 함수의 구현입니다.

void ListInit(List* plist)
{
	plist->head = NULL;
	plist->cur = NULL;
	plist->numOfData = 0;
}

해당 함수는 리스트를 생성하고 가장 처음 호출되는 함수이기 때문에 해당 리스트에는 저장된 데이터가 아무것도 없습니다. 따라서 head, cur 포인터를 NULL포인터로 저장하고 데이터 개수를 저장하는 numOfData도 0으로 초기화합니다.

 

다음은 데이터의 저장을 수행하는 LInsert 함수의 구현입니다.

void LInsert(List* plist, Data data)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	newNode->next = plist->head;

	if (plist->head != NULL) plist->head->prev = newNode;

	newNode->prev = NULL;
	plist->head = newNode;
	plist->numOfData++;
}

이 리스트에서는 추가되는 노드를 머리에 붙입니다. 이는 newNode를 우선 머리 앞에 붙인 후, newNode->next가 머리를 가리키게 하고, 머리의 prev가 newNode를 가리키게 한 뒤, newNode를 머리로 선언하는 과정으로 구현할 수 있습니다.

 

이제 데이터를 조회하는 함수인 LFirst 함수, LNext 함수, LPrevious 함수를 구현해 보겠습니다.

int LFirst(List* plist, Data* pdata)
{
	if (plist->head == NULL) return FALSE;

	plist->cur = plist->head;

	*pdata = plist->cur->data;
	return TRUE;
}

int LNext(List* plist, Data* pdata)
{
	if (plist->cur->next == NULL) return FALSE;

	plist->cur = plist->cur->next;

	*pdata = plist->cur->data;
	return TRUE;	
}

int LPrevious(List* plist, Data* pdata)
{
	if (plist->cur->prev == NULL) return FALSE;

	plist->cur = plist->cur->prev;
	
	*pdata = plist->cur->data;
	return TRUE;
}

데이터의 조회는 머리에서부터 이루어집니다. 그리고 위 세 함수 중 LFirst 함수가 가장 먼저 호출되어야 하는 함수입니다. LFirst 함수가 호출되면 cur 포인터를 머리의 위치로 초기화합니다. 그리고 해당 데이터를 조회합니다. LNext 함수는 next 방향으로 조회를 수행합니다. cur포인터의 next에 참조할 데이터가 있는지 확인한 후 해당 노드로 옮겨가 조회를 수행합니다. LPrevious 함수는 LNext 함수와 기능은 같으나 방향만 반대입니다.

 

이제 지금까지 구현한 헤더 파일을 테스트해 볼 main 함수를 선언하여 그 실행결과를 보이겠습니다.

//DBLinkedList.h 헤더 파일로 저장
#ifndef DB_LINKEDLIST_H
#define DB_LINKEDLIST_H

#define TRUE 1
#define FALSE 0

#define NEXT 1
#define PREV -1

typedef int Data;

typedef struct Node
{
	Data data;
	struct Node* next;
	struct Node* prev;
} Node;

typedef struct DLinkedList
{
	Node* head;
	Node* cur;
	int numOfData;
} DBLinkedList;

typedef DBLinkedList List;

void ListInit(List* plist);
void LInsert(List* plist, Data data);
int LFirst(List* plist, Data* pdata);
int LNext(List* plist, Data* pdata);
int LPrevious(List* plist, Data* pdata);
int LCount(List* plist);

#endif

//DBLinkedList.c 소스 파일로 저장
#include "DBLinkedList.h"
#include <stdio.h>
#include <stdlib.h>

void ListInit(List* plist)
{
	plist->head = NULL;
	plist->cur = NULL;
	plist->numOfData = 0;
}
void LInsert(List* plist, Data data)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	if (newNode == NULL) exit(1);
	newNode->data = data;

	newNode->next = plist->head;

	if (plist->head != NULL) plist->head->prev = newNode;

	newNode->prev = NULL;
	plist->head = newNode;
	plist->numOfData++;
}
int LFirst(List* plist, Data* pdata)
{
	if (plist->head == NULL) return FALSE;

	plist->cur = plist->head;

	*pdata = plist->cur->data;
	return TRUE;
}
int LNext(List* plist, Data* pdata)
{
	if (plist->cur->next == NULL) return FALSE;

	plist->cur = plist->cur->next;

	*pdata = plist->cur->data;
	return TRUE;	
}
int LPrevious(List* plist, Data* pdata)
{
	if (plist->cur->prev == NULL) return FALSE;

	plist->cur = plist->cur->prev;
	
	*pdata = plist->cur->data;
	return TRUE;
}
int LCount(List* plist)
{
	return plist->numOfData;
}

//main.c 소스 파일로 저장
#include <stdio.h>
#include "DBLinkedList.h"

int main(void)
{
	//양방향 연결 리스트의 생성 및 초기화
	List list;
	int data;
	ListInit(&list);

	//8개의 데이터 저장
	LInsert(&list, 1);
	LInsert(&list, 2);
	LInsert(&list, 3);
	LInsert(&list, 4);
	LInsert(&list, 5);
	LInsert(&list, 6);
	LInsert(&list, 7);
	LInsert(&list, 8);

	//저장된 데이터의 조회
	if (LFirst(&list, &data))
	{
		printf("%d ", data);

		//오른쪽 노드로 이동하며 데이터 조회
		while (LNext(&list, &data))
		{
			printf("%d ", data);
		}

		//왼쪽 노드로 이동하며 데이터 조회
		while (LPrevious(&list, &data))
		{
			printf("%d ", data);
		}

		printf("\n\n");
	}

	return 0;
}

/*
실행결과

8 7 6 5 4 3 2 1 2 3 4 5 6 7 8

*/

혹시 이해가 가지 않거나 추가 설명이 필요하다면 언제든지 물어봐주기 바랍니다.