C语言数据结构——详细讲解 双链表

前言

         在数据结构的广袤天地里，链表作为一种重要的线性数据结构，以其独特的存储方式和灵活的操作特性，在众多编程场景中发挥着关键作用。今天，我们就来深入探讨一下从单链表到双链表的发展历程，看看双链表是如何在单链表的基础上应运而生，并解决了单链表所面临的一些问题。

一、单链表回顾

• 首先，我们来回顾一下单链表的基本结构。单链表是由一系列节点组成的数据结构，每个节点包含两部分：数据域和指针域。数据域用于存储具体的数据，指针域则存储指向下一个节点的指针，通过这样的指针链接，各个节点依次相连，形成了一条链表。
• 单链表不带头单向不循环，是链表结构中较为基础的一种形式，与带头节点的单链表不同，不带头节点的单链表在进行操作时，第一个节点就直接存储了实际的数据，没有专门设置一个额外的头节点来简化某些操作逻辑。

以下是带头单链表和不带头单链表的图片

以上这些图片均表示单链表

• 例如，我们有一个简单的单链表存储整数数据，节点结构可以定义如下

typedef struct ListNode 
{
    int data;
    struct ListNode *next;
} ListNode;

• 单链表在很多场景下都非常有用，它能够方便地进行动态内存分配，实现数据的灵活存储和操作，比如插入和删除节点等操作相对数组来说更加灵活，不需要移动大量元素

二、单链表的局限性

• 然而，单链表也存在一些局限性：
• 单向遍历：

单链表的指针只能指向一个方向，也就是只能从表头顺着指针依次访问到表尾的节点

• 删除操作的不便:

当我们想要删除单链表中的某个节点时，如果只知道要删除节点的指针（而不是它的前驱节点指针），操作起来会比较麻烦,，往往需要从头开始遍历链表去找到前驱节点，这同样会影响操作的效率。

三、什么是双链表

• 双链表的每个节点除了包含数据域和指向下一个节点的指针域外，还增加了一个指向前一个节点的指针域。也就是说，双链表的节点结构可以定义如下：

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

• 在这个结构中，**prev 指针指向当前节点的前一个节点，next 指针指向当前节点的下一个节点。**这样一来，双链表就具备了双向遍历的能力。

双链表可以分为带头节点和不带头结点

• 不带头节点的双链表
  
• 结构特点：

1.链表的第一个节点就直接存储实际的数据元素，不存在一个专门作为 “头” 的额外节点。
2.每个节点除了数据域外，有两个指针域，一个指向前驱节点（prev 指针），一个指向后继节点（next 指针）

• 带头结点的双链表
  

• 结构特点：

1.有一个专门的头节点，这个头节点的数据域一般不存储实际的数据（当然也可以根据具体需求赋予特殊含义，但通常为空数据域），主要作用是方便链表的各种操作。
2.头节点同样有两个指针域，prev 指针一般指向 NULL（因为它是表头，前面没有节点了），next 指针指向链表中的第一个实际存储数据的节点。

四、双链表的优势

1.双向遍历

从表头到表尾遍历：和单链表类似，我们可以通过每个节点的 next 指针依次访问后续节点，从而实现从表头到表尾的遍历。

• 删除操作的便利性

在双链表中删除一个节点就变得更加容易了。假设我们要删除节点 p，我们可以直接通过 p 的 prev 和 next 指针来完成删除操作，而不需要像单链表那样去专门寻找它的前驱节点

2.不带头双链表的用途

• 节省内存空间：

每一个节点都实实在在地用于存储数据及相关指针，不存在一个仅为了方便操作而占据空间但通常不存储实际有效数据的头节点。

• 体现数据原始性

3.带头双链表的用途

• 简化操作逻辑：

• 插入 无论是头插、尾插还是指定位置插入，由于有头节点的存在，不需要针对链表为空的情况单独设计特殊的处理逻辑。

• 删除 进行头删、尾删或指定位置删除时，操作逻辑相对统一，不用特别考虑链表为空时删除操作的特殊变化。

• 遍历 遍历链表时，从头节点的下一个节点开始顺着 next 指针向后遍历（正向遍历）以及从链表末尾顺着 prev 指针向前遍历（反向遍历）的逻辑较为清晰、简单，不用像不带头双链表那样，正向遍历要从第一个实际存储数据的节点开始，反向遍历要先找到末尾节点。

五、双链表的操作

双链表的插入操作

（一）双链表的尾插操作

void LTTPushFront(LTNode* head, int x)
{
    assert(head);
    LTNode* newnode = new LTNode;
    newnode->data = x;
   
    newnode->next = head;
    head = newnode;

    // 打印链表
    printList(head);
}

• head 为双链表的头结点
• x为要插入的数值

插入节点的步骤

• LTNode* newnode = new LTNode创建新节点
• newnode->data = x初始化新节点的数据
• newnode->next = head
• 这行代码将新节点的next指针指向当前的头节点head。这样，新节点就指向了原来的第一个节点
• head = newnode
• 这行代码将头节点head更新为新节点newnode。这样，新节点就成为了链表的新头节点。

（二）双链表的头插操作

// 头插操作
void LTPushFront(LTNode* head, int x) 
{
    assert(head);
    LTNode* newnode = buyNode(x);
    newnode->next = head->next;
    newnode->prev = head;
    head->next->prev = newnode;
    head->next = newnode;
}

• newnode->next = head->next;
• newnode->prev = head;
• 第一行代码将新节点newnode的next指针指向当前头节点head的下一个节点（即原来链表中的第一个节点）。
• 第二行代码将新节点newnode的prev指针指向头节点head
• head->next->prev = newnode;
• 将原来链表中第一个节点（即head->next）的prev指针指向新节点newnode。这一步是为了让原来的第一个节点知道它的前一个节点变成了新节点
• head->next = newnode;
• 将头节点head的next指针指向新节点newnode。这一步是为了让头节点指向新插入的节点，从而使新节点成为链表中的第一个节点

（三）双链表在指定位置之后插入数据

// 在pos位置之后插入数据
void LTInsert(LTNode* pos, int x) {
    assert(pos);
    LTNode* newnode = buyNode(x);
    newnode->next = pos->next;
    newnode->prev = pos;
    if (pos->next) {
        pos->next->prev = newnode;
    }
    pos->next = newnode;
}

• newnode->next = pos->next;：
• 将新节点newnode的next指针指向pos节点的下一个节点。
• newnode->prev = pos;
• 将新节点newnode的prev指针指向pos节点
• if (pos->next) { pos->next->prev = newnode; }：
• 如果pos节点有下一个节点（即pos->next不为NULL），那么将pos的下一个节点的prev指针指向新节点newnode。
• 这一步是为了保持双链表的双向连接关系
• 最后将pos节点的next指针指向新节点newnode，完成新节点在pos节点之后的插入操作

双链表的删除操作

（一）双链表的尾删操作

// 尾删
void LTPopBack(LTNode* head) 
{
    assert(!LTEmpty(head));
    LTNode* del = head->prev;
    LTNode* prev = del->prev;
    prev->next = head;
    head->prev = prev;
    delete del;
}

• LTNode* del = head->prev;
• 双链表通常有一个头节点，尾节点是头节点的前一个节点，所以这里head->prev就是尾节点，将其赋值给del
• LTNode* prev = del->prev;，找到尾节点del的前一个节点prev
• prev->next = head;，将尾节点的前一个节点的next指针指向头节点，这样就把尾节点从链表中移除了。
• head->prev = prev;，同时更新头节点的prev指针指向新的尾节点（原来尾节点的前一个节点）

（二）双链表的头删操作

// 头删操作
void LTpopFront(LTNode* head) {
    assert(!LTEmpty(head));
    LTNode* del = head->next;
    head->next = del->next;
    if (del->next) {
        del->next->prev = head;
    }
    delete del;
}

• LTNode* del = head->next;头节点的下一个节点就是要删除的第一个数据节点，将其赋值给del
• head->next = del->next;，将头节点的next指针指向要删除节点del的下一个节点，这样就把del从链表中移除了。
• if (del->next) { del->next->prev = head; }，如果del有下一个节点（即del不是尾节点），那么将del的下一个节点的prev指针指向头节点

（三）双链表删除指定位置数据

// 删除指定位置数据
void LTEarse(LTNode* pos) {
    assert(pos);
    pos->prev->next = pos->next;
    if (pos->next) {
        pos->next->prev = pos->prev;
    }
    delete pos;
}

• pos->prev->next = pos->next;，将pos节点的前一个节点的next指针指向pos节点的下一个节点，这样就把pos从链表中移除了。
• if (pos->next) { pos->next->prev = pos->prev; }，如果pos有下一个节点，那么将pos的下一个节点的prev指针指向pos的前一个节点