数据结构：双向链表

文章目录

1. 双向带头循环链表的结构

与单链表不同的是：

• 双向链表有一个“哨兵位”作为单独的头节点
• 每个节点都可以指向其前驱和后继节点
• 链表是循环的

带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨的”
“哨兵位”存在的意义：遍历循环链表避免死循环。

typedefint ListDataType;typedefstructList{
    ListDataType data;structList* prev;//指向前驱节点structList* next;//指向后继节点}List;

2. 相关操作

2.1 创建节点

• 创建的每个节点应该自己成环

List*BuyNode(ListDataType x){
    List* newnode =(List*)malloc(sizeof(List));if(newnode ==NULL){perror(malloc);returnNULL;}
    newnode->data = x;
    newnode->next = newnode;
    newnode->prev = newnode;}

创建哨兵位：

intmain(){//哨兵位
    List* head =BuyNode(-1);return0;}

2.2 尾插

voidListPushBack(List* phead, ListDataType x){assert(phead);
    List* newnode =BuyNode(x);

    newnode->next = phead;
    newnode->prev = phead->prev;//尾节点指向新节点
    phead->prev->next = newnode;
    
    phead->prev = newnode;}

2.3 头插

voidListPushFront(List* phead, ListDataType x){assert(phead);
    List* newnode =BuyNode(x);

    newnode->next = phead->next;
    newnode->prev = phead;
    phead->next = newnode;//只有头节点时，就是头节点的prev
    phead->next->prev = newnode;}

2.4 打印

由于是循环链表，所以循环停止的条件应该是：cur != head

voidListPrint(List* phead){assert(phead);

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

2.5 尾删

• 不能没有节点
• 尾节点的前驱节点指向头节点
• 头节点指向尾节点的前驱节点
• 释放尾节点

voidListPopBack(List* phead){assert(phead);//只有头节点assert(phead->next != phead);

    List* del = phead->prev;
    del->prev->next = phead;
    phead->prev = del->prev;free(del);}

2.6 头删

• 不能没有节点
• 待删除节点的后继节点的prev指向头节点
• 头节点指向待删除节点的后继节点

voidListPopFront(List* phead){assert(phead);assert(phead->next != phead);

    List* del = phead->next;
    del->next->prev = phead;
    phead->next = del->next;free(del);}

2.7 查找

List*ListFind(List* phead, ListDataType x){assert(phead);assert(phead->next != phead);
    List* cur = phead->next;while(cur != phead){if(cur->data == x){return cur;}
        cur = cur->next;}returnNULL;}

2.8 指定位置前/后插入

• 将新节点与指定位置相连即可

指定位置前

voidListPosFrontInsert(List* pos, ListDataType x){assert(pos);

    List* newnode =BuyNode(x);
    List* prev = pos->prev;

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

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

指定位置后

voidListPosBackInsert(List* pos, ListDataType x){assert(pos);

    List* newnode =BuyNode(x);
    List* next = pos->next;

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

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

2.9 删除指定位置的节点

• 将指定位置的前驱节点、后继节点连接即可

voidListPosDel(List* pos){assert(pos);

    List* prev = pos->prev;
    List* next = pos->next;

    prev->next = next;
    next->prev = prev;free(pos);
    pos =NULL;}

2.10 删除指定位置后的节点

• 若指定位置是尾节点，则应该执行头删

voidListPosAfterDel(List* phead, List* pos){assert(phead);assert(pos);if(pos->next == phead){ListPopFront(phead);}else{
        List* del = pos->next;
        del->next->prev = pos;
        pos->next = del->next;free(del);}}

2.11 销毁链表

• 此接口的参数是一级指针，所以并不能将哨兵位销毁；因此需要再调用处再将哨兵位置为空

voidListDestroy(List* phead){assert(phead);assert(phead->next != phead);

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

3.顺序表与链表区别

不同点顺序表链表存储空间上物理上一定连续逻辑上连续，物理上不一定连续随机访问O(1)O(N)任意位置插入或删除可能需要搬运元素，效率低O(N)只需修改指针指向插入动态顺序表，空间不够需要扩容没有容量的概念应用场景元素高效存储，频繁访问任意位置频繁插入/删除缓存利用率高低