你好！所有最新課程都專注於ArrayList。這種數據結構非常方便和有用。它可以處理大量任務。但是 Java 還有很多其他的數據結構。為什麼？最重要的是，因為任務的範圍是巨大的，並且最有效的數據結構對於不同的任務是不同的。今天我們將認識一個新結構：Java LinkedList，一個雙向鍊錶。
![鍊錶 - 1]()
讓我們看看它是如何組織的，為什麼稱為雙向鏈接，它與ArrayList有何不同。Java LinkedList中的元素實際上是單個鏈中的鏈接。除了數據之外，每個元素還存儲對前一個和下一個元素的引用。這些引用使您可以從一個元素移動到另一個元素。這是你如何創建一個：
![鍊錶 - 2]()
讓我們看看如何添加新元素。這是使用add()方法完成的。
![鍊錶 - 3]()
結果，str2和str1通過存儲在列表的這個節點中的 下一個和上一個鏈接鏈接起來：![鍊錶 - 4]()
現在您應該理解雙向鍊錶的主要思想了。這個鏈接鏈正是使LinkedList元素成為單個列表的原因。與ArrayList不同，LinkedList內部沒有數組或任何類似數組的內容。任何（嗯，大多數）使用 ArrayList 歸結為使用內部數組。任何與Java LinkedList相關的工作歸結為更改鏈接。通過在列表中間添加一個元素可以非常清楚地看到這一點：
![鍊錶 - 5]()
![鍊錶 - 6]()
![Java university]()
![鍊錶 - 7]()
更新鏈接後，我們得到了期望的結果： 與ArrayList![鍊錶 - 8]()
中的刪除操作不同，這裡不需要移動數組元素或任何類型的東西。我們只是更新str1和str3的鏈接。它們現在指向彼此，並且str2已經從鏈接鏈中 “退出”並且不再是列表的一部分。
![Java webinar]()
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 ”）。
|
更多閱讀： |
|---|