双向链表(结构体+指针)

首先当然得了解单向链表了

传送门

首先，表中的各个元素称作“结点”。双向链表的结点时结构体，有数据本体，指向前一元素的指针prev以及指向后一元素的指针next组成。这些结构体通过指针构成一个链表，就形成了双向链表。

struct node{
    int key;
    node *prev,*next;//注意不是node *prev,next
};

另外，在表头设置一个特殊节点可以简化链表的实现，将这个结点称为“头节点”，头节点中不包括实际数据，但它可以让我们更轻松地对链表做更改。

init函数用于初始化链表。它会生成一个NIL节点作为链表的头节点，然后让prev和next都指向这个头节点，从而创建一个空表。

node *nil;
void init()
{
    nil=(node*)malloc(sizeof(node));
    nil->next=nil;
    nil->prev=nil;
}

然后就是很重要的插入元素。

void insert(int key)
{
    node *x=(node*)malloc(sizeof(node));
    x->key=key;
    x->next=nil->next;
    nil->next->prev=x;
    nil->next=x;
    x->prev=nil;
}

listsearch函数用于搜索元素，它可以在链表中寻找包含指定键值的结点，并返回其指针，假设cur为指向当前位置结点的指针，那么只要从头节点的next所指的结点，即链表开头的元素逐个进行cur=cur->next，即可逐一访问每个结点。

node* listsearch(int key)
{
    node *cur=nil->next;
    while(cur!=nil&&cur->key!=key){
        cur=cur->next;
    }
    return cur;
}

deletenode函数删除指定结点t。

void deletenode(node *t)
{
    if(t==nil){
        return ;
    }
    t->prev->next=t->next;//修改前面的指向
    t->next->prev=t->prev;//修改后面的指向
    free(t);
}

void deletefirst()
{
    
    deletefirst(nil->next);
}

void deletelast()
{
    deletenode(nil->prev);
}

void deletekey(int key)
{
    deletekey(listsearch(key));
}

deletelastfirst函数，deletelast函数分别用于删除头节点next，prev所指向的结点，deletekey函数可以删除包含指定key的结点，它可以先通过listsearch函数搜索出与key一致的结点t，然后再使用deletenode(t)删除该节点。

整体运用一下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>

using namespace std;

struct node{
    int key;
    node *prev,*next;
};

node *nil;
void init()
{
    nil=(node*)malloc(sizeof(node));
    nil->next=nil;
    nil->prev=nil;
}

void insert(int key)
{
    node *x=(node*)malloc(sizeof(node));
    x->key=key;
    x->next=nil->next;
    nil->next->prev=x;
    nil->next=x;
    x->prev=nil;
}

void deleteNode(node*t)
{
    if(t==nil){
        return ;
    }
    t->prev->next=t->next;
    t->next->prev=t->prev;
    free(t);
}

void deleteFirst()
{
    deleteNode(nil->next);
}

void deleteLast()
{
    deleteNode(nil->prev);
}

node* listSearch(int key)
{
    node *cur=nil->next;
    while(cur!=nil&&cur->key!=key){
        cur=cur->next;
    }
    return cur;
}

void deleteKey(int key)
{
    deleteNode(listSearch(key));
}

void printList()
{
    node*cur=nil->next;
    int isf=0;
    while(1){
        if(cur==nil){
            break;
        }
        if(isf++>0){
            printf(" ");
        }
        printf("%d",cur->key);
        cur=cur->next;
    }
    printf("\n");
}

int main()
{
    int n,key;
    char com[20];
    scanf("%d",&n);
    init();
    for(int i=0;i<n;i++){
        scanf("%s%d",com,&key);
        if(com[0]=='i'){
            insert(key);
        }else if(com[0]=='d'){
            if(strlen(com)>=6){
                if(com[6]=='F'){
                    deleteFirst();
                }else if(com[6]=='L'){
                    deleteLast();
                }else{
                    deleteKey(key);
                }
            }
        }
    }
    printList();
    return 0;
}
/*
7
insert 5
insert 2
insert 3
insert 1
delete 3
insert 6
delete 5
*/