链表是通过“指针”将一组零散的内存块串联起来的数据结构,相比数组就是使用一组连续的内存块来存储数据的数据结构。
常见的链表有:
- 单链表: 每个数据块只有一个指针指向下一节点的数据。其中有两个特殊的节点,一个是头节点,数据块是空的,只有一个指针指向下一节点;另一个节点是尾节点,他的特点是,指针是指向空地址 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。