요약
- 링크드 리스트의 문제였던 탐색 문제를 개선한 링크드 리스트 자료구조
- 첫 데이터를 헤드, 끝 데이터를 테일, 각 데이터를 노드라고 부름
- 각 노드의 다음 노드 주소와 이전 노드 주소 양 방향을 관리
- 노드가 앞 뒤 양 방향을 다루므로 접근은 용이하나 삭제 등에서 각각 전부 삭제해 주어야 함
- 데이터의 접근이 어려우나, 생성, 소멸, 삭제 등은 쉬움
더블 링크드 리스트(Double Linked List)란
더블 링크드 리스트란 링크드 리스트의 탐색 기능을 개선한 자료구조이다.
기존 링크드 리스트에서 탐색을 하기 위해 헤드에서 테일 방향으로의 노드를 모두 거쳐야 했다.
이러한 불편함을 더블 링크드 리스트 구조에선 헤드 -> 테일 및 테일 -> 헤드 방향, 즉 양방향 탐색이 가능하도록 개선했다.
양방향 탐색이 가능한 이유는 노드의 구조가 변경되었기 때문이다.
링크드 리스트에서 노드가 다음 노드를 가리키는 포인터였다면, 더블 링크드 리스트의 노드는 자신의 앞에 있는 노드를 가리키는 포인터도 갖고 있다.
그래서 더블 링크드 리스트의 노드는 앞과 뒤 모두 이동이 가능하다.
이를 구조체로 선언하면 다음과 같이 선언할 수 있다.
typedef int ElementType;
typedef struct tagNode
{
ElementType data; // 저장할 데이터
struct tagNode* prevNode; // 앞 노드의 주소와 데이터
struct tagNode* nextNode; // 뒤 노드의 주소와 데이터
} Node;
위 구조체를 사용하여 노드를 구성할 경우 더블 링크드 리스트가 된다.
링크드 리스트의 주요 연산
링크드 리스트의 주요 연산은 두 종류로, 자료구조를 구축하기 위한 연산과 자료구조에 저장된 데이터를 활용하기 위한 연산이다
기존 링크드 리스트의 연산과 동일하다.
- 노드 생성(CreatedNode) 및 소멸(DestroyNode)
- 노드 추가(AppendNode)
- 노드 탐색(GetNodeAt)
- 노드 삭제(RemoveNode)
- 노드 삽입(InsertAfter, InsertNewHead)
위 리스트 중 생성 및 소멸, 추가 삭제는 자료구조를 구축하기 위한 연산, 탐색은 활용 연산이다.
노드의 생성/소멸 연산
노드를 생성하기 위해 힙 메모리 영역에 데이터를 할당해야 한다.
지역 변수로 같이 데이터를 생성하면 함수가 종료되면서 스택에 있던 데이터는 소멸된다.
// 노드 생성
Node* DLL_CreateNode(ElementType newData)
{
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = newData; // 저장할 데이터
newNode->prevNode = NULL; // 앞 노드의 정보
newNode->nextNode = NULL; // 뒤 노드의 정보
return newNode;
}
노드의 소멸시키는 방법은 free 함수로 간단하게 처리할 수 있다.
// 노드 소멸
void DLL_Destroy(Node* node)
{
free(node);
}
노드 추가 연산
노드 추가는 테일 노드 뒤에 새로운 노드를 만들어 연결하는 연산이다.
싱글 링크드 리스트와 다르게 새로운 테일의 prevNode 포인터도 기존 테일의 주소를 가리키도록 해야한다.
DLL_CreateNode() 함수를 노드 생성 후 기존 테일의 노드를 가리키게 한다.
void DLL_AppendNode(Node** head, Node* newNode)
{
// 헤드의 노드가 NULL일 경우 새로운 노드가 헤드가 됨
if((*head) == NULL) {
*head = newNode;
}
// 헤드의 노드가 NULL이 아닐 경우 테일을 찾아 NewNode를 연결
else {
// 테일에 연결
Node* tail = (*head);
while(tail->nextNode != NULL) {
tail = tail->nextNode;
}
tail->nextNode = newNode;
newNode->prevNode = tail; // 기존의 테일을 새로운 테일의 prevNode가 가리킴
}
}
DLL_AppendNode 함수는 다음과 같이 사용할 수 있다.
Node* list = NULL;
DLL_AppendNode(&list, DLL_CreateNode(117));
DLL_AppendNode(&list, DLL_CreateNode(119));
노드 탐색 연산
링크드 리스트에서 노드에 접근하기 위해서는 헤드부터 다음 노드에 대한 포인터를 징검다리 삼아 모든 노드를 거쳐야 한다.
찾고자 하는 요소가 N번째에 있다면 N - 1개의 노드를 전부 거쳐야 하므로 비효울적이다.
이 경우가 링크드 리스트의 단점이며, 반대로 정적인 배열은 한 번에 거칠수 있으므로 반대의 개념이 된다.
Node* DLL_GetNodeAt(Node* head, int location)
{
Node* current = head;
while(current != NULL && (--location) >= 0) {
current = current->nextNode;
}
return current;
}
노드 삭제 연산
더블 링크드 리스트에서 삭제할 노드는 양쪽 포인터 2개, 이전 노드의 nextNode 포인터, 다음 노드의 prevNode 포인터 4개를 삭제해야 한다.
삭제할 노드의 nextNode 포인터가 가리키던 노드를 이전 노드의 nextNode 포인터가 가리키게 바꾸고,
삭제할 prevNode 포인터가 가리키던 노드를 다음 노드의 prevNode 포인터가 가리키게 바꾼다.
그리고 삭제할 노드의 nextNode와 prevNode는 NULL로 값을 초기화한다.
void DLL_RemoveNode(Node** head, Node* remove)
{
if(*head == removeNode) {
*head = removeNode->nextNode;
if((*head) != NULL) {
(*head)->prevNode = NULL;
}
// 삭제할 노드의 가리키고 있는 값 초기화
removeNode->prevNode = NULL;
removeNode->nextNode = NULL;
}
else {
Node* temp = removeNode;
// 삭제할 노드의 prevNode 포인터가 가리키던 노드를 이전 노드의 nextNode 포인터가 가리키게 변경
if(removeNode->prevNode != NULL) {
removeNode->prevNode->nextNode = temp->nextNode;
}
// 삭제할 노드의 nextNode 포인터가 가리키던 노드를 이전 노드의 nextNode 포인터가 가리키게 변경
if(removeNode->nextNode != NULL) {
removeNode->nextNode->prevNode = temp->prevNode;
}
// 삭제할 노드의 가리키고 있는 값 초기화
removeNode->prevNode = NULL;
removeNode->nextNode = NULL;
}
}
노드 삽입
노드 삽입은 노드와 노드 사이에 새로운 노드를 끼워 넣는 연산이다.
새로운 노드를 삽입할 때 prevNode 포인터로는 이전 노드를 가리키게 하고,
nextNode 포인터로는 다음 노드를 가리키게 한다.
그리고 이전 노드의 nextNode 포인터와 다음 노드의 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;
}
}
노드 개수 세기
노드의 개수를 세는 연산은 링크드 리스트 내에 존재하는 모든 노드의 개수를 반환한다.
int DLL_GetNodeCount(Node* head)
{
int count = 0;
Node* current = head;
while(current != NULL) {
current = current->nextNode;
count++;
}
return count++;
}
예제 코드
#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* newHead); // 노드 추가
void DLL_InsertAfter(Node* current, Node* newNode); // 노드 삽입
void DLL_InsertNewHead(Node** head, Node* newHead); // 헤드 삽입
void DLL_RemoveNode(Node** head, Node* removeNode); // 노드 삭제
Node* DLL_GetNodeAt(Node* head, int location); // 노드 탐색
int DLL_GetNodeCount(Node* head); // 노드 개수
int main()
{
int i = 0;
int count = 0;
Node* list = NULL;
Node* newNode = NULL;
Node* current = NULL;
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");
count = DLL_GetNodeCount(list);
for(i = 0; i < count; i++) {
current = DLL_GetNodeAt(list, i);
printf("List[%d] : %d\n", i, current->data);
}
// 모든 노드 소멸
printf("Destroying List\n\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;
}
// 노드 생성
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일 경우 새로운 노드가 헤드가 됨
if((*head) == NULL) {
*head = newNode;
}
// 헤드의 노드가 NULL이 아닐 경우 테일을 찾아 NewNode를 연결
else {
// 테일에 연결
Node* tail = (*head);
while(tail->nextNode != NULL) {
tail = tail->nextNode;
}
tail->nextNode = newNode;
newNode->prevNode = tail; // 기존의 테일을 새로운 테일의 prevNode가 가리킴
}
}
// 노드 탐색
Node* DLL_GetNodeAt(Node* head, int location)
{
Node* current = head;
while(current != NULL && (--location) >= 0) {
current = current->nextNode;
}
return current;
}
// 노드Node
void DLL_RemoveNode(Node** head, Node* removeNode)
{
if(*head == removeNode) {
*head = removeNode->nextNode;
if((*head) != NULL) {
(*head)->prevNode = NULL;
}
// 삭제할 노드의 가리키고 있는 값 초기화
removeNode->prevNode = NULL;
removeNode->nextNode = NULL;
}
else {
Node* temp = removeNode;
// 삭제할 노드의 prevNode 포인터가 가리키던 노드를 이전 노드의 nextNode 포인터가 가리키게 변경
if(removeNode->prevNode != NULL) {
removeNode->prevNode->nextNode = temp->nextNode;
}
// 삭제할 노드의 nextNode 포인터가 가리키던 노드를 이전 노드의 nextNode 포인터가 가리키게 변경
if(removeNode->nextNode != NULL) {
removeNode->nextNode->prevNode = temp->prevNode;
}
// 삭제할 노드의 가리키고 있는 값 초기화
removeNode->prevNode = NULL;
removeNode->nextNode = NULL;
}
}
// 노드 삽입
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;
}
}
// 노드 개수
int DLL_GetNodeCount(Node* head)
{
int count = 0;
Node* current = head;
while(current != NULL) {
current = current->nextNode;
count++;
}
return count++;
}
https://github.com/JeHeeYu/Algorithm/blob/main/List/Double%20Linked%20List/double_linked_list.c
GitHub - JeHeeYu/Algorithm: 알고리즘 문제 풀이
알고리즘 문제 풀이. Contribute to JeHeeYu/Algorithm development by creating an account on GitHub.
github.com
출처 : 이것이 자료구조+알고리즘이다 with c 언어
'Algorithm > 이론' 카테고리의 다른 글
| [Algorithm] C - 재귀함수(Recursion) (2) | 2022.11.12 |
|---|---|
| [Algorithm] C - 큐(Queue) (0) | 2022.11.08 |
| [Algorithm] C - 스택(Stack) (0) | 2022.11.07 |
| [Algorithm] C - 환형 더블 링크드 리스트(Circular Double Linked List) (0) | 2022.11.07 |
| [Algorithm] C - 링크드 리스트(Linked List) (0) | 2022.11.06 |