你好!所有最新課程都專注於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,我住在加拿大] 這是我們的列表的樣子: 讓我們看看如何添加新元素。這是使用add()方法完成的。
earlBio.add(str2);
在代碼中,我們的列表包含一個元素:字符串str1。讓我們看看圖中接下來會發生什麼: 結果,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);
}
}
如您所見,重載的add()方法允許您為新項目指定特定索引。在這種情況下,我們要在str1和str3之間添加 String str2。這是內部會發生的事情: 更改內部鏈接後,str2已成功添加到列表中: 現在所有 3 個元素都已連接。您可以通過下一個鏈接從鏈上的第一個元素移動到最後一個元素,然後再返回。所以,我們對插入相當滿意,但是刪除元素呢?原理完全一樣。我們只是更新被刪除元素的“左側和右側”兩個元素中的鏈接:
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 的項目(它在列表的中間)會發生什麼: 更新鏈接後,我們得到了期望的結果: 與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 + '\'' +
'}';
}
}
輸出: [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 個元素是一回事,而對一百萬個元素執行相同操作則是另一回事。
理論上
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 ”)。
更多閱讀: |
---|
GO TO FULL VERSION