JavaRush /Java 博客 /Random-ZH /Java 中的链表

第 41 级

28 二月 2021
49 views
0 comments

Java 中的链表

你好！最近的所有讲座都致力于研究ArrayList列表。这种数据结构非常方便，可以让你解决很多问题。然而，Java 还有许多其他数据结构。为什么？首先，因为现有任务的范围非常广泛，对于不同的任务不同的数据结构是最有效的。今天我们将认识一种新的结构——双向链表LinkedList。让我们弄清楚它是如何工作的，为什么它被称为双连接，以及它与ArrayList有何不同。在LinkedList 中，元素实际上是链中的链接。每个元素除了它存储的数据之外，还具有到上一个和下一个元素的链接。这些链接允许您从一个元素移动到另一个元素。它是这样创建的：

public class Main {

   public static void main(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 Moscow");

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

       System.out.println(earlBio);

   }
}

结论：


[Hello World! My name is Earl, I love Java, I live in Moscow]

这就是列表的结构：

让我们看看如何添加新元素。这是使用add().

earlBio.add(str2);

在执行这行代码时，我们的列表由一个元素组成 - string str1。让我们看看接下来的图中会发生什么：链表 - 3

结果str2，并通过其中str1存储的链接建立连接：现在你应该明白双向链表的主要思想了。正是由于这个链接链，这些元素才成为一个列表。里面没有数组，比如 in或类似的东西。所有使用ArrayList 的工作（总的来说）都归结为使用内部数组。所有工作都归结为更改链接。通过向列表中间添加一个元素可以非常清楚地看到这一点： nextprevious 链表 - 4

LinkedListLinkedListArrayListLinkedList

public class Main {

   public static void main(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 Moscow");

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

       System.out.println(earlBio);

   }
}

如您所见，重载方法add()允许您为新元素指定特定索引。在本例中，我们要在和str2之间添加一行。这就是内部将发生的情况：由于更改了内部链接，该元素已成功添加到列表中：现在所有 3 个元素都已链接。从链上的第一个元素开始，您可以转到最后一个元素并返回。我们或多或少已经弄清楚了插入，但是删除元素呢？工作原理是一样的。我们只需重新定义被删除元素“两侧”的两个元素的链接： str1str3 链表 - 5

str2

next

public class Main {

   public static void main(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 Moscow");

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

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

如果我们删除索引为 1 的元素（位于列表的中间），将会发生以下情况：链表 - 7

重新定义链接后，我们得到了所需的结果：链表 - 8

与删除不同，ArrayList没有数组元素的移位等。str1我们只需重新定义和元素的引用即可str3。现在它们互相指向，并且该对象str2已从该链接链中“退出”，并且不再是列表的一部分。

方法概述

它与方法LinkedList有很多相似之处。ArrayList例如，诸如add()、remove()、indexOf()、clear()、contains()（是列表中包含的元素）、set()（插入替换元素）之类的方法size()都存在于两个类中。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'}]

结果，福特位居榜首，菲亚特垫底。

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 left on the list?");
   System.out.println(cars);
}

结论：


Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}
What осталось в списке?
[Car{model='Bugatti Veyron'}]

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 个元素是一回事，但对 100 万个元素执行相同操作则完全是另一回事。

也就是说，如果在您的程序中插入/删除操作更频繁地发生在列表的中间，那么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 to run for LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

结论：


Время работы для LinkedList (в мorсекундах) = 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 to run for 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));

那么在 [2_000_000] 的情况下，ArrayList这是内存中的特定地址，因为它内部有一个数组。而LinkedList数组则不然。它将沿着链接链查找编号为 2_000_000 的元素。对他来说，这不是内存中的地址，而是仍然需要到达的链接：


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“a”本身的结构。扩展内部数组、复制所有元素和移动元素是由一个特殊的内部函数 - 执行的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("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

完全不同的结果！将一百万个元素插入到列表开头需要超过 43 秒ArrayList，而只LinkedList用了 0.1 秒就完成了！事实上，在这种情况下，LinkedList我们不必每次都通过链接链“运行”到列表的中间。他立即在列表的开头找到了所需的索引，操作原理的差异已经在他这边了:)事实上，“ArrayList对比LinkedList”的讨论非常广泛，我们暂时不深入讨论等级。您需要记住的主要事情是：

并非“纸面上”的特定集合的所有优点都会在现实中发挥作用（我们使用列表中间的示例来查看这一点）
在选择集合时，你不应该走极端（“ArrayList它总是更快，使用它，你不会出错。LinkedList很长时间没有人使用它了”）。

虽然连创作者LinkedListJoshua Bloch 都这么说：）但是，这个观点远非 100% 正确，对此我们深信不疑。在我们之前的示例中，LinkedList它的运行速度快了 400 (!) 倍。另一件事是，在很少的情况下LinkedList它是最好的选择。但它们确实存在，而且在适当的时候LinkedList它们可以认真地帮助你。不要忘记我们在讲座开始时谈到的内容：不同的数据结构对于不同的任务最有效。在了解问题的所有条件之前，不可能 100% 确信哪种数据结构更好。稍后你会对这些藏品有更多的了解，也会更容易做出选择。但最简单、最有效的选择始终是相同的：对程序中的真实数据进行测试。然后你就可以亲眼看到两个列表的结果了，绝对不会出错:)

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