C언어] 이중 연결 리스트

[이중 연결 리스트]

1. 이중 연결 리스트 란?
각 노드가 이전 노드오 ㅏ다음 노드를 가리키는 링크를 가지고 있는 자료 구조.

각 노드는 데이터를 저장하는 부분과 두 개의 링크를 가지고 있다.

 

기본적으로 연결 리스트는 각 노드가 다음 노드만 가리키는 단일 연결 리스트와는 달리, 이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 모두 가리키기 때문에 양방향으로 탐색할 수 있다.

 

| Prev  | Data  | Next  |

구성으로 

Prev: 이전 노드(앞쪽 노드)를 가리키는 포인터(링크)
Data: 노드가 저장하는 데이터
Next: 다음 노드(뒤쪽 노드)를 가리키는 포인터(링크)

 

// 이중 연결 리스트
 
#include <stdio.h>
#include <stdlib.h>
 
//& 이중 연결 리스트의 노드를 나타내는 구조체
struct Node 
{
    int data;
    struct Node* prev;
    struct Node* next;
};
 
//& 이중 연결 리스트에 노드를 추가하는 함수
void insertNode(struct Node** head, int newData)
{
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->prev = NULL;
    newNode->next = *head;
 
    if (*head != NULL)
    {
        (*head)->prev = newNode;
    }
 
    *head = newNode;
}
 
//& 이중 연결 리스트를 출력하는 함수
void printList(struct Node* node)
{
    while (node != NULL)
    {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}
 
int main() 
{
    struct Node* head = NULL;
 
    //& 노드 추가
    insertNode(&head, 3);
    insertNode(&head, 6);
    insertNode(&head, 9);
    insertNode(&head, 12);
    insertNode(&head, 15);
 
    //& 연결 리스트 출력
    printf("이중 연결 리스트: ");
    printList(head);
 
    return 0;
}// main
/*
* | NULL |  3   | next | --> NULL
* | NULL |  6   | next | --> 3
* | NULL |  9   | next | --> 6
* | NULL | 12   | next | --> 9
* | NULL | 15   | next | --> 12
*/