Doubly Linked List는 단방향(Head -> Tail) 탐색만이 가능한 Singly Linked List의 탐색 기능을 개선한 자료구조입니다.
사진 출처 – GeeksforGeeks
Doubly Linked List의 연산은 ‘이전 노드’를 처리하기 위한 구현이 추가 될 뿐, Singly Linked List와 차이점이 전혀 없습니다. 아래 Singly Linked List 참조 바랍니다.
Doubly Linked List의 주요 연산
- 노드 생성/소멸
- 노드 추가
- 노드 탐색
- 노드 삭제
- 노드 삽입
노드 구현
1 2 3 4 5 6 | typedef struct Node { int data; struct Node* nextNode; struct Node* prevNode; } Node; | cs |
Singly Linked List와 구별되는 점은 prevNode가 추가되었다는 점입니다.
노드 생성
1 2 3 4 5 6 7 8 9 | Node* DLL_createNode(int data) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode–>data = data; newNode–>nextNode = NULL; newNode–>prevNode = NULL; return newNode; } | cs |
입력받은 데이터를 newNode->data에 입력해주고, nextNode와 prevNode 모두 NULL값을 할당합니다.
노드 소멸
1 2 3 4 | void DDL_destroyNode(Node* node) { free(node); } | cs |
free 함수는 <stdlib.h>를 include해주셔야 사용이 가능합니다.
노드 추가
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | void DDL_appendNode(Node** head, Node* newNode) { if(*head == NULL) { *head = newNode; } else { Node *tail = *head; while(tail–>nextNode != NULL) tail = tail–>nextNode; tail–>nextNode = newNode; newNode–>prevNode = tail; } } | cs |
Tail 뒤에 새로운 노드를 추가하는 연산으로 Singly와 대부분 유사하나 newNode->prevNode = tail; 부분만 추가되었습니다.
노드 탐색
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | Node* DDL_getNodeAt(Node* head, int index) { Node* current = head; while(current != NULL && ––index >= 0) { current = current–>nextNode; } return current; } int main(int argc, const char * argv[]) { Node *list = NULL; Node *newNode = NULL; DDL_appendNode(&list, DLL_createNode(4)); DDL_appendNode(&list, DLL_createNode(5)); Node* searchedNode = DDL_getNodeAt(list, 1); printf(“%d\n”,searchedNode–>data); //결과값 5 } | cs |
Singly Linked List와 다른 부분이 하나도 없습니다.
노드 삭제
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | void DDL_removeNode(Node** head, Node* removedNode) { if(*head == removedNode) { *head = removedNode–>nextNode; if(*head != NULL) { (*head)–>prevNode = NULL; } removedNode–>nextNode = NULL; removedNode–>prevNode = NULL; } else { Node* temp = removedNode; removedNode–>prevNode–>nextNode = temp–>nextNode; if(removedNode–>nextNode != NULL) removedNode–>nextNode–>prevNode = temp–>prevNode; removedNode–>nextNode = NULL; removedNode–>prevNode = NULL; } } int main(int argc, const char * argv[]) { Node *list = NULL; Node *newNode = NULL; DDL_appendNode(&list, DLL_createNode(4)); DDL_appendNode(&list, DLL_createNode(5)); DDL_appendNode(&list, DLL_createNode(7)); DDL_appendNode(&list, DLL_createNode(8)); DDL_display(&list); Node* searchedNode = DDL_getNodeAt(list, 1); DDL_removeNode(&list, searchedNode); DDL_display(&list); } | cs |
Doubly Linked List의 삭제 연산은 삭제할 노드의 prev, next 그리고 이전 노드의 next, 다음 노드의 prev, 총 4가지 포인터를 수정해주어야 합니다. 보통 아래 순서대로 수정하시면 포인터 지정의 혼란을 피할 수 있습니다.
- 이전 노드의 next Node
- 다음 노드의 prev Node
- 삭제할 노드의 prev, next = NULL
노드 삽입
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | void insertAfter(Node* current, Node* newNode) { if(current != NULL) { newNode–>prevNode = current; newNode–>nextNode = current–>nextNode; if(current–>nextNode != NULL) current–>nextNode–>prevNode = newNode; current–>nextNode = newNode; } } int main(int argc, const char * argv[]) { Node *list = NULL; Node *newNode = NULL; DDL_appendNode(&list, DLL_createNode(4)); DDL_appendNode(&list, DLL_createNode(5)); DDL_appendNode(&list, DLL_createNode(7)); DDL_appendNode(&list, DLL_createNode(8)); DDL_display(&list); Node* searchedNode = DDL_getNodeAt(list, 2); insertAfter(searchedNode, DLL_createNode(99)); DDL_display(&list); } | cs |
노드 삭제와 마찬가지로 4가지 포인터(현재노드의 prev, next, 이전의 next, 다음의 prev)를 조정해야 합니다. 아래 순서대로 수정하면 혼선을 피할 수 있습니다.
- 현재 노드의 Prev
- 현재 노드의 Next
- 다음 노드의 Prev
- 이전 노드의 Next
C로 구현된 Doubly Linked List 전체 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | #include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node* nextNode; struct Node* prevNode; } Node; Node* DLL_createNode(int data) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode–>data = data; newNode–>nextNode = NULL; newNode–>prevNode = NULL; return newNode; } void DDL_destroyNode(Node* node) { free(node); } void DDL_appendNode(Node** head, Node* newNode) { if(*head == NULL) { *head = newNode; } else { Node *tail = *head; while(tail–>nextNode != NULL) tail = tail–>nextNode; tail–>nextNode = newNode; newNode–>prevNode = tail; } } Node* DDL_getNodeAt(Node* head, int index) { Node* current = head; while(current != NULL && ––index >= 0) { current = current–>nextNode; } return current; } void DDL_display(Node** head) { Node* current = *head; printf(“PRINT CURRENT NODES\n”); printf(“===================\n”); while(current != NULL) { printf(“%d\t”,current–>data); current = current–>nextNode; } printf(“\n===================\n\n”); } void DDL_removeNode(Node** head, Node* removedNode) { if(*head == removedNode) { *head = removedNode–>nextNode; if(*head != NULL) { (*head)–>prevNode = NULL; } removedNode–>nextNode = NULL; removedNode–>prevNode = NULL; } else { Node* temp = removedNode; removedNode–>prevNode–>nextNode = temp–>nextNode; if(removedNode–>nextNode != NULL) removedNode–>nextNode–>prevNode = temp–>prevNode; removedNode–>nextNode = NULL; removedNode–>prevNode = NULL; } } void insertAfter(Node* current, Node* newNode) { if(current != NULL) { newNode–>prevNode = current; newNode–>nextNode = current–>nextNode; if(current–>nextNode != NULL) current–>nextNode–>prevNode = newNode; current–>nextNode = newNode; } } int main(int argc, const char * argv[]) { Node *list = NULL; Node *newNode = NULL; DDL_appendNode(&list, DLL_createNode(4)); DDL_appendNode(&list, DLL_createNode(5)); DDL_appendNode(&list, DLL_createNode(7)); DDL_appendNode(&list, DLL_createNode(8)); DDL_display(&list); Node* searchedNode = DDL_getNodeAt(list, 2); insertAfter(searchedNode, DLL_createNode(99)); DDL_display(&list); } | cs |
참조