链表

1、什么是链表

链表也是一种线性表，链表的内存结构是不需要一块连续的内存空间，是通过指针将一组零散的内存块串联起来使用
优点：插入、删除效率高（只需更改指针指向即可）
缺点：随机访问效率低（需要从链头到链尾遍历）

2、常用链表结构:

单链表：

a 每个节点只包含一个后继指针
b 单链表有两个特殊节点，首尾节点，首节点地址表示整条链表，尾节点的后继指针指向NULL

双向链表：

a 节点除了存储数据外，还有两个指针分别指向前一个节点地址（前驱指针prev）和下一个节点地址（后继指针next）
b 首节点的前驱指针和尾节点的后继指针都指向NULL

循环链表：

a 除了尾节点的后继指针指向首节点的地址外，其余和单链表一致
b 适合存储有循环特点的数据。如约瑟夫问题。

3、数组和链表对比

因为内存储存的区别，它们插入、删除和随机访问操作时间复杂度正好相反。
如何选择？
数组简单易用，在实现上使用连续的内存空间，可以借助CPU缓冲机制预读数组中的数据，所以访问效率高，而链表在内存中不是连续储存，所以对CPU缓存不友好，没办法预读，如果代码对内存的使用非常苛刻，就选择数组。