【数据结构】线性数据结构——链表

1. 定义

链表是一种线性数据结构，由多个节点（Node）组成。每个节点存储数据和指向下一个节点的指针。与数组不同，链表的节点不需要在内存中连续存储。

2. 特点

• 动态存储： 链表的大小不固定，可以动态增加或减少节点，灵活性强。

• 非连续存储： 节点的内存地址不连续，通过指针（或引用）连接，适合频繁插入和删除操作。

• 顺序访问： 需要从头节点依次遍历，无法像数组那样通过索引直接访问元素。

• 占用额外空间： 每个节点需要额外存储一个指针（或引用），存储效率略低于数组。

3. 类型

根据结构的不同，链表可以分为以下几种：

• 单链表（Singly Linked List）： 每个节点包含数据和指向下一个节点的指针。只能从头到尾顺序遍历。

• 双链表（Doubly Linked List）： 每个节点包含数据、指向下一个节点的指针和指向前一个节点的指针。支持双向遍历，操作更灵活，但占用更多内存。

• 循环链表（Circular Linked List）： 链表的最后一个节点指向头节点，形成一个环。可单向或双向，常用于需要循环处理的场景。

• 带头节点的链表： 在链表开始部分增加一个特殊的头节点，不存储数据，仅用于简化边界情况的处理。

4. 主要操作

• 插入节点： 头部插入：将新节点的指针指向当前头节点，再更新头指针。尾部插入： 遍历到尾节点，将尾节点的指针指向新节点。中间插入： 调整相邻节点的指针。时间复杂度： O(1)（头部插入），O(n)（尾部或中间插入）。

• 删除节点： 修改前一个节点的指针，使其指向被删除节点的下一个节点。
  如果是尾节点，需更新尾指针。时间复杂度：O(1)（删除头节点），O(n)（删除其他节点）。

• 查找节点： 从头节点开始逐个比较，直到找到目标节点或到链表末尾。时间复杂度：O(n)。

• 遍历链表： 从头节点开始依次访问每个节点，直到链表结束。

5. 优缺点

优点： 动态扩展：不需要预先分配存储空间。/ 高效插入和删除：不需要移动数据，只需调整指针。

缺点： 顺序访问：访问速度慢，需从头遍历到目标节点。/ 占用额外空间：每个节点需要存储一个指针，增加内存开销。/ 操作复杂：指针处理复杂，容易出错。

6. 应用场景

• 动态数据存储：适用于大小不固定的数据集合。
• 实现其他数据结构：栈、队列、哈希表中的链地址法等常用链表实现。
• 需要频繁插入和删除的场景：如操作系统中的任务调度、内存分配管理。