你好！所有最新课程都专注于ArrayList。这种数据结构非常方便和有用。它可以处理大量任务。但是 Java 还有很多其他的数据结构。为什么？最重要的是，因为任务的范围是巨大的，并且最有效的数据结构对于不同的任务是不同的。今天我们要认识一个新的结构：Java LinkedList，一个双向链表。
![链表 - 1]()
让我们看看它是如何组织的，为什么称为双向链接，它与ArrayList有何不同。Java LinkedList中的元素实际上是单个链中的链接。除了数据之外，每个元素还存储对前一个和下一个元素的引用。这些引用使您可以从一个元素移动到另一个元素。这是你如何创建一个：
![链表 - 2]()
让我们看看如何添加新元素。这是使用add()方法完成的。
![链表 - 3]()
结果，str2和str1通过存储在列表的这个节点中的 下一个和上一个链接链接起来：![链表 - 4]()
现在您应该理解双向链表的主要思想了。这个链接链正是使LinkedList元素成为单个列表的原因。与ArrayList不同，LinkedList内部没有数组或任何类似数组的东西。任何（嗯，大多数）使用 ArrayList 归结为使用内部数组。任何与Java LinkedList相关的工作归结为更改链接。通过在列表中间添加一个元素可以非常清楚地看到这一点：
![链表 - 5]()
![链表 - 6]()
![链表 - 7]()
更新链接后，我们得到了期望的结果： 与ArrayList![链表 - 8]()
中的删除操作不同，这里不需要移动数组元素或任何类型的东西。我们只是更新str1和str3的链接。它们现在指向彼此，并且str2已经从链接链中 “退出”并且不再是列表的一部分。
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);
}
}
让我们看看如何添加新元素。这是使用add()方法完成的。
earlBio.add(str2);
结果，str2和str1通过存储在列表的这个节点中的 下一个和上一个链接链接起来：
现在您应该理解双向链表的主要思想了。这个链接链正是使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);
}
}
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);
}
}
更新链接后，我们得到了期望的结果： 与ArrayList
中的删除操作不同，这里不需要移动数组元素或任何类型的东西。我们只是更新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 + '\'' +
'}';
}
}
- 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());
}
- 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);
}
- 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));
}
- 检查是否有足够的空间（插入时）
- 如果没有，那么我们创建一个新数组并将数据复制到那里（插入时）
- 我们删除/插入元素，并将所有其他元素向右/向左移动（取决于操作类型）。而这个过程的复杂性在很大程度上取决于列表的大小。复制/移动 10 个元素是一回事，而对一百万个元素执行相同操作则是另一回事。
理论上
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));
}
}
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));
}
}
list.add(2_000_000, new Integer(Integer.MAX_VALUE));
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());
}
}
}
- 并非任何特定集合的所有理论优势在现实中总是有效（我们在涉及列表中间的示例中看到了这一点）
- 在选择集合时不要采取极端立场（“ ArrayList总是更快。使用它不会出错。没有人长期使用LinkedList ”）。
|
更多阅读： |
|---|
GO TO FULL VERSION