【JavaSE专栏49】Java集合类LinkedList解析，链表和顺序表有什么不同？

一、什么是LinkedList集合

LinkedList 集合是Java编程语言中的一种双向链表数据结构，它实现了 List 接口和 Deque 接口。

与 ArrayList 类似，LinkedList 也是一种动态数组，可以根据需要动态地增加或减少元素的大小。

然而，LinkedList 与 ArrayList 在内部实现和性能方面有所不同。

LinkedList 使用双向链表来存储元素，每个元素都包含一个指向前一个元素和后一个元素的引用，这种结构使得 LinkedList 在插入和删除元素时效率较高，因为它只需要调整节点的引用，而不需要移动其他元素。

但是，LinkedList 在随机访问元素时的性能相对较差，因为它需要遍历链表来获取指定索引处的元素。

LinkedList 提供了一系列方法来操作和管理元素。它实现了 List 接口和 Deque 接口的所有方法，包括添加、删除、获取和修改元素的方法。此外，LinkedList 还提供了一些特定于链表操作的方法，如 addFirst()、addLast()、removeFirst()、removeLast() 等。

LinkedList的一些常见应用场景包括以下 5 55 类，请同学们认真学习。

1. 需要频繁插入和删除元素的场景，因为 LinkedList 在插入和删除操作上效率较高。
2. 实现队列和双向队列的场景，因为 LinkedList 实现了 Deque 接口。
3. 实现堆栈的场景，可以使用 LinkedList 的 addFirst() 和 removeFirst() 方法来模拟堆栈的入栈和出栈操作。
4. 实现循环链表的场景，因为 LinkedList 的首尾节点相连，可以形成一个循环链表。
5. 需要进行大量顺序遍历操作的场景，因为 LinkedList 的顺序遍历效率较高。

需要注意的是，与 ArrayList 一样，LinkedList 也不是线程安全的。如果在多个线程中同时访问和修改 LinkedList，可能会引发并发访问的问题，在多线程环境中使用 LinkedList 时，应该采取相应的线程安全措施，如使用同步机制或使用线程安全的替代方案。

二、LinkedList集合的使用

以下是 LinkedList 集合的一些常见使用方式的示例代码：

2.1 创建 LinkedList 集合、添加元素、遍历元素

LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("apple");
linkedList.add("banana");
linkedList.add("orange");
for (String fruit : linkedList) {
    System.out.println(fruit);
}

2.2 在指定位置插入元素

LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("apple");
linkedList.add("banana");
linkedList.add("orange");
linkedList.add(1, "grape");
System.out.println(linkedList); // 输出：[apple, grape, banana, orange]

2.3 获取指定位置的元素

LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("apple");
linkedList.add("banana");
linkedList.add("orange");
String fruit = linkedList.get(1);
System.out.println(fruit); // 输出：banana

2.4 删除指定位置的元素

LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("apple");
linkedList.add("banana");
linkedList.add("orange");
linkedList.remove(1);
System.out.println(linkedList); // 输出：[apple, orange]

2.5 在开头或末尾插入元素

LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("apple");
linkedList.add("banana");
linkedList.add("orange");
linkedList.addFirst("grape");
linkedList.addLast("watermelon");
System.out.println(linkedList); // 输出：[grape, apple, banana, orange, watermelon]

三、LinkedList集合的应用场景

LinkedList 集合在以下场景中通常会得到应用，请同学们认真学习。

1. 需要频繁地进行元素插入和删除操作的场景：由于 LinkedList 采用双向链表的数据结构，插入和删除元素的效率较高，因为只需要调整节点的引用即可，而不需要像数组一样移动其他元素。
2. 实现队列和双向队列的场景：LinkedList 实现了 Deque 接口，因此可以用来实现队列和双向队列。例如，可以使用 LinkedList 的 addFirst() 和 removeFirst() 方法来模拟队列的入队和出队操作。
3. 实现堆栈的场景：LinkedList 也可以用来实现堆栈数据结构。通过使用 LinkedList 的 addFirst() 和 removeFirst() 方法来模拟堆栈的入栈和出栈操作。
4. 需要进行大量顺序遍历操作的场景：LinkedList 的顺序遍历效率较高，因为它是一个链表数据结构，可以按顺序依次遍历元素。
5. 实现循环链表的场景：由于 LinkedList 的首尾节点相连，可以形成一个循环链表。这在某些场景下可能会有用，例如处理循环队列。

四、LinkedList面试题

一、Java 中的 LinkedList 是什么？

答：LinkedList 是 Java 集合框架中的一种双向链表实现的数据结构。它实现了 List 接口，可以存储各种类型的对象，并且支持插入、删除和访问操作。

二、LinkedList 和 ArrayList 的区别是什么？

答：LinkedList 和 ArrayList 都可以实现 List 接口，但它们的内部实现不同，主要区别如下。

• LinkedList 是基于双向链表实现的，而 ArrayList 是基于动态数组实现的。
• LinkedList 在插入和删除操作上具有更好的性能，因为只需要调整链表节点的指针，而 ArrayList 需要移动数组中的元素。
• ArrayList 在随机访问操作上具有更好的性能，因为可以通过索引直接访问数组中的元素，而 LinkedList 需要从头节点或尾节点开始遍历链表。
• LinkedList 需要更多的内存空间来存储链表节点的指针，而 ArrayList 需要更多的内存空间来存储数组的容量。

三、LinkedList 如何实现插入和删除操作？

答：LinkedList 通过操作节点的指针来实现插入和删除操作。

• 在插入操作中，可以通过修改前后节点的指针来将新节点插入到链表中的任意位置。
• 在删除操作中，可以通过修改前后节点的指针来删除指定节点。

四、LinkedList 适用于什么场景？

答：LinkedList 适用于以下情况：

• 需要频繁地进行插入和删除操作。
• 需要高效地使用迭代器进行遍历操作。
• 不需要随机访问元素，或者只需要在链表的头部和尾部进行访问。

五、如何使用 LinkedList 的迭代器进行遍历？

答：可以通过调用 LinkedList 的 iterator() 方法来获取迭代器，并且使用 while 循环和 next() 方法来遍历链表中的元素。

LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
Iterator<String> iterator = linkedList.iterator();
while (iterator.hasNext()) {
    String element = iterator.next();
    System.out.println(element);
}

五、总结

本文讲解了 Java 中集合类 LinkedList 的语法、使用说明和应用场景，并给出了样例代码。在下一篇博客中，将讲解 Java 中 动态数组 Vector 类的知识。