양방향 연결 리스트

양방향 연결 리스트는 머리(Head)와 꼬리(Tail)를 모두 가진다는 특징이 있습니다

각 노드는 앞 노드와 뒤 노드의 정보를 모두 저장하고 있습니다

prev		next	prev		next	prev		next
Head			일반 노드			Tail

 

양방향 연결 리스트 선언

#include <stdio.h>
#include <stdlib.h>
 
typedef struct {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;
 
Node *head, *tail;
 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
 
typedef struct {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;
 
Node *head, *tail;
 
void insert(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    Node* cur;
    cur = head->next;
    while (cur->data < data && cur != tail) {
        cur = cur->next;
    }
    Node* prev = cur->prev;
    prev->next = node;
    node->prev = prev;
    cur->prev = node;
    node->next = cur;
}
 
void removeFront() {
    Node* node = head->next;
    head->next = node->next;
    Node* next = node->next;
    next->prev = head;
    free(node);
}
 
void show() {
    Node* cur = head->next;
    while (cur != tail) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
}
 
int main (void){
    head = (Node*)malloc(sizeof(Node));
    tail = (Node*)malloc(sizeof(Node));
    head->next = tail;
    head->prev = head;
    tail->next = tail;
    tail->prev = head;
    insert(2);
    insert(1);
    insert(3);
    insert(9);
    insert(7);
    removeFront();
    show();
    return 0;
}