Linked List 2 - Doubly Linked List

하나의 노드에 자신의 앞에 있는 포인트와 그 자신의 뒤에 있는 노드의 포인트를 연결시킨 구조로 여러 노드들이 포인터로 연결된 연결 리스트 구조, 이것은 리드를 전방 혹은 후방의 양방향으로 탐색이 가능하고 노드의 삽입이나 삭제가 쉽다는 장점을 갖는다.

#include <stdio.h>
#include <malloc.h>

typedef struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
} Node;

Node *head, *tail;

void insertNode(int data)
{
    Node* node = head;

    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;

    while (node->next != tail) {
        node = node->next;
    }

    newNode->next = node->next;
    newNode->prev = node;
    node->next->prev = newNode;
    node->next = newNode;
}

void deleteNode(int key)
{
    Node* curNode = head->next;
    Node* prevNode = head;

    while ((curNode->data != key) && (curNode != tail)) {
        curNode = curNode->next;
    }

    if (curNode != tail) {
        curNode->prev->next = curNode->next;
        curNode->next->prev = curNode->prev;
        free(curNode);
    }
}

Node* findNode(int key) {
    Node* node;
    node = head->next;

    while ((node->data != key) && (node != tail)) {
        node = node->next;
    }

    return node;
}

void printList() {
    Node* node = head->next;

    printf("LinkedList :");
    while (node != tail) {
        printf(" %d", node->data);
        node = node->next;
    }
    printf("\n");
}

void clear() {
    Node* node = head;
    Node* delNode;
    while (node != NULL) {
        delNode = node;
        node = node->next;
        free(delNode);
    }
}

int main()
{
    head = (Node*)malloc(sizeof(Node));
    tail = (Node*)malloc(sizeof(Node));

    head->next = tail;
    head->prev = NULL;
    tail->prev = head;
    tail->next = NULL;

    insertNode(5);
    insertNode(3);
    insertNode(1);
    insertNode(4);
    insertNode(2);

    printList();

    printf("findNode() - %d\n", findNode(1)->data);

    deleteNode(4);

    printList();

    clear();

    return 0;
}

* 출처 : https://www.tutorialspoint.com/data_structures_algorithms/