首页 数据结构 链表

ps: 本文图片来自 leetcode 线性结构 - 双链表

# 简介

上篇文章说过单链表.

单链表中的节点具有 数据域和指针域，常见基本形式为 充当数据域的 value 字段 和 充当指针域的 next 引用字段。节点通过引用字段 有序链接，称为链表

一个数据结构的出现，肯定会有其变式，用于优化原先数据结构的不足.
双链表的出现也是如此，双链表解决了链表不可逆向查找的问题.

# 定义

双链表既为单链表的变式，其工作方式必然也与单链表相似。但变式毕竟是变式，还是会有不同的地方.
双链表 比单链表多出了 一个引用字段 prev . 有了这个字段，我们就可以找到当前节点的 前驱节点.
双链表例子如图:
双链表
绿色箭头表示 prev 工作方式

# 节点结构

双向链表节点典型定义

typedef struct DoublyListNode{
    int val;
    struct DoublyListNode *prev;
    struct DoublyListNode *next;
} DoublyListNode;

与单链接列表类似，我们将使用头结点来表示整个列表.

一样还是来个 cpp 版本

struct DoublyListNode {
    int val;
    DoublyListNode *next, *prev;
    DoublyListNode(int x) : val(x), next(NULL), prev(NULL) {}
};

# 操作分析

同样的单链表有的双链表都不会少，增删查改都是类似的.
与单链表相同的方式访问数据:

  1. 无法在常量级的时间内访问随机位置.
  2. 必须从头部遍历才能得到我们想要的结点.
  3. 在最坏的情况下，时间复杂度将是 O (N), 其中 N 是链表的长度.
    对于基本操作，添加和删除，下面还会单独说明，这两个操作由于多出一个前驱引用，操作略显麻烦一些.

# 添加操作

# 在链表中添加节点

一般来说，想在现有节点 prev 之后插入一个新节点 cur , 分为 3 个步骤:

  1. 初始化 cur 节点，将 val 赋予 cur->val ;
    init
  2. 链接 cur 与 prev 和 next , next 为 prev 原始的下一个节点；
    20211127092731
  3. 用 cur 重新链接 prev 和 next
    20211127092752

# 特例一：在头部添加节点

同样的 在头部的操作也是双链表的一个特例，步骤如下:

  1. 初始化 cur 节点，将 val 赋予 cur->val ;
    head_insert
  2. 链接 cur 与 head 节点， cur 的 prev 引用字段链接到空
    head_insert
  3. 将 head 的 prev 字段与 cur 链接
    head_insert

# 特例二：在尾部添加节点

  1. 初始化 cur 节点，将 val 赋予 cur->val ;
    end_insert
  2. 找到 tail 节点，将 cur 与 tail 节点连接， cur 的 next 引用字段链接到空
    end_insert
  3. 将 tail 的 next 字段与 cur 链接
    end_insert

# 删除操作

如果我们想从双链表中删除一个现有的结点 cur , 我们可以简单地将它的前一个结点 prev  与下一个结点 next  链接起来

与单链表不同，使用 “prev” 字段可以很容易地在常量时间内获得前一个结点。

因为我们不再需要遍历链表来获取前一个结点，所以时间和空间复杂度都是 O (1)

# 在链表中删除节点

删除节点步骤如下 (步骤略微细分):

  1. 链接 cur->next 到 cur->prev
    delete
  2. 链接 cur->prev 到 cur->next
    delete
  3. cur 的 两个引用字段链接到自己，然后释放
    delete

# 特例一：在头部删除节点

删除头部节点步骤如下:

  1. 链接 head->next->prev 到 空指针
    delete_head
  2. head->next 链接到空指针，释放 head
    delete_head

# 特例二：在尾部删除节点

删除头部节点步骤如下:

  1. 链接 head->next->prev 到 空指针
    delete_tail
  2. head->next 链接到空指针，释放 head
    delete_tail

# 代码实现

下面的代码以带头节点的链表格式实现。大体思路实现与不带头节点的链表原理一致.
接口格式源于 leetcode 707 链表设计.
各位可自行测试自己的实现方式，本文的所有代码都在本地测试过，放心食用 (ฅ・ω・ฅ)

# 完整代码

需要注意上面说的几个特例，在插入删除的操作的时候

typedef struct MyLinkedList
{
    int val;
    struct MyLinkedList *next;
    struct MyLinkedList *prev;
} MyLinkedList;
MyLinkedList *myLinkedListCreate()
{
    struct MyLinkedList *head = (MyLinkedList *)malloc(sizeof(MyLinkedList));
    head->val = 0;
    head->next = head->prev = NULL;
    return head;
}
int myLinkedListGet(MyLinkedList *obj, int index)
{
    // 1. index < 0
    // 2. 链表为空
    // 3. index 过大
    if (index < 0 && !(obj->next))
        return -1;
    MyLinkedList *head = obj->next;
    // 查找 第 index 个节点，可能存在两种情况
    //  1. 存在 第 index 个节点
    //  2. 不存在 第 index 个节点
    for (int i = 0; head && i < index; i++)
    {
        head = head->next;
    }
    //head 非空代表存在整个值 返回 -1 ,
    // 否则返回 val
    return (head ? head->val : -1);
}
void myLinkedListAddAtHead(MyLinkedList *obj, int val)
{
    // 初始化新节点
    MyLinkedList *node = (MyLinkedList *)malloc(sizeof(MyLinkedList));
    node->val = val;
    // 指向 head 后面的节点
    // 如果为空，也会指向空，所以无需 next 指向空
    //obj 为头节点，obj->next 为第一个节点
    // 1. node->next 指向 obj->next 表示 新节点指向原本的第一个节点，从此之后 新节点 就可以访问到旧节点
    node->next = obj->next;
    // 2. node->prev = obj 表示 node 的前驱指针 链接上 头节点 node, 这个时候就可以断开，obj->next 和 obj 之间的链接了
    node->prev = obj;
    // 3. obj->next 指针 指向 node , node 成为链表的第一个节点
    obj->next = node;
    // 这里考虑第一次插入节点
    if (NULL == node->next)
        return;
    // 4. 因为 node 在 1 出获得了 原本第一个节点的地址，所以 next->prev 为原本第一个节点的前驱指针，指向了 node, node 的 前驱链接合
    node->next->prev = node;
}
void myLinkedListAddAtTail(MyLinkedList *obj, int val)
{
    // 当链表为空，尾插变头插
    if (NULL == obj->next)
    {
        myLinkedListAddAtHead(obj, val);
        return;
    }
    // 初始化节点
    MyLinkedList *node = (MyLinkedList *)malloc(sizeof(MyLinkedList));
    node->val = val;
    node->next = NULL;
    // 查找最后一个节点
    MyLinkedList *tail = obj->next;
    while (tail->next)
    { //obj 为空 无法获取到前一个节点
        tail = tail->next;
    }
    // 尾节点指向新节点
    tail->next = node;
    node->prev = tail;
}
void myLinkedListAddAtIndex(MyLinkedList *obj, int index, int val)
{
    // 过滤非法 index < 0, 使用头插法，题目要求，正常情况过滤负数，特判头节点
    if (index <= 0)
        return myLinkedListAddAtHead(obj, val);
    // 找到第 index-1 个节点
    int i = 0;
    MyLinkedList *head = obj->next;
    for (i = 0; head->next && i < index - 1; i++)
    { // 和获取第 index 值 类似，只不过这里需要获取 前一个节点
        head = head->next;
    }
    // 判断退出条件
    if (index - 1 != i)
    {
        return;
    }
    // 初始化节点，避免浪费空间
    MyLinkedList *node = (MyLinkedList *)malloc(sizeof(MyLinkedList));
    node->val = val;
    // 插入节点，道理同 myLinkedListAddAtHead 部分的注释
    //node 链接 到 head 和 head->next
    node->next = head->next; // 链接到 head
    node->prev = head;       // 链接到 head->next
    //head 和 head->next 链接到 node
    head->next = node;
    // 插入尾节点特判
    if (NULL == node->next)
        return;
    node->next->prev = node; // head->next =
}
void myLinkedListDeleteAtIndex(MyLinkedList *obj, int index)
{
    // 异常拦截
    if (!(obj->next) || index < 0)
        return;
    // 分类讨论
    MyLinkedList *temp = NULL;
    // 1. 删除头节点
    if (0 == index)
    {
        // 存下要销毁的节点
        temp = obj->next;
        // 头节点指向第二个节点
        obj->next = obj->next->next;
        // 第二个节点链接上头节点
        // 考虑所删除的链表只有一个节点
        if (NULL == obj->next)
            return;
        obj->next->prev = obj;
        temp->next = temp;
        free(temp);
        return;
    }
    // 找到 第 index - 1 个节点
    int i = 0;
    MyLinkedList *head = obj->next;
    for (i = 0; head->next && i < index - 1; i++)
    {
        head = head->next;
    }
    if (i != index - 1 || (NULL == head->next))
        return;
    // 删除节点
    // 保留节点指针
    temp = head->next;
    //index-1 节点的 链接到  index+1 节点
    head->next = head->next->next;
    // 特判删除最后一个节点
    if (NULL == head->next)
        return;
    //index+1 节点的 链接到  index-1 节点
    head->next->prev = head;
    // 释放节点
    temp->next = temp;
    free(temp);
}
void myLinkedListFree(MyLinkedList *obj)
{
    // 异常拦截
    if (!obj)
        return;
    MyLinkedList *head = obj->next;
    MyLinkedList *temp = NULL;
    while (head)
    {
        temp = head;
        head = head->next;
        temp->next = temp->prev = NULL;
        free(temp);
    }
    obj = NULL;
}
# 本地测试代码
这里是一组测试样例
#define GET_INDEX 5
void printfList(MyLinkedList *obj)
{
    MyLinkedList *head = obj->next;
    while (head)
    {
        printf("%d ", head->val);
        head = head->next;
    }
    putchar('\n');
}
int main(void)
{
    // 创建链表
    MyLinkedList *obj = myLinkedListCreate();
    // 头插法
    myLinkedListAddAtHead(obj, 2);
    printfList(obj);
    // 按索引删除
    myLinkedListDeleteAtIndex(obj, 1);
    printfList(obj);
    // 添加 4 个节点
    myLinkedListAddAtHead(obj, 2);
    printfList(obj);
    myLinkedListAddAtHead(obj, 7);
    printfList(obj);
    myLinkedListAddAtHead(obj, 3);
    printfList(obj);
    myLinkedListAddAtHead(obj, 5);
    printfList(obj);
    // 尾插法
    myLinkedListAddAtTail(obj, 5);
    printfList(obj);
    printf("This is index %d value %d\n", GET_INDEX, myLinkedListGet(obj, GET_INDEX));
   
    // 按索引删除节点
    myLinkedListDeleteAtIndex(obj, 6);
    printfList(obj);
    myLinkedListDeleteAtIndex(obj, 4);
    printfList(obj);
    // 释放链表
    myLinkedListFree(obj);
    printf("============================================================\n");
    printf("Test finis\n");
    return 0;
}
大道五十，天衍四十九，人遁其一！