더블 링크드 리스트란
링크드 리스트의 탐색 기능을 개선한 자료구조입니다.
자신의 앞에 있는 노드를 가리키는 포인터도 있어서, 앞으로도 뒤로도 이동할 수 있습니다.
다음은 더블 링크드 리스트를 표현한 구조체입니다.
typedef struct Node {
struct Node* prevNode;
int Data;
struct Node* nextNode;
}Node;
특별한건 없고 '앞 노드'를 처리하기 위한 포인터만 추가됩니다.
노드 생성
다음은 노드를 생성하는 CreateNode() 함수 입니다.
'앞 노드'를 가리키는 prevNode 포인터를 NULL로 초기화 하는것 말고는 싱글 링크드 리스트와 똑같습니다.
Node* CreateNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->prevNode = NULL;
newNode->nextNode = NULL;
return newNode;
}
노드 추가
테일을 찾아서 새 노드를 추가합니다.
새 노드의 prevNode 포인터가 tail 노드를 가리키도록 합니다.
void AppendNode(Node** head, Node* newNode) {
if (NULL == (*head)) { //헤드 노드가 없다면, 새 노드가 헤드 노드
(*head) = newNode;
}
else { // 테일 노드를 찾아서, 테일 뒤에 새 노드를 덧붙인다
Node* tail = (*head);
while (NULL != tail->nextNode) {
tail = tail->nextNode;
}
newNode->prevNode = tail;
tail->nextNode = newNode;
}
}
헤드 노드가 없으면, 새 노드가 헤드 노드가 됩니다.
그렇지 않으면, 현재 노드가 테일 노드가 될 때까지 이동하고,
테일을 찾아내면,새 노드의 이전이 테일이고, 테일의 다음 노드가 새 노드가 되도록 포인터 변수값을 넣습니다.
노드 삭제
조금 어려운 부분입니다.
변경 해야 할 노드의 포인터가 4개이기 때문입니다.
앞 노드, 삭제할 노드, 뒷 노드 순으로 존재한다고 가정할 때,
삭제할 노드의 '앞 노드'와 삭제할 노드의 '뒷 노드'의 포인터를 포함하여 총 4개입니다.
void RemoveNode(Node** head, Node* target) {
printf("[RemoveNode] %2d를 삭제합니다.\n", target->data);
if ((*head) == target) { // 헤드를 삭제하는 경우,
// 헤드를 변경
(*head) = target->nextNode;
if (NULL != (*head)) {
(*head)->prevNode = NULL;
}
// 타겟을 제거
target->nextNode = NULL;
target->prevNode = NULL;
free(target);
}
else {
// temp = 타겟
Node* temp = target;
// temp의 앞과 temp의 뒤를 이어준다 (타겟의 앞과 뒤를 이어준다)
temp->prevNode->nextNode = temp->nextNode;
if (NULL != temp->nextNode) {
temp->nextNode->prevNode = temp->prevNode;
}
target->nextNode = NULL;
target->prevNode = NULL;
free(target);
}
}삭제할 노드의 '앞 노드'가 삭제할 노드의 '뒷 노드'를 가리키도록 변경합니다.
'뒷 노드'의 prevNode* 가 '앞 노드'의 nextNode*를 가리키도록 변경합니다.
삭제할 노드의 앞뒤 포인터 두 개를 전부 NULL을 가리키도록 변경합니다.
중복을 제거한 다음 코드도 정상 동작합니다.
void RemoveNode(Node** head, Node* target) {
printf("[RemoveNode] %2d를 삭제합니다.\n", target->data);
if ((*head) == target) { // 헤드를 삭제하는 경우,
// 헤드를 변경
(*head) = target->nextNode;
if (NULL != (*head)) {
(*head)->prevNode = NULL;
}
}
else {
// temp = 타겟
Node* temp = target;
// temp의 앞과 temp의 뒤를 이어준다 (타겟의 앞과 뒤를 이어준다)
temp->prevNode->nextNode = temp->nextNode;
if (NULL != temp->nextNode) {
temp->nextNode->prevNode = temp->prevNode;
}
}
target->nextNode = NULL;
target->prevNode = NULL;
free(target);
}
노드 삽입
기준 노드(current) 뒤에 새 노드(newNode)를 삽입하는 것이므로 새 노드의 포인터만 주의하면 됩니다.
새 노드의 뒤 노드는 기준노드의 다음 노드를 가리킵니다.
새 노드의 앞 노드는 기준노드를 가리킵니다.
기준노드의 다음노드의 앞 포인터(current->nextNode->prevNode)와 기준노드의 뒷 포인터(current->nextNode)를 수정합니다.
void InsertAfter(Node* current, Node* newNode) {
newNode->prevNode = current;
newNode->nextNode = current->nextNode;
if (NULL != current->nextNode) {
current->nextNode->prevNode = newNode;
}
current->nextNode = newNode;
}
전체 코드 입니다.
#include <stdio.h>
#include <stdlib.h>
// 더블 링크드 리스트
/* 노드 선언 */
typedef struct Node {
struct Node* prevNode;
struct Node* nextNode;
int data;
};
/* 노드 생성 */
Node* CreateNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->prevNode = NULL;
newNode->nextNode = NULL;
return newNode;
}
/* [공통] 노드 탐색 */
Node* GetLocation(Node* head, int location) {
printf("[GetLocation]%d번째 노드를 찾아보자. \n", location);
Node* current = head;
while ((NULL != current) && (--location) >= 0) {
printf("location : %d 번째 탐색 \n", location);
current = current->nextNode;
}
return current;
}
/* [공통] 리스트 출력 */
void PrintList(Node* head) {
printf("[PrintList] 리스트 전체를 출력합니다. \n");
Node* tempNode = head;
int count = 0;
while (NULL != tempNode) {
printf("%5d", tempNode->data);
tempNode = tempNode->nextNode;
count++;
}
printf("\n");
printf("%5d개의 노드가 있습니다.\n", count);
}
/* 노드 추가. 테일 뒤에 새 노드를 덧붙인다 */
void AppendNode(Node** head, Node* newNode) {
printf("[AppendNode] 데이터 %2d 추가합니다. \n", newNode->data);
if (NULL == (*head)) { //헤드 노드가 없다면, 새 노드가 헤드 노드
(*head) = newNode;
}
else { // 테일 노드를 찾아서, 테일 뒤에 새 노드를 덧붙인다
Node* tail = (*head);
while (NULL != tail->nextNode) {
tail = tail->nextNode;
}
newNode->prevNode = tail;
tail->nextNode = newNode;
}
}
/* 노드 삭제 */
void RemoveNode(Node** head, Node* target) {
printf("[RemoveNode] %2d를 삭제합니다.\n", target->data);
if ((*head) == target) { // 헤드를 삭제하는 경우,
// 헤드를 변경
(*head) = target->nextNode;
if (NULL != (*head)) {
(*head)->prevNode = NULL;
}
}
else {
// temp = 타겟
Node* temp = target;
// temp의 앞과 temp의 뒤를 이어준다 (타겟의 앞과 뒤를 이어준다)
temp->prevNode->nextNode = temp->nextNode;
if (NULL != temp->nextNode) {
temp->nextNode->prevNode = temp->prevNode;
}
}
target->nextNode = NULL;
target->prevNode = NULL;
free(target);
}
/* 노드 삽입. 특정 노드 뒤에 새 노드를 삽입한다. */
void InsertAfter(Node* current, Node* newNode) {
printf("[InsertAfter] %2d를 %d 뒤에 삽입합니다.\n", newNode->data, current->data);
newNode->prevNode = current;
newNode->nextNode = current->nextNode;
if (NULL != current->nextNode) {
current->nextNode->prevNode = newNode;
}
current->nextNode = newNode;
}
int main() {
Node* list = NULL;
AppendNode(&list, CreateNode(10));
AppendNode(&list, CreateNode(20));
AppendNode(&list, CreateNode(30));
PrintList(list);
// 2번째 노드 위치 탐색(인덱스 1)
// 2번째 노드 삭제
RemoveNode(&list, GetLocation(list, 1));
PrintList(list);
// 헤드 뒤에 삽입
InsertAfter(list, CreateNode(40));
PrintList(list);
// 3번째 노드(인덱스 2) 뒤에 삽입
InsertAfter(GetLocation(list, 2), CreateNode(50));
PrintList(list);
return 0;
}
콘솔 화면 입니다.
다음 포스팅은 '환형 링크드 리스트' 입니다.
728x90
'알고리즘 > 알고리즘 C' 카테고리의 다른 글
| 순환 큐 (0) | 2020.03.09 |
|---|---|
| 링크드 리스트로 구현하는 스택 (0) | 2020.02.19 |
| 배열로 구현하는 스택 (0) | 2020.02.18 |
| 환형 링크드 리스트 (0) | 2020.02.17 |
| 링크드 리스트 (c로 구현한 추가 탐색 순회 삭제) (0) | 2020.02.12 |
