链表
目录
定义
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
详解
- 链表的存在就是为了解决数组的增删复杂耗时，内存占用较大的问题。它并不需要一块连续的内存空间，它通过指针将一组零散的内存块串联起来。
- 根据指针的不同，有单链表，双向链表，循环链表之分。
- 数组和链表是相互补充的一对数据结构。
优点：
- 操作指针即可删除该元素或者插入新元素，时间复杂度 O(1)。
- 链表因为元素不连续，而是靠指针指向下一个元素的位置，本身没有大小的限制，不存在数组的扩容问题，所以天然地支持动态扩容。
- 空间没有限制
- 插入删除元素很快
缺点：
- 因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问。
- 由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。
- 同时内存不连续，容易造成内存碎片。
- 存取速度很慢
对比
数组
数组存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为O(1)；数组的特点是：寻址容易，插入和删除困难。
链表
链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O（N）。链表的特点是：寻址困难，插入和删除容易。
哈希表
那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？这就是我们要提起的哈希表。
分类
- 单向链表 一个节点指向下一个节点。
- 双向链表 一个节点有两个指针域。
- 循环链表 能通过任何一个节点找到其他所有的节点，将两种(双向/单向)链表的最后一个结点指向第一个结点从而实现循环。