链表是通过“指针”将一组零散的内存块串联起来的数据结构，相比数组就是使用一组连续的内存块来存储数据的数据结构。
常见的链表有：
- 单链表： 每个数据块只有一个指针指向下一节点的数据。其中有两个特殊的节点，一个是头节点，数据块是空的，只有一个指针指向下一节点；另一个节点是尾节点，他的特点是，指针是指向空地址 NULL。
- 循环链表： 循环链表是，每个数据块都有一个指针指向下一节点，尾节点的指针指向头节点，另有一个单独的头指针指向开头。
- 双链表： 双链表是在单链表的基础上，在每个数据块节点上增加一个指针指向上一节点。
- 双向循环链表：双向循环链表是每个数据块都有两个指针，一个向前指向，一个向后指向，另有一个单独的指针指向一个数据块节点，这个指针是头指针。
性能
链表的随机访问性能是 O(n),数组是 O(1)。链表的插入、删除操作的性能是 O(1)，数组是 O(n)。
这里的链表，插入，删除，是指知道要插入的点，删除的点的指针，比如单链表插入时知道插入点上一节点的指针时，通过改变指针的指向就可以完成 O(1) 时间内的数据插入，删除同理。
若是单链表删除时，不知道指向要删除的具体节点的指针，那么就要在删除前先进行随机访问，那么性能就是 O(n)。
对于有序双向链表，查询效率会比单链表高一点，因为我们可以记录上次查找的位置 P，每次查询时，根据要查询的值与 P 的大小关系，决定往前还是往后查找，所以平均只需要查找一般的数据。
在 Java 语言中，LinkedHashMap 这个容器，他的实现原理就用到了双向链表这个数据结构。
数组 VS 链表
数组简单易用，在实现上是使用连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中不是连续存储，对 CPU 缓存不友好，没办法有效预读。
但数组的特点也是它的不足，他的内存空间是固定的，如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致内存不足(out of memory)，例如如果现在系统由 100M 不连续的内存空间，声明 100M 数组就会失败，另外到数组扩容时，复制原数组的内容到新数组也很费时。这就是数组和链表最大的区别。
另外如果我们的代码对内存使用非常苛刻，那应该使用数组，比如安卓之类的，因为链表需要维护额外的空间去存储指针。而且对链表进行频繁的插入、删除操作，还对导致频繁的内存申请和释放，容易造成内存碎片。如果是 Java 语言，就可能导致频繁的 gc。
网友评论