[자료구조] 연결리스트 - (3)이중 연결 리스트

#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct DListNode
{
    element data;
    struct DListNode* prev;
    struct DListNode* next;
}DListNode;

typedef struct DListType
{
    DListNode* head;
    DListNode* tail;
    int size;
}DListType;

void init(DListType* DL)
{
    DL->head = NULL;
    DL->tail = NULL;
    DL->size = 0;
}

int isEmpty(DListType* DL)
{
    return DL->size == 0;
}

void insertFirst(DListType* DL, element e)
{
    DListNode* node = (DListNode*)malloc(sizeof(DListNode));
    node->data = e;
    node->prev = NULL;
    DListNode* p = DL->head;
    node->next = p;
    if(isEmpty(DL))
        DL->head = DL->tail = node;
    else
    {
        DL->head = node;
        p->prev = node;
    }
    DL->size++;
}

void insertLast(DListType* DL, element e)
{
    DListNode* node = (DListNode*)malloc(sizeof(DListNode));
    node->data = e;
    node->next = NULL;
    DListNode* q = DL->tail;
    node->prev = q;
    if(isEmpty(DL))
        DL->head = DL->tail = node;
    else
    {
        DL->tail = node;
        q->next = node;
    }
    DL->size++;
}

void insert(DListType* DL, int pos, element e)
{
    DListNode* node = (DListNode*)malloc(sizeof(DListNode));
    DListNode* p = DL->head;
    if(pos == 1)
        insertFirst(DL, e);
    else if(pos == DL->size+1)
        insertLast(DL, e);
    else 
    {
        node->data = e;
        for(int i=1;i<pos;i++)
            p=p->next;
        node->next = p;
        node->prev = p->prev;
        p->prev->next=node;
        p->prev=node;
        DL->size++;
    }
}

element deleteFirst(DListType* DL)
{
    DListNode* p = DL->head;
    element e = p -> data;
    if(isEmpty(DL))
    {
        printf("underflow!\n");
        return -1;
    }
    if(DL->head == DL->tail)
    {
        DL->tail = DL->head = NULL;
    }
    else
    {
        DL->head = p->next;
    }
    DL->size--;
    return e;
}

element deleteLast(DListType* DL)
{
    DListNode* p = DL->tail;
    element e = p -> data;
    if(isEmpty(DL))
    {
        printf("underflow!\n");
        return -1;
    }
    if(DL->head == DL->tail)
    {
        DL->tail = DL->head = NULL;
    }
    else
    {
        DL->tail = p->prev;
    }
    DL->size--;
    return e;
}

element delete(DListType* DL, int pos)
{
    DListNode* p = DL->head;
    if(isEmpty(DL))
    {
        printf("underflow!\n");
        return -1;
    }
    if(pos == 1)
        deleteFirst(DL);
    else if(pos == DL->size)
        deleteLast(DL);
    else
    {
        for(int i=1;i<pos;i++)
            p=p->next;
        element e = p->data;
        p->prev->next =p->next;
        p->next->prev=p->prev;
        DL->size--;
        return e;
    }
}
void print(DListType* DL)
{
    DListNode* p = DL->head;
    for(int i=1;i<=DL->size;i++)
    {
        printf("[%d] => ", p->data);
        p=p->next;
    }
    printf("\b\b\b  \n");
}

int main()
{   DListType DL;
    init(&DL);
    
    insertFirst(&DL, 10); print(&DL);
    insertFirst(&DL, 20); print(&DL);    
    insertLast(&DL, 30); print(&DL);   
    insertLast(&DL, 40); print(&DL);
    insert(&DL, 5, 50); print(&DL);
    insert(&DL, 1, 60); print(&DL);
    insert(&DL, 3, 70); print(&DL);
    
    printf("[%d] is deleted! ", deleteFirst(&DL)); print(&DL);
    printf("[%d] is deleted! ", deleteLast(&DL)); print(&DL);
    printf("[%d] is deleted! ", delete(&DL, 3)); print(&DL);
    return 0;
}