연결리스트(Linked List) - 양방향

1. 양방향 연결리스트

단방향 연결리스트는 다음노드의 주소값을 이전노드에 추가해서 노드끼리 연결하는 구조였습니다. 이게 단점이 역방향 탐색이 불가능합니다. 즉, 노드를 찾으러 Head에서 Tail로 탐색하다가 다시 앞으로 가고싶으면, 다시 처음인 Head부터 탐색을 시작해야합니다.

이 단점을 보완하기 위해 만든게 양방향 연결리스트입니다. 다음 노드에도 이전노드의 주소값을 저장을 해서, 다음노드에서도 이전노드로 접근이 가능하게 만듭니다. 단점은 노드가 많아지면, 단방향 연결리스트보다 노드의 하나의 크기가 더 크기 때문에, 메모리 공간상으론 단방향 연결리스트보다 좋지 못합니다. 그러나, 요즘 컴퓨터는 HDD나 SSD가 용량이 엄청 크게 나오기 때문에 공간을 조금 더 쓰더라도 시간을 줄이는게 더 효율적입니다.

헤더파일

먼저 헤더파일을 뜯어보겠습니다.
DoublyLinkedList.h

#ifndef DOUBLY_LINKEDLIST_H
#define DOUBLY_LINKEDLIST_H

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

typedef int ElementType;

typedef struct tagNode {
	ElementType Data;
	struct tagNode* PrevNode;
	struct tagNode* NextNode;
} Node;

//함수 원형 선언
Node* DLL_CreateNode(ElementType NewData);
void DLL_DestroyNode(Node* Node);
void DLL_AppendNode(Node** Head, Node* NewNode);
void DLL_InsertAfter(Node* Current, Node* NewNode);
void DLL_RemoveNode(Node** Head, Node* Remove);
Node* DLL_GetNodeAt(Node* Head, int Location);
int DLL_GetNodeCount(Node* Head);

#endif

일단 Node부터 살펴보면

typedef struct tagNode {
	ElementType Data;
	struct tagNode* PrevNode;
	struct tagNode* NextNode;
} Node;

PrevNode가 추가된 것을 볼 수 있습니다. PrevNode에는 이전 노드의 주소값이 들어갑니다.

함수들을 뜯어보면

Node* DLL_CreateNode(ElementType NewData); ->노드를 생성하는 함수
void DLL_DestroyNode(Node* Node); ->노드를 삭제하는 함수
void DLL_AppendNode(Node** Head, Node* NewNode); ->노드를 리스트에 추가하는 함수
void DLL_InsertAfter(Node* Current, Node* NewNode); ->노드를 리스트중 원하는 곳에 추가하는 함수
void DLL_RemoveNode(Node** Head, Node* Remove); ->노드를 리스트에서 제거하는 함수
Node* DLL_GetNodeAt(Node* Head, int Location); ->노드를 탐색하는 함수
int DLL_GetNodeCount(Node* Head); ->노드의 개수를 반환하는 함수

함수자체는 단방향 연결리스트와 크게 달라지지 않은 모습입니다.

소스파일

함수 자체가 단방향 연결리스트와 크게 달라지지 않았기 때문에, 아마 PrevNode부분만 추가한 것 말고는 바뀌는게 없을 것 입니다.
DoublyLinkedList.c

#include "DoublyLinkedList.h"

//노드 생성
Node* DLL_CreateNode(ElementType NewData) {
	Node* NewNode = (Node*)malloc(sizeof(Node));

	NewNode->Data = NewData;
	NewNode->PrevNode = NULL;
	NewNode->NextNode = NULL;

	return NewNode;
}

//노드 소멸
void DLL_DestroyNode(Node* Node) {
	free(Node);
}

//노드 추가
void DLL_AppendNode(Node** Head, Node* NewNode) {
	//헤드 노드가 NULL이라면 새로운 노드가 Head가 된다.
	if ((*Head) == NULL) {
		*Head = NewNode;
	}
	else {
		//테일을 찾아 NewNode를 연결한다.
		Node* Tail = (*Head);
		while (Tail->NextNode != NULL) {
			Tail = Tail->NextNode;
		}

		Tail->NextNode = NewNode;
		NewNode->PrevNode = Tail;//기존 테일을 새로운 테일의 PrevNode가 가리킨다.
	}
}

//노드 삽입
void DLL_InsertAfter(Node* Current, Node* NewNode) {
	NewNode->NextNode = Current->NextNode;
	NewNode->PrevNode = Current;

	if (Current->NextNode != NULL) {
		Current->NextNode->PrevNode = NewNode;
		Current->NextNode = NewNode;
	}
}

//노드 제거
void DLL_RemoveNode(Node** Head, Node* Remove) {
	if (*Head == Remove) {
		*Head = Remove->NextNode;
		if ((*Head) != NULL) {
			(*Head)->PrevNode = NULL;
		}
		Remove->PrevNode = NULL;
		Remove->NextNode = NULL;
	}
	else {
		Node* Temp = Remove;

		if (Remove->PrevNode != NULL) {
			Remove->PrevNode->NextNode = Temp->NextNode;
		}
		if (Remove->NextNode != NULL) {
			Remove->NextNode->PrevNode = Temp->PrevNode;
		}

		Remove->PrevNode = NULL;
		Remove->NextNode = NULL;
	}
}

//노드 탐색
Node* DLL_GetNodeAt(Node* Head, int Location) {
	Node* Current = Head;

	while (Current != NULL && (--Location) >= 0) {
		Current = Current->NextNode;
	}

	return Current;
}

//노드 개수 세기
int DLL_GetNodeCount(Node* Head) {
	unsigned int Count = 0;
	Node* Current = Head;
	
	while (Current != NULL) {
		Current = Current->NextNode;
		Count++;
	}
	return Count;
}

void PrintNode(Node* _Node) {
	if (_Node->PrevNode == NULL) {
		printf("Prev: NULL");
	}
	else {
		printf("Prev: %d", _Node->PrevNode->Data);
		printf("Current: %d", _Node->Data);
	}

	if (_Node->NextNode == NULL) {
		printf("Next: NULL\n");
	}
	else {
		printf("Next: %d\n", _Node->NextNode->Data);
	}
}

실행예시

단방향 연결리스트와 마찬가지로, 헤더파일만 봐도 메인함수의 결과를 어느정도 예측가능합니다. 메인함수 실행결과를 확인하고, 마무리하겠습니다.
DoublyLinkedListMain.c

#include "DoublyLinkedList.h"

int main() {
	int i = 0;
	int Count = 0;
	Node* List = NULL;
	Node* NewNode = NULL;
	Node* Current = NULL;

	//노드 5개 추가
	for (i = 0; i < 5; i++) {
		NewNode = DLL_CreateNode(i);
		DLL_AppendNode(&List, NewNode);
	}

	//리스트 출력
	Count = DLL_GetNodeCount(List);
	for (i = 0; i < Count; i++) {
		Current = DLL_GetNodeAt(List, i);
		printf("List[%d] : %d\n", i, Current->Data);
	}

	//리스트의 세 번째 칸 뒤에 노드 삽입
	printf("\nInserting 3000 After [2]...\n\n");

	Current = DLL_GetNodeAt(List, 2);
	NewNode = DLL_CreateNode(3000);
	DLL_InsertAfter(Current, NewNode);

	//리스트 출력
	Count = DLL_GetNodeCount(List);
	for (i = 0; i < Count; i++) {
		Current = DLL_GetNodeAt(List, i);
		printf("List[%d] : %d\n", i, Current->Data);
	}

	//모든 노드를 메모리에서 제거
	printf("\nDestroying List...\n");
	
	Count = DLL_GetNodeCount(List);

	for (i = 0; i < Count; i++) {
		Current = DLL_GetNodeAt(List, 0);

		if (Current != NULL) {
			DLL_RemoveNode(&List, Current);
			DLL_DestroyNode(Current);
		}
	}

	return 0;
}

결과

List[0] : 0
List[1] : 1
List[2] : 2
List[3] : 3
List[4] : 4

Inserting 3000 After [2]...

List[0] : 0
List[1] : 1
List[2] : 2
List[3] : 3000
List[4] : 3
List[5] : 4

Destroying List...