JavaRush /Java Blog /Random-TW /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