原文： https://howtodoinjava.com/java/collections/java-linkedlist-class/

Java LinkedList类是List和Deque接口的双链列表实现。 它实现所有可选的列表操作，并允许所有元素（包括null）。

  1. Table of Contents
  3. 1\. LinkedList Hierarchy
  4. 2\. LinkedList Features
  5. 3\. LinkedList Constructors
  6. 4\. LinkedList Methods
  7. 5\. LinkedList Example
  8. 6\. LinkedList Usecases
  9. 7\. LinkedList Performance
  10. 8\. ArrayList vs LinkedList
  11. 9\. Conclusion

1. LinkedList层次结构

LinkedList类扩展了AbstractSequentialList类，实现了List和Deque接口。 这里E是值链表存储的类型。

  1. public class LinkedList<E>
  2.     extends AbstractSequentialList<E>
  3.     implements List<E>, Deque<E>, Cloneable, java.io.Serializable
  4. {
  5.     //implementation
  6. }

Java `LinkedList`类 - 图1

LinkedList层次结构

2. LinkedList特性

  • 双链表实现，它实现List和Deque接口。 因此，它也可以用作队列，双端队列或栈。
  • 允许所有元素，包括重复和NULL。
  • LinkedList维护元素的插入顺序。
  • 未同步。 如果多个线程同时访问一个链表，并且至少一个线程在结构上修改了该链表，则它必须在外部进行同步。
  • 使用Collections.synchronizedList(new LinkedList())获取同步链表。
  • 此类返回的迭代器是快速失败的，并且可能抛出ConcurrentModificationException。
  • 它没有实现RandomAccess接口。 因此，我们只能按顺序访问元素。 它不支持随机访问元素。
  • 我们可以使用ListIterator来迭代LinkedList元素。

3. LinkedList构造器

  1. LinkedList()：初始化一个空的LinkedList实现。
  2. LinkedListExample(Collection c)：初始化一个LinkedList，其中包含指定集合的元素，并按集合的迭代器返回它们的顺序。

4. LinkedList方法

  1. boolean add(Object o)：将指定的元素附加到列表的末尾。
  2. void add(int index, Object element)：将指定元素插入列表中指定位置的索引处。
  3. void addFirst(Object o)：将给定元素插入列表的开头。
  4. void addLast(Object o)：将给定元素附加到列表的末尾。
  5. int size()：返回列表中的元素数
  6. boolean contains(Object o)：如果列表包含指定元素，则返回true，否则返回false。
  7. boolean remove(Object o)：删除列表中指定元素的首次出现。
  8. Object getFirst()：返回列表中的第一个元素。
  9. Object getLast()：返回列表中的最后一个元素。
  10. int indexOf(Object o)：返回指定元素首次出现的列表中的索引；如果列表不包含指定元素，则返回 -1。
  11. lastIndexOf(Object o)：返回指定元素最后一次出现的列表中的索引；如果列表不包含指定元素，则返回 -1。
  12. Iterator iterator()：按适当的顺序返回此列表中元素的迭代器。
  13. Object[] toArray()：按正确顺序返回包含此列表中所有元素的数组。
  14. List subList(int fromIndex, int toIndex)：返回此列表中指定的fromIndex（包括）和toIndex（不包括）之间的视图。

5. Java LinkedList示例

5.1 添加，删除，迭代

Java 程序演示链表类中基本方法的用法。

  1. import java.util.LinkedList;
  2. import java.util.ListIterator;
  4. public class LinkedListExample 
  5. {
  6.     public static void main(String[] args) 
  7.     {
  8.         //Create linked list
  9.         LinkedList<String> linkedList = new LinkedList<>();
  11.         //Add elements
  12.         linkedList.add("A");
  13.         linkedList.add("B");
  14.         linkedList.add("C");
  15.         linkedList.add("D");
  17.         System.out.println(linkedList);
  19.         //Add elements at specified position
  20.         linkedList.add(4, "A");
  21.         linkedList.add(5, "A");
  23.         System.out.println(linkedList);
  25.         //Remove element
  26.         linkedList.remove("A");        //removes A
  27.         linkedList.remove(0);        //removes B
  29.         System.out.println(linkedList);
  31.         //Iterate
  32.         ListIterator<String> itrator = linkedList.listIterator();
  34.         while (itrator.hasNext()) {
  35.             System.out.println(itrator.next());
  36.         }
  37.     }
  38. }

程序输出。

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

5.2 在数组和LinkedList之间转换

Java 程序将LinkedList转换为数组，将数组转换为Linkedlist。

  1. LinkedList<String> linkedList = new LinkedList<>();
  3. linkedList.add("A");
  4. linkedList.add("B");
  5. linkedList.add("C");
  6. linkedList.add("D");
  8. //1\. LinkedList to Array
  9. String array[] = new String[linkedList.size()];
  10. linkedList.toArray(array);
  12. System.out.println(Arrays.toString(array));
  14. //2\. Array to LinkedList
  15. LinkedList<String> linkedListNew = new LinkedList<>(Arrays.asList(array));
  17. System.out.println(linkedListNew);

程序输出：

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

5.3 如何排序LinkedList

使用Collections.sort()方法对LinkedList排序的 Java 示例。 请注意，对于对象的自定义排序，我们可以使用Collections.sort(linkedList, comparator)方法。

  1. LinkedList<String> linkedList = new LinkedList<>();
  3. linkedList.add("A");
  4. linkedList.add("C");
  5. linkedList.add("B");
  6. linkedList.add("D");
  8. //Unsorted
  9. System.out.println(linkedList);
  11. //1\. Sort the list
  12. Collections.sort(linkedList);
  14. //Sorted
  15. System.out.println(linkedList);
  17. //2\. Custom sorting
  18. Collections.sort(linkedList, Collections.reverseOrder());
  20. //Custom sorted
  21. System.out.println(linkedList);

程序输出：

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

6. LinkedList用例

在任何桌面应用程序中，动作都可以记录在链表中，并实现从上一次迭代的撤消和重做特性。

可以使用链表对浏览器的“下一个”和“上一个”按钮进行编程。

链表（与哈希表配对）对于 LRU 缓存非常有用。

7. LinkedList性能

在 Java LinkedList类中，由于不需要进行任何转换，因此处理速度很快。 因此，基本上，所有添加和删除方法都提供非常好的性能O(1)。

  • add(E element)方法是O（1）。
  • get(int index)和add(int index, E element)方法的类型为O(n)。
  • remove(int index)方法的值为O(n)。
  • Iterator.remove()为O(1)。
  • ListIterator.add(E element)为O(1)。

应该首选LinkedList，因为没有大量的元素随机访问，而有大量的添加/删除操作。

8. ArrayList与LinkedList

让我们列出arraylist和链表之间的一些值得注意的差异。

  • ArrayList是使用动态可调整大小的数组的概念实现的。 而LinkedList 是双向链表实现。
  • ArrayList允许随机访问其元素，而LinkedList则不允许。
  • LinkedList还实现Queue接口，该接口添加了比 ArrayList 更多的方法，例如offer()，peek()，poll()等。
  • 与LinkedList相比，ArrayList 的添加和删除速度较慢，但获取速度较快，因为如果数组在LinkedList中已满，则无需调整数组大小并将内容复制到新数组中 。
  • LinkedList比ArrayList具有更多的内存开销，因为在ArrayList中，每个索引仅保存实际对象，但是在LinkedList的情况下，每个节点都保存下一个和上一个节点的数据和地址。

9. 总结

在此 Java LinkedList教程中，我们学习了什么是LinkedList，LinkedList和ArrayList之间的区别是什么，如何创建LinkedList，如何在 LinkedList中添加，删除和搜索元素，以及如何遍历LinkedList。

让我知道您的问题。

学习愉快！

参考：

LinkedList Java 文档