[数据结构]我滴双链表完成辣，Ура

这个是一个标题哦

在淦了四篇刷题笔记之后，菜鸡大学生想起她之前在单链表挖的坑还没填。遂，填。有一说一菜鸡大学生的坑品还是可以的。下一篇是动图教程哦，所以…（暗示） 开搞！

双链表

（今天的攻略对象）

和上次的单链表相比，今天要写的双链表有以下不同：

1. 带哨兵位的头结点。
2. 双向的，每个节点不仅可以指向下一个，还可以指向上一个。
3. 循环链表，最后一个节点指向第一个节点。

那么，开始准备吧

双链表的本体

加上一个前驱的指针，欸嘿嘿。

typedefint ListDataType;typedefstructListNode{structListNode* prev;//*structListNode* next;
    ListDataType data;}ListNode;

初始化

在初始化的时候我们就要带上我们的哨兵位了。
我们先生成一个节点，里面的数据置为0 (数据多少都无所谓，反正都不会用上) 然后将节点的前指针和后指针统统指向自己。
这样，一个循环链表的雏形就出来了。

//初始化
ListNode*ListInit(){
    ListNode* phead=BuyListNode(0);
    phead->next = phead;
    phead->prev= phead;return phead;}

得到一个节点

没啥，就多了一个前指针。
随便写写就好。

//得到一个节点
ListNode*BuyListNode(ListDataType x){
    ListNode* newnode =(ListNode*)malloc(sizeof(ListNode));
    newnode->data = x;
    newnode->next =NULL;
    newnode->prev =NULL;return newnode;}

打印链表

同上，注意结束条件变成了

cur!=phead

，因为是循环链表嘛。

//打印voidListPrint(ListNode* phead){assert(phead);

    ListNode* cur = phead->next;while(cur!=phead){printf("%d ", cur->data);
        cur = cur->next;}printf("\n");}

销毁链表

整一个cur指针，从头的下一个节点开始删，直到下一个节点是头，然后把头和cur一起删掉。

我决定画个图玩玩。

//销毁voidListDestory(ListNode* phead){assert(phead);

    ListNode* cur = phead->next;
    ListNode* next = phead->next;while(next!=phead){free(cur);
        cur = next;
        next = next->next;}free(cur);free(phead);}

经典的增删查改

插入操作

头插

双链表由于结构的优越性，增删查改变得嘎嘎简单，只要我们能找到要插入的节点两侧的节点，然后就是无脑操作。

所以我们就大致画画图，放个代码就好了😀。

1. 首先创建新节点
2. 接着我们将phead和first与新节点链接。
3. 然后就结束了。

好耶！

//头插voidListPushFront(ListNode* phead, ListDataType x){assert(phead);
    ListNode* newnode =BuyListNode(x);
    ListNode* first = phead->next;
    
    phead->next = newnode;
    newnode->next = first;
    newnode->prev = phead;
    first->prev = newnode;}

尾插

同理。
我连图都懒得画。

//尾插voidListPushBack(ListNode* phead, ListDataType x){assert(phead);
    ListNode* newnode =BuyListNode(x);
    ListNode* tail = phead->prev;

    phead->prev = newnode;
    newnode->next = phead;
    newnode->prev = tail;
    tail->next = newnode;}

指定位置前插入

…（暗示）

//某个位置前插入数据voidListInsert(ListNode* pos, ListDataType x){
    ListNode* newnode =BuyListNode(x);
    ListNode* prev = pos->prev;

    prev->next = newnode;
    newnode->prev = prev;
    newnode->next = pos;
    pos->prev = newnode;}

遇到困难偷大懒

有了指定位置插入我们可以偷头插和尾插的懒了。

• 尾插就是在phead的前面插入数据。
• 头插就是在phead的下一位前面插入数据。

所以：

voidListPushFront(LTNode* phead, LTDataType x){assert(phead);ListInsert(phead->next, x);}voidListPushBack(LTNode* phead, LTDataType x){assert(phead);ListInsert(phead, x);}

删除操作

似乎更加简单了？但是要检查链表是不是为空即

phead->next!=phead

.

//头删voidListPopFront(ListNode* phead){assert(phead);assert(phead->next!=phead);

    ListNode* first = phead->next;
    phead->next = first->next;
    first->next->prev = phead;free(first);}//尾删voidListPopBack(ListNode* phead){assert(phead);assert(phead->next != phead);
    
    ListNode* tail = phead->prev;
    phead->prev = tail->prev;
    tail->prev->next = phead;free(tail);}//删除某个位置数据voidListErase(ListNode* phead, ListNode* pos){assert(phead);assert(phead->next != phead);//稍微考虑一下phead吧，不考虑也行

    ListNode* prev = pos->prev;
    ListNode* next = pos->next;
    prev->next = next;
    next->prev = prev;free(pos);}

简单偷个懒吧！

这里使用的是不带phead玩的版本。

//尾删voidListPopBack(LTNode* phead){assert(phead);assert(phead->next != phead);ListErase(phead->prev);}//头删voidListPopFront(LTNode* phead){assert(phead);assert(phead->next != phead);ListErase(phead->next);}

查询和修改

很简单哦，只要遍历就可以了。

//查某个值，返回地址
ListNode*ListFind(ListNode* phead, ListDataType x){
    ListNode* cur = phead->next;while(cur != phead){if(cur->data == x){return cur;}
        cur = cur->next;}returnNULL;}//改某个值voidListChange(ListNode* phead, ListDataType sourse, ListDataType destination){assert(phead);
    
    ListNode* pos=ListFind(phead, sourse);
    pos->data = destination;}

最后

感觉这一篇好水哦（笑）

看在下一篇是动图教程的份上，捧个小场不过分吧😀。