이중 연결 리스트(Double Linked List), C언어 구현, 코드

 

들어가기 앞서

 

연결 리스트 기억나나요?

안난다면 밑에 링크 ㄱㄱ

https://8ehrmin.tistory.com/5

Linked List (C언어), 연결 리스트 C언어 구현, 코드(너 ㅋ 이해하고 싶어?)

 

 

정적인 배열을 사용하기 보다, 동적으로 메모리를 할당하여 메모리의 효율을 높이는 연결 리스트를 사용했습니다.

 

하지만서도 단점은 존재하는데요.

연결리스트 (Licked List) 단점
1. 다음 노드를 가리키는 포인터로 인하여 각 노드마다 추가적인 메모리가 필요하다.
2. 특정 위치에 있는 노드에 접근(탐색 시간)하기 위한 n시간이 필요하다. 

 

일반적으로 연결 리스트는 위와같은 단점을 가지고 있습니다.

 

오늘 배워볼 이중 연결 리스트(Double Linked List)는 연결 리스트의 탐색 기능을 개선한 자료구조인데요.

어떻게 하는지 함 봅시다. 뤠츠고

 

---

 

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

Double Licked List
- 하나의 노드에 해당 노드의 바로 앞과 뒤에 있는 노드를 연결한 구조로 노드 하나당 두 개의 지시자가 있는 연결 리스트 (네이버)
- 연결 리스트의 탐색 기능을 개선한 자료구조 (이것이 자료구조+알고리즘이다)

 

쉽게 말하면 다음 노드만 가리키던 연결 리스트에서, 다음과 이전 모두 가리키는 노드들로 구성된 자료 구조 입니다.

팔이 두개가 되었어유

어머나 이제 서로를 찌를 수 있게 되었어요.

그렇다 보니 내 이전이 누군지 알게 되었죠?

이 말은 즉슨, 탐색 과정에서 내 다음으로만 찾던 흐름이 이전으로도 갈 수 있게 되었가는 말 입니다.

 

그렇다면 구조체도 달라져야 겠죠?

---

노드의 구조체

 

구조체는 이전 연결 리스트와 거의 비슷합니다.

단순히 추가 된 것은, 이전 노드를 가리키는 포인터만 추가되면 되겠죠?

모르겠다면 이전 게시물을 보고 오세용.

---

typedef int elementType;

typedef struct tagNode
{
	elementType data;
	struct tagNode* nextNode;
	struct tagNode* prevNode; // 얘만 추가

} Node;

 

---

노드 생성과 소멸

노드의 생성과 소멸 또한, 이전과 거의 동일합니다.

다른 것 하나는, 이전 노드를 가리키는 포인터가 추가되었으므로 생성 과정에서 해당 요소의 NULL을 넣어주어야 한다는 것이죠.

 

NULL을 넣는 이유는, 아직 애기 노드이기때문에 누구를 가리키고 있는지, 내 이전 노드인지 모르기 떄문입니다.

이 포인터가 채워지는 연산은 다음에 있으니 안심하고 지나가도록 할게요. 

---

// 노드 생성(애기 노드 탄생)
Node* createNode(elementType newData)
{
	Node* newNode = (Node*)malloc(sizeof(Node));

	newNode->data = newData;
	newNode->nextNode = NULL;
	newNode->prevNode = NULL;

	return newNode;
}
// 노드 소멸(해제)
void destroyNode(Node* node)
{
	free(node);
}

 

---

노드 추가 연산

노드 추가 연산 : 노드를 Tail 노드 뒤에 추가하는 연산 

생성과 소멸 코드를 작성했으니, 노드를 추가하는 연산도 있어야 겠죠?

노드를 Tail 뒤로 추가하기 위해 알아야 할 것은 Tail이 누구인지 알아야 합니다.

---

void appendNode(Node** head, Node* newNode)
{
	//head가 없다면, 추가되는 노드가 head가 된다. 
	if ((*head) == NULL)
	{
		*head = newNode;

	}
	else
	{
		//테일을 찾아서 newNode에 연결한다.
		Node* tail = (*head);
		while (tail->nextNode != NULL)
		{
			tail = tail->nextNode;
		}

		tail->nextNode = newNode;
		newNode->prevNode = tail;
	}
}

---

이전에 말씀드렸듯이, head는 리스트입니다.

왜냐하면 포인터로 리스트의 맨 앞을 가리키고 있고 맨 앞은 head이기 때문이지요.

 

따라서 if head가 NULL이라는 물음은, head가 NULL 즉 리스트가 없는 초기 상태 이기 때문에, 새로운 노드는 head가 됩니다.

 

//head가 없다면, 추가되는 노드가 head가 된다. 
if ((*head) == NULL)
{
	*head = newNode;

}

---

 

그럼 head가 있다면?

tail을 찾는 여정으로 갑니다.

tail의 특징은 nextNode가 없다는 것이죠?

 

따라서 리스트를 tail로 두고 nextNode가 없는 노드를 찾아야 합니다.

찾는다면 tail의 next노드를 새 노드로 두고, 새 노드의 이전 노드를 tail로 두어야 할 것 입니다.

 

주목 받는게 싫어요

 

else
{
	//테일을 찾아서 newNode에 연결한다.
	Node* tail = (*head);
	while (tail->nextNode != NULL)
	{
		tail = tail->nextNode;
	}

	tail->nextNode = newNode;
	newNode->prevNode = tail;
}

 

이후에 헤드를 이중 포인터(**)로 받는 설명을 했었는데요, 궁금하시다면 이전 게시물을 보고 와주세요.

https://8ehrmin.tistory.com/5

Linked List (C언어), 연결 리스트 C언어 구현, 코드(너 ㅋ 이해하고 싶어?)

 

---

노드 탐색 연산

노드 탐색 연산 : n번째에 있는 노드를 리턴하는 연산

 

연결 리스트와 동일하게 이어집니다.

추가적인 설명은 안하겠습니다.

---

Node* getNodeAt(Node* head, int location)
{
	Node* current = head;

	while (current != NULL && (--location) >= 0)
	{
		current = current->nextNode;
	}

	return current;
}

 

---

노드 삭제 연산

 

노드를 삭제할 때, 연결 리스트에서는 인수인계 과정을 거쳐야 한다고 설명하였습니다.

이중 연결 리스트에서도 인수인계 과정을 거쳐야 하는데요.

 

1. 삭제할 노드의 nextNodePointer를 prevNode의 nextNodePointer로 넘긴다.

2. 삭제할 노드의 prevNodePointer를 nextNode의 prevNodePointer로 넘긴다.

 

이 과정을 그림으로 그리면?

 

인수인계가 아주 잘 되었죠?

---

void 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;
	}
}

---

첫 if문을 보겠습니다.

1) head가 곧 지워야 할 대상이라면, 이 head의 다음 노드가 head가 되는 것 이겠죠?

따라서 head는 지워야 할 노드의 다음 노드가 head가 되는 것 입니다.

 

2) 다음으로는 헤드의 특징인 이전 노드를 가리키는 포인터가 NULL인 것 이겠죠?

따라서 이전 노드를 가리키는 포인터 즉 PrevNode를 NULL로 바꿔주는 것 입니다.

 

3) 그다음은 지워야 할 노드의 이전 및 다음 포인터를 모두 지워주면 끝입니다.

 

if ((*head) == remove)
{
	// 1
	*head = remove->nextNode;
    
    //2
	if ((*head) != NULL) (*head)->prevNode = NULL;
	
    
    //3
	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;
}

 

---

 

노드 삽입 연산

 

맨 끝에 노드를 추가하는 쉬운 방법이 아닌, 중간에 끼우고 싶다면 해당 연산을 수행하야 합니다.

그러려면 인수인계 과정이 여기서도 들어가야겠죠?

 

n번째 노드 뒤로 삽입한다는 것으로 쉽게 정리하면 다음과 같습니다.

1. 새로운 노드의 nextNodePointer를 n번째 노드의 nextNodePointer로 채웁니다.

2. 새로운 노드의 prevNodePointer를 n번째 노드로 채웁니다.

3. n+1번째 노드의 prevNodePointer를 새로운 노드로 채웁니다.

4. n번째 노드의 nextNodePointer를 새로운 노드로 채웁니다.

 

하하 글로 정리하니 어이가 없지만 그림으로 보면 쉬울 것 입니다.

 

 

새로운 노드는 1번노드 뒤로 가고싶어 하는군요.

 

 

1) 새로운 노드의 nextNodePointer를 1번째 노드의 nextNodePointer로 채웁니다.

 

2) 새로운 노드의 prevNodePointer를 1번째 노드로 채웁니다.

 

3) n+1번째 노드의 prevNodePointer를 새로운 노드로 채웁니다.

4. n번째 노드의 nextNodePointer를 새로운 노드로 채웁니다.

 

자 이렇게 되면 모두 친하게 지낼 수 있게 될 것 입니다.

 

---

void insertAfter(Node* current, Node* newNode)
{
	
	newNode->nextNode = current->nextNode; //1)
    newNode->prevNode = current; //2)

	if (current->nextNode != NULL)
	{
		current->nextNode->prevNode = newNode;  //3)
		current->nextNode = newNode; //4)
	}
}

---

Double Linked List 예제 프로그램

 

지금까지 배운 연산을 모두 활용할 수 있는 프로그램을 작성해 보겠습니다.

 

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

typedef int elementType;

typedef struct tagNode
{
	elementType data;
	struct tagNode* nextNode;
	struct tagNode* prevNode; // 얘만 추가

} Node;

Node* createNode_DDL(elementType newData)
{
	Node* newNode = (Node*)malloc(sizeof(Node));

	newNode->data = newData;
	newNode->nextNode = NULL;
	newNode->prevNode = NULL;

	printf("[%d]노드 생성 완료..\n", newNode->data);
	return newNode;
}

void destroyNode_DDL(Node* node)
{
	printf("[%d]노드 해제 완료..\n", node->data);
	free(node);
}

void appendNode_DDL(Node** head, Node* newNode)
{
	//head가 없다면, 추가되는 노드가 head가 된다. 
	if ((*head) == NULL)
	{
		*head = newNode;

	}
	else
	{
		//테일을 찾아서 newNode에 연결한다.
		Node* tail = (*head);
		while (tail->nextNode != NULL)
		{
			tail = tail->nextNode;
		}

		tail->nextNode = newNode;
		newNode->prevNode = tail;
	}
}



Node* getNodeAt_DDL(Node* head, int location)
{
	Node* current = head;

	while (current != NULL && (--location) >= 0)
	{
		current = current->nextNode;
	}

	return current;
}

void removeNode_DDL(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;
	}
}

void insertAfter_DDL(Node* current, Node* newNode)
{
	newNode->nextNode = current->nextNode;
	newNode->prevNode = current;

	if (current->nextNode != NULL)
	{
		current->nextNode->prevNode = newNode;
		current->nextNode = newNode;
	}

	printf("[%d] -> [%d]\n", current->data, newNode->data);
}

int getNodeCount_DDL(Node* head)
{
	int count = 0;
	Node* current = head;

	while (current != NULL)
	{
		current = current->nextNode;
		count++;
	}

	return count;
}
void printbarr_DDL()
{
	printf("================================================================\n");
}

void main()
{
	Node* list = NULL;
	Node* newNode = NULL;
	Node* current = NULL;

	int count = 0;


	printbarr_DDL();
	printf("다중 연결 리스트의 노드 개수를 입력 해 주세요 : ");
	int nodeNum;
	scanf("%d", &nodeNum);

	//노드 생성
	printbarr_DDL();
	for (int i = 0; i < nodeNum; i++)
	{
		appendNode_DDL(&list, createNode_DDL(i + 1));
	}

	//노드 추가
	printbarr_DDL();
	printf("노드 추가 생성 중 입니다..\n");
	count = getNodeCount_DDL(list);
	appendNode_DDL(&list, createNode_DDL(count + 1));

	//노드 중간에 추가 
	printbarr_DDL();
	printf("노드를 중간에 삽입 중 입니다..\n");
	count = getNodeCount_DDL(list);
	int mid = 0;
	if (count > 1) mid = 1;

	Node* midNode = getNodeAt_DDL(list, mid);
	newNode = createNode_DDL(10);
	insertAfter_DDL(midNode, newNode);


	// 노드들 출력
	printbarr_DDL();
	printf("노드를 출력 중 입니다..\n");
	count = getNodeCount_DDL(list);
	for (int i = 0; i < count; i++)
	{
		current = getNodeAt_DDL(list, i);
		printf("[%d번째]노드 데이터 : %d\n", i + 1, current->data);
	}


	//노드 제거
	printbarr_DDL();
	printf("노드를 해제 합니다..\n");
	count = getNodeCount_DDL(list);
	for (int i = 0; i < count; i++)
	{
		current = getNodeAt_DDL(list, 0);
		if (current != NULL)
		{
			removeNode_DDL(&list, current);
			destroyNode_DDL(current);
		}

	}
}

 

정시니가 없네

 

---

끝으로

흠.. 글쎄요 연결 리스트나 더블 연결 리스트나 어째저쨰 비슷하죠?

 

너무 쉬운 것 같아서 하품이 난다면 항상 겸손해야 한다고 말씀드리고 싶습니다 킄킄.

 

틀린 점이 있다면 알려주세요

 

이해 안가는 부분이 있다면 장문으로 물어도 좋으니 언제든 물어봐주시길 바랍니다.

 

참고

이것이 자료구조 알고리즘이다 with C언어