链表

Posted 2025-01-14 Updated 2025-01- 15

By Administrator

49~63 min read

链表概念

内存空间是所有程序的公共资源，在一个复杂的系统运行环境下，空闲的内存空间可能散落在内存各处。我们知道，存储数组的内存空间必须是连续的，而当数组非常大时，内存可能无法提供如此大的连续空间。此时链表的灵活性优势就体现出来了。

链表（linked list）是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过指针相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。

链表的设计使得各个节点可以分散存储在内存各处，它们的内存地址无须连续。

图 4-5 链表定义与存储方式

观察图 4-5 ，链表的组成单位是节点（node）对象。每个节点都包含两项数据：节点的“值”和指向下一节点的“引用”。

链表的首个节点被称为“头节点”，最后一个节点被称为“尾节点”。
尾节点指向的是 NULL。
在 C、C++、Go 和 Rust 等支持指针的语言中，上述“引用”应被替换为“指针”。

如以下代码所示，链表节点 ListNode 除了包含值，还需额外保存一个引用（指针）。因此在相同数据量下，链表比数组占用更多的内存空间。

链表分类：

单向链表：单向链表的节点包含值和指向下一节点的引用两项数据。我们将首个节点称为头节点，将最后一个节点称为尾节点，尾节点指向空 NULL 。
环形链表：如果我们令单向链表的尾节点指向头节点（首尾相接），则得到一个环形链表。在环形链表中，任意节点都可以视作头节点。（可以是单向的环形链表也可以双向的环形链表）
双向链表：与单向链表相比，双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用（指针）。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但相应地也需要占用更多的内存空间。

单向链表

分类：

包含头节点（声明一个固定的头结点）
不包含头结点（头结点不是固定，每次往头部插入，都会更新一次头结点）

含头结点的单向链表相关方法

#include <stdio.h>
#include <stdlib.h>

// 注意：当一个结构体内部需要使用自己的时候不能使用 匿名结构体，在结构体内部声明的时候不能使用别名。
typedef struct node {
    int data;  // 节点数据
    struct node* next; // 节点下一个节点的指针
} Node;


// 创建新节点
Node* createNode(int data) {
    Node* node = malloc(sizeof(Node));
    node->data = data; // 节点的数据
    node->next = NULL; // 创建出来新节点是不知道需要指向那个节点的
    return node;
}


// 头部插入
void addHead(Node* head, int data) {
    Node* node = createNode(data); // 创建一个新节点
    node->next = head->next; // 新节点的 next 指向原来头节点的 next 
    head->next = node; // 头结点.next 指向新节点
}

// 遍历节点
void forEach(Node* head) {
    // 空链表不需要遍历
    if ( head == NULL || head.next == NULL) {
        return;
    }

    Node* node = head->next;
    while (node != NULL) {
        printf("%d ", node->data);
        // 去到下一个节点
        node = node->next;
    }
    printf("\n");
}


/// @brief 在指定节点的后面插入的一个新节点
/// @param n0  节点
/// @param data  新节点的数据
void afterInsert(Node* n0, int data) {
    Node* node = createNode(data);

    // 新增节点 next ，指向原来节点的  next
    node->next = n0->next;

    // 原来节点的 next 指向新增的节点
    n0->next = node;
}

/// @brief 根据值查询，第一个符合条件的节点进行返回，如果没有查找到范湖NULL
/// @param head 头结点（包含头结点 （头结点是数据无效的 ））
/// @param data  （要查找的节点的值）
/// @return 节点或者 NULLL
Node* findNode(Node* head, int data) {
    if (head->next == NULL) {
        return NULL;
    }

    Node* node = head->next;
    while (node != NULL) {
        // 找到第一个符合的节点进行返回
        if (node->data == data) {
            return node;
        }
        node = node->next;
    }

    // 如果节点不存在返回NULL
    return NULL;

}
 

void tailInsert(Node* head, int data) {
    // 遍历出尾节点
    // 头节点直接 next 可能会出现 next 为空 （也就链表为空， head 既是头节点也是尾节点）
    //  Node* node = head->next;     // 解决，从头结点开始判断
    Node* node = head;

    // node.next 下一个如果为 NULL ，就代表该节点就是尾部节点了
    while (node->next != NULL) {
        node = node->next;
    }
    Node* newNode = createNode(data);
    node->next = newNode;
}

// 删除节点
void delNode(Node* head, int val) {
    Node* node = head;
    // 找到要被删除的节点的前一个节点 
    while (node->next != NULL) {
        if (node->next->data == val) {
            break;
        }
        node = node->next;
    }
  
    if (node->next != NULL && node->next->data == val) {
        Node* rmNode = node->next;
        // 删除节点的前一个节点的 next 指向 ， 删除节点的 next 
        node->next = rmNode->next;
        // 删除节点的堆空间释放掉
        free(rmNode);
    }
}



// 向指定值插入节点
void insertNode(Node* head, int target, int data) {
    // 找到需要插入的位置
    Node* node = head->next;
    while (node != NULL) {
        // 找到了
        if (node->data == target) {
            break;
        }

        node = node->next;
    }
    // 只有 node 不为空的时候找到了
    if (node != NULL) {
        // 创建新节点
        Node* newNode = createNode(data);
        newNode->next = node->next;
        node->next = newNode;
    }
}


// 销毁链表 ，一个节点一个节点来进行销毁
void destroyList(Node** head) {
    Node* node = (*head)->next;
    while (node != NULL) {
        // 获取当前节点
        Node* temp = node;

        // 去到当前的节点的下一个节点
        node = node->next;

        // 释放当前节点 ， 不用将当前节点设置为 NULL ，
        //  原因是一旦头结点被释放掉，就没有方法可以使用该指针了
        free(temp);
    }

    // 释放头节点
    free(*head);
    // 防止头指针成为野指针
    *head = NULL;
}

int main(int argc, char const* argv[]) {
    Node* head = createNode(-1);
    addHead(head, 1);
    addHead(head, 2);
    addHead(head, 3);

    forEach(head);
    // 销毁
    destroyList(&head);
    printf("释放链表： %d \n", head == NULL);
    return 0;
}

含头节点的特点：

头结点保存的数据是无效的，头结点的 next 指向第一个包含有效数据的节点。
每一次向头部插入数据，头结点的 next 指向的新创建出来的节点。

不含头的单向链表相关方法

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int data;
    struct node* next;
} Node;


// 创建新节点
Node* createNode(int data) {
    Node* node = malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    return node;
}


// 头部插入
void addHead(Node** head, int data) {
    Node* node = createNode(data);
    // node->next = head->next;
    // head->next = node;
    node->next = *head;
    *head = node;
}

// 遍历节点
void forEach(Node* head) {
    Node* node = head;
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}



// 实现 void insert(ListNode *n0, int data) 给 n0节点后面插入一个节点

/// @brief 在指定节点的后面插入的一个新节点
/// @param n0  节点
/// @param data  新节点的数据
void afterInsert(Node* n0, int data) {
    Node* node = createNode(data);

    // 新增节点 next ，指向原来节点的  next
    node->next = n0->next;

    // 原来节点的 next 指向新增的节点
    n0->next = node;
}

/// @brief 根据值查询，第一个符合条件的节点进行返回，如果没有查找到范湖NULL
/// @param head 头结点（包含头结点 （头结点是数据无效的 ））
/// @param data  （要查找的节点的值）
/// @return 节点或者 NULLL
Node* findNode(Node* head, int data) {
    Node* node = head;
    while (node != NULL) {
        // 找到第一个符合的节点进行返回
        if (node->data == data) {
            return node;
        }
        node = node->next;
    }

    // 如果节点不存在返回NULL
    return NULL;

}

// 实现 void tail_head 尾查法(向链表末尾插入节点), 
// 遍历整个链表，找到 NULL 之前的那个节点（也就是最后的那个节点）
void addLast(Node* head, int data) {
    Node* newNode = createNode(data);

    // 第二个元素的位置
    Node* node = head;
    while (node != NULL) {
        // 找到最后一个节点
        if (node->next == NULL) {
            break;
        }
        node = node->next;
    }

    node->next = newNode;
}


// 实现 删除第一个等于指定值节点 void insert(int data) 
// 通过循环，来判断如果一个节点的下一个元素的数据 == val ，就找到了
// 节点.next = 删除节点的.next 
void removeNode(Node** head, int val) {
    Node* node = *head;

    // 删除头部的第一个元素
    if (node->data == val) {
        *head = node->next;
        node = NULL;
        return;
    }

    while (node->next != NULL) {
        if (node->next->data == val) {
            break;
        }

        node = node->next;
    }
    if (node == NULL || node->next == NULL) return;

    // 删除节点的前一个节点的 next 指向 ， 删除节点的 next 
    Node* rmNode = node->next;
    node->next = rmNode->next;
    // 释放
    free(rmNode);

}



int main(int argc, char const* argv[]) {
    Node* head = createNode(1);
    // addHead(&head, 2);
    addHead(&head, 3);
    // addHead(&head, 4);

    addLast(head, 8);
    addLast(head, 7);
    addLast(head, 6);
    addLast(head, 5);



    forEach(head);
    // printf("----------------------\n");

    // removeNode(&head, 8);
    // Node* n = findNode(head, 8);
    // if (n != NULL) {
    //     printf("n = %d \n", n->data);
    // }

    // forEach(head);
    return 0;
}

特点：

头结点也保存这有效的数据。
往头插入数据，实际上是不断地更新头结点
创建头节点的时候就需要传递有效数据

图片：

无头结点.png

使用注意点：

在函数中修改外部函数的变量，调用函数的地方需要将变量的地址传递过来（地址传递）
无头结点的，其实是头节点的不断地更新的为新的节点。

双向链表

代码：

#include <stdio.h>
#include <malloc.h>
// 定义结构体
typedef struct node {
    int data;
    struct node* prev;// 节点前一个节点的地址 (前驱节点)
    struct node* next; // 节点下一个节点的地址 （后继节点）
} Node;


// 创建新节点
Node* createNode(int data) {
    Node* node = malloc(sizeof(Node));
    node->data = data;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

// 头插法
void headInsert(Node* head, int data) {
    Node* newNode = createNode(data);

    // 空链表
    if (head->next != NULL) {
        // 原来头节点的下一个节点 ， 的前指针指向新的节点
        head->next->prev = newNode;
    }
    // 新节点的后继节点 = 头结点的原来的 next 节点
    newNode->next = head->next;
    // 新节点的前驱节点 = head 
    newNode->prev = head;
    // 头结点的后继节点 = 新的节点。
    head->next = newNode;
}


// 删除指定节点的元素
void delNode(Node* head, int val) {

    Node* node = head->next;
    // 空链表无法删除。
    if (node == NULL) {
        return;
    }
    while (node != NULL) {
        // 找到要删除的节点了
        if (node->data == val) {
            break;
        }
        node = node->next;
    }

    printf("删除  = %d \n", node->data);
    node->prev->next = node->next;
    if (node->next != NULL) {
        node->next->prev = node->prev;
    }


    free(node);
}

// 销毁: 每一个节点都是堆空间的,需要使用 free 进行释放, 一个节点一个节点的销毁
// 销毁的效果：node 往前走一步，就销毁原来的node位置的节点占用的堆空间.
void destroyList(Node** head) {
    Node* node = (*head)->next;
    while (node != NULL) {
       // 需要被销毁的节点
        Node* temp = node;
        // 释放当前节点之前需要节点先去到下一个节点。
        node = node->next;

        // 释放当前节点释放堆空间
        free(node);
    }
    // 释放头节点
    free(*head);
    *head = NULL;
}

// 遍历
void forEach(Node* head) {
    Node* node = head->next;
    printf("正序： ");
    Node* lastNode = NULL;
    while (node != NULL) {
        // 找到尾节点
        if (node->next == NULL) {
            lastNode = node;
        }

        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
    // 倒序遍历需要从尾节点开始遍历 ，所有需要先获取的尾节点
    printf("倒序： ");
    while (lastNode != head) {
        printf("%d ", lastNode->data);
        lastNode = lastNode->prev;
    }
    printf("\n");

}



int main(int argc, char const* argv[]) {
    // 创建一个含头的节点
    Node* head = createNode(-1);
    headInsert(head, 9);
    headInsert(head, 8);
    headInsert(head, 7);
    headInsert(head, 6);
    headInsert(head, 5);
    forEach(head);

    delNode(head, 5);
    forEach(head);

    destroyList(&head);
    printf("%d \n" , head == NULL);

    // printf("%d \n", head->next->data);
    return 0;
}

新增节点的图片:

双向链表.png

循环链表

循环双向链表 (重点)

特点：

第一个节点既是头节点也是尾节点。
当只有一个节点的时候，该节点的 next 指向自己，该节点的 prev 指向自己。
遍历的节点的时候的如果移动的 node == head 就代表遍历完整个链表了。

代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int data;
    struct node* prev;
    struct node* next;
} Node;



// 创建节点
Node* createNode(int data) {
    Node* node = malloc(sizeof(Node));
    node->data = data;
    node->prev = node;
    node->next = node;

    return node;
}


// 头插法
void headInsert(Node* head, int data) {
    Node* node = createNode(data);

    // next方向 
    // node 的后继节点 指向 头结点的后继节点
    node->next = head->next;
    // 头结点的后继节点指向的新增节点。
    head->next = node;

    // prev 方向
    // node 的 后继节点已经更新为 head 的后继节点 ， 
    // 该节点的前驱节点指向新增的节点
    node->next->prev = node;
    // 新增节点的前驱节指向头节点
    node->prev = head;


}

// 删除节点 
void delNode(Node* head, int val) {
    // 头部开始找
    Node* node = head->next;

    // 空链表
    if (node == NULL) {
        return;
    }

    // 找到要删除的节点 , 开始找到头节点（尾节点）
    while (node != head) {
        if (node->data == val) {
            break;
        }
        node = node->next;
    }

    // 判断
    if (node != NULL && node->data == val) {
        // 删除节点的前一个的 next  指向 ，删除节点的next 
        node->prev->next = node->next;

        // 删除节点的后一个 prev 指向 ， 删除节点的 node.prev 
        node->next->prev = node->prev;
    }
}

// 销毁整个列表 : 遍历整个链表 ， 回收每一个节点的堆空间。
void destroyList(Node** head) {
    Node* node = (*head)->next;
    // 注意：循环完整个数组的条件是 node == head ，当前节点一旦为 head 就证明链表已经循环到头了
    while (node != *head) {
        Node* temp = node;
        node = node->next;
        temp->prev = NULL;
        free(temp);
    }
    // free(node);
    free(*head);
    printf("%d \n" , (*head)->data);
    *head = NULL;
}


// 尾部插入
void tailInsert(Node* head, int data) {
    Node* newNode = createNode(data);

    // prev 方向
    //  新增的节点的前驱节点的 指向 头节点的前驱节点
    newNode->prev = head->prev;
    // 头节点的前驱节点指向新增的节点
    head->prev = newNode;

    // next 方法  
    // newnode 的前驱节点已经更新成了 head 原来的 prev 
    // 该的节点的后继节点指向新增的节点
    newNode->prev->next = newNode;
    // 新增节点的后继节点指向头节点
    newNode->next = head;

}

// 遍历
void foreachList(Node* head, int isReversal) {
    // 倒序遍历
    if (isReversal) {
        printf("倒序: ");
        Node* node = head->prev;
        while (node != head) {
            printf("%d ", node->data);
            node = node->prev;
        }

    } else {
        printf("正序: ");
        // 正序遍历
        Node* node = head->next;
        while (node != head) {
            printf("%d ", node->data);
            node = node->next;
        }
    }

    printf("\n");
}

int main(int argc, char const* argv[]) {
    // 头节点
    Node* head = createNode(-1);
    headInsert(head, 1);
    headInsert(head, 2);
    tailInsert(head, 4);
    tailInsert(head, 5);

    foreachList(head, 0);

    // 删除
    delNode(head, 4);
    delNode(head, 1);
    // delNode(head, 66);
    foreachList(head, 0);

    destroyList(&head);
    printf("%d \n", head == NULL);

    return 0;
}

头插入图片：

插入新节点：

循环单向链表

特点：

从头节点开始从一个方向开始指，最后指回头结点
第一个节点，既是头节点也是尾节点
当只有一个节点的时候，该节点的 next 指自己。

图片：

代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int data;
    struct node* next;
} Node;


// 创建节点
Node* createNode(int data) {
    Node* node = malloc(sizeof(Node));
    node->data = data;
    node->next = node; // 自己指向自己
    return node;
}


// 头插法
void  headInsert(Node* head, int data) {
    Node* newNode = createNode(data);

    // 头部插入
    newNode->next = head->next;
    head->next = newNode;
}


// 遍历
void forEachList(Node* head) {
    Node* node = head->next;
    // 循环的结束条件当前节点 = 头节点了
    while (node != head) {  // 循环链表  
        printf("%d ", node->data);
        node = node->next;
    }

    printf("\n");
}

int main(int argc, char const* argv[]) {
    // 做单向循环链表,只做头插法
    Node* head = createNode(-1);
    headInsert(head, 1);
    headInsert(head, 2);
    headInsert(head, 3);
    headInsert(head, 4);
    forEachList(head);
    return 0;
}

总结：

创建新节点的代码，只考虑初始化的头结点的就行了
遍历循环链表的时候，循环的结束条件， ndoe == head 一直移动的节点 == 头结点的时候就代表循环完一次链表了
单向链表删除元素的时候需要先获取删除元素的前一个节点。

链表的使用场景：

单向链表通常用于实现栈、队列、哈希表和图等数据结构。

栈与队列：当插入和删除操作都在链表的一端进行时，它表现的特性为先进后出，对应栈；当插入操作在链表的一端进行，删除操作在链表的另一端进行，它表现的特性为先进先出，对应队列。
哈希表：链式地址是解决哈希冲突的主流方案之一，在该方案中，所有冲突的元素都会被放到一个链表中。
图：邻接表是表示图的一种常用方式，其中图的每个顶点都与一个链表相关联，链表中的每个元素都代表与该顶点相连的其他顶点。

双向链表常用于需要快速查找前一个和后一个元素的场景。

高级数据结构：比如在红黑树、B 树中，我们需要访问节点的父节点，这可以通过在节点中保存一个指向父节点的引用来实现，类似于双向链表。
浏览器历史：在网页浏览器中，当用户点击前进或后退按钮时，浏览器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单。
LRU 算法：在缓存淘汰（LRU）算法中，我们需要快速找到最近最少使用的数据，以及支持快速添加和删除节点。这时候使用双向链表就非常合适。

环形链表常用于需要周期性操作的场景，比如操作系统的资源调度。

时间片轮转调度算法：在操作系统中，时间片轮转调度算法是一种常见的 CPU 调度算法，它需要对一组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU 将切换到下一个进程。这种循环操作可以通过环形链表来实现。
数据缓冲区：在某些数据缓冲区的实现中，也可能会使用环形链表。比如在音频、视频播放器中，数据流可能会被分成多个缓冲块并放入一个环形链表，以便实现无缝播放。

数据结构与算法

License: CC BY 4.0