【JAVA】LinkedList 详解

LinkedList

LinkedList 是一种常见的数据结构，它由一组节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。与数组不同，LinkedList 中的元素在内存中并不是连续存储的，而是通过指针链接在一起的。这使得 LinkedList 在某些情况下比数组更灵活，但也有其独特的优缺点。

1. 类型

LinkedList 主要有以下几种类型：

单向链表 (Singly Linked List): 这是最基本的链表形式，每个节点只包含一个数据元素和一个指向下一个节点的指针。链表的最后一个节点指向 null，表示链表的结束。
双向链表 (Doubly Linked List): 在双向链表中，每个节点不仅包含一个指向下一个节点的指针，还包含一个指向前一个节点的指针。这使得链表可以在两个方向上遍历，增加了灵活性。
循环链表 (Circular Linked List): 在循环链表中，链表的最后一个节点指向链表的第一个节点，形成一个循环结构。它可以是单向的，也可以是双向的。

2. 基本操作

以下是一些常见的 LinkedList 操作：

插入 (Insertion): 可以在链表的头部、尾部或中间插入一个新节点。插入操作的时间复杂度取决于插入位置，但在最坏情况下，时间复杂度为 O(n)。
删除 (Deletion): 可以删除链表中的第一个节点、最后一个节点或特定位置的节点。删除操作的时间复杂度也是 O(n)，取决于删除位置。
查找 (Search): 查找特定元素的操作时间复杂度为 O(n)，因为在最坏的情况下，可能需要遍历整个链表。
遍历 (Traversal): 可以从头到尾或从尾到头（在双向链表中）遍历链表，时间复杂度为 O(n)。

3. 优缺点

优点:

动态大小: LinkedList 的大小可以动态增长或缩小，不需要像数组那样预先分配内存。
高效的插入和删除操作: 在已知节点位置的情况下，插入和删除操作可以在 O(1) 时间内完成，而数组在最坏情况下需要 O(n) 的时间。

缺点:

内存开销大: 每个节点都需要额外的内存来存储指针，特别是在双向链表中。
随机访问性能差: 由于 LinkedList 不支持随机访问，查找特定元素需要从头开始遍历，时间复杂度为 O(n)，而数组可以在 O(1) 时间内进行随机访问。

4. 使用场景

LinkedList 适用于频繁插入和删除操作、大小动态变化且不需要频繁随机访问的场景。例如，LRU缓存、链式哈希表、以及一些需要实现栈和队列的数据结构等。

面试题

1. 反转链表 (Reverse a Linked List)

问题描述: 给定一个单向链表，将其反转。
示例: 输入: 1 -> 2 -> 3 -> 4 -> 5 -> null
输出: 5 -> 4 -> 3 -> 2 -> 1 -> null

解答：
1.链表基础
链表是由一系列节点（Node）组成的线性数据结构。每个节点包含两部分：

值 (value): 节点保存的数据。
指针 (next): 指向下一个节点的引用（指针）。

链表的第一个节点叫做头节点 (Head)，最后一个节点指向 null，表示链表的结束。

java">class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}
}

2.反转链表 (Reverse a Linked List)
问题描述: 给定一个单向链表，将其反转，即链表中所有节点的顺序颠倒。
示例: 输入: 1 -> 2 -> 3 -> 4 -> 5 -> null
输出: 5 -> 4 -> 3 -> 2 -> 1 -> null
思路:

我们需要遍历链表，并在遍历过程中反转节点的指针方向。
使用三个指针变量：prev, curr, 和 nextTemp。
- prev 指向当前节点的前一个节点，初始为 null。
- curr 指向当前正在处理的节点。
- nextTemp 用来暂时存储当前节点的下一个节点，以便后续处理。

步骤:
1.初始化 prev 为 null, curr 为 head。
2.遍历链表：

保存当前节点的下一个节点 nextTemp = curr.next。
将当前节点的指针指向 prev, curr.next = prev。
将 prev 移动到 curr, curr 移动到 nextTemp。

3.遍历结束时，prev 将指向新的头节点，返回 prev。

java">public class LinkedListProblems {public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode nextTemp = curr.next;  // 保存下一个节点curr.next = prev;  // 反转当前节点的指针prev = curr;  // 将 prev 移到当前节点curr = nextTemp;  // 将 curr 移到下一个节点}return prev;  // prev 最终指向新的头节点}
}

3.测试接口
我们可以写一个简单的测试方法，创建链表并测试 reverseList 方法。

java">public class LinkedListTest {public static void main(String[] args) {// 创建链表 1 -> 2 -> 3 -> 4 -> 5ListNode head = new ListNode(1);head.next = new ListNode(2);head.next.next = new ListNode(3);head.next.next.next = new ListNode(4);head.next.next.next.next = new ListNode(5);// 打印原链表System.out.println("Original List:");printList(head);// 反转链表LinkedListProblems solution = new LinkedListProblems();ListNode reversedHead = solution.reverseList(head);// 打印反转后的链表System.out.println("Reversed List:");printList(reversedHead);}// 辅助方法：打印链表public static void printList(ListNode head) {ListNode curr = head;while (curr != null) {System.out.print(curr.val + " -> ");curr = curr.next;}System.out.println("null");}
}

4.测试结果
运行上面的 LinkedListTest 类时，你会看到以下输出：

java">Original List:
1 -> 2 -> 3 -> 4 -> 5 -> null
Reversed List:
5 -> 4 -> 3 -> 2 -> 1 -> null