结构体

typedef int datatype;
typedef struct node_t
{
    datatype data;
    struct node_t *next;
    struct node_t *prior;
}link_node_t,*link_list_t;
typedef struct doublelinklist
{
    link_list_t head;
    link_list_t tail;
    int len;
}double_node_t,*double_list_t;

和单向链表不同的是，双向链表得结构体多了一个指针域成员，这个成员指向前一个节点，另外，还结合了链式队列得思想，将头指针、尾指针和链表长度封装在一个单独得结构体里。

创建空双向链表

double_list_t createEmptyDoubleLinkList()
{
    double_node_t *p = (double_node_t *)malloc(sizeof(double_node_t));
    if (p == NULL)
    {
        perror("p malloc error");
        return NULL;
    }
    p->len = 0;
    p->head = p->tail = (link_node_t *)malloc(sizeof(link_node_t));
    if (p->head == NULL)
    {
        perror("p->head&p->tail malloc error");
        return NULL;
    }
    p->head->next = NULL;
    p->head->prior = NULL;
    return p;
}

1.开辟指针结构体类型大小的空间
2.p->len初始化为0，头指针和尾指针初始化指向新开辟的双向链表结构体大小的空间（头节点）
3.初始化头节点的next域和prio域为NULL
4.返回指针结构体首地址

指定位置插入

int insertIntoDoubleLinkList(double_list_t p, int post, datatype data)
{
    if (post < 0 || post > p->len)
    {
        perror("pose error");
        return -1;
    }
    link_node_t *pnew = (link_list_t)malloc(sizeof(link_node_t));
    if (pnew == NULL)
    {
        perror("pnew malloc error");
        return -1;
    }
    pnew->data = data;
    pnew->next = NULL;
    pnew->prior = NULL;
    link_node_t *temp = NULL;
    if (post == p->len)
    {
        p->tail->next = pnew;
        pnew->prior = p->tail;
        p->tail = pnew;
    }
    else
    {
        if (post < p->len / 2)
        {
            temp = p->head;
            for (int i = 0; i < post + 1; i++)
                temp = temp->next;
        }
        else
        {
            temp = p->tail;
            for (int i = 0; i < p->len - post - 1; i++)
                temp = temp->prior;
        }
        pnew->prior = temp->prior;
        temp->prior->next = pnew;
        pnew->next = temp;
        temp->prior = pnew;
    }
    p->len++;
    return 0;
}

1.容错判断
2.开辟新节点并初始化
3.判断插入位置是在尾插还是在中间插
4.中间插时，插入位置在前半段遍历头指针到插入位置，后半段反之
5.中间插时，先连接前面的节点，后连接后面的节点，最后长度+1

遍历双向链表

void showDoubleLinkList(double_list_t p)
{
    printf("正向遍历\n");
    link_list_t temp = p->head;
    while (temp->next != NULL)
    {
        temp = temp->next;
        printf("%d ", temp->data);
    }
    printf("\n");
    printf("反向遍历\n");
    temp = p->tail;
    while (temp != p->head)
    {
        printf("%d ", temp->data);
        temp = temp->prior;
    }
    printf("\n");
}

正向遍历相当于遍历有头链表，反向遍历相当于遍历无头链表（停止条件是尾指针和头指针相等时）

删除指定位置的数据

int deletePostDoubleLinkList(double_list_t p, int post)
{
    link_list_t temp = NULL;
    if (post < 0 || post >= p->len || isEmptyDoubleLinkList(p))
    {
        perror("empty");
        return -1;
    }
    if (post == p->len - 1)
    {
        p->tail = p->tail->prior;
        free(p->tail->next);
        p->tail->next = NULL;
    }
    else
    {
        if (post < p->len / 2)
        {
            temp = p->head;
            for (int i = 0; i < post + 1; i++)
                temp = temp->next;
        }
        else
        {
            temp = p->tail;
            for (int i = 0; i < p->len - 1 - post; i++)
                temp = temp->prior;
        }

        temp->prior->next = temp->next;
        temp->next->prior = temp->prior;
        free(temp);
    }
    p->len--;
    return 0;
}

1.容错判断
2.判断删除位置是尾删还是在中间删
3.中间删时，删除位置在前半段遍历头指针到删除位置，后半段反之
4.跨过删除位置，释放删除的节点
5.长度-1

删除指定的数据

int deleteDataDoubleLinkList(double_list_t p, datatype data)
{
    link_list_t pdel = NULL;
    link_list_t temp = p->head->next;
    while (temp != NULL)
    {
        if (temp->data == data)
        {
            if (temp == p->tail)
            {
                p->tail = p->tail->prior;
                free(p->tail->next);
                p->tail->next = NULL;
            }
            else
            {
                temp->prior->next = temp->next;
                temp->next->prior = temp->prior;
                pdel = temp;
                temp = temp->next;
                free(pdel);
                pdel = NULL;
            }
            p->len--;
        }
        else
            temp = temp->next;
    }
    return 0;
}

1.定义结构体指针类型的临时变量指向头节点的下一个节点，遍历所有节点
2.如果遇到数据和需要删除的数据相同时，判断是尾删还是中间删
3.删除一次结束长度-1
4.临时变量temp向下一位移动一位
中间删时，要注意temp是用来遍历链表的，不能直接free，要再定义一个临时变量pdel来保存一下需要删除的节点，以免链表丢失

查找指定数据出现的位置

int searchPostDoubleLinkList(double_list_t p, datatype data)
{
    int post = 0;
    link_list_t temp = p->head->next;
    while (temp != NULL)
    {
        if (temp->data == data)
        {
            return post;
        }
        temp = temp->next;
        post++;
    }
    printf("not find\n");
    return -1;
}

1.定义一个临时变量temp代替头指针遍历链表
2.判断当时节点的数据域是否和指定数据相等
3.相等返回当前节点位置
4.不相等指针向后移动且位置+1

修改指定位置的数据

int changeDataDoubleLinkList(double_list_t p, int post, datatype data)
{
    if (post < 0 || post >= p->len || isEmptyDoubleLinkList(p))
    {
        perror("post error");
        return -1;
    }
    link_list_t temp = NULL;
    if (post < p->len / 2)
    {
        temp = p->head;
        for (int i = 0; i < post + 1; i++)
            temp = temp->next;
    }
    else
    {
        temp = p->tail;
        for (int i = 0; i < p->len - post - 1; i++)
            temp = temp->prior;
    }
    temp->data = data;
    return 0;
}

1.容错判断
2.定义一个临时变量来代替头/尾指针移动
3.判断修改位置在前半段还是后半段，在前半段移动头指针，在后半段移动尾指针
4.移动到指定位置并修改数据