【数据结构】链表(单链表实现+详解+原码)

链表

一、链表的本质

• 线性数据结构（逻辑连续），物理存储非连续，通过节点引用（指针）串联
• 最小单元：节点（包含数据域 + 引用域）

二、链表的类型

• 单链表
  • 节点包含：数据 + 下一个节点的引用
  • 特点：只能从头部向尾部单向遍历，尾节点引用指向null
• 双链表
  • 节点包含：数据 + 上一个节点的引用 + 下一个节点的引用
  • 特点：可双向遍历，插入/删除时需同时维护前驱和后继引用
• 循环链表
  • 分类：单向循环链表（尾节点引用指向头节点）、双向循环链表（首尾节点相互指向）
  • 特点：无首尾边界，可循环遍历，适合环形业务场景

三、链表的核心操作

• 插入节点
  • 分类：头部插入、尾部插入、指定位置插入
  • 核心：修改节点引用关系，无需移动其他元素
• 删除节点
  • 分类：删除头节点、删除尾节点、删除指定节点
  • 核心：找到前驱节点，修改引用跳过目标节点（单链表）
• 遍历
  • 方式：从头节点开始，依次跟随引用遍历至结束（null/头节点）
  • 特点：无法随机遍历，只能顺序访问
• 查找
  • 方式：遍历链表，匹配目标数据/节点
  • 特点：无下标支持，需逐个比对

四、链表的核心特性

• 访问效率：O(n)（需遍历，无随机访问能力）
• 插入/删除效率：O(1)（找到目标位置后，仅修改引用）
• 内存特性：按需分配，无空间浪费，无需预分配容量
• 适用场景：频繁插入/删除、数据量不固定、无需频繁查询的场景

五、链表与数组的核心差异（关键对比）

• 存储结构：数组物理连续；链表物理非连续、逻辑连续
• 访问方式：数组支持下标随机访问；链表仅支持顺序遍历
• 空间效率：数组易浪费空间（预分配）；链表内存利用率高
• 操作效率：数组查询快、插入删除慢；链表插入删除快、查询慢

class Node:
    def __init__(self, data, next=None, prev=None):
        self.data = data
        self.next = next
        self.prev = prev

class Node {
  data: any;
  next: Node | null;
  prev: Node | null;

  constructor(data: any) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}