为什么需要链表 使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。 链表数组对比： 链表与数组的各种操作复杂度如下所示：
| 操作 | 链表 | 数组 |
|---|---|---|
| 查找 | O(n) | O(1) |
| 在头部插入/删除 | O(1) | O(n) |
| 在尾部插入/删除 | O(n) | O(1) |
| 在中间插入/删除 | O(n) | O(n) |
注意虽然表面看起来复杂度都是 O(n)，但是链表和数组在插入和删除时进行的是完全不同的操作。链表的主要耗时操作是历遍查找，删除和插入操作本身的复杂度是O(1)。数组查找很快，主要耗时的操作是拷贝覆盖。因为除了目标元素在尾部的特殊情况，数组进行插入和删除时需要对操作点之后的所有元素进行前后移位操作，只能通过拷贝和覆盖的方法进行。
##链表的定义 链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)
##如何去实现 Python的内建类型列表list底层是由C数组实现的，list在功能上更接近C++的vector（因为可以动态调整数组大小）。我们都知道，数组是连续列表，链表是链接列表，二者在概念和结构上完全不同，因此list不能用于实现链表。在C/C++中，通常采用“指针+结构体”来实现链表；而在Python中，则可以采用“引用+类”来实现链表
##链表的应用场景
1.linux内核中大量的链表
2.redis中的list结构使用双向链表实现
3.树的结构实现
4.nginx中内存池的实现
5.还有哈希表中也有部分结构链表实现
等等