双向链表

// 双向线性链表

#include <iostream>
using namespace std;
typedef struct node
{
    int data;
    struct node * front;
    struct node *next;
}NODE;
typedef struct doublelist
{
    NODE* head;
    NODE* tail;
}LIST;
LIST* create_list()
{
    LIST* list = new LIST;
    list->head = NULL;
    list->tail = NULL;
    return list;
}
NODE* create_node(int data)
{
    NODE* node = new NODE;
    node->data = data;
    node->front = NULL;
    node->next = NULL;
    return node;
}
void list_append(LIST* list, int data)
{
    NODE* node = create_node(data);
    if(list->tail == NULL)
    {
        list->head = node;
        list->tail = node;
    }
    else
    {
        list->tail->next = node;
        node->front = list->tail;
        list->tail = node;
    }
}
void front_print(LIST* list)
{
    NODE* node = NULL;
    for(node=list->head;node;node=node->next)
    {
        cout<<node->data<<" ";
    }
    cout<<endl;
}


void reverse_print(LIST* list)
{
    NODE* node = NULL;
    for(node =list->tail;node;node=node->front)
    {
        cout<<node->data<<" ";
    }
    cout<<endl;
}
NODE* destroy_node(NODE* node)
{
    NODE* next = node->next;
    delete node;
    return next;
}
void clear(LIST* list)
{
    while(list->head)
    {
        list->head = destroy_node(list->head);
    }
    list->tail = NULL;
}
void destroy_list(LIST* list)
{
    clear(list);
    delete list;
}
void list_insertAfter(LIST* list, int data,int pos) //后插 最起码应该第一个后面
{
    NODE* find = NULL;
    for(find =list->head;find;find=find->next)
    {
        if(!--pos)
        {
            NODE* node =create_node(data);
            if(find->next == NULL)
            {
                node->front =list->tail;
                list->tail->next = node; list->tail = node;
            }
            else
            {
                node->front = find;
                node->next = find->next;
                find->next->front =node;
                find->next = node;
            }
        }
    }
}
void list_delete(LIST* list, int data)
{
    NODE* Front = NULL;
    NODE* node = list->head;
    while(node)
    {
        if(data == node->data)
        {
            if(list->head ==node)
            {
                list->head = node->next;
                node->next->front = NULL;
                delete node;
                node = list->head;
            }
            else
            {
                Front->next = node->next;
                if(node->next != NULL)
                {
                    node->next->front = Front;
                    delete node;
                    node = Front->next;
                }
                else
                {
                    list->tail = node->front;
                    delete node;
                }
            }
        }
        else
        {
            Front = node;
            node = node->next;
        }
    }
}
void list_insertFront(LIST* list,int data,int pos)
{
    //NODE* front = NULL;
    NODE* find = NULL;
    for(find=list->head;find;find=find->next)
    {
        if(!--pos)
        {
            NODE* node = create_node(data);
            if(find==list->head)
            {
                node->next = list->head;
                list->head->front = node;
                list->head = node;
            }
            else
            {
                node->next = find;
                node->front = find->front;
                find->front->next = node;
                find->front = node;
            }
        }
    }
}
int main()
{
    LIST* list = create_list();
    for(int i=10;i<=50;i+=10)
    {
        list_append(list, i);
    }
    //    list_insertAfter(list,55,5);
    //    list_insertAfter(list,15,1);
    list_insertFront(list,15,2);
    list_insertFront(list,50,6);
     list_insertAfter(list,10,7);
    front_print(list);
    list_delete(list,10);
    front_print(list);
    reverse_print(list);
    destroy_list(list);
    return 0;
}