Java LinkedList · Programiz 中文系列教程

# Java `LinkedList` > 原文： [https://www.programiz.com/java-programming/linkedlist](https://www.programiz.com/java-programming/linkedlist) #### 在本教程中，我們將通過許多示例詳細了解`LinkedList`類。 Java 集合框架的`LinkedList`類提供了鏈表數據結構的功能。 * * * ## 由`LinkedList`實現的接口 * [Java `List`接口](/java-programming/list "Java List interface") * [Java `Queue`接口](/java-programming/queue "Java Queue interface") * [Java `Deque`接口](/java-programming/deque "Java Deque interface") ![Interfaces implemented by the Linked List](https://img.kancloud.cn/10/36/1036b263765d6bec5e8ecbb535d80a8f_838x792.png) * * * ## Java 中的`LinkedList`實現 Java `LinkedList`類提供了一個雙向鏈表實現。 ![Node in a linked list](https://img.kancloud.cn/a8/89/a88939344b64ea169b5017d1ffdde920_534x498.png) 鏈表中的每個元素稱為**節點**。它包含 3 個字段： * **上一個** - 將上一個元素的地址存儲在列表中。第一個元素為`null`。 * **下一個** - 在列表中存儲下一個元素的地址。最后一個元素為`null`。 * **數據** - 存儲實際數據。鏈表中的元素未按順序存儲。相反，它們分散并通過鏈接（上一個和下一個）連接。 ![Working of LinkedList in Java](https://img.kancloud.cn/67/90/679063bb02c5477797bf658f956f7d22_1092x502.png) 在這里，鏈表中有 3 個元素。 * `Dog` - 它是第一個將`null`作為先前地址并將`Cat`作為下一個地址的元素 * `Cat` - 它是持有`Dog`作為先前地址的地址以及`Cow`作為下一地址的地址的第二個元素 * `Cow` - 它是保留`Cat`地址作為前一個地址，而`null`作為下一個元素的最后一個元素 * * * ## 創建一個`LinkedList` 這是我們如何用 Java 創建鏈表的方法： ```java LinkedList<Type> linkedList = new LinkedList<>(); ``` 在此，`Type`表示鏈表的類型。例如， ```java // create Integer type linked list LinkedList<Integer> linkedList = new LinkedList<>(); // create String type linked list LinkedList<String> linkedList = new LinkedList<>(); ``` * * * ## 使用接口創建`LinkedList` 讓我們舉個例子。 ```java List<String> animals1 = new LinkedList<>(); ``` 在這里，我們使用`List`接口聲明了一個鏈表`animals1`。鏈表只能訪問`List`接口的方法。讓我們再舉一個例子。 ```java Queue<String> animals2 = new LinkedList<>(); Deque<String> animals3 = new LinkedList<>(); ``` 在這里，`animals2`可以訪問`Queue`接口的方法。但是，`animals3`只能訪問`Deque`和`Queue`接口的方法。這是因為`Deque`是`Queue`的子接口。 * * * ## `LinkedList`的方法 `LinkedList`提供了多種方法，可讓我們在鏈表中執行不同的操作。 * * * ### 將元素添加到`LinkedList` **1.添加元素：使用`add()`方法** 要將元素（節點）添加到鏈表的末尾，我們使用`add()`方法。例如， ```java import java.util.LinkedList; class Main { public static void main(String[] args){ LinkedList<String> animals = new LinkedList<>(); // Add elements to LinkedList animals.add("Dog"); animals.add("Cat"); animals.add("Horse"); System.out.println("LinkedList: " + animals); } } ``` **輸出** ```java LinkedList: [Dog, Cat, Horse] ``` * * * **2.添加元素：使用索引號** 我們還可以使用索引將元素添加到鏈表中。例如， ```java import java.util.LinkedList; class Main { public static void main(String[] args){ LinkedList<String> animals = new LinkedList<>(); // Add elements using indexes animals.add(0,"Dog"); animals.add(1,"Cat"); animals.add(2,"Horse"); System.out.println("LinkedList: " + animals); } } ``` **輸出**： ```java LinkedList: [Dog, Cat, Horse] ``` * * * **3.添加元素：一個鏈表到另一個鏈表** 要將鏈表的所有元素添加到另一個鏈表，我們使用`addAll()`方法。例如， ```java import java.util.LinkedList; class Main { public static void main(String[] args){ LinkedList<String> mammals = new LinkedList<>(); mammals.add("Dog"); mammals.add("Cat"); mammals.add("Horse"); System.out.println("Mammals: " + mammals); LinkedList<String> animals = new LinkedList<>(); animals.add("Crocodile"); // Add all elements of mammals in animals animals.addAll(mammals); System.out.println("Animals: " + animals); } } ``` **輸出**： ```java Mammals: [Dog, Cat, Horse] Animals: [Crocodile, Dog, Cat, Horse] ``` * * * **4.添加元素：使用`listIterator()`方法** 我們還可以使用`listsIterator()`方法將元素添加到鏈表中。要使用它，我們必須導入`java.util.ListIterator`包。例如， ```java import java.util.ArrayList; import java.util.ListIterator; class Main { public static void main(String[] args) { ArrayList<String> animals= new ArrayList<>(); // Creating an object of ListIterator ListIterator<String> listIterate = animals.listIterator(); listIterate.add("Dog"); listIterate.add("Cat"); System.out.println("LinkedList: " + animals); } } ``` **輸出**： ```java LinkedList: [Dog, Cat] ``` * * * ### 訪問`LinkedList`元素 **1.訪問元素：使用`get()`方法** 要訪問鏈表中的元素，我們可以使用`get()`方法。例如， ```java import java.util.LinkedList; class Main { public static void main(String[] args) { LinkedList<String> animals= new LinkedList<>(); // Add elements in the linked list animals.add("Dog"); animals.add("Horse"); animals.add("Cat"); System.out.println("LinkedList: " + animals); // Get the element from the linked list String str = animals.get(1); System.out.print("Element at index 1: " + str); } } ``` **輸出**： ```java LinkedList: [Dog, Horse, Cat] Element at index 1: Horse ``` * * * **2.訪問元素：使用`iterator()`方法** 要遍歷鏈表的元素，我們可以使用`iterator()`方法。我們必須導入`java.util.Iterator`包才能使用此方法。例如， ```java import java.util.LinkedList; import java.util.Iterator; class Main { public static void main(String[] args) { LinkedList<String> animals= new LinkedList<>(); // Add elements in LinkedList animals.add("Dog"); animals.add("Horse"); animals.add("Cat"); // Creating an object of Iterator Iterator<String> iterate = animals.iterator(); System.out.print("LinkedList: "); while(iterate.hasNext()) { System.out.print(iterate.next()); System.out.print(", "); } } } ``` **輸出**： ```java LinkedList: Dog, Cat, Horse, ``` 這里， * `hasNext()` - 如果存在下一個元素，則返回`true` * `next()` - 返回下一個元素要了解有關`Iterator`的更多信息，請訪問 Java `Iterator`接口。 * * * **3.訪問元素：使用`listIterator()`方法** 我們還可以使用`listIterator()`方法來迭代鏈表的元素。要使用此方法，我們必須導入`java.util.ListIterator`包。在鏈表中，`listsIterator()`方法更為可取。這是因為`listIterator()`的對象也可以向后迭代。例如， ```java import java.util.LinkedList; import java.util.ListIterator; class Main { public static void main(String[] args) { LinkedList<String> animals= new LinkedList<>(); // Add elements in LinkedList animals.add("Dog"); animals.add("Horse"); animals.add("Cat"); // Create an object of ListIterator ListIterator<String> listIterate = animals.listIterator(); System.out.print("LinkedList: "); while(listIterate.hasNext()) { System.out.print(listIterate.next()); System.out.print(", "); } // Iterate backward System.out.print("\nReverse LinkedList: "); while(listIterate.hasPrevious()) { System.out.print(listIterate.previous()); System.out.print(", "); } } } ``` **輸出**： ```java LinkedList: Dog, Horse, Cat, Reverse LinkedList: Cat, Horse, Dog, ``` Here, * `hasNext()` - 如果存在下一個元素，則返回`true` * `next()` - 返回下一個元素 * `hasPrevious()` - 如果先前存在元素，則返回`true` * `previous()` - 返回上一個元素要了解有關`ListIterator`的更多信息，請訪問 Java `ListIterator`接口。 * * * ### 搜索`LinkedList`元素 **1.搜索元素：使用`contains()`方法** 要檢查鏈表是否包含特定元素，我們使用`contains()`方法。例如， ```java import java.util.LinkedList; class Main { public static void main(String[] args) { LinkedList<String> animals= new LinkedList<>(); // Add elements in the linked list animals.add("Dog"); animals.add("Horse"); animals.add("Cat"); System.out.println("LinkedList: " + animals); // Checks if Dog is in the linked list if(animals.contains("Dog")) { System.out.println("Dog is in LinkedList."); } } } ``` **輸出**： ```java LinkedList: [Dog, Horse, Cat] Dog is in LinkedList. ``` * * * **2.搜索元素：使用`indexOf()`方法** * `indexOf()` - 返回元素首次出現的索引 * `lastIndexOf()` - 返回元素最后一次出現的索引例如， ```java import java.util.LinkedList; class Main { public static void main(String[] args) { LinkedList<String> animals= new LinkedList<>(); // Add elements in the linked list animals.add("Dog"); animals.add("Horse"); animals.add("Cat"); animals.add("Dog"); System.out.println("LinkedList: " + animals); // First Occurrence of Dog int index1 = animals.indexOf("Dog"); System.out.println("First Occurrence of Dog: " + index1); // Last Occurrence of Dog int index2 = animals.lastIndexOf("Dog"); System.out.println("Last Occurrence of Dog: " + index2); } } ``` **輸出**： ```java LinkedList: [Dog, Horse, Cat, Dog] First Occurrence of Dog: 0 Last Occurrence of Dog: 3 ``` **注意**：如果找不到指定的元素，則`indexOf()`和`lastIndexOf()`都返回`-1`。 * * * ### 更改`LinkedList`元素 **1.更改元素：使用`set()`方法** 要更改鏈表的元素，可以使用`set()`方法。例如， ```java import java.util.LinkedList; class Main { public static void main(String[] args) { LinkedList<String> animals= new LinkedList<>(); // Add elements in the linked list animals.add("Dog"); animals.add("Horse"); animals.add("Cat"); animals.add("Dog"); System.out.println("LinkedList: " + animals); // Change elements at index 3 animals.set(3, "Zebra"); System.out.println("New LinkedList: " + animals); } } ``` **輸出**： ```java LinkedList: [Dog, Horse, Cat, Dog] New LinkedList: [Dog, Horse, Cat, Zebra] ``` * * * **2.更改元素：使用`listIterator()`方法** 我們還可以使用`listIterator()`方法更改鏈表中的元素。例如， ```java import java.util.ArrayList; import java.util.ListIterator; class Main { public static void main(String[] args) { ArrayList<String> animals= new ArrayList<>(); // Add elements animals.add("Dog"); animals.add("Cat"); animals.add("Horse"); System.out.println("LinkedList: " + animals); // Creating an object of ListIterator ListIterator<String> listIterate = animals.listIterator(); listIterate.next(); // Change element returned by next() listIterate.set("Cow"); System.out.println("New LinkedList: " + animals); } } ``` **輸出**： ```java LinkedList: [Dog, Cat, Horse] New LinkedList: [Cow, Cat, Horse] ``` * * * ### 刪除`LinkedList`元素 **1.刪除元素：使用`remove()`方法** 要從鏈表中刪除一個元素，我們可以使用`remove()`方法。例如， ```java import java.util.LinkedList; class Main { public static void main(String[] args) { LinkedList<String> animals= new LinkedList<>(); // Add elements in LinkedList animals.add("Dog"); animals.add("Horse"); animals.add("Cat"); animals.add("Zebra"); System.out.println("LinkedList: " + animals); // Remove elements from index 1 String str = animals.remove(1); System.out.println("Removed Element: " + str); System.out.println("New LinkedList: " + animals); } } ``` **輸出**： ```java LinkedList : [Dog, Horse, Cat, Zebra] Removed Element: Horse New LinkedList: [Dog, Cat, Zebra] ``` * * * **2.刪除元素：使用`listIterator()`方法** 我們還可以使用`listsIterator()`方法從鏈表中刪除元素。例如， ```java import java.util.ArrayList; import java.util.ListIterator; class Main { public static void main(String[] args) { ArrayList<String> animals= new ArrayList<>(); // Add elements animals.add("Dog"); animals.add("Cat"); animals.add("Horse"); System.out.println("LinkedList: " + animals); // Creating an object of ListIterator ListIterator<String> listIterate = animals.listIterator(); listIterate.next(); // Remove element returned by next() listIterate.remove(); System.out.println("New LinkedList: " + animals); } } ``` **輸出**： ```java LinkedList: [Dog, Cat, Horse] New LinkedList: [Cat, Horse] ``` * * * **3.刪除元素：使用`clear()`方法** 要從鏈表中刪除所有元素，我們使用`clear()`方法。例如， ```java import java.util.LinkedList; class Main { public static void main(String[] args) { LinkedList<String> animals= new LinkedList<>(); // Add elements in LinkedList animals.add("Dog"); animals.add("Cat"); animals.add("Horse"); System.out.println("LinkedList: " + animals); // Remove all the elements animals.clear(); System.out.println("New LinkedList: " + animals); } } ``` **輸出**： ```java LinkedList: [Dog, Cat, Horse] New LinkedList: [] ``` **注意**：我們也可以使用`removeAll()`方法刪除所有元素。但是，`clear()`方法被認為比`removeAll()`方法更有效。 * * * **4.刪除元素：使用`removeIf()`方法** 如果元素滿足特定條件，我們也可以從鏈表中刪除它們。為此，我們使用`removeIf ()`方法。例如， ```java import java.util.LinkedList; class Main { public static void main(String[] args) { LinkedList<Integer> animals= new LinkedList<>(); // Add elements in LinkedList animals.add(2); animals.add(3); animals.add(4); animals.add(5); System.out.println("LinkedList: " + animals); // Remove all elements less than 4 animals.removeIf((Integer i)->i < 4); System.out.println("New LinkedList: " + animals); /** Here we have used the lambda expression * For now just remember * parameter inside removeIf() is a condition */ } } ``` **輸出**： ```java LinkedList: [2, 3, 4, 5] New LinkedList: [4, 5] ``` **注意**： `(Integer i)->i<4`是 lambda 表達式。要了解 lambda 表達式，請訪問 [Java Lambda 表達式](https://www.programiz.com/java-programming/lambda-expression)。 * * * ## `LinkedList`作為雙端隊列和隊列由于`LinkedList`類還實現了`Queue`和`Deque`接口，因此它也可以實現這些接口的方法。以下是一些常用方法： * * * ### `addFirst()`和`addLast()`方法 * `addFirst()` - 在鏈表的開頭添加指定的元素 * `addLast()` - 將指定的元素添加到鏈表的末尾例如： ```java import java.util.LinkedList; import java.util.Deque; class Main { public static void main(String[] args){ Deque<String> animals = new LinkedList<>(); // Add element at starting of LinkedList animals.addFirst("Cow"); animals.addFirst("Dog"); animals.addFirst("Cat"); System.out.println("LinkedList: " + animals); // Add elements at the end of LinkedList animals.addLast("Zebra"); System.out.println("New LinkedList: " + animals); } } ``` **輸出**： ```java LinkedList: [Cat, Dog, Cow] New LinkedList: [Cat, Dog, Cow, Zebra] ``` * * * ### `getFirst()`和`getLast()`方法 * `getFirst()` - 返回第一個元素 * `getLast()` - 返回最后一個元素例如： ```java import java.util.LinkedList; import java.util.Deque; class Main { public static void main(String[] args) { Deque<String> animals= new LinkedList<>(); // Add elements in the linked list animals.add("Dog"); animals.add("Horse"); animals.add("Cat"); System.out.println("LinkedList: " + animals); // Get the first element from the linked list String str1 = animals.getFirst(); System.out.println("First Element: " + str1); // Get the last element from the linked list String str2 = animals.getLast(); System.out.println("Last Element: " + str2); } } ``` **輸出**： ```java LinkedList: [Dog, Horse, Cat] First Element: Dog Last Element: Cat ``` * * * ### `removeFirst()`和`removeLast()`方法 * `removeFirst()` - 刪除第一個元素 * `removeLast()` - 刪除最后一個元素例如： ```java import java.util.LinkedList; import java.util.Deque; class Main { public static void main(String[] args) { Deque<String> animals= new LinkedList<>(); // Add elements in LinkedList animals.add("Dog"); animals.add("Horse"); animals.add("Cat"); System.out.println("LinkedList: " + animals); // Remove the first element from LinkedList String str1 = animals.removeFirst(); System.out.println("Removed Element: " + str1); // Remove the last element from LinkedList String str2 = animals.removeLast(); System.out.println("Removed Element: " + str2); System.out.println("New LinkedList: " + animals); } } ``` **輸出**： ```java LinkedList: [Dog, Horse, Cat] Removed Element: Dog Removed Element: Cat New LinkedList: [Horse] ``` * * * ### `peek()`方法 `peek()`方法返回鏈表的第一個元素（頭）。例如， ```java import java.util.LinkedList; import java.util.Queue; class Main { public static void main(String[] args) { Queue<String> animals= new LinkedList<>(); // Add elements in LinkedList animals.add("Dog"); animals.add("Horse"); animals.add("Cat"); System.out.println("LinkedList: " + animals); // Access the first element of LinkedList String str = animals.peek(); System.out.println("Element Accessed: " + str); System.out.println("New LinkedList: " + animals); } } ``` **輸出**： ```java LinkedList: [Dog, Horse, Cat] Element Accessed: Dog New LinkedList: [Dog, Horse, Cat] ``` * * * ### `poll()`方法 `poll()`方法返回并從鏈表中刪除第一個元素。例如， ```java import java.util.LinkedList; import java.util.Queue; class Main { public static void main(String[] args) { Queue<String> animals= new LinkedList<>(); // Add elements in LinkedList animals.add("Dog"); animals.add("Horse"); animals.add("Cat"); System.out.println("LinkedList: " + animals); // Returns and removes the first element String str = animals.poll(); System.out.println("Removed Element: " + str); System.out.println("New LinkedList: " + animals); } } ``` **輸出**： ```java LinkedList: [Dog, Horse, Cat] Removed Element: Dog New LinkedList: [Horse, Cat] ``` ### `offer()`方法 `offer()`方法將指定的元素添加到鏈表的末尾。例如， ```java import java.util.LinkedList; import java.util.Queue; class Main { public static void main(String[] args) { Queue<String> animals= new LinkedList<>(); // Add elements in LinkedList animals.add("Dog"); animals.add("Horse"); System.out.println("LinkedList: " + animals); // Adds element at the end of LinkedList animals.offer("Cat"); System.out.println("New LinkedList: " + animals); } } ``` **輸出**： ```java LinkedList: [Dog, Horse] New LinkedList: [Dog, Horse, Cat] ``` * * * ## 迭代`LinkedList` **1.使用`forEach`循環** ```java import java.util.LinkedList; class Main { public static void main(String[] args) { // Creating a linked list LinkedList<String> animals = new LinkedList<>(); animals.add("Cow"); animals.add("Cat"); animals.add("Dog"); System.out.println("LinkedList: " + animals); // Using forEach loop System.out.println("Accessing linked list elements:"); for(String animal: animals) { System.out.print(animal); System.out.print(", "); } } } ``` **輸出**： ```java LinkedList: [Cow, Cat, Dog] Accessing linked list elements: Cow, Cat, Dog, ``` * * * **2.使用`for`循環** ```java import java.util.LinkedList; class Main { public static void main(String[] args) { // Creating a linked list LinkedList<String> animals = new LinkedList<>(); animals.add("Cow"); animals.add("Cat"); animals.add("Dog"); System.out.println("LinkedList: " + animals); // Using for loop System.out.println("Accessing linked list elements:"); for(int i=0; i < animals.size(); i++) { System.out.print(animals.get(i)); System.out.print(", "); } } } ``` **輸出**： ```java LinkedList: [Cow, Cat, Dog] Accessing linked list elements: Cow, Cat, Dog, ``` 在兩個示例中，我們都使用循環訪問了鏈表的各個元素。 * * * **3.使用`iterator()`方法** 我們可以使用`iterator()`方法訪問鏈表的元素。為了使用此方法，我們必須導入`java.util.Iterator`包。 ```java import java.util.LinkedList; import java.util.Iterator; class Main { public static void main(String[] args) { // Creating a linked list LinkedList<String> animals = new LinkedList<>(); animals.add("Cow"); animals.add("Cat"); animals.add("Dog"); System.out.println("LinkedList: " + animals); // Using the iterator() method System.out.println("LinkedList using the iterator() method:"); Iterator<String> iterate = animals.iterator(); while(iterate.hasNext()) { System.out.print(iterate.next()); System.out.print(", "); } } } ``` **輸出**： ```java LinkedList: [Cow, Cat, Dog] LinkedList using the iterator() method: Cow, Cat, Dog, ``` * * * ## `LinkedList`與`ArrayList` `LinkedList`和`ArrayList`都實現`Collections`框架的`List`接口。但是，它們之間存在一些差異。 | `LinkedList` | `ArrayList` | | --- | --- | | 在單個位置存儲 3 個值（**前一個地址**，**數據**和**下一個地址**） | 將單個值存儲在單個位置 | | 提供`List`的雙鏈表實現 | 提供可調整大小的數組實現 | | 每當添加元素時，`prev`和`next`地址都會更改 | 每當添加元素時，該位置之后的所有元素都會移動 | | 要訪問元素，我們需要從頭開始迭代到元素 | 可以使用索引隨機訪問元素。 |