数据结构 - 链表详解一 - 链表的介绍

一. 为什么要学习链表

我们已经学习了顺序表了，在学习的时候发现顺序表的功能很多，所以我们为什么还要学习链表呢，学习链表有什么用吗？ 下面我将通过几个方面去研究一下

1. 动态数据操作

顺序表（如数组）通常在内存中占据连续的空间，并且在创建时其大小就已经确定。这意味着如果顺序表已满，你需要重新分配一个更大的空间来存储更多的数据，这个过程可能涉及复制整个表到一个新的位置，这是一个成本较高的操作。而链表由于其非连续的存储方式，可以在不需要整体复制数据的情况下动态地添加或删除节点，这对于数据量动态变化的应用非常有用。

2. 高效的插入和删除操作

在顺序表中，插入或删除元素（特别是在表的中间）通常需要移动一部分元素以维护元素的连续性，这可能导致较高的时间成本。相比之下，链表的插入和删除操作只需要改变相应节点的指针，因此时间成本通常是固定的，这使得链表在需要频繁进行这类操作的场景下非常高效。

3. 不预设固定大小

链表不需要在构建时预设大小，它可以根据需要随时扩展。这一点对于不确定数据量的场景非常有利，而顺序表需要预设一个固定的大小，或者使用诸如动态数组这样的结构来允许动态扩容，但这仍可能涉及到复制等成本高昂的操作。

4. 多样的变体

链表有多种变体，包括单向链表、双向链表、循环链表等，每种类型的链表都有其特定的优势。例如，双向链表允许从两个方向遍历，这使得某些特定操作更加高效。了解这些变体可以帮助你更好地解决特定的编程问题。

5. 深入理解数据结构和指针操作

链表的操作往往涉及复杂的指针操作，学习链表可以帮助你更好地理解指针和动态内存分配的概念，这对深入学习更复杂的数据结构和算法非常有帮助。

二. 链表的概念

链表（Linked List）是一种常用的基础数据结构，它通过每个元素指向下一个元素的方式组织数据。相对于数组，链表在插入和删除数据时可以提供更高的效率，因为这些操作不需要移动链表中的其他元素。以下是链表的一些基本特征：

1. 节点：

链表由节点组成，每个节点包含数据部分和指向列表中下一个节点的链接（指针或引用）。

2. 类型：
     单向链表：节点只包含到下一个节点的链接。
     双向链表：节点包含两个链接，一个指向前一个节点，一个指向下一个节点，这样可以从两个方向遍历链表。
     循环链表：最后一个节点指向第一个节点的链接，形成一个闭环。

3. 优点：
     动态大小：链表的大小可以根据需要动态增长或减少，不需要在创建时确定大小。
     插入和删除效率高：不需要移动数据，只需要改变指针。

4. 缺点：
     高内存开销：每个节点不仅要存储数据，还要存储至少一个链接。
     访问速度慢：访问链表中的元素需要从头开始遍历，因此访问时间可能较长，特别是对于长链表。

链表在物理存储结构和逻辑结构上的表现是其核心特点之一，这也是它与数组等其他线性数据结构的主要区别所在。

链表的结构

1. 什么是节点

在链表这种数据结构中，"节点"（Node）是链表的基本组成单元。一个节点通常包含以下两个主要部分：

1. 数据域：这部分存储了节点所持有的数据。在不同的应用中，这个数据可以是任何类型，如整数、字符串、复杂的对象等。

2. 指针域（或引用域）：这部分指向链表中的下一个节点，从而将多个节点连接起来形成链表。在双向链表中，节点不仅会有指向下一个节点的指针，还可能有指向前一个节点的指针，使得可以双向遍历链表。

注意：链表通过这些节点的连接（通常是单向或双向链接）组织数据。节点在内存中是散乱分布的，它们是通过地址来寻找下一个节点。这和数组的连续存储有着很大的区别。

2. 链表的逻辑结构

链表的逻辑结构是线性的，即元素之间是一对一的关系。每个元素（通常称为“节点”）包含两部分：数据和指向列表中下一个元素的指针（在双向链表中，还可能有指向前一个元素的指针）。这种结构使得元素之间像是一串连续的链条，每个链节直接指向下一个，从而形成一个序列。

逻辑上，链表可以很容易地进行扩展，只需要添加或移除节点即可，而不需要重新组织整个结构。这使得链表在需要频繁插入和删除操作的应用中特别有用。

注意：此时的链表是我们人为想象出来的，是为了让大家更好的去理解链表，现实中并不存在箭头，并且现实中每一个节点的地址都不一定连续，而且可能会离得很远。 

3. 链表的物理存储结构

在物理存储上，链表的节点不需要像数组那样在内存中连续存储。每个节点只需有足够的内存来存储其数据和指针即可，这些节点可以散布在内存的任何地方。节点之间的关系通过指针来维护，这些指针指向内存中的具体地址。

这种分散的存储方式带来了几个好处：

• 动态大小：链表的大小可以根据需要动态增加或减少，不受初始内存分配的限制。
• 高效的插入和删除：添加或删除节点不需要移动其他元素，只需修改一些指针即可。

但是，这也带来了一些缺点：

• 增加了内存开销：每个节点需要额外存储指针。
• 访问效率低：由于节点在内存中不连续，访问特定元素时可能需要从头节点遍历到目标节点，这使得随机访问性能较差。

三. 链表的介绍

链表的结构多种多样：

1. 带头与不带头的链表

带头节点的链表

• 定义：带头节点的链表拥有一个特殊的节点，通常称为“头节点”或“哨兵节点”，位于链表的最前端。这个节点不存储任何实际意义的数据（或者说其数据部分通常被忽略），它的主要作用是简化链表操作，特别是插入和删除操作，因为这样链表的每个节点都有一个前驱节点，使得链表操作中的特殊情况（如插入到链表头部）变得统一。
• 优点：操作简化。每个节点都有相同的插入和删除操作逻辑，无需对第一个元素特殊处理。
• 缺点：轻微的空间浪费（一个额外的节点）和初始化复杂性。

不带头节点的链表

• 定义：不带头节点的链表的第一个元素直接存储数据，链表的头指针直接指向第一个数据节点。在这种链表中，对第一个节点的操作可能需要特殊处理，例如在链表头部插入或删除节点时，可能需要更新头指针。
• 优点：不浪费空间，结构简单直观。
• 缺点：插入和删除操作时，需要考虑多种情况，特别是涉及链表头部的操作。

总结：带头节点的链表虽然稍微复杂一点和占用更多空间，但它可以大大简化编程时对特殊情况的处理，特别是在进行大量插入和删除操作时。不带头节点的链表则更加简洁，适合空间要求较高或数据结构较简单的情况。 

2. 单向与双向的链表

单向链表

结构：

• 单向链表由一系列节点组成，每个节点包含两部分：数据域和指针域。
• 数据域用于存储数据（如整数、字符串等），而指针域存储指向链表中下一个节点的指针。
• 链表的结束由一个指向null的指针标记，这表示没有更多的节点。

优点：

• 简单性：单向链表的结构相对简单，操作（如添加和删除节点）较为直接。
• 空间效率：与双向链表相比，单向链表节省了指向前一个节点的指针空间。

缺点：

• 访问限制：单向链表只能向一个方向遍历，从第一个节点到最后一个节点。这意味着回溯（如返回上一个节点）需要重新从头开始遍历。
• 操作限制：某些操作，如在给定节点之前插入一个新节点或删除一个特定节点，可能更复杂，需要额外的步骤来维护链表的完整性。

双向链表（Doubly Linked List）

结构：

• 双向链表中的每个节点都有两个指针：一个指向下一个节点，另一个指向前一个节点。
• 这种结构允许链表从两个方向进行遍历：从前到后和从后到前。
• 和单向链表一样，双向链表的起始和结束节点分别指向null。

优点：

• 灵活性：可以双向遍历，方便执行诸如从尾到头的遍历等操作。
• 操作方便：在节点前或节点后插入和删除操作更加直接，因为可以通过前驱和后继指针直接访问相关节点。

缺点：

• 空间开销：每个节点需要额外的空间来存储前驱指针，相较于单向链表，这增加了内存使用。
• 实现复杂性：在进行插入和删除操作时，需要更新两个指针，这可能导致错误发生的机会增多，实现也更为复杂。

应用场景

• 单向链表适用于数据结构简单且主要进行单向遍历的应用中，如实现简单的队列。
• 双向链表更适用于需要频繁进行双向遍历和复杂元素插入或删除的场合，如实现一个高效的双向队列（deque）或在UI编程中管理层次结构的元素。

3. 循环与非循环的链表

非循环链表（Non-Circular Linked List）

结构：

• 在非循环链表中，节点按顺序连接，链表的开始节点（头节点）和结束节点（尾节点）都明确指定。
• 尾节点的指针域指向null，表示链表的终结。

优点：

• 简单直观：对于大多数常规用途，非循环链表的结构直观易懂，便于实现和维护。
• 灵活性：容易扩展和修改，适合大多数动态数据集的管理。

缺点：

• 单向访问限制：在单向非循环链表中，只能从头到尾进行遍历，不便于回溯。
• 尾部操作限制：在需要频繁访问或修改尾部元素的应用中，可能需要遍历整个链表才能到达尾部。

循环链表（Circular Linked List）

结构：

• 在循环链表中，链表的尾节点不是指向null，而是指向头节点，形成一个闭环。
• 这种结构可以是单向的也可以是双向的，双向循环链表的每个节点都有指向前一个和后一个节点的指针，尾节点的下一个指针指向头节点，头节点的前一个指针指向尾节点。

优点：

• 无终点遍历：循环链表允许持续遍历，这对于需要周期性访问数据的应用非常有用，例如操作系统的任务调度。
• 统一操作：所有节点的插入和删除操作都统一，没有特殊的头尾处理逻辑。

缺点：

• 复杂性：在实现时需要小心处理环形结构的逻辑，特别是在插入和删除节点时，防止打破循环结构。
• 错误风险：如果遍历操作没有正确管理，可能导致无限循环。

应用场景

• 非循环链表广泛用于实现数据集合管理、栈、队列等基本数据结构，在这些应用中，通常只需要从头到尾的顺序访问。
• 循环链表特别适用于需要循环遍历数据的场景，如网络游戏的玩家循环、应用程序的轮询调度等。它也常用于实现高效的资源共享，比如多线程程序中的资源分配。