Java中的链表数据结构

为不同的目的创建不同的数据结构。你可能知道ArrayList（如果还不知道，我们建议你先阅读一下）。在本文中，我们将了解LinkedList并了解此集合的用途。如果您查看 LinkedList Java 8（或该语言的更高版本）类代码源（在 Oracle 网站或您的 IDE 中，如果是 IDEA：类名上的 crtl+B），您将看到下一个声明：

public class LinkedList<E>
   extends AbstractSequentialList<E>
   implements List<E>, Deque<E>, Cloneable, java.io.Serializable

目前，代码中最重要的信息是LinkedList实现了List和Deque接口。List 接口保持添加项目的顺序，并允许通过索引访问项目。“普通” Queue支持在末尾添加元素，从头提取元素。Deque 是一个双向队列，它支持从两侧添加和删除元素。您可以将其视为堆栈和队列的组合。因此，LinkedList 是这两者的实现，它允许我们创建一个双向队列，该队列由包括 null 在内的任何对象组成。链表是元素的集合。我们在类的代码源中可以看到，这次要注意字段：

transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;

每个元素，通常我们称之为Node，包含一个对象和对两个相邻对象的引用——前一个和下一个。因此，它在使用内存方面不是很有效。 由于LinkedList实际上是一个双向结构，我们可以很容易地从两侧添加或删除元素。

链表构造函数

回到代码源，我们可以发现LinkedList有两个构造函数

• 不带参数的LinkedList()用于构造一个空列表。
• >LinkedList(Collection<? extends E> c)用于创建包含指定集合的​​元素的列表，它们按顺序由集合的迭代器返回。

链表声明

事实上，链表（Java 或任何其他语言）由一系列节点组成。每个节点都旨在存储创建时定义的类型的对象。因此，要创建LinkedList，接下来是 Java 代码：

LinkedList<Integer> myList = new LinkedList<>();

我们有一个对象来保存一系列整数和到邻居的链接。然而，此刻它是空的。

链表主要操作

像往常一样，在 Collections 的情况下，您可以将元素放入LinkedList（到它的末尾或中间），从那里删除，然后通过索引获取元素。所以他们在这里：

• add(E element)将指定的元素附加到此列表的末尾；
• add(int index, E element)在指定位置index插入元素；
• get(int index)返回此列表中指定位置的元素；
• remove(int index)移除索引位置的元素；
• remove(Object o)移除第一次出现的 ? o此列表中的元素（如果存在）。
• remove()检索并删除列表的第一个元素。

Java中的链表实现，添加和删除元素。例子

让我们在实践中尝试这些操作。首先，Java LinkedList 实现：创建一个字符串的 LinkedList，添加 3 个元素。然后去掉一个，再在中间加一个。

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

运行这个程序的结果：

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]

LinkedList是Collection框架的一部分，您可以使用 Iterator 来删除元素，以及用于列表的特殊迭代器- ListIterator。更重要的是，使用迭代器的操作提供了LinkedList类的主要优点：插入/删除操作的良好性能。使用 Iterator 你可能会得到一个固定的时间。在本文的后面，我们将编写一个代码示例来比较ArrayList和LinkedList+Iterator

• Iterator.remove()删除此迭代器返回的最后一个元素。
• ListIterator.add(E element)向列表中插入一个元素

Java 链表示例：迭代器的工作原理

这里我们有一个小的 Java LinkedList示例代码，我们尝试通过 Iterator 添加和删除。

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
 
       Iterator i = linkedList.iterator();
       String str = "";
       while (i.hasNext()) {
           str = (String)i.next();
           if (str.equals("favorite")) {
               i.remove();
               break;
           }
       }

       System.out.println("linkedList after removing element via Iterator:");
       System.out.println(linkedList);
       ListIterator listIterator = linkedList.listIterator();
       listIterator.add("I've got");
       System.out.println("linkedList after adding the element via ListIterator");
       System.out.println(linkedList);
 
   }
}

运行这个程序的结果：

linkedList after removing element via Iterator:
[my, book]
linkedList after adding the element via ListIterator
[I've got, my, book]

更多 Java LinkedList操作：

• addFirst() , addLast() 添加一个元素到列表的开头/结尾
• clear()从列表中删除所有元素
• 如果列表包含 o 元素，则contains(Object o)返回 true。
• indexOf(Object o)返回 o 元素第一次出现的索引，如果不在列表中则返回 -1。
• set(int index, E element)用元素替换索引位置的元素
• size() 返回列表中元素的数量。
• toArray()返回一个数组，其中包含列表中从第一个元素到最后一个元素的所有元素。

顺便说一句， Java 中的 LinkedList是一个双大小的队列，具有特定于堆栈的操作：

• pop()从堆栈中弹出一个元素（由列表表示）
• push(E e)将元素推入堆栈（由此列表表示）

如何反转 LinkedList：示例

这是一个小例子，一个流行的，但对初学者来说是一个简单的任务。我们有一个LinkedList并且应该反转它。最简单的算法是以相反的顺序遍历LinkedList并将每个元素放入新的。但是，也许您会找到更好的方法？这是反向链表java程序的代码：

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println(linkedList);
       System.out.println("Reversed LinkedList:");
       System.out.println(reverseLinkedList(linkedList));
   }
   public static LinkedList<String> reverseLinkedList(LinkedList<String> list)
   {
       LinkedList<String> LinkedList = new LinkedList<String>();
       for (int i = list.size() - 1; i >= 0; i--) {
           LinkedList.add(list.get(i));
       }
       return LinkedList;
   }
}

结果：

[I've got, my, book]
Reversed LinkedList:
[book, my, I've got]

LinkedList 与 ArrayList：何时使用第一个

LinkedList和ArrayList都是List接口的实现。LinkedList用双向链表来实现它。ArrayList使用动态调整大小的数组来实现它。如您所知，LinkedList的每个节点都包含对象和两个对邻居的引用。这意味着在 Java LinkedList的情况下存储元素之间的引用需要额外的内存成本。ArrayList使用动态调整大小的数组来实现它。某些LinkedList和ArrayList操作看起来相同，但它们的工作方式不同。在数组列表中在这种情况下，您在LinkedList中使用内部数组进行操作——使用引用。 ArrayList是最流行的List实现。当索引访问优先时，您绝对应该使用ArrayList，因为这些操作是在恒定时间内执行的。平均添加到列表的末尾也是在恒定时间内完成的。更重要的是，ArrayList没有存储一堆元素的额外成本。当不在列表末尾时，您可以将插入和删除操作的速度算作 Cons。 链表在某些方面的插入和删除操作性能的情况下更有用：如果您使用迭代器，它会在恒定时间内发生。通过从头到尾（取较近的）搜索所需元素来执行按索引的访问操作。但是，不要忘记在元素之间存储引用的额外成本。因此，这里是具有算法运行时的标准LinkedList和ArrayList操作。N指的是列表中已经存在的项目数。O(N)意味着在最坏的情况下，我们应该“遍历”整个列表，直到找到所需的位置，例如，将新元素插入列表中。O(1)意味着操作发生在常数时间内，独立于项目的数量。

链表时间复杂度

ArrayList 时间复杂度

何时使用 LinkedList：示例

毫无疑问，ArrayList是最流行的List实现。但是，您可能会遇到过于频繁地需要添加/删除操作的情况。在这种情况下，LinkedList与 Iterator 一起使用可能会有所帮助。这是一个例子。我们有一个很长的列表，我们应该从这个列表中删除每个元素。让我们用ArrayList和LinkedList + Iterator来完成这个任务。我们比较每个操作的时间并将其打印到控制台。这里的代码：

import java.util.*;
import java.util.function.BiPredicate;
 
public class ListTest2 {
 
   static void removeElements(List<Double> list, BiPredicate<Integer, Double> predicate) {
       // start navigation from end to preserve indexes of removed items
       ListIterator<Double> iterator = list.listIterator(list.size());
 
       while (iterator.hasPrevious()) {
           Double element = iterator.previous();
           if (predicate.test(iterator.previousIndex()+1, element)) {
               iterator.remove();
           }
       }
   }
 
   static class TestCase1 {
       public static void main(String[] args) {
           LinkedList<Double> testedList1 = new LinkedList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList1, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList1 after removeElements(..): " + testedList1);
 
           ArrayList<Double> testedList2 = new ArrayList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList2, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList2 after removeElements(..): " + testedList2);
       }
   }
 
   static class TestLinkedListPerformance {
       public static void main(String[] args) {
           LinkedList<Double> testedList = new LinkedList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `0.1527659`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
 
   static class TestArrayListPerformance {
       public static void main(String[] args) {
           ArrayList<Double> testedList = new ArrayList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `53.4952635`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
}

ArrayList 的结果：

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 481.8824414

链表的结果：

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 0.4586458

如您所见，在这种情况下，LinkedList 更有效。说实话。在实际的软件开发中，LinkedList 的使用是一种罕见的事件。尽管如此，专业人员应该了解这种数据结构的存在及其优点。如果说在实际代码中LinkedList是个稀罕客，那么在 Java Junior 面试中它就非常受欢迎。然而，这是 Joshua Bloch 写的关于LinkedList的内容：

AddOn：单链表 Java

Java中经典的Collection中没有单向链表，单向链表是一种结构，其中每个节点都包含一个对象和对下一个节点的引用，但不包含对前一个节点的引用。Java LinkedList是双向链表，但没有人会干涉您创建自己的数据结构，例如单链表，code>Linked List。以下是解决这些任务的一些步骤：

1. 创建一个具有两个属性 data 和 next 的Node类。Next 是对下一个节点的引用。
2. 创建具有两个属性 head 和 tail 的FirstLast类。
3. 创建一个add()方法以将新节点添加到列表中。首先检查列表是否为空（head == null）。如果是，则 head 和 tail 指的是新节点。如果链表不为空，新节点会被添加到末尾，所以tail的next属性指的是添加的节点，新节点成为链表的尾部。

顺便说一句，您也可以尝试创建自己的LinkedList作为练习。祝你学习顺利。