线性表的链式存储是什么？线性表链式存储结构的特点

线性表的链式存储结构,通常被称为链表（Linked List），是一种通过指针将存储在内存中非连续地址的节点连接起来的数据结构，与顺序表（数组）不同，链表不需要预先分配连续的内存空间，而是通过每个节点中保存的指针域指向下一个节点的地址，从而在逻辑上形成线性关系，这种结构极大地提高了内存空间的利用率，特别是在数据量动态变化较大的场景中，其优势尤为明显。

节点结构与内存布局

链表的基本组成单元是节点（Node），每个节点至少包含两个部分：数据域（Data Field）和指针域（Next Field），数据域用于存储实际的数据元素，而指针域则存储指向下一个节点的内存地址，在单链表中，最后一个节点的指针域通常指向空值（NULL），标志着链表的结束，为了便于操作，链表通常维护一个头指针（Head Pointer），它指向链表中的第一个节点；若链表为空，则头指针指向 NULL。

链表的分类与特性

根据指针指向的不同,链表可以分为多种类型，其中最常见的是单链表、双向链表和循环链表，单链表每个节点只有一个指向后继的指针；双向链表每个节点既有指向后继的指针，也有指向前驱的指针，这使得双向遍历成为可能；循环链表则是将单链表或双向链表的尾节点指针重新指向头节点，形成一个闭环。

链式存储的主要特性包括：

1. 动态分配：内存空间在运行时动态分配，无需预先确定大小。
2. 非连续存储：逻辑上相邻的元素在物理上不一定相邻。
3. 随机访问困难：无法像数组那样通过下标直接访问第 $i$ 个元素，必须从头指针开始逐个遍历。
4. 插入删除高效：在已知节点位置的情况下，插入和删除操作仅需修改指针指向，时间复杂度为 $O(1)$，无需移动大量元素。

基本操作实现逻辑

插入操作

在链表中插入一个新节点时,关键在于调整指针的指向，假设要在节点 A 之后插入新节点 New，操作步骤如下：

1. 将 New 节点的指针域指向 A 的原后继节点。
2. 将 A 节点的指针域指向 New 节点。

   这一过程必须严格按照顺序执行，否则会导致链表断裂，丢失后续节点。

删除操作

删除节点 B 时，需要找到其前驱节点 A，然后执行以下操作：

1. 将 A 节点的指针域指向 B 的后继节点。
2. 释放 B 节点占用的内存空间（在支持手动内存管理的语言如 C/C++ 中）。

   同样，指针的重新链接必须在释放内存之前完成。

查找操作

由于链表不支持随机访问,查找第 $i$ 个元素或查找特定值必须从头节点开始，逐个遍历节点，直到找到目标或到达链表末尾，查找操作的时间复杂度通常为 $O(n)$。

优缺点分析

应用场景

链表特别适用于以下场景：

• 数据量不确定：当程序运行前无法预估数据规模时。
• 频繁增删：在列表中间频繁进行插入和删除操作，且不需要频繁随机访问的场景。
• 实现其他数据结构：如栈、队列、哈希表的链地址法解决冲突、图的邻接表表示等。

相关问题与解答

问题 1：为什么在单链表中删除指定节点的时间复杂度通常被认为是 $O(1)$，但在实际编程中往往需要 $O(n)$？

解答：

理论上，如果已经直接获得了待删除节点的指针（例如在遍历过程中当前指针正好指向该节点），删除操作本身只需修改前驱节点的指针并释放内存，时间复杂度为 $O(1)$，在大多数实际应用场景中，我们通常只知道要删除的“值”或“位置索引”，而不知道其物理地址，为了找到该节点，必须从头节点开始遍历链表，这个过程需要 $O(n)$ 的时间，单链表没有指向前驱节点的指针，因此即使找到了目标节点，也无法直接修改前驱节点的指针域，除非在遍历过程中同时记录前驱节点，综合查找和删除两个步骤，整体时间复杂度为 $O(n)$。

问题 2：双向链表相比单链表，在内存占用和操作复杂度上有哪些主要区别？

解答：

双向链表在每个节点中增加了一个指向前驱节点的指针域，因此其内存占用比单链表多出一部分（每个节点多一个指针的大小），在操作复杂度方面，双向链表的优势在于支持双向遍历，可以从头到尾，也可以从尾到头，这在需要反向查找或插入的场景下非常有用，在插入和删除操作中，双向链表可以更容易地访问前驱节点，无需像单链表那样额外维护一个前驱指针变量，代码逻辑在某些情况下更清晰，但代价是，每次插入或删除节点时，需要同时修改两个方向的指针（前驱和后继），操作步骤比单链表更复杂，出错概率略高，且需要更多的 CPU 周期来维护指针的一致性。