Java LinkedList 类

Java LinkedList 类使用双向链表来存储元素。它提供了一个链表数据结构。它继承了 AbstractList 类并实现了 List 和 Deque 接口。

在 Java 中，LinkedList 是一个实现了 List 接口的类，代表一个链表数据结构。与将元素存储在连续内存位置的数组不同，链表将元素存储为节点，每个节点包含元素本身以及指向序列中下一个节点的引用（或指针）。

Java LinkedList 的重要注意事项如下：

• Java LinkedList 类可以包含重复元素。
• Java LinkedList 类保持插入顺序。
• Java LinkedList 类是不同步的。
• 在 Java LinkedList 类中，操作速度很快，因为不需要发生元素移动。
• Java LinkedList 类可以用作列表、堆栈或队列。

LinkedList 的一个关键特性是其动态大小，这意味着它可以根据需要增长或缩小。这是因为每个元素都存储在其自己的节点中，从而可以高效地插入和删除元素。但是，与数组相比，通过索引访问 LinkedList 中的元素效率较低，因为它需要从头或尾开始遍历列表才能到达所需的元素。

Java 中的 LinkedList 类提供了各种方法来操作列表，例如添加或删除元素、按索引访问元素以及搜索元素。此外，它还提供了执行诸如在列表开头或结尾添加元素、在特定位置插入元素以及按索引或值删除元素等操作的方法。

LinkedList 类的层次结构

List 接口扩展了 Collection 接口，代表一个有序的元素集合。列表允许重复元素，并提供按整数索引访问元素的方法。LinkedList 类实现了 List 接口，代表双向链表数据结构。

LinkedList 由一系列节点组成，每个节点都包含一个指向序列中下一个节点和上一个节点的引用。它允许高效的插入和删除操作，因为每个节点只需要更新其相邻节点的引用。但是，与 ArrayList 相比，通过索引访问 LinkedList 中的元素效率较低，因为它需要从头或尾开始遍历列表才能到达所需的元素。

双向链表

在 Java 中，双向链表是一种链表，其中每个节点都包含一个指向序列中下一个节点和上一个节点的引用。它允许列表向前和向后遍历，这与只允许单向遍历的单向链表不同。

双向链表的一个优点是与单向链表相比，它可以更有效地删除元素，因为可以直接访问给定节点的前一个节点。这使得在不遍历整个列表的情况下更容易从列表的中间删除元素。

在双向链表的情况下，我们可以从两端添加或删除元素。

然而，双向链表的一个缺点是它比单向链表需要更多的内存，因为每个节点都包含一个指向前一个节点的附加指针。此外，维护前向指针增加了列表实现的复杂性。

LinkedList 类声明

作为 List，LinkedList 维护元素的插入顺序并允许重复元素。它提供了在列表的特定位置添加、删除和访问元素的方法。此外，作为 Deque，LinkedList 支持列表两端的操作，例如在列表的开头和结尾添加和删除元素。

让我们看一下 java.util.LinkedList 类的声明。

Java LinkedList 构造函数

Java 中的 LinkedList 类提供了构造函数来创建链表实例。一个构造函数通过将 size 字段初始化为零并将 first 和 last 字段设置为 null 来创建一个空链表，表示一个空列表。当我们想创建一个没有初始元素的链表时，此构造函数很有用。

另一个构造函数允许我们从现有集合（如 ArrayList 或另一个 LinkedList）创建链表。构造函数会初始化一个空链表，然后使用 addAll 方法将集合中的所有元素添加到链表中。当我们想将集合转换为链表同时保留元素顺序时，此构造函数很方便。

Java LinkedList 类方法

Java LinkedList 示例

输出

Ravi
Vijay
Ravi
Ajay

Java LinkedList 添加元素的示例

在这里，我们看到添加元素的各种方法。

输出

Initial list of elements: []
After invoking add(E e) method: [Ravi, Vijay, Ajay]
After invoking add(int index, E element) method: [Ravi, Gaurav, Vijay, Ajay]
After invoking addAll(Collection<? extends E> c) method: 
[Ravi, Gaurav, Vijay, Ajay, Sonoo, Hanumat]
After invoking addAll(int index, Collection<? extends E> c) method: 
[Ravi, John, Rahul, Gaurav, Vijay, Ajay, Sonoo, Hanumat]
After invoking addFirst(E e) method: 
[Lokesh, Ravi, John, Rahul, Gaurav, Vijay, Ajay, Sonoo, Hanumat]
After invoking addLast(E e) method: 
[Lokesh, Ravi, John, Rahul, Gaurav, Vijay, Ajay, Sonoo, Hanumat, Harsh]

Java LinkedList 删除元素的示例

在这里，我们看到删除元素的各种方法。

输出

Initial list of elements: [Ravi, Vijay, Ajay, Anuj, Gaurav, Harsh, Virat, Gaurav, Harsh, Amit]
After invoking remove(object) method: [Ravi, Ajay, Anuj, Gaurav, Harsh, Virat, Gaurav, Harsh, Amit]
After invoking remove(index) method: [Ajay, Anuj, Gaurav, Harsh, Virat, Gaurav, Harsh, Amit]
Updated list : [Ajay, Anuj, Gaurav, Harsh, Virat, Gaurav, Harsh, Amit, Ravi, Hanumat]
After invoking removeAll() method: [Ajay, Anuj, Gaurav, Harsh, Virat, Gaurav, Harsh, Amit]
After invoking removeFirst() method: [Gaurav, Harsh, Virat, Gaurav, Harsh, Amit]
After invoking removeLast() method: [Gaurav, Harsh, Virat, Gaurav, Harsh]
After invoking removeFirstOccurrence() method: [Harsh, Virat, Gaurav, Harsh]
After invoking removeLastOccurrence() method: [Harsh, Virat, Gaurav]
After invoking clear() method: []

Java LinkedList 反转元素列表的示例

输出

 Ajay
Vijay
Ravi

Java LinkedList 示例：图书

输出

101 Let us C Yashwant Kanetkar BPB 8
102 Data Communications & Networking Forouzan Mc Graw Hill 4
103 Operating System Galvin Wiley 6

Java LinkedList 选择题

1. Java 中的 LinkedList 类实现了哪个接口？

1. 列表
2. Deque
3. Queue
4. 以上全部。

2. 在 Java 中，在 LinkedList 的开头插入元素的 time complexity 是多少？

1. O(1)
2. O(log n)
3. O(n)
4. O(n log n)

3. 哪个方法用于检索但不删除 Java LinkedList 的头部？

1. poll()
2. peek()
3. remove()
4. get()

4. 下列代码的输出是什么？

System.out.println(list);

1. [A, B, C, D]
2. [D, A, B, C]
3. [A, D, B, C]
4. [D, B, C, A]

5. 在 Java 中，可以使用哪个方法将元素添加到 LinkedList 的末尾？

1. add()
2. addLast()
3. offer()
4. 以上全部。