LinkedList底层原理
节点（Node）结构
LinkedList 的核心是一个内部类 Node，每个 Node 对象代表链表中的一个元素，并且每个节点包含三个部分：
- 元素值 (
item)：存储实际的数据。 - 前驱节点引用 (
prev)：指向当前节点前面的节点。 - 后继节点引用 (
next)：指向当前节点后面的节点。
private static class Node<E> {E item;Node<E> next;Node<E> prev;Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}}LinkedList 类维护了两个引用，分别是指向链表的头部节点和尾部节点：
- 头节点 (
first)：指向链表的第一个节点。 - 尾节点 (
last)：指向链表的最后一个节点。 - 长度（size）
transient int size = 0;
transient Node<E> first;
transient Node<E> last;链表的基本操作
插入操作
插入新节点时，通常需要更新相邻节点的前后指针以及链表的头尾指针。例如，插入到链表尾部的操作addLast()：
- 创建一个新的
Node实例。 - 将新节点的
prev指向当前尾部节点。 - 如果链表为空，则同时设置
first和last指向新节点；否则，设置当前尾部节点的next指向新节点，并更新last指向新节点。
源码：
public void addLast(E e) {linkLast(e);}void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;modCount++;}示例：
public class LinkedListTest {public static void main(String[] args) {LinkedList<String> sites = new LinkedList<>();sites.add("Google");sites.addLast("Wiki");System.out.println(sites);}
}删除操作
- 找到要删除的节点。
- 更新前驱节点的
next指针和后继节点的prev指针。 - 如果删除的是头部节点，更新
first；如果是尾部节点，更新last。
部分源码：
public boolean remove(Object o) {//处理null值if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {unlink(x);//删除return true;}}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {unlink(x);//删除return true;}}}return false;}//删除操作E unlink(Node<E> x) {final E element = x.item;final Node<E> next = x.next;final Node<E> prev = x.prev;if (prev == null) {first = next;} else {prev.next = next;x.prev = null;}if (next == null) {last = prev;} else {next.prev = prev;x.next = null;}x.item = null;size--;modCount++;return element;}查找操作
查找一个节点通常是从头节点开始遍历链表，直到找到目标节点或到达尾部节点。
源码：
public int indexOf(Object o) {int index = 0;for (Node<E> x = first; x != null; x = x.next) {if (o == null ? x.item == null : o.equals(x.item))return index;++index;}return -1;
}基于源码，他有以下特点：
-
快速插入和删除:
- 插入和删除操作的时间复杂度通常为 O(1)。
- 插入和删除操作只需要修改相邻节点的引用，而不需要移动元素。
- 这一点与
ArrayList不同，ArrayList在插入或删除时可能需要移动大量元素。
-
随机访问相对较慢:
- 随机访问某个位置的元素需要从头或尾开始遍历，时间复杂度为 O(n)。
- 这是因为链表不像数组那样连续存储数据，无法直接通过索引访问元素。
-
允许重复元素
-
允许
null值 -
线程不安全:
LinkedList的基本操作（如add,get,set,remove等）不是线程安全的。- 如果多个线程并发地访问或修改
LinkedList，需要外部同步机制。
-
所有指定位置的操作都是从头开始遍历进行的:
对于基于索引的操作（如get(int index)或set(int index, E element)），遍历会从头部开始直到到达指定的位置。 -
有序性:即元素的顺序保持不变，除非显式地重新排序或修改链表。
-
实现多种接口:
LinkedList 实现了 List、Deque（双端队列）、Queue 等接口，因此可以作为队列、堆栈或双端队列使用。
什么时候会使用到这些接口？
使用 List 接口
如果你需要一个有序的列表，那么使用 List 接口。
例如：
- 维护一个动态的历史记录列表：例如浏览器的历史记录，或者最近打开的文件列表。
- 实现一个灵活的任务列表：其中任务可能被添加或移除，并且这种操作非常频繁。
使用 Queue 接口
如果你需要一个先进先出的数据结构，那么使用 Queue 接口。
例如：
- 消息队列：处理来自客户端的消息或事件。
- 任务队列：例如用于异步处理的作业队列，如批量处理任务、打印队列等。
- 缓存队列：例如在内存中缓存最近访问的数据项，当队列满时移除最旧的数据项。
使用 Deque 接口
如果你需要一个可以从两端进行操作的数据结构，那么使用 Deque 接口。
例如：
- 滑动窗口算法：在算法问题中，需要维护一个固定长度的滑动窗口，例如计算滑动窗口内的最大值或最小值。
- 后进先出（LIFO）操作：虽然
Deque支持 FIFO 和 LIFO 操作，但如果你需要一个简单的栈，可以使用Deque的相关方法。 - 双端队列队列：例如在实现优先级队列时，你可以使用双端队列来存储不同优先级的元素。
示例代码
import java.util.LinkedList;
import java.util.Queue;
import java.util.Deque;public class LinkedListExample {public static void main(String[] args) {// 使用 LinkedList 作为 QueueQueue<String> queue = new LinkedList<>();queue.offer("One");queue.offer("Two");System.out.println("Queue: " + queue);System.out.println("Poll from Queue: " + queue.poll());// 使用 LinkedList 作为 DequeDeque<Integer> deque = new LinkedList<>();deque.addFirst(1);deque.addLast(2);System.out.println("Deque: " + deque);System.out.println("Remove from front of Deque: " + deque.removeFirst());}
}