Java笔记 · · By/蜜汁炒酸奶

数据结构02-链表

什么是链表

  • 和数组一样是一种线性表。
  • 从内存结构来看,链表的内存结构是不连续的内存空间,是将一组零散的内存块串联起来,从而进行数据存储的数据结构。
  • 链表中的每一个内存块被称为结点Node。结点除了存储数据外,还需记录链上的下一个结点的地址,即后继指针next。

常用链表

单链表、循环链表、双向链表、双向循环链表

单链表

  • 每个结点只包含一个指针,即后继指针。
  • 单链表有两个特殊结点,即头结点尾结点。头结点用来记录链表的基地址,可以遍历得到整条链表。尾结点指向一个空地址 NULL,表示这是链表上最后一个结点。
  • 插入和删除结点的时间复杂度为O(1),查找的时间复杂度为O(n)。

循环链表

一种特殊的单链表。

  • 它跟单链表唯一的区别是尾结点指针是指向链表的头结点。
  • 循环链表的优点是从链尾到链头比较方便。适用于处理具有环型结构特点的数据,比如著名的约瑟夫问题。

双向链表

  • 结点除了存储数据外,还有两个指针分别指向前一个结点地址(前驱指针prev)和下一个结点地址(后继指针next)。
  • 头结点的前驱指向为空,尾结点指向为空。
  • 给定数据值查询/删除对应结点,双向和单链表的时间复杂度均是O(n);给定结点的查询/删除,双向O(1),单链表O(n)。

双向循环链表

首节点的前驱指针指向尾节点,尾节点的后继指针指向首节点。

用空间换时间的设计思想

对于执行较慢的程序,可以通过消耗更多的内存(空间换时间)来进行优化。
消耗过多内存的程序,可以通过消耗更多的时间(时间换空间)来降低内存的消耗。

数组和链表比较:

  • 链表插入、删除数据效率高,时间复杂度O(1),随机访问效率低,时间复杂度O(n)。
  • 数组插入、删除数据效率低,时间复杂度O(n),随机访问效率高,时间复杂度O(1)。

数组简单易用,在实现上使用的是连续的内存空间,可以借助 CPU 的缓存机制,预读数组中的数据,所以访问效率更高。而链表在内存中并不是连续存储,所以对 CPU 缓存不友好,没办法有效预读。

链表本身没有大小的限制,天然地支持动态扩容。

如果代码对内存的使用非常苛刻,那数组就更适合。

数组缺点

内存中没有足够的连续空间时,数组申请空间会失败,导致内存不足(out of memory)。

数组大小固定,当不够用时,需要扩容,一旦扩容就要进行数据复制,而这时非常费时。

链表缺点

内存消耗大,因为要消耗额外的空间存储指针信息。

对链表进行频繁的插入和删除操作,会导致频繁的内存申请和释放,容易造成内存碎片。Java语言中还可能会造成频繁的GC(Garbage Collection,垃圾回收)。

相关文章

参考资料

数据结构与算法之美

评论已关闭

example
C
蜜汁炒酸奶

当前处于试运行期间,可能存在不稳定情况,敬请见谅。

欢迎点击此处反馈访问过程中出现的问题