介绍
LinkedList 类是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的地址。
Java 的 LinkedList 底层是一个双向链表，位于 java.util 包中，使用前需要引入它
LinkedList
- LinkedList 是一个继承于
AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。 - LinkedList 实现 List 接口，能对它进行队列操作。
- LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
- LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
- LinkedList 实现
java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。 - LinkedList 是非同步的。
缺陷：
LinkedList 是链表，与ArrayList相比，LinkedList插入、删除元素操作方便，性能高。但如果访问、查找元素，是遍历链表方式的，开销大，所以应尽量减少get(int location)、indexOf(Object object)的使用。
在实际运用中ArrayList 和 LinkedList 怎么选择？
查询、访问频繁：ArrayList
插入、删除频繁：LinkedList
LinkedList使用
LinkedList 实例化方式
1、无参构造法
LinkedList <Integer> linkedList = new LinkedList <>();
2、有参数——参数是其他 Collection
Collection是集合框架中的一个接口，实现了这个接口的类的对象就可以作为参数，说白了就是
可以把其他的顺序表，链表，栈，队列等等 作为参数传参，例如：
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
LinkedList<Integer> linkedList= new LinkedList<arrayList >(arrayList );
我先 new 了一个顺序表对象 arrayList ，在这个表中插入了 “1” “2” 两个数据，顺序表中的数据是顺序存储的
当 arrayList 作为参数传递时，linkedList 对象中就有了 arrayList 中的所有数据，linkedList 中的数据是链式
LinkedList 常用方法
3.1 、添加元素
3.1.1 add 方法
要向 LinkedList 中添加元素，您可以使用 add 方法。它将元素添加到列表的末尾。
linkedList.add("橙子");
3.1.2 在指定位置添加元素
您还可以使用 add 方法在指定位置插入元素。指定位置是通过索引来确定的，索引从 0 开始。
linkedList.add(1, "葡萄"); // 在索引 1 处插入 "葡萄"
3.2 、获取元素
3.2.1 get 方法
要获取 LinkedList 中的元素，可以使用 get 方法，指定元素的索引。
String fruit = linkedList.get(0); // 获取第一个元素
3.3、 删除元素
3.3.1 remove 方法
要删除 LinkedList 中的元素，可以使用 remove 方法。可以指定要删除的元素或要删除的元素的索引。
linkedList.remove("香蕉"); // 删除 "香蕉"
linkedList.remove(1); // 删除索引 1 处的元素
4、遍历 LinkedList
遍历 LinkedList 可以使用不同的方式，最常见的是使用 for-each 循环或迭代器。
4.1 使用 for-each 循环
for (String fruit : linkedList) {
System.out.println(fruit);
}
4.2 使用迭代器
Iterator<String> iterator = linkedList.iterator();
while (iterator.hasNext()) {
String fruit = iterator.next();
System.out.println(fruit);
}
5、特殊操作
5.1 在开头和末尾添加元素
LinkedList 允许在开头和末尾高效添加元素。
5.1.1 在开头添加元素
linkedList.addFirst("草莓");
5.1.2 在末尾添加元素
linkedList.addLast("樱桃");
5.2 在特定位置插入元素
LinkedList 也允许在特定位置插入元素。
linkedList.add(2, "葡萄"); // 在索引 2 处插入 "葡萄"
5.3 替换元素
您可以使用 set 方法来替换 LinkedList 中的元素。
linkedList.set(1, "蓝莓"); // 将索引 1 处的元素替换为 "蓝莓"
6、性能考虑
6.1 LinkedList与 ArrayList 的比较
在考虑使用 LinkedList 时，需要权衡性能。与 ArrayList 相比，LinkedList 在插入和删除操作方面通常更快，因为它不需要移动大量元素。然而，它在随机访问元素时的性能较差，因为需要从头部或尾部开始遍历链表。
6.2 时间复杂度
- 添加和删除元素：平均时间复杂度为 O(1)（在已知位置的情况下），最坏情况下为 O(n)（如果需要遍历整个链表）。
- 获取元素：平均时间复杂度为 O(n/2)（在平均情况下，需要遍历一半的链表）。
- 随机访问元素：最坏情况下为 O(n)（需要从头或尾遍历整个链表）。
7、使用注意事项
在使用 LinkedList 时，需要注意以下事项：
LinkedList不是线程安全的。如果在多个线程中使用，必须采取适当的同步措施，或者考虑使用线程安全的替代品。- 避免过多的随机访问，因为它的性能较差。如果需要频繁的随机访问，请考虑使用
ArrayList。 - 谨慎使用大型
LinkedList，因为它可能会占用大量内存。
8、高级用法
8.1 双向链表
LinkedList 是一种双向链表的实现，这意味着每个节点都包含指向前一个节点和后一个节点的引用。这种双向连接使得在链表中向前和向后遍历都非常高效。以下是关于双向链表的高级用法示例：
8.1.1 逆序遍历链表
LinkedList 的双向性质使得逆序遍历变得容易。您可以从链表的尾部开始遍历，不断跟随前一个节点的引用，直到达到链表的头部。
LinkedList<String> linkedList = new LinkedList<>();
// 添加元素到链表
// ...
// 逆序遍历链表
ListIterator<String> iterator = linkedList.listIterator(linkedList.size());
while (iterator.hasPrevious()) {
String item = iterator.previous();
System.out.println(item);
}
8.1.2 在特定位置插入元素
双向链表的特性使得在特定位置插入元素更加高效，因为您可以从两个方向进行遍历。这可以在需要在链表中间插入元素时提供性能优势。
LinkedList<String> linkedList = new LinkedList<>();
// 添加元素到链表
// ...
// 在中间位置插入元素
ListIterator<String> iterator = linkedList.listIterator(linkedList.size() / 2); // 在中间位置开始
iterator.add("新元素");
8.2 循环链表
LinkedList 也可以用作循环链表，即链表的最后一个节点指向第一个节点，形成一个闭环。这种结构在某些算法和数据结构中非常有用，例如循环队列。
LinkedList<String> circularList = new LinkedList<>();
circularList.add("元素1");
circularList.add("元素2");
circularList.add("元素3");
// 构建循环链表，将最后一个元素指向第一个元素
circularList.getLast().setNext(circularList.getFirst());
// 遍历循环链表
Node<String> currentNode = circularList.getFirst();
do {
System.out.println(currentNode.getData());
currentNode = currentNode.getNext();
} while (currentNode != circularList.getFirst());
示例代码
以下是一些使用 LinkedList 的基础示例代码：
// 创建一个 LinkedList
LinkedList<String> linkedList = new LinkedList<>();
// 添加元素
linkedList.add("苹果");
linkedList.add("香蕉");
// 获取元素
String fruit = linkedList.get(0);
// 删除元素
linkedList.remove("香蕉");
// 遍历 LinkedList
for (String item : linkedList) {
System.out.println(item);
}
总结
LinkedList 是 Java 中强大的数据结构，它在插入和删除操作方面非常高效。但是，在随机访问元素时性能较差，因此需要谨慎选择使用。希望本篇博客能够帮助您更好地理解和使用 LinkedList，并在编写 Java 代码时做出明智的选择。无论您是初学者还是有经验的开发者，掌握 LinkedList 都将为您的编程旅程增添新的工具和技巧。