链表理论基础

1. 链表的定义

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

2. 链表的类型

• 单链表

如定义所示。

• 双链表

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

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

• 循环链表

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

3. 链表的存储方式

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

4. 链表的定义

Go

type ListNode struct {
    Val  int
    Next *ListNode
}

5. 链表的操作

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

6. 性能分析

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