Skip to content

链表理论基础

1. 链表的定义

  • 一种通过指针串联在一起的线性结构
  • 每一个节点由两部分组成,分别是数据域和指针域(存放指向下一个节点的指针)
  • 第一个节点称为链表的头结点即 head,最后一个节点的指针域指向空指针

2. 链表的类型

  • 单链表

如定义所示。

  • 双链表

每一个节点有两个指针域,可分别指向上一个节点和下一个节点。

即说明能做到向前查询和向后查询。

  • 循环链表

即链表首尾是相连的。可以用来解决约瑟夫环问题。

3. 链表的存储方式

  • 数组是在内存中是连续分布的,但是链表在内存中可不是连续分布的
  • 链表是通过指针域的指针链接在内存中各个节点,即链表中的节点在内存中不是连续分布的,而是散乱分布在内存中的某地址上
  • 其内存的分配机制取决于操作系统的内存管理

4. 链表的定义

Go
type ListNode struct {
    Val  int
    Next *ListNode
}

5. 链表的操作

链表操作 操作的解释
删除节点
注意:节点的删除并没有释放被删除节点的内存。
添加节点

6. 性能分析

插入/删除 查询 适用场景
数组 \(O(n)\) \(O(1)\) 数据量固定,频繁查询,较少增删
链表 \(O(1)\) \(O(n)\) 数据量不固定,频繁增删,较少查询