Java中的鍊錶數據結構

為不同的目的創建不同的數據結構。你可能知道ArrayList（如果還不知道，我們建議你先閱讀一下）。在本文中，我們將了解LinkedList並了解此集合的用途。如果您查看 LinkedList Java 8（或該語言的更高版本）類代碼源（在 Oracle 網站或您的 IDE 中，如果是 IDEA：類名上的 crtl+B），您將看到下一個聲明：

public class LinkedList<E>
   extends AbstractSequentialList<E>
   implements List<E>, Deque<E>, Cloneable, java.io.Serializable

目前，代碼中最重要的信息是LinkedList實現了List和Deque接口。List 接口保持添加項目的順序，並允許通過索引訪問項目。“普通” Queue支持在末尾添加元素，從頭提取元素。Deque 是一個雙向隊列，它支持從兩側添加和刪除元素。您可以將其視為堆棧和隊列的組合。因此，LinkedList 是這兩者的實現，它允許我們創建一個雙向隊列，該隊列由包括 null 在內的任何對象組成。鍊錶是元素的集合。我們在類的代碼源中可以看到，這次要注意字段：

transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;

每個元素，通常我們稱之為Node，包含一個對象和對兩個相鄰對象的引用——前一個和下一個。因此，它在使用內存方面不是很有效。 由於LinkedList實際上是一個雙向結構，我們可以很容易地從兩側添加或刪除元素。

鍊錶構造器

回到代碼源，我們可以發現LinkedList有兩個構造函數

• 不帶參數的LinkedList()用於構造一個空列表。
• >LinkedList(Collection<? extends E> c)用於創建包含指定集合的​​元素的列表，它們按順序由集合的迭代器返回。

鍊錶聲明

事實上，鍊錶（Java 或任何其他語言）由一系列節點組成。每個節點都旨在存儲創建時定義的類型的對象。因此，要創建LinkedList，接下來是 Java 代碼：

LinkedList<Integer> myList = new LinkedList<>();

我們有一個對象來保存一系列整數和到鄰居的鏈接。然而，此刻它是空的。

鍊錶主要操作

像往常一樣，在 Collections 的情況下，您可以將元素放入LinkedList（到它的末尾或中間），從那裡刪除，然後通過索引獲取元素。所以他們在這裡：

• add(E element)將指定的元素附加到此列表的末尾；
• add(int index, E element)在指定位置index插入元素；
• get(int index)返回此列表中指定位置的元素；
• remove(int index)移除索引位置的元素；
• remove(Object o)移除第一次出現的 ? o此列表中的元素（如果存在）。
• remove()檢索並刪除列表的第一個元素。

Java中的鍊錶實現，添加和刪除元素。例子

讓我們在實踐中嘗試這些操作。首先，Java LinkedList 實現：創建一個字符串的 LinkedList，添加 3 個元素。然後去掉一個，再在中間加一個。

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

運行這個程序的結果：

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]

LinkedList是Collection框架的一部分，您可以使用 Iterator 來刪除元素，以及用於列表的特殊迭代器 - ListIterator。更重要的是，使用迭代器的操作提供了LinkedList類的主要優點：插入/刪除操作的良好性能。使用 Iterator 你可能會得到一個固定的時間。在本文的後面，我們將編寫一個代碼示例來比較ArrayList和LinkedList+Iterator

• Iterator.remove()刪除此迭代器返回的最後一個元素。
• ListIterator.add(E element)向列表中插入一個元素

Java 鍊錶示例：迭代器的工作原理

這裡我們有一個小的 Java LinkedList示例代碼，我們嘗試通過 Iterator 添加和刪除。

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
 
       Iterator i = linkedList.iterator();
       String str = "";
       while (i.hasNext()) {
           str = (String)i.next();
           if (str.equals("favorite")) {
               i.remove();
               break;
           }
       }

       System.out.println("linkedList after removing element via Iterator:");
       System.out.println(linkedList);
       ListIterator listIterator = linkedList.listIterator();
       listIterator.add("I've got");
       System.out.println("linkedList after adding the element via ListIterator");
       System.out.println(linkedList);
 
   }
}

運行這個程序的結果：

linkedList after removing element via Iterator:
[my, book]
linkedList after adding the element via ListIterator
[I've got, my, book]

更多 Java LinkedList操作：

• addFirst() , addLast() 添加一個元素到列表的開頭/結尾
• clear()從列表中刪除所有元素
• 如果列表包含 o 元素，則contains(Object o)返回 true。
• indexOf(Object o)返回 o 元素第一次出現的索引，如果不在列表中則返回 -1。
• set(int index, E element)用元素替換索引位置的元素
• size() 返回列表中元素的數量。
• toArray()返回一個數組，其中包含列表中從第一個元素到最後一個元素的所有元素。

順便說一句， Java 中的 LinkedList是一個雙大小的隊列，具有特定於堆棧的操作：

• pop()從堆棧中彈出一個元素（由列表表示）
• push(E e)將元素推入堆棧（由此列表表示）

如何反轉 LinkedList：示例

這是一個小例子，一個流行的，但對初學者來說是一個簡單的任務。我們有一個LinkedList並且應該反轉它。最簡單的算法是以相反的順序遍歷LinkedList並將每個元素放入新的。但是，也許您會找到更好的方法？這是反向鍊錶java程序的代碼：

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println(linkedList);
       System.out.println("Reversed LinkedList:");
       System.out.println(reverseLinkedList(linkedList));
   }
   public static LinkedList<String> reverseLinkedList(LinkedList<String> list)
   {
       LinkedList<String> LinkedList = new LinkedList<String>();
       for (int i = list.size() - 1; i >= 0; i--) {
           LinkedList.add(list.get(i));
       }
       return LinkedList;
   }
}

結果：

[I've got, my, book]
Reversed LinkedList:
[book, my, I've got]

LinkedList 與 ArrayList：何時使用第一個

LinkedList和ArrayList都是List接口的實現。LinkedList用雙向鍊錶來實現它。ArrayList使用動態調整大小的數組來實現它。如您所知，LinkedList的每個節點都包含對象和兩個對鄰居的引用。這意味著在 Java LinkedList的情況下存儲元素之間的引用需要額外的內存成本。ArrayList使用動態調整大小的數組來實現它。某些LinkedList和ArrayList操作看起來相同，但它們的工作方式不同。在數組列表中在這種情況下，您在LinkedList中使用內部數組進行操作——使用引用。 ArrayList是最流行的List實現。當索引訪問優先時，您絕對應該使用ArrayList，因為這些操作是在恆定時間內執行的。平均添加到列表的末尾也是在恆定時間內完成的。更重要的是，ArrayList沒有存儲一堆元素的額外成本。當不在列表末尾時，您可以將插入和刪除操作的速度算作 Cons。 鍊錶在某些方面的插入和刪除操作性能的情況下更有用：如果您使用迭代器，它會在恆定時間內發生。通過從頭到尾（取較近的）搜索所需元素來執行按索引的訪問操作。但是，不要忘記在元素之間存儲引用的額外成本。因此，這裡是具有算法運行時的標準LinkedList和ArrayList操作。N指的是列表中已經存在的項目數。O(N)意味著在最壞的情況下，我們應該“遍歷”整個列表，直到找到所需的位置，例如，將新元素插入列表中。O(1)意味著操作發生在常數時間內，獨立於項目的數量。

鍊錶時間複雜度

ArrayList 時間複雜度

何時使用 LinkedList：示例

毫無疑問，ArrayList是最流行的List實現。但是，您可能會遇到過於頻繁地需要添加/刪除操作的情況。在這種情況下，LinkedList與 Iterator 一起使用可能會有所幫助。這是一個例子。我們有一個很長的列表，我們應該從這個列表中刪除每個元素。讓我們用ArrayList和LinkedList + Iterator來完成這個任務。我們比較每個操作的時間並將其打印到控制台。這裡的代碼：

import java.util.*;
import java.util.function.BiPredicate;
 
public class ListTest2 {
 
   static void removeElements(List<Double> list, BiPredicate<Integer, Double> predicate) {
       // start navigation from end to preserve indexes of removed items
       ListIterator<Double> iterator = list.listIterator(list.size());
 
       while (iterator.hasPrevious()) {
           Double element = iterator.previous();
           if (predicate.test(iterator.previousIndex()+1, element)) {
               iterator.remove();
           }
       }
   }
 
   static class TestCase1 {
       public static void main(String[] args) {
           LinkedList<Double> testedList1 = new LinkedList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList1, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList1 after removeElements(..): " + testedList1);
 
           ArrayList<Double> testedList2 = new ArrayList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList2, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList2 after removeElements(..): " + testedList2);
       }
   }
 
   static class TestLinkedListPerformance {
       public static void main(String[] args) {
           LinkedList<Double> testedList = new LinkedList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `0.1527659`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
 
   static class TestArrayListPerformance {
       public static void main(String[] args) {
           ArrayList<Double> testedList = new ArrayList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `53.4952635`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
}

ArrayList 的結果：

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 481.8824414

鍊錶的結果：

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 0.4586458

如您所見，在這種情況下，LinkedList 更有效。說實話。在實際的軟件開發中，LinkedList 的使用是一種罕見的事件。儘管如此，專業人員應該了解這種數據結構的存在及其優點。如果說在實際代碼中LinkedList是個稀罕客，那麼在 Java Junior 面試中它就非常受歡迎。然而，這是 Joshua Bloch 寫的關於LinkedList的內容：

AddOn：單鍊錶 Java

Java中經典的Collection中沒有單向鍊錶，單向鍊錶是一種結構，其中每個節點都包含一個對象和對下一個節點的引用，但不包含對前一個節點的引用。Java LinkedList是雙向鍊錶，但沒有人會干涉您創建自己的數據結構，例如單鍊錶，code>Linked List。以下是解決這些任務的一些步驟：

1. 創建一個具有兩個屬性 data 和 next 的Node類。Next 是對下一個節點的引用。
2. 創建具有兩個屬性 head 和 tail 的FirstLast類。
3. 創建一個add()方法以將新節點添加到列表中。首先檢查列表是否為空（head == null）。如果是，則 head 和 tail 指的是新節點。如果鍊錶不為空，新節點會被添加到末尾，所以tail的next屬性指的是添加的節點，新節點成為鍊錶的尾部。

順便說一句，您也可以嘗試創建自己的LinkedList作為練習。祝你學習順利。