双向链表的插入和删除

双向链表基于单链表。单链表是单向的，有一个头结点，一个尾结点，要访问任何结点，都必须知道头结点，不能逆着进行。而双链表添加了一个指针域，通过两个指针域，分别指向结点的前结点和后结点。这样的话，可以通过双链表的任何结点，访问到它的前结点和后结点。

在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点的地址，一般称为右链域；一个存储直接前驱结点地址，一般称之为左链域。
双向链表的插入

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

创建一个双向链表首先创建一个头结点，方便进行插入。不用头节点也可以。不过不易插入。

双向链表的插入。

双向链表的插入。如果是第一个节点。让头结点的next指向新节点，新节点的前驱指向头节点。让新结点的后继为空。

如果插入的不是第一个节点：让新节点的后继指向前节点的后继。旧节点的下一节点的前驱指向新节点。新节点的前驱指向上一节点。上一节点的后继指向新节点。

#include <stdio.h>
#include <stdlib.h>
 
typedef struct DuLnode
{
    int data;
    struct DuLnode *next, *prior;
}DuLnode, *DuLLinklist;
 
DuLLinklist CreateDuLlist(DuLLinklist L, int n)
{
    //创建头节点
    L->next = NULL;
    L->prior = NULL;
    //头插法创建双向链表
    //头插法，插入的第一个节点和后续要插入的节点的方式有所不同
    //插入第一个节点不需要考虑后继节点
    //第二个节点开始要考虑后继节点的前驱指针
    for(int i = 0; i < n; i++)
    {
        DuLLinklist newNode = (DuLLinklist)malloc(sizeof(DuLnode));
        printf("请输入要插入的节点值：");
        scanf("%d", &newNode->data);
        if(L->next == NULL)//插入第一个节点时
        {
            L->next = newNode;//头节点的next域指向新插入的节点
            newNode->prior = L;//新插入节点的prior域指向头节点
            newNode->next = NULL;//新插入节点的next赋空
        }
        else//插入后续节点
        {
            newNode->next = L->next;//将上一个插入的节点连接到新插入的节点的next域
            L->next->prior = newNode;//将上一个插入的节点的前驱prior域指向新插入的节点
            newNode->prior = L;//新插入节点的前驱域指向头节点
            L->next = newNode;//头节点的next域指向新插入的节点
        }
    }
}
 
void Printlist(DuLLinklist L, int n)
{
    DuLLinklist temp = L->next;
    printf("链表为：");
    for(int i = 0; i < n; i++)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
}
 
DuLLinklist Listdelete(DuLLinklist L, int i)
{
    //DuLLinklist s = (DuLLinklist)malloc(sizeof(DuLnode));
    DuLLinklist temp = (DuLLinklist)malloc(sizeof(DuLnode));
    temp = L->next;
    int cnt = 1;
    while(cnt != i)//找到第i个要删除的节点
    {
        temp = temp->next;
        cnt++;
    }
    if(temp->next != NULL)
    {
        int e = temp->data;//保留要删除节点的数据
        temp->prior->next = temp->next;//该删除节点的前驱节点的next域连接到该删除节点的后继节点
        temp->next->prior = temp->prior;//该删除节点的后继节点的prior域连接到该删除节点的前驱节点
        free(temp);
    }
    else//如果删除的是最后一个节点
    {
        temp->prior->next = NULL;
        free(temp);
    }
}
int main()
{
    DuLLinklist L = (DuLLinklist)malloc(sizeof(DuLnode));
    int n, i;
    printf("请输入要创建多少个节点：");
    scanf("%d", &n);
    CreateDuLlist(L, n);
    printf("链表为：");
    Printlist(L, n);
    printf("输入要删除的节点：");
    scanf("%d", &i);
    Listdelete(L, i);
    Printlist(L, n);
    return 0;
}

链表的删除：首先用while循环或者for循环找到要删除的节点。然后申请一个节点。让申请的节点到处于删除位置，就是删除节点。然后让所需删除节点的前一结点的后继指向所需删除的节点的后一节点。再让后一节点的前驱找到删除节点的前一节点。并释放删除结点。

如果是最后一个节点直接free就可以了。