LinkedList 是 Java 集合框架中非常常用的一种实现类，主要用于存储有序元素的链式结构。与 ArrayList 这种基于数组的实现不同，LinkedList 使用双向链表来管理数据。在本文中，我们将从 LinkedList 的基本特点、继承关系、扩容机制、常用方法源码介绍、增删改查等多个方面详细解读 LinkedList 的工作原理，帮助大家全面理解这一常用的数据结构。
1. LinkedList 的基本特点
LinkedList 是 Java 中 List 接口的一种实现类，底层是基于双向链表（Doubly Linked List）实现的。与 ArrayList 的固定大小数组不同，LinkedList 通过节点（Node）将元素串联起来，节点之间通过指针相互链接。具体特点如下：
- 双向链表：
LinkedList是基于双向链表实现的，每个节点包含指向前一个节点和后一个节点的引用，使得在双向链表中插入和删除元素的操作非常高效。 - 无序存储：与
ArrayList不同，LinkedList不保证元素的存储顺序，因此，它在内存中的存储是离散的，每个元素都有一个指向前后元素的引用。 - 内存消耗：由于每个节点需要额外的内存来存储前后指针，因此，
LinkedList的内存开销要大于ArrayList。 - 插入和删除效率：
LinkedList在插入和删除元素时（尤其是在中间位置）非常高效，时间复杂度为 O(1)，但访问元素的时间复杂度为 O(n)，不如ArrayList快。 - 线程不安全：与其他集合类一样，
LinkedList并不是线程安全的。
示例：
LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.add("C++");
list.add("Python");
System.out.println(list); // 输出: [Java, C++, Python]
2. LinkedList 的继承关系
LinkedList 继承自 AbstractSequentialList 并实现了 List 和 Deque 接口。具体的继承关系如下：
Object
|
AbstractCollection
|
AbstractSequentialList
|
LinkedList
AbstractCollection：提供了Collection接口的默认实现。AbstractSequentialList：提供了基于链表的List接口实现，它主要通过继承AbstractList，并通过链表特性优化get(int index)和set(int index, E element)方法。LinkedList：实现了List接口，提供了链表结构的各种操作（例如插入、删除、获取元素等）。
3. 增加元素 + 扩容机制
LinkedList 与 ArrayList 不同，LinkedList 不需要进行扩容，因为它是通过链表实现的，元素是动态链接的。因此，链表结构本身是灵活的，可以在任意位置插入或删除元素。
增加元素：
在 LinkedList 中，可以使用 add() 方法向链表尾部添加元素，也可以使用 addFirst() 和 addLast() 分别将元素添加到链表的头部和尾部。
LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.addFirst("C++");
list.addLast("Python");
System.out.println(list); // 输出: [C++, Java, Python]
插入元素：
可以使用 add(index, element) 方法在指定位置插入元素。如果指定的索引无效，则抛出 IndexOutOfBoundsException。
list.add(1, "Ruby");
System.out.println(list); // 输出: [C++, Ruby, Java, Python]
4. 常用的方法源码介绍
add() 方法
add() 方法用于在链表的尾部添加元素。它在实现中会创建一个新的节点并将其连接到链表的末尾。
public boolean add(E e) {
linkLast(e);
return true;
}
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;
else
l.next = newNode;
size++;
modCount++;
}
remove() 方法
remove() 方法用于删除链表中的元素。如果删除的是指定元素，则需要遍历链表来找到该元素并进行删除。
public E remove() {
if (size == 0)
throw new NoSuchElementException();
return unlinkFirst(first);
}
E unlinkFirst(Node<E> f) {
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null;
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
get() 方法
get() 方法用于获取指定位置的元素。由于 LinkedList 是基于链表的，获取元素的时间复杂度为 O(n)。
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
5. 删除元素
删除元素时，LinkedList 提供了几种常用方法：
remove()：移除并返回链表头部的元素。removeLast()：移除并返回链表尾部的元素。remove(int index)：移除指定索引位置的元素。
删除元素：
list.remove(1); // 删除索引为1的元素
System.out.println(list); // 输出: [C++, Java]
6. 改动元素
改动元素通常使用 set() 方法，它会替换链表中指定位置的元素。
list.set(1, "JavaScript");
System.out.println(list); // 输出: [C++, JavaScript]
7. 查询元素
在 LinkedList 中，常用的查询方法包括 get()、indexOf() 和 contains()。
get()：根据索引获取元素。contains()：检查链表中是否包含指定元素。indexOf()：查找元素第一次出现的位置。
查询元素：
boolean contains = list.contains("Java");
System.out.println(contains); // 输出: true
int index = list.indexOf("JavaScript");
System.out.println(index); // 输出: 1
8. 最后总结
总结：
LinkedList 是基于双向链表实现的集合类，具有以下优点：
- 插入和删除效率高：在链表的头部和尾部进行插入和删除操作非常高效，时间复杂度为 O(1)。
- 内存开销大：每个节点需要额外的空间存储前向和后向的引用，因此
LinkedList的内存开销相对较大。 - 查询效率低：由于
LinkedList是线性结构，因此查询元素的时间复杂度为 O(n)，效率较低。
使用建议：
LinkedList适合用于频繁插入和删除操作的场景，特别是当插入和删除发生在链表的头部或尾部时。- 如果需要频繁随机访问元素，则应该选择
ArrayList，因为它的查询速度更快，且内存开销较小。
LinkedList 提供了灵活的链表操作方式，可以帮助我们在适当的场景下选择合适的集合类。