(C) 자료구조 - 이중 연결 리스트(Doubly Linked List)

안녕하세요.

오늘은 저번 단일 연결 리스트에 이어 이중연결 리스트를 구현해 보도록 하겠습니다.

저번과 마찬가지로 malloc 과 free 를 사용하였습니다.

 

1. 이중 연결 리스트(Doubly Linked List)란?

 

다음 노드 정보만 가지고 있는 단일연결 리스트와는 다르게

이중 연결리스트는 이전 노드 정보도 가지고 있다는게 큰 특징이에요.

그래서 이전 노드를 찾으려고 head 부터 돌 필요가 없는 대신

앞 뒤로 연결을 해주어야 하기때문에 단일 연결리스트 보다는 구현이 조금 더 복잡하다는 단점이 있어요.

또한 이전 노드 정보도 가지고 있기 때문에 단일연결에 비해서 약간의 byte 를 더 사용 합니다.

 

2. 이중 연결 리스트(Doubly Linked list) 방식 설명

 

저번 단일 연결 링크드 리스트처럼 더미노드를 사용하는 방식으로 구현 할거에요.

잘 모르겠다! 하시는 분들은 단일 연결리스트를 구현한 방식을 한번 보고 오시면 어떤 방식인지 이해 되실거에요

(C) 자료구조 - 단일 연결 리스트(Singly Linked List)

 

3. 이중 연결 링크드 리스트 구현

 

struct Node
{
	int data;	// 가지고 있는 데이터
	Node* prev;	// 이전 노드 정보
	Node* next;	// 다음 노드 정보
};

prev 이전 노드가 추가 된것을 보실 수 있습니다.

 

Node* head;	//더미 머리 
Node* tail;	//더미 꼬리 
int size;	//링크드 리스트 크기

void InitList();						//리스트 초기화
bool InsertAfter(int value, Node* node);			//특정 노드 뒤 삽입
bool InsertBefore(int value, Node* node);			//특정 노드 앞 삽입
bool DeleteNode(Node* node);					//특정 노드 삭제
Node* FindNodeUsingValue(int value);				//data 비교하여 노드 찾기
Node* FindNodeUsingIndex(int num);				//index 비교하여 노드찾기
int GetIndex(int value);					//특정 data 의 index 반환
int GetSize() { return size; }					//리스트의 크기 반환
void DeleteAll();						//모든 노드 제거
void PrintList();						//모든 노드 출력

 기본적으로 단일 연결 리스트랑 선언이 같습니다.

InsertBefore 함수가 추가 되고 DeleteNext 함수를 지웠어요.

 

InitList

void InitList()
{
	head = (Node*)malloc(sizeof(Node));		//머리 메모리 할당
	tail = (Node*)malloc(sizeof(Node));		//꼬리 메모리 할당
    	head->prev = head;				//머리 앞은 머리
	head->next = tail;				//머리 다음은 꼬리
   	tail->prev = head;				//꼬리 앞은 머리
	tail->next = tail;				//꼬리 다음은 꼬리
	size = 0;					//사이즈는 0
}

더미 노드인 head 와 tail 을 만들어 주고 앞뒤로 연결 해주었습니다.

 

InsertAfter

bool InsertAfter(int value, Node* node)
{
	if (node == tail)				//꼬리 뒤에 삽입 할수 없다.
		return false;

	Node* newNode = (Node*)malloc(sizeof(Node));	//메모리 할당
	newNode->data = value;				//값을 넣어준다
	node->next->prev = newNode;			//앞에 있는 노드는 새로운 노드를 가르킨다.
	newNode->next = node->next;			//새로운 노드도 앞 노드를 가르킨다.
	newNode->prev = node;				//새로운 노드 뒤에 특정노드가 있다.
	node->next = newNode;				//특정 노드 앞에 새로운 노드가 있다.
	size++;						//크기를 하나 늘려준다.
	printf("After %d\n", newNode->data);
	return true;
}

특정 노드 앞에 노드를 추가하는 InsertAfter 함수 입니다.

 

InsertBefore

bool InsertBefore(int value, Node* node)
{
	if (node == head)				
		return false;

	Node* newNode = (Node*)malloc(sizeof(Node));	
	newNode->data = value;				
	node->prev->next = newNode;			
	newNode->prev = node->prev;
	newNode->next = node;
	node->prev = newNode;
	size++;
	printf("Before %d\n", newNode->data);
	return true;
    
    
}

특정 노드 뒤에 노드를 추가하는 InsertBrfore 함수입니다.

위에 있는 InsertAfter와 같은데 prev와 next 위치만 바뀌었습니다.

단일연결리스트에서 Before를 구현하려면 순차적으로 돌아야 하는데

이중 연결리스트에서는 쉽게 구현할 수 있습니다.

 

DeleteNode

bool DeleteNode(Node* node)
{
	if (node == head || node == tail)		//머리나 꼬리는 지울수 없다.
		return false;

	node->next->prev = node->prev;			//특정노드의 앞 노드는 특정노드의 뒤를 가르킨다.
	node->prev->next = node->next;			//특정노드의 뒷 노드는 특정노드의 앞을 가르킨다.
	printf("delete %d\n", node->data);
	free(node);					//메모리 해제
	size--;
	return true;
}

이 함수는 특정 노드를 지우는 함수입니다.

앞노드부터 순차적으로 검색하여 지우던

단일연결 리스트에 비해서 많이 간소화 된 것을 볼수있습니다.

 

FindNodeUsingValue

Node* FindNodeUsingValue(int value)
{
	Node* temp = head->next;		//찾는 노드
	while (temp != tail)			//리스트를 끝까지 돈다
	{
		if (temp->data == value)	//특정 값을 가진 노드를 찾았으면
		{
			printf("Find Value Data : %d \n", temp->data);
			return temp;		//노드를 반환한다.
		}
		temp = temp->next;		//못 찾았으면 다음 노드로
	}
	return temp;				//끝까지 돌았는데 없으면 꼬리 노드 반환
}

단일 연결 리스트와 동일합니다!

검색을 위해서는 단일이나 이중이나 순차적으로 돌아야 하기 때문이죠

 

FindNodeUsingIndex

Node* FindNodeUsingIndex(int num)
{
	if (num < 0 || num >= size)			//크기에 벗어나 있으면 꼬리반환
		return tail;

	Node* temp = head->next;			//head next 가 index 0 노드이다
	for (int i = 0; i < num;++i)			//반복문을 돌아서
		temp = temp->next;			//num 번째 node를 찾는다.

	printf("Find index : %d Data : %d \n", num, temp->data);
	return temp;
}

마찬가지로 단일 연결 리스트와 동일합니다!

 

GetIndex

int GetIndex(int value)
{
	int index = 0;
	Node* temp = head->next;		
	while (temp != tail)		
	{
		if (temp->data == value)
		{
			printf("Value : %d index : %d \n", value, index);
			return index;
		}
		++index;
		temp = temp->next;
	}

	return -1;
}

 이것도 동일합니다.

 

DeleteAll

void DeleteAll()
{
	Node* temp = head->next;		//찾는 노드
	Node* deleteNode;			//지울 노드
	while (temp != tail)			//리스트 끝까지 돈다.
	{
		deleteNode = temp;		//현재 노드를 지울 노드로 지정한다.
		temp = temp->next;		//현재 노드는 다음 노드로 넘어간다.
		free(deleteNode);		//지울 노드를 지워준다.
	}
	size = 0;				//사이즈 초기화
	head->next = tail;			//다 비었으니 head 다음은 tail
	tail->prev = head;			//tail 이전은 head

	printf("Delete All\n");
}

이것도 동일한데

마지막

tail->prev = head 이부분만 추가되었습니다.

 

PrintList

void PrintList()
{
	Node* temp = head->next;			//찾는 노드
	while (temp != tail)				//리스트 끝까지 돈다.
	{
		printf("%d \n", temp->data);		//메세지 출력
		temp = temp->next;			//다음 노드로
	}
	printf("size : %d \n", size);			//크기도 출력
}

이것도 동일합니다.

리스트에 담겨 있는 모든 노드를 출력합니다.

 

4. 테스트

int main()
{
	InitList();		//시작 전에 꼭 해주어야 한다.

	InsertAfter(10, head);
	InsertAfter(20, FindNodeUsingIndex(0));
	InsertAfter(30, FindNodeUsingValue(10));
	InsertAfter(40, FindNodeUsingIndex(GetSize() - 1));
	PrintList();

	printf("\n");
	DeleteNode(FindNodeUsingIndex(GetIndex(40) - 1));
	DeleteNode(FindNodeUsingValue(10));
	DeleteNode(FindNodeUsingValue(100));		//find 실패로 작동하지 않음
	PrintList();

	printf("\n");
	InsertBefore(50, tail);
	InsertBefore(60, FindNodeUsingIndex(0));
	InsertBefore(70, FindNodeUsingValue(10));	//10 이 지워져서 찾지 못했기 때문에 tail 반환
	InsertBefore(80, FindNodeUsingIndex(GetSize() - 1));
	PrintList();

	printf("\n");
	DeleteAll();
	PrintList();
}

출력 결과

 

이것으로 이중 연결리스트 구현을 마치도록 하겠습니다.

감사합니다.

 

다른 자료구조

단일 연결 리스트(Singly Linked List)

이중 연결 리스트(Doubly Linked List)

스택(Stack) - 배열(Array), 링크드리스트(Linked List)

큐(Queue) - 배열(Array), 링크드리스트(Linked List)

이진트리(Binary Tree) - 링크드리스트(Linked List)

이진트리(Binary Tree) - 링크드리스트(Linked List)

우선순위 큐(Priority Queue) - 힙(Heap) - 배열(Array)