LinkedList底层原理

节点（Node）结构

LinkedList 的核心是一个内部类 Node，每个 Node 对象代表链表中的一个元素，并且每个节点包含三个部分：

1. 元素值 (item)：存储实际的数据。
2. 前驱节点引用 (prev)：指向当前节点前面的节点。
3. 后继节点引用 (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 类维护了两个引用，分别是指向链表的头部节点和尾部节点：

1. 头节点 (first)：指向链表的第一个节点。
2. 尾节点 (last)：指向链表的最后一个节点。
3. 长度（size）

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

链表的基本操作

        插入操作

        插入新节点时，通常需要更新相邻节点的前后指针以及链表的头尾指针。例如，插入到链表尾部的操作addLast()：

1. 创建一个新的 Node 实例。
2. 将新节点的 prev 指向当前尾部节点。
3. 如果链表为空，则同时设置 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);}
}

        删除操作

1. 找到要删除的节点。
2. 更新前驱节点的 next 指针和后继节点的 prev 指针。
3. 如果删除的是头部节点，更新 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;
}

基于源码，他有以下特点：

1. 快速插入和删除:

   • 插入和删除操作的时间复杂度通常为 O(1)。
   • 插入和删除操作只需要修改相邻节点的引用，而不需要移动元素。
   • 这一点与 ArrayList 不同，ArrayList 在插入或删除时可能需要移动大量元素。

2. 随机访问相对较慢:

   • 随机访问某个位置的元素需要从头或尾开始遍历，时间复杂度为 O(n)。
   • 这是因为链表不像数组那样连续存储数据，无法直接通过索引访问元素。

3. 允许重复元素

4. 允许 null 值

5. 线程不安全:

   • LinkedList 的基本操作（如 add, get, set, remove 等）不是线程安全的。
   • 如果多个线程并发地访问或修改 LinkedList，需要外部同步机制。

6. 所有指定位置的操作都是从头开始遍历进行的:

   对于基于索引的操作（如 get(int index) 或 set(int index, E element)），遍历会从头部开始直到到达指定的位置。

7. 有序性:即元素的顺序保持不变，除非显式地重新排序或修改链表。

8. 实现多种接口:

   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());}
}