第 41 级

San Francisco

21 七月 2023
325 views
0 comments

Java链表

你好！所有最新课程都专注于ArrayList。这种数据结构非常方便和有用。它可以处理大量任务。但是 Java 还有很多其他的数据结构。为什么？最重要的是，因为任务的范围是巨大的，并且最有效的数据结构对于不同的任务是不同的。今天我们要认识一个新的结构：Java LinkedList，一个双向链表。

让我们看看它是如何组织的，为什么称为双向链接，它与ArrayList有何不同。Java LinkedList中的元素实际上是单个链中的链接。除了数据之外，每个元素还存储对前一个和下一个元素的引用。这些引用使您可以从一个元素移动到另一个元素。这是你如何创建一个：


public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str2);
       earlBio.add(str3);
       earlBio.add(str4);

       System.out.println(earlBio);

   }
}

输出： [你好世界！我叫 Earl，我喜欢 Java，我住在加拿大] 这是我们的列表的样子：链表 - 2

让我们看看如何添加新元素。这是使用add()方法完成的。


earlBio.add(str2);

在代码中，我们的列表包含一个元素：字符串str1。让我们看看图中接下来会发生什么：链表 - 3

结果，str2和str1通过存储在列表的这个节点中的下一个和上一个链接链接起来：链表 - 4

现在您应该理解双向链表的主要思想了。这个链接链正是使LinkedList元素成为单个列表的原因。与ArrayList不同，LinkedList内部没有数组或任何类似数组的东西。任何（嗯，大多数）使用 ArrayList 归结为使用内部数组。任何与Java LinkedList相关的工作归结为更改链接。通过在列表中间添加一个元素可以非常清楚地看到这一点：


public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       System.out.println(earlBio);

   }
}

如您所见，重载的add()方法允许您为新项目指定特定索引。在这种情况下，我们要在str1和str3之间添加 String str2。这是内部会发生的事情：更改内部链接后，str2已成功添加到列表中：现在所有 3 个元素都已连接。您可以通过下一个链接从链上的第一个元素移动到最后一个元素，然后再返回。所以，我们对插入相当满意，但是删除元素呢？原理完全一样。我们只是更新被删除元素的“左侧和右侧”两个元素中的链接：链表 - 5


public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       earlBio.remove(1);
       System.out.println(earlBio);
   }
}

下面是如果我们删除索引为 1 的项目（它在列表的中间）会发生什么：链表 - 7

更新链接后，我们得到了期望的结果：与ArrayList 链表 - 8

中的删除操作不同，这里不需要移动数组元素或任何类型的东西。我们只是更新str1和str3的链接。它们现在指向彼此，并且str2已经从链接链中 “退出”并且不再是列表的一部分。

方法概述

LinkedList与ArrayList有很多共同的方法。例如，这两个类都有add()、remove()、indexOf()、clear()、contains()（指示项目是否在列表中）、set()（替换现有元素）和尺寸（）。尽管它们中的许多在内部工作方式不同（正如我们在add()和remove()中发现的那样），但最终结果是相同的。但是，LinkedList确实有单独的方法来处理列表的开头和结尾，而ArrayList没有：

addFirst() , addLast()：这些方法用于将元素添加到列表的开头/结尾


public class Car {

   String model;

   public Car(String model) {
       this.model = model;
   }

   public static void main(String[] args) {
       LinkedList<Car> cars = new LinkedList<>();
       Car ferrari = new Car("Ferrari 360 Spider");
       Car bugatti = new Car("Bugatti Veyron");
       Car lambo = new Car("Lamborghini Diablo");
       Car ford = new Car("Ford Mondeo");
       Car fiat = new Car("Fiat Ducato");

       cars.add(ferrari);
       cars.add(bugatti);
       cars.add(lambo);
       System.out.println(cars);

       cars.addFirst(ford);
       cars.addLast(fiat);
       System.out.println(cars);
   }

   @Override
   public String toString() {
       return "Car{" +
               "model='" + model + '\'' +
               '}';
   }
}

输出： [Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] [Car{model='Ford Mondeo'}, Car{model=' Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}, Car{model='Fiat Ducato'}] 我们最终在列表的顶部看到“Ford” ，最后是“菲亚特”。

peekFirst()、peekLast()：这些方法返回列表中的第一个/最后一个元素。如果列表为空，它们返回null 。


public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.peekFirst());
   System.out.println(cars.peekLast());
}

输出： Car{model='Ferrari 360 Spider'} Car{model='Lamborghini Diablo'}

pollFirst()、pollLast()：这些方法返回列表中的第一个/最后一个元素并将其从列表中移除。如果列表为空，它们返回 null


public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.pollFirst());
   System.out.println(cars.pollLast());

   System.out.println ("What's on the list?");
   System.out.println(cars);
}

输出： Car{model='Ferrari 360 Spider'} Car{model='Lamborghini Diablo'} 列表中还剩下什么？[汽车{model='布加迪威龙'}]

toArray()：此方法返回包含列表项的数组


public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   Car[] carsArray = cars.toArray(new Car[3]);
   System.out.println(Arrays.toString(carsArray));
}

输出： [Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] 现在我们知道 LinkedList 的工作原理以及它的组织与ArrayList有何不同。使用LinkedList有什么好处？最重要的是，我们在列表中间工作时受益。LinkedList中间的插入和删除操作比 ArrayList 简单得多。我们只需更新相邻元素的链接，不需要的元素就会从链接链中“退出”。但是在ArrayList中，我们必须

检查是否有足够的空间（插入时）
如果没有，那么我们创建一个新数组并将数据复制到那里（插入时）
我们删除/插入元素，并将所有其他元素向右/向左移动（取决于操作类型）。而这个过程的复杂性在很大程度上取决于列表的大小。复制/移动 10 个元素是一回事，而对一百万个元素执行相同操作则是另一回事。

换句话说，如果列表中间的插入/删除操作在您的程序中最常见，那么LinkedList应该比ArrayList更快。

理论上


public class Main {

   public static void main(String[] args) {
       List<Integer> list = new LinkedList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

输出： LinkedList 花费的时间（以毫秒为单位）= 1873


public class Main {

   public static void main(String[] args) {
       List<Integer> list = new ArrayList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

输出： ArrayList 花费的时间（以毫秒为单位）= 181 这出乎意料！我们执行了一个LinkedList应该更有效的操作：在列表中间插入 100 个项目。我们的列表非常庞大：5,000,000 个元素。ArrayList必须在每次插入时移动几百万个项目！怎么赢的？首先， ArrayList访问元素所需的时间是固定的（常量）。当你写


list.add(2_000_000, new Integer(Integer.MAX_VALUE));

那么ArrayList [2_000_000]就是一个具体的内存地址（毕竟list有内部数组）。但是，LinkedList没有数组。它将沿着链接链搜索元素编号 2_000_000。对于LinkedList，这不是一个内存地址，而是一个仍然需要到达的链接： fistElement.next.next.next.next.next.next.next.next.next.next.next.next.next.next。 next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next………… 这样一来，每次插入（移除）中间的链表, ArrayList已经知道要访问的确切内存地址，但LinkedList仍然需要“到达那里”。二、 ArrayList的结构本身。一个特殊的内部函数 ( System.arrayCopy() ) 扩展内部数组，并复制和移动所有元素。它非常快，因为它针对这项特定工作进行了优化。但是当您不必“获取”特定索引时，LinkedList是赢家。假设我们在列表的最开头插入。让我们尝试在那里插入一百万个元素：


public class Main {

   public static void main(String[] args) {
       getTimeMsOfInsert(new ArrayList());
       getTimeMsOfInsert(new LinkedList());
   }

   public static long getTimeMsOfInsert(List list) {
       // Write your code here
       Date currentTime = new Date();
       insert1000000(list);
       Date newTime = new Date();
       long msDelay = newTime.getTime() - currentTime.getTime(); // Calculate the difference
       System.out.println("The result in milliseconds: " + msDelay);
       return msDelay;

   }

   public static void insert1000000(List list) {
       for (int i = 0; i < 1000000; i++) {
           list.add(0, new Object());
       }
   }

}

输出： 以毫秒为单位的结果：43448 以毫秒为单位的结果：107 现在我们得到一个完全不同的结果！ ArrayList花了超过 43 秒的时间在列表的前面插入一百万个项目，而LinkedList设法在 0.1 秒内完成！ LinkedList在这里受益，因为它不必每次都通过链接链运行到列表的中间。它立即在列表的开头找到所需的索引，因此不同的算法已经是一个优势。:) 事实上，关于“ ArrayList与LinkedList ”的讨论非常广泛，目前我们不会深入探讨。你需要记住的主要事情是：

并非任何特定集合的所有理论优势在现实中总是有效（我们在涉及列表中间的示例中看到了这一点）
在选择集合时不要采取极端立场（“ ArrayList总是更快。使用它不会出错。没有人长期使用LinkedList ”）。

尽管连LinkedList的作者 Joshua Bloch 都说是这样的。:) 尽管如此，这个观点远非 100% 正确，我们已经确信这一点。在我们之前的示例中，LinkedList快了 400 (!) 倍。另一件事是，确实很少有LinkedList是最佳选择的情况。但它们确实存在，并且在适当的时候LinkedList能给你丰厚的回报。不要忘记我们在课程开始时说过的话：最高效的数据结构对于不同的任务是不同的。在了解任务的所有条件之前，不可能 100% 确定哪种数据结构最好。稍后您将对这些集合有更多了解，这将使选择更加容易。但最简单和最有效的选择总是相同的：在程序中使用的实际数据上尝试两者。然后您将能够亲眼看到这两种列表的性能，并且您绝对不会出错。:)为了巩固您所学的知识，我们建议您观看我们的 Java 课程中的视频课程

更多阅读：
链表 Java 数据结构

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION