数据结构：第十节-线性表的链式存储（上）

山月

线性表的链式存储是一种通过指针来表示元素之间关系的存储方式，即它可以用一组物理位置任意的存储单元来存放数据。

链式存储的每个元素称为节点（Node），节点由两部分组成：数据域（存储元素数据）和指针域（指向下一个节点的指针）。链表的起始节点称为头节点，它存储链表的起始地址。

如上图所示，head为头指针，存储了头节点的地址，它指向表中的第一个节点，下一个即为头节点，头节点的数据域一般不存储任何信息，指针域存储首元节点的地址，从首元节点开始才存储有效数据，后面的节点均包含有数据域和指针域，如a,b,c为数据；101BH，221BH，1050H为地址，指向下一节点。最后一个节点的指针域指向为NULL，因为其已经没有下一数据需要指向。

常见的链式存储结构有单链表（线性链表）、双向链表和循环链表。

1.单链表：上述图中所描述的链表即为单链表,单链表的特点如下：

单链表的每个节点包含一个数据域和一个指向下一个节点的指针域。最后一个节点的指针域指向空（nullptr）。单链表只能从头节点开始顺序访问，不能从末尾直接访问。

2.双向链表：双向链表的每个节点包含一个数据域、两个指针域，一个指向下一个节点，一个指向前一个节点。双向链表可以从头节点或尾节点开始访问，支持双向遍历。

3.循环链表：循环链表是一种特殊的链表，最后一个节点的指针域指向链表的头节点，形成一个循环。循环链表可以从任意节点开始遍历，遍历到尾节点后会回到头节点。

struct LNode {
    int data;           // 数据域，存储节点的数据
    LNode* next;     // 指针域，指向下一个节点的指针
};

通过这个结构体，我们可以创建一个单链表的节点，每个节点都包含一个整数类型的数据和一个指向下一个节点的指针。

定义好单链表后，我们需要对单链表进行操作，单链表的基本操作包括创建、插入、删除、查找、遍历等。

1.创建单链表：创建一个空的单链表，可以通过初始化一个头节点来实现。头节点不存储有效数据，其指针域指向第一个存储数据的节点。单链表的初始化操作很简单，只需将头指针指向空即可。

单链表初始化的时间复杂度和空间复杂度均为 O(1)。

 class LinkedList {
private:
    ListNode* head;     // 头指针，指向链表的头节点


public:
    // 构造函数，初始化链表为空表
    LinkedList() : head(nullptr) {}
    }；

由此我们判断单链表是否为空的操作是检查链表是否包含任何节点。单链表为空的条件是头指针为空。如果头指针为空，则返回 true；否则返回 false。

class LinkedList {
private:
    ListNode* head;     // 头指针，指向链表的头节点
public:
    // 构造函数，初始化链表为空表
    LinkedList() : head(nullptr) {}
    // 判断链表是否为空
    bool isEmpty() {
        return head == nullptr;
    }
};

如果isEmpty（）为true则链表为空，否则不为空。

为了释放链表中每个节点所占用的内存空间，防止内存泄漏，同时提高程序的性能和资源利用率，我们需要进行单链表的销毁。

我们需要从头节点开始，首先访问当前节点，获取该节点的指针，释放当前节点所占用的内存空间，然后将当前节点指针指向下一个节点，以便继续遍历链表，逐个释放，直到链表为空，最后将头指针指向空（nullptr）。

单链表的销毁操作的时间复杂度为 O(n)，空间复杂度为 O(1)，其中 n 是链表中节点的个数。

class LinkedList {
private:
    ListNode* head;     // 头指针，指向链表的头节点
public:
    // 构造函数，初始化链表为空表
    LinkedList() : head(nullptr) {}
    // 销毁链表
    void destroyList() {
        ListNode* current = head;
        while (current) {
            ListNode* temp = current;
            current = current->next;
            delete temp;
        }
        head = nullptr; // 将头指针指向空
    }
}

对于上述销毁算法，首先，将头指针 head 赋值给临时指针变量 current，以便从头开始遍历链表。只要当前节点 current 不为空，就执行循环体内的操作。在循环体内，首先将当前节点的指针赋值给临时指针变量 temp，以便稍后释放当前节点的内存空间。（释放当前节点后，current 指针失效了，无法直接通过 current->next 访问下一个节点，因为 current 已经被释放，其指针无效，因此我们需要使用 temp 变量来暂存当前节点，能够确保在释放当前节点后，仍然能够继续访问下一个节点，并正确释放整个链表中的每个节点的内存空间，避免内存泄漏问题。）然后，将当前节点的指针移动到下一个节点，即 current = current->next，以便继续遍历链表。我们使用 delete 关键字释放临时指针 temp 指向的节点的内存空间，即释放当前节点，直到遍历完整个链表。最后，将头指针 head 指向空（nullptr），表示链表已经被销毁，避免出现悬空指针。

我们先介绍链式存储的这些操作，感谢观看！欢迎各位的点赞与关注！您的点赞和关注是我学习更新的动力！如有问题，可下方留言！