链表

链表是一种物理结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表与数组的区别

特性	数组	链表
内存结构	连续	非连续
大小	固定	动态可变
访问方式	随机访问(O(1))	顺序访问(O(n))
插入/删除	需要移动元素(O(n))	修改指针(O(1))
空间开销	只需存储数据	需要额外存储指针
缓存友好性	高	低

链表的分类

1. 按指针方向分类

• 单向链表：每个节点只有一个指针域，指向下一个节点
• 双向链表：每个节点有两个指针域，分别指向前驱和后继节点
• 循环链表：尾节点指针指向头节点，形成环状结构

2. 按实现方式分类

• 静态链表：使用数组实现的链表（如某些嵌入式系统中使用）
• 动态链表：通过动态内存分配实现的链表（最常见）

3. 按存储结构分类

• 普通链表：节点在内存中离散分布
• 块状链表：结合了数组和链表的特性，每个节点存储多个元素

4. 特殊类型链表

• 跳表(Skip List)：在链表基础上添加多级索引，提高查找效率
• 十字链表：用于存储稀疏矩阵的特殊链表结构
• 异或链表：使用异或运算减少双向链表的空间开销

5. 按是否有序分类

• 有序链表：节点按特定顺序排列
• 无序链表：节点顺序无特定要求

链表的数据结构

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}