链表
链表，也称为链式存储。链表的 内存是不连续的，不像数组那样连续存储在内存中，而是由一系列 节点 组成
节点
每个节点包含两部分：
数据域（存储实际值）指针域（指向下一个节点的地址）
如下图：
分类
单链表
双向链表
循环链表
单链表
单链表是最简单的链表
指针
除了最后一个结点，每个结点的指针，指向下一个结点
不带头结点的单链表（很少）
如下图，没有头结点的单链表，很少
单链表（默认带头结点）
头结点：第一个有效结点之前的那个结点，存放链表首地址。
作用：方便对链表的操作，如：在链表头部执行删除结点、插入结点。
头指针：指向 头结点 的 指针变量
首结点
第一个有效结点(存有数据的结点）
尾结点
尾结点：最后一个有效结点。尾结点的指针域指向 null，表示链表结束。
优点
不需要连续空间，对内存友好。可以零散分布，内存利用率更高
插入、删除效率高。不需要移动大量元素，只需要修改指针，时间复杂度
O (1)（不算找到位置的时间）适合频繁增删的场景
长度动态可变，可随时扩展。不像数组那样，要预先设置大小
缺点
- 耗费更多空间，存储下一个元素的地址
- 随机访问效率极低，时间复杂度：
O (n)（要访问第k个节点，必须从头节点开始，顺着指针逐个遍历到第 k 个，不能像数组那样，通过索引访问）。 - 遍历效率低于数组，链表的节点是不连续的，分散在内存各处，每次访问节点都要重新寻址
特点
n个结点离散分布，彼此通过指针相联系。
除头结点和尾结点外，每个结点 只有一个前驱结点 和 一个后继结点。头结点没有前驱结点，尾结点没有后继结点。
头结点不存放数据，只存放链表首节点的地址。其头结点的数据类型和首结点类型一样
对比数组
| 操作 | 数组（顺序表） | 单链表 |
|---|---|---|
| 插入/删除 | 需移动大量元素，效率低 O(n) | 仅改指针，效率高 O(1) |
| 存储空间 | 必须连续，预先固定大小 | 可不连续，动态申请 |
| 长度变化 | 固定或扩容麻烦 | 随时增减，灵活 |
| 按序号访问 | 随机访问，O(1) | 只能从头遍历，O(n) |
单链表的操作
头部插入
把新节点添加到链表最开头（注意：头结点的指针指向新节点）
操作：新节点的指针指向原头节点，再把链表的头结点的指针指向新节点。
时间复杂度： O(1)，无需遍历，是单链表最高效的插入方式。
头部删除
移除链表第一个节点（不是头结点），让第二个节点成为新的头节点。
操作：直接把head指针指向第二个节点
时间复杂度： O(1)，无需遍历，仅修改head指针的指向，
尾部插入
把新节点添加到链表的末尾，成为新的尾节点
操作：遍历找尾节点（从head开始，顺着每个节点的next指针往后走，直到找到当前尾节点），把尾节点指针指向新节点
时间复杂度：O(n)，必须遍历整个链表找到尾节点，节点数越多，遍历步数越多（最多走 n 步）。
尾部删除
移除链表的最后一个节点，让倒数第二个节点成为新的尾节点。
操作： 遍历找倒数第二个节点（从头结点开始遍历，直到找到倒数第二个节点），把倒数第二个节点的指针置为 null
时间复杂度：O(n)，必须遍历整个链表找到尾节点，节点数越多，遍历步数越多（最多走 n-1 步）。
中间位置插入
删除节点
总结
链式存储的空间密度 <1，因为存储指向下一个节点的指针
题
设有一个包含n个元素的有序线性表。在等概率情况下删除其中的一个元素，若采用 顺序存储结构，则平均需要移动（）个元素；若采用 单链表存储，则平均需要移动（）个元素。
A、1
B、(n-1)/2
C、logn
D、n
A、0
B、1
C、(n-1)/2
D、n/2
答案
B
A，因为是单链表，不需要移动元素，只需要改指针