本章内容

链表定义

链表是一种线性表数据结构，它通过指针将一组零散的内存块串（节点）连接在一起组成的存储结构。每个节点包含两部分内容：节点存储的数据和节点指向下一个节点的指针（next）。

单链表

单链表存储结构，如图所示：

其中：

• data：单链表节点存储的数据。
• next：单链表节点指向下一个节点的指针。

单链表中有两个比较特殊的节点：

• 头节点：即链表的第一个节点，用来记录链表的基地址。
• 尾节点：即链表的最后一个节点，它指向一个空地址（NULL）。

单链表操作

插入或删除节点

在链表中，插入或者删除一个节点时，由于链表不是连续的存储空间，不需要为保持内存的连续性而迁移结点，因此，在链表中插入和删除一个节点非常高效。如图所示：

其中：

• 向指定节点后插入节点时，将指定节点的next指针指向新节点、新节点的next指针指向指定节点的后继节点。时间复杂度为O(1)。
• 向指定节点前插入节点时，需要从头结点开始向后遍历单链表中的所有节点，直到找到指定节点的前一个节点，再将指定节点的前一个节点的next指针指向新节点，新节点的next指针指向指定节点。时间复杂度为O(n)。
• 同理，删除指定节点的时间复杂度为O(n)，删除指定节点的后继节点的时间复杂度为O(1)。

随机访问节点

在链表中，随机访问第n个节点时，需要根据指针遍历链表中的所有节点，直到找到目标节点。因此，链表随机访问的时间复杂度为O(n)。

循环链表

循环链表是一种特殊的单链表。它与单链表唯一的区别是尾节点指针不是指向空地址，而是指向链表的头结点。如图所示：

循环链表与单链表相比，其主要优势是从链表的尾节点到头节点非常的方便。

双向链表

与单向表不同的是，双向链表中的每个节点存在两个指针，分别是指向前驱节点的prev指针和指向后继节点的next指针。如图所示：

其中，双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。因此，存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，使得双向链表的操作更加灵活。

双向链表操作

向双向链表中插入节点

如图所示：

向节点x的前面插入新节点temp。时间复杂度为O(1)。

插入步骤：

• 1）将节点x的prev指针指向新节点temp。
• 2）将新节点temp的next指针指向节点x。
• 3）将节点x的prev指针指向的节点head的next指针指向新节点temp。
• 4）将新节点temp的prev指针指向节点x的prev指针指向的节点head。

注意：

• 如果向双向链表的头部插入新节点temp，只需将新节点的next指针指向头节点head、头节点head的prev指针指向新节点temp即可。时间复杂度为O(1)。
• 如果向双向链表的尾部插入新节点temp，只需将新节点的prev指针指向尾节点tail、尾节点tail的next指针指向新节点temp即可。时间复杂度为O(1)。

删除目标节点

如图所示：

删除双向链表中的目标节点x。时间复杂度为O(n)。

删除步骤：

• 1）遍历双向链表中的所有节点找到目标节点x。
• 2）将节点x的prev指针指向的节点head的next指针指向节点x的next指针指向的节点y。
• 3）将节点x的next指针指向的节点y的prev指针指向节点x的prev指针指向的节点head。

删除目标节点的相邻节点

如图所示：

删除双向链表中的目标节点x的相邻节点y。时间复杂度为O(1)。

删除步骤：

• 1）将节点x的prev->prev指针指向的节点head的next指针指向节点x。
• 2）将节点x的prev指针指向的节点x的prev->prev指针指向节点head。

注意：目标节点是x，只能通过目标节点寻找其他节点。

随机访问节点

随机访问节点的时间复杂度与单向链表一样，为O(n)。

总之，双向链表的核心思想是用空间换时间。

数组与链表对比

数组与链表的主要区别：

• 1）数组随机访问的时间复杂度为O(1)，插入、删除的时间复杂度为O(n)；而链表随机访问的时间复杂度为O(n)，插入、删除的时间复杂度为O(1)。
• 2）数组使用连续的内存空间进行存储，可以借助CPU的缓存机制，预读数组中的数据，访问效率更高；而链表在内存中并不是连续存储，对CPU缓存不够友好，无法有效预读。
• 3）数组使用连续的、固定大小的内存空间进行存储，初始容量声明过大，容易造成空间浪费，初始容量声明过小，会导致频繁扩容，影响性能；而链表本身没有大小的限制，天然地支持动态扩容。

【阅读推荐】

想了解常用算法（如：快速排序、堆与堆排序、二分查找、动态规划、广度优先搜索算法（BFS）、深度优先搜索算法（DFS）等）的童鞋请移步->算法系列合集（持续更新中）。

更多内容持续更新中......

【作者简介】

一枚热爱技术和生活的老贝比，专注于Java领域，关注【南秋同学】带你一起学习成长～