【数据结构】双向链表

Hi~！这里是奋斗的小羊，很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~~
💥💥个人主页：奋斗的小羊
💥💥所属专栏：C语言

🚀本系列文章为个人学习笔记，在这里撰写成文一为巩固知识，二为展示我的学习过程及理解。文笔、排版拙劣，望见谅。

目录

前言

单链表只能通过某个节点的地址单向的访问数据，而双向链表可以通过某个节点的地址双向的访问数据，增删查改的效率更高，但是代码的实现却比单链表简单，总的来说，双向链表优势更明显一些。

1、链表的分类

链表分为带头的、不带头的，单向的、双向的，循环的、不循环的组合起来一共八种，而我们只学习常见的不带头单向不循环链表和带头双向循环链表，也就是单链表和双向链表。
双向链表：

其实在上篇文章中我们将单链表的第一个节点称作头节点是不准确的，之所以这么称呼是为了好理解，因为单链表是不带头的，双向链表才有头结点，也称作哨兵位。

• 双向链表头节点内不存有效数据，存的是无效的数据。
• 哨兵位是不能改变的，只能改变其指向

2、双向链表的实现

2.1双向链表节点

双向链表的节点需要存数据，还要存前一个和后一个节点的地址，因此双向链表的节点为：

typedefint dlist_data_type;//双向链表节点typedefstructdlist{
    dlist_data_type data;structdlist* next
    structdlist* prev;}dlist;

2.2申请节点

不像单链表，双向链表最少得有一个节点，就是头节点，也叫哨兵位。
在增删查改之前，双向链表必须初始化一个哨兵位，哨兵位内存一个无效数据。

申请的节点初始时两个指针指向自己。

//申请节点
dlist*dlist_buy(dlist_data_type x){
    dlist* newdlist =(dlist*)malloc(sizeof(dlist));if(newdlist ==NULL){perror("malloc fail!");return1;}
    newdlist->data = x;
    newdlist->next = newdlist;
    newdlist->prev = newdlist;return newdlist;}

初始化哨兵位有以下两种方法：
以参数的形式返回：

voiddlist_init(dlist** pphead){assert(pphead);*pphead =dlist_buy(-1);}

这个方法要求使用二级指针。
以返回值的形式返回：

dlist*dlist_init(){
    dlist* phead =dlist_buy(-1);return phead;}

这个方法更加简单易理解。

2.3数据的打印和查找

数据的打印和查找跟单链表区别不大，就不再赘述了。
唯一需要注意的是结束循环的条件，当指针指向哨兵位时结束循环，而不是判

NULL

。

//打印数据voiddlist_print(dlist* phead){assert(phead);
    dlist* pcur = phead->next;while(pcur != phead){printf("%d->", pcur->data);
        pcur = pcur->next;}printf("NULL\n");}//查找
dlist*dlist_find(dlist* phead, dlist_data_type x){assert(phead);
    dlist* pcur = phead->next;while(pcur != phead){if(pcur->data == x){return pcur;}
        pcur = pcur->next;}returnNULL;}

2.4头插和尾插

与单链表不同的是，双向链表的增删查改操作不会改变哨兵位，因此只需要传值调用就可。
双向链表的插入操作需要对三个节点做修改，在修改的过程中，注意先修改新节点，再修改后一个节点，最后修改前一个节点。

//插入操作不改变哨兵位，因此传一级指针即可//尾插voiddlist_push_back(dlist* phead, dlist_data_type x){assert(phead);
    dlist* newdlist =dlist_buy(x);//新尾节点
    newdlist->prev = phead->prev;
    newdlist->next = phead;//旧尾节点
    phead->prev->next = newdlist;//头节点（哨兵位）
    phead->prev = newdlist;}//头插voiddlist_push_front(dlist* phead, dlist_data_type x){assert(phead);
    dlist* newdlist =dlist_buy(x);//新节点
    newdlist->prev = phead;
    newdlist->next = phead->next;//旧节点
    phead->next->prev = newdlist;//哨兵位
    phead->next = newdlist;}

2.5头删和尾删

删除操作的前提是不能没有节点（哨兵位不算），在删除前还是先保存节点的地址，将双向链表重新拼接起来后再释放节点。

//尾删voiddlist_pop_back(dlist* phead){assert(phead);assert(phead->next != phead);//双向链表不能为空
    dlist* del = phead->prev;//新尾节点
    del->prev->next = phead;//哨兵位
    phead->prev = del->prev;free(del);
    del =NULL;}//头删voiddlist_pop_front(dlist* phead){assert(phead);assert(phead->next != phead);
    dlist* del = phead->next;
    del->next->prev = phead;
    phead->next = del->next;free(del);
    del =NULL;}

2.6在指定位置插入、删除数据

//在指定位置之后插入数据voiddlist_insert_back(dlist* pos, dlist_data_type x){assert(pos);
    dlist* newdlist =dlist_buy(x);
    newdlist->prev = pos;
    newdlist->next = pos->next;

    pos->next->prev = newdlist;
    pos->next = newdlist;}//删除指定位置的节点voiddlist_erase(dlist* pos){assert(pos);
    dlist* del = pos;
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;free(pos);
    pos =NULL;}

删除指定位置的数据后，**因为这个函数我们用的是传值调用，在释放掉指定位置的节点后，只是把形参指针置

NULL

，而实参指针依旧指向这个位置，因此在函数调用结束后要给实参指针置

NULL

。**

2.7销毁双向链表

双向链表销毁的结束条件也是当遍历指针指向头节点时跳出循环，最后还要单独释放哨兵位，双向链表的销毁函数调用结束后，也要给指向哨兵位的指针置

NULL

。

//销毁voiddlist_destroy(dlist* phead){assert(phead);
    dlist* pcur = phead->next;while(pcur != phead){
        dlist* next = pcur->next;free(pcur);
        pcur = next;}free(pcur);
    pcur =NULL;}

3、双向链表完整代码

dlist.h:

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefint dlist_data_type;//双向链表节点typedefstructdlist{
    dlist_data_type data;structdlist* next;structdlist* prev;}dlist;//初始化//插入数据之前，双向链表必须初始化到只有一个头节点（哨兵位）//void dlist_init(dlist** pphead);//以参数的形式返回
dlist*dlist_init();//以返回值的形式返回//打印数据voiddlist_print(dlist* phead);//查找
dlist*dlist_find(dlist* phead, dlist_data_type x);//尾插voiddlist_push_back(dlist* phead, dlist_data_type x);//头插voiddlist_push_front(dlist* phead, dlist_data_type x);//尾删voiddlist_pop_back(dlist* phead);//头删voiddlist_pop_front(dlist* phead);//在指定位置之后插入数据voiddlist_insert_back(dlist* pos, dlist_data_type x);//删除指定位置的节点voiddlist_erase(dlist* pos);//销毁voiddlist_destroy(dlist* phead);

dlist.c:

#define_CRT_SECURE_NO_WARNINGS#include"dlist.h"//申请节点
dlist*dlist_buy(dlist_data_type x){
    dlist* newdlist =(dlist*)malloc(sizeof(dlist));if(newdlist ==NULL){perror("malloc fail!");return1;}
    newdlist->data = x;
    newdlist->next = newdlist;
    newdlist->prev = newdlist;return newdlist;}//初始化//void dlist_init(dlist** pphead)//{//    assert(pphead);//    *pphead = dlist_buy(-1);//}

dlist*dlist_init(){
    dlist* phead =dlist_buy(-1);return phead;}//打印数据voiddlist_print(dlist* phead){assert(phead);
    dlist* pcur = phead->next;while(pcur != phead){printf("%d->", pcur->data);
        pcur = pcur->next;}printf("NULL\n");}//查找
dlist*dlist_find(dlist* phead, dlist_data_type x){assert(phead);
    dlist* pcur = phead->next;while(pcur != phead){if(pcur->data == x){return pcur;}
        pcur = pcur->next;}returnNULL;}//插入操作不改变哨兵位，因此传一级指针即可//尾插voiddlist_push_back(dlist* phead, dlist_data_type x){assert(phead);
    dlist* newdlist =dlist_buy(x);//新尾节点
    newdlist->prev = phead->prev;
    newdlist->next = phead;//旧尾节点
    phead->prev->next = newdlist;//头节点（哨兵位）
    phead->prev = newdlist;}//头插voiddlist_push_front(dlist* phead, dlist_data_type x){assert(phead);
    dlist* newdlist =dlist_buy(x);//新节点
    newdlist->prev = phead;
    newdlist->next = phead->next;//旧节点
    phead->next->prev = newdlist;//哨兵位
    phead->next = newdlist;}//尾删voiddlist_pop_back(dlist* phead){assert(phead);assert(phead->next != phead);//双向链表不能为空
    dlist* del = phead->prev;//新尾节点
    del->prev->next = phead;//哨兵位
    phead->prev = del->prev;free(del);
    del =NULL;}//头删voiddlist_pop_front(dlist* phead){assert(phead);assert(phead->next != phead);
    dlist* del = phead->next;
    del->next->prev = phead;
    phead->next = del->next;free(del);
    del =NULL;}//在指定位置之后插入数据voiddlist_insert_back(dlist* pos, dlist_data_type x){assert(pos);
    dlist* newdlist =dlist_buy(x);
    newdlist->prev = pos;
    newdlist->next = pos->next;

    pos->next->prev = newdlist;
    pos->next = newdlist;}//删除指定位置的节点voiddlist_erase(dlist* pos){assert(pos);
    dlist* del = pos;
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;free(pos);
    pos =NULL;}//销毁voiddlist_destroy(dlist* phead){assert(phead);
    dlist* pcur = phead->next;while(pcur != phead){
        dlist* next = pcur->next;free(pcur);
        pcur = next;}free(pcur);
    pcur =NULL;}

test.c:

#define_CRT_SECURE_NO_WARNINGS#include"dlist.h"voidtest(){//dlist* plist = NULL;//dlist_init(&plist);

    dlist* plist =dlist_init();//尾插dlist_push_back(plist,1);dlist_push_back(plist,2);dlist_push_back(plist,3);dlist_print(plist);//头插//dlist_push_front(plist, 1);//dlist_push_front(plist, 2);//dlist_push_front(plist, 3);//dlist_print(plist);//尾删//dlist_pop_back(plist);//dlist_pop_back(plist);//dlist_pop_back(plist);//dlist_print(plist);//头删//dlist_pop_front(plist);//dlist_print(plist);//dlist_pop_front(plist);//dlist_print(plist);//dlist_pop_front(plist);//dlist_print(plist);//dlist* find = dlist_find(plist, 2);//dlist_insert_back(find, 4);//dlist_print(plist);//dlist* find = dlist_find(plist, 2);//dlist_erase(find);//find = NULL;//dlist_print(plist);dlist_destroy(plist);
    plist =NULL;//手动置空}intmain(){test();return0;}

4、顺序表和链表比较

顺序表链表（双向链表）存储空间上逻辑、物理上都连续逻辑上连续、物理上不一定连续随机访问复杂度O(1)复杂度O(N)任意位置插入或删除数据需要挪动数据，复杂度O(N)只需要改变指针指向插入动态顺序表，空间不够时扩容，扩容本身就有消耗，还容易空间浪费没有容量的概念应用场景数据高效存储+频繁访问任意位置频繁插入、删除数据缓存利用率高低
顺序表和链表优势互补，在不同的应用场景下能发挥各自的优势。

总结

• 如果应用场景中需要频繁进行查找和删除操作，并且能够接受更多的内存消耗，双向链表可能更加合适。
• 如果内存比较有限或者对查找和删除操作的效率要求不高，单链表可能更适合.