刷过力扣的肯定对单链表非常熟悉力扣上的单链表节点定义如下class ListNode { int val; ListNode next; ListNode(int x) { val x; } }这仅仅是一个最简单的单链表节点方便力扣出算法题来考你。而在实际编程中我们使用的链表节点通常会稍微复杂一些大致如下class NodeE { E val; NodeE next; NodeE prev; Node(NodeE prev, E element, NodeE next) { this.val element; this.next next; this.prev prev; } }主要区别体现在以下两个方面1、编程语言标准库一般都会提供泛型即你可以指定val字段为任意类型而力扣的单链表节点的val字段只有 int 类型。2、编程语言标准库一般使用的都是双链表而非单链表。单链表节点只有一个next指针指向下一个节点而双链表节点有两个指针prev指向前一个节点next指向下一个节点。有了prev前驱指针链表便支持双向遍历但由于需要额外维护一个指针增删查改时会稍微复杂一些。为什么需要链表前面介绍了 数组顺序存储的底层原理说白了就是一块连续的内存空间只要拿到这块内存空间的首地址就能直接通过索引计算出任意位置的元素地址。链表则不同一条链表并不需要一整块连续的内存空间来存储元素。链表的元素可以分散在内存中的各个角落通过每个节点上的next, prev指针将零散的内存块串联起来形成一个链式结构。这样做的好处很明显。首先它能有效提高内存的利用效率链表的节点不需要紧挨在一起只要有内存new 出来一个节点就能直接用对操作系统来说非常友好。另一个好处在于链表的节点需要时接上、不需要时拆掉即可完全不用考虑扩容缩容和数据搬移的问题。理论上讲链表没有容量限制除非把所有内存都占满不过这几乎不可能。当然有优势就必然有局限。数组最大的优势是支持通过索引快速访问元素而链表恰恰做不到这一点。这个不难理解吧因为元素并不是紧挨着的所以如果你想要访问第 3 个链表元素你就只能从头结点开始往顺着next指针往后找直到找到第 3 个节点才行。上面是对链表这种数据结构的基本介绍接下来我们就结合代码实现单/双链表的几个基本操作。单链表的基本操作class ListNode { int val; ListNode next; ListNode(int x) { val x; } } // 输入一个数组转换为一条单链表 ListNode createLinkedList(int[] arr) { if (arr null || arr.length 0) { return null; } ListNode head new ListNode(arr[0]); ListNode cur head; for (int i 1; i arr.length; i) { cur.next new ListNode(arr[i]); cur cur.next; } return head; }查/改单链表的遍历/查找/修改访问单链表的每一个节点并打印其值可以这样写// 创建一条单链表 ListNode head createLinkedList(new int[]{1, 2, 3, 4, 5}); // 遍历单链表 for (ListNode p head; p ! null; p p.next) { System.out.println(p.val); }类似的如果是要通过索引访问或修改链表中的某个节点也只能用 for 循环从头结点开始往后找直到找到索引对应的节点然后进行访问或修改。这个操作的最坏时间复杂度是 O(n)其中 n 是链表的长度。增在单链表头部插入新元素我们会持有单链表的头结点所以只需要将插入的节点接到头结点之前并将新插入的节点作为头结点即可。// 创建一条单链表 ListNode head createLinkedList(new int[]{1, 2, 3, 4, 5}); // 在单链表头部插入一个新节点 0 ListNode newNode new ListNode(0); newNode.next head; head newNode; // 现在链表变成了 0 - 1 - 2 - 3 - 4 - 5这个操作的时间复杂度是 O(1)。在单链表尾部插入新元素// 创建一条单链表 ListNode head createLinkedList(new int[]{1, 2, 3, 4, 5}); // 在单链表尾部插入一个新节点 6 ListNode p head; // 先走到链表的最后一个节点 while (p.next ! null) { p p.next; } // 现在 p 就是链表的最后一个节点 // 在 p 后面插入新节点 p.next new ListNode(6); // 现在链表变成了 1 - 2 - 3 - 4 - 5 - 6这个操作的时间复杂度是 O(n)因为需要先遍历到链表尾部。当然如果我们持有对链表尾节点的引用那么在尾部插入新节点的操作就会变得非常简单不用每次从头去遍历了。这个优化会在后面具体实现双链表时介绍。在单链表中间插入新元素这个操作稍微有点复杂我们要先找到要插入位置的前驱节点然后操作前驱节点把新节点插入进去// 创建一条单链表 ListNode head createLinkedList(new int[]{1, 2, 3, 4, 5}); // 在第 3 个节点后面插入一个新节点 66 // 先要找到前驱节点即第 3 个节点 ListNode p head; for (int i 0; i 2; i) { p p.next; } // 此时 p 指向第 3 个节点 // 组装新节点的后驱指针 ListNode newNode new ListNode(66); newNode.next p.next; // 插入新节点 p.next newNode; // 现在链表变成了 1 - 2 - 3 - 66 - 4 - 5这个操作的时间复杂度是 O(n)因为需要先找到插入位置的前驱节点。删在单链表中删除一个节点删除一个节点时首先要找到它的前驱节点然后把这个前驱节点的next指针指向被删除节点的下一个节点这样就能将被删除节点从链表中摘除。// 创建一条单链表 ListNode head createLinkedList(new int[]{1, 2, 3, 4, 5}); // 删除第 4 个节点要操作前驱节点 ListNode p head; for (int i 0; i 2; i) { p p.next; } // 此时 p 指向第 3 个节点即要删除节点的前驱节点 // 把第 4 个节点从链表中摘除 p.next p.next.next; // 现在链表变成了 1 - 2 - 3 - 5这个操作的时间复杂度是 O(n)因为需要先找到被删除节点的前驱节点。在单链表尾部删除元素这个操作比较简单找到倒数第二个节点然后把它的next指针置为 null 就行了// 创建一条单链表 ListNode head createLinkedList(new int[]{1, 2, 3, 4, 5}); // 删除尾节点 ListNode p head; // 找到倒数第二个节点 while (p.next.next ! null) { p p.next; } // 此时 p 指向倒数第二个节点 // 把尾节点从链表中摘除 p.next null; // 现在链表变成了 1 - 2 - 3 - 4这个操作的时间复杂度是 O(n)因为需要先遍历到倒数第二个节点。在单链表头部删除元素这个操作比较简单直接把head移动到下一个节点就行了// 创建一条单链表 ListNode head createLinkedList(new int[]{1, 2, 3, 4, 5}); // 删除头结点 head head.next; // 现在链表变成了 2 - 3 - 4 - 5这个操作的时间复杂度是 O(1)。不过可能有读者疑惑之前那个旧的头结点1的next指针依然指向节点2这样会不会造成内存泄漏不会的。节点1指向其他节点并没有关系只要没有其他引用指向这个节点1它就能被垃圾回收器回收掉。不过要注意这种「自动回收」只适用于 Java、Go、Python、JavaScript 这类带有垃圾回收GC的语言。C/C 没有 GC被摘除的节点必须手动free/delete释放否则就会造成内存泄漏所以上面 C/C 版本的代码里我都显式释放了被删除的节点。当然如果你愿意显式把节点1的next指针置为 null这也是个很好的习惯在其他场景中或许能避免指针错乱带来的潜在问题。显式地把待删除节点的 next 指针置为 null 了链表的增删查改操作确实比数组复杂。这是因为链表的节点并非紧挨在一起要增删一个节点必须先找到它的前驱和后驱节点进行协同再通过指针操作将其插入或删除。上面给出的代码还只是最简单的例子你会发现头部、尾部、中间增删元素的代码各不相同。若要实现一个真正可用的链表还需考虑诸多边界情况比如链表可能为空、前驱或后驱节点可能为空等这些情况都必须保证不出错。双链表的基本操作class DoublyListNode { int val; DoublyListNode next, prev; DoublyListNode(int x) { val x; } } DoublyListNode createDoublyLinkedList(int[] arr) { if (arr null || arr.length 0) { return null; } DoublyListNode head new DoublyListNode(arr[0]); DoublyListNode cur head; // for 循环迭代创建双链表 for (int i 1; i arr.length; i) { DoublyListNode newNode new DoublyListNode(arr[i]); cur.next newNode; newNode.prev cur; cur cur.next; } return head; }查/改双链表的遍历/查找/修改对于双链表的遍历和查找我们可以从头节点或尾节点开始根据需要向前或向后遍历// 创建一条双链表 DoublyListNode head createDoublyLinkedList(new int[]{1, 2, 3, 4, 5}); DoublyListNode tail null; // 从头节点向后遍历双链表 for (DoublyListNode p head; p ! null; p p.next) { System.out.println(p.val); tail p; } // 从尾节点向前遍历双链表 for (DoublyListNode p tail; p ! null; p p.prev) { System.out.println(p.val); }这个操作的最坏时间复杂度是 O(n)。访问或修改节点时可以根据索引是靠近头部还是尾部选择合适的方向遍历这样可以一定程度上提高效率。增在双链表头部插入新元素在双链表头部插入元素需要调整新节点和原头节点的指针// 创建一条双链表 DoublyListNode head createDoublyLinkedList(new int[]{1, 2, 3, 4, 5}); // 在双链表头部插入新节点 0 DoublyListNode newHead new DoublyListNode(0); newHead.next head; head.prev newHead; head newHead; // 现在链表变成了 0 - 1 - 2 - 3 - 4 - 5这个操作的时间复杂度是 O(1)。在双链表尾部插入新元素在双链表尾部插入元素时如果我们持有尾节点的引用这个操作会非常简单// 创建一条双链表 DoublyListNode head createDoublyLinkedList(new int[]{1, 2, 3, 4, 5}); DoublyListNode tail head; // 先走到链表的最后一个节点 while (tail.next ! null) { tail tail.next; } // 在双链表尾部插入新节点 6 DoublyListNode newNode new DoublyListNode(6); tail.next newNode; newNode.prev tail; // 更新尾节点引用 tail newNode; // 现在链表变成了 1 - 2 - 3 - 4 - 5 - 6这个操作的时间复杂度是 O(n)因为需要先遍历到尾节点。如果持有尾节点引用则是 O(1)。在双链表中间插入新元素在双链表的指定位置插入新元素需要调整前驱节点和后继节点的指针。// 创建一条双链表 DoublyListNode head createDoublyLinkedList(new int[]{1, 2, 3, 4, 5}); // 想要插入到索引 3第 4 个节点 // 需要操作索引 2第 3 个节点的指针 DoublyListNode p head; for (int i 0; i 2; i) { p p.next; } // 组装新节点 DoublyListNode newNode new DoublyListNode(66); newNode.next p.next; newNode.prev p; // 插入新节点 p.next.prev newNode; p.next newNode; // 现在链表变成了 1 - 2 - 3 - 66 - 4 - 5这个操作的时间复杂度是 O(n)因为需要先找到插入位置。删在双链表中删除一个节点在双链表中删除节点时需要调整前驱节点和后继节点的指针来摘除目标节点// 创建一条双链表 DoublyListNode head createDoublyLinkedList(new int[]{1, 2, 3, 4, 5}); // 删除第 4 个节点 // 先找到第 3 个节点 DoublyListNode p head; for (int i 0; i 2; i) { p p.next; } // 现在 p 指向第 3 个节点我们它后面那个节点摘除出去 DoublyListNode toDelete p.next; // 把 toDelete 从链表中摘除 p.next toDelete.next; toDelete.next.prev p; // 把 toDelete 的前后指针都置为 null 是个好习惯可选 toDelete.next null; toDelete.prev null; // 现在链表变成了 1 - 2 - 3 - 5这个操作的时间复杂度是 O(n)因为需要先找到被删除节点的位置。如果已知被删除节点的引用则删除操作本身是 O(1)。在双链表头部删除元素在双链表头部删除元素需要调整头节点的指针// 创建一条双链表 DoublyListNode head createDoublyLinkedList(new int[]{1, 2, 3, 4, 5}); // 删除头结点 DoublyListNode toDelete head; head head.next; head.prev null; // 清理已删除节点的指针 toDelete.next null; // 现在链表变成了 2 - 3 - 4 - 5这个操作的时间复杂度是 O(1)。在双链表尾部删除元素在单链表中由于缺乏前驱指针所以删除尾节点时需要遍历到倒数第二个节点操作它的next指针才能把尾节点摘除出去。但在双链表中由于每个节点都存储了前驱节点的指针所以我们可以直接操作尾节点把它自己从链表中摘除// 创建一条双链表 DoublyListNode head createDoublyLinkedList(new int[]{1, 2, 3, 4, 5}); // 删除尾节点 DoublyListNode p head; // 找到尾结点 while (p.next ! null) { p p.next; } // 现在 p 指向尾节点 // 把尾节点从链表中摘除 p.prev.next null; // 把被删结点的指针都断开是个好习惯可选 p.prev null; // 现在链表变成了 1 - 2 - 3 - 4这个操作的时间复杂度是 O(n)因为需要先遍历到尾节点。如果持有尾节点引用则是 O(1)。