Java LinkedList類 · HowToDoInJava 中文系列教程

# Java `LinkedList`類 > 原文： [https://howtodoinjava.com/java/collections/java-linkedlist-class/](https://howtodoinjava.com/java/collections/java-linkedlist-class/) Java `LinkedList`類是`List`和[`Deque`](https://docs.oracle.com/javase/7/docs/api/java/util/Deque.html)接口的雙鏈列表實現。它實現所有可選的列表操作，并允許所有元素（包括`null`）。 ```java Table of Contents 1\. LinkedList Hierarchy 2\. LinkedList Features 3\. LinkedList Constructors 4\. LinkedList Methods 5\. LinkedList Example 6\. LinkedList Usecases 7\. LinkedList Performance 8\. ArrayList vs LinkedList 9\. Conclusion ``` ## 1\. `LinkedList`層次結構 `LinkedList`類擴展了`AbstractSequentialList`類，實現了`List`和`Deque`接口。這里`E`是值鏈表存儲的類型。 ```java public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { //implementation } ``` ![LinkedList Hierarchy](https://img.kancloud.cn/c7/64/c7649325a69ad581321ab424ed60deab_541x432.png) `LinkedList`層次結構 ## 2\. `LinkedList`特性 * **雙鏈表**實現，它實現`List`和`Deque`接口。因此，它也可以用作隊列，雙端隊列或棧。 * 允許所有元素，包括重復和`NULL`。 * `LinkedList`維護元素的**插入順序**。 * **未同步**。如果多個線程同時訪問一個鏈表，并且至少一個線程在結構上修改了該鏈表，則它*必須在外部進行*同步。 * 使用`Collections.synchronizedList(new LinkedList())`獲取同步鏈表。 * 此類返回的迭代器是快速失敗的，并且可能拋出`ConcurrentModificationException`。 * 它沒有實現[`RandomAccess`](https://docs.oracle.com/javase/7/docs/api/java/util/RandomAccess.html)接口。因此，我們只能按順序訪問元素。它不支持隨機訪問元素。 * 我們可以使用[`ListIterator`](https://docs.oracle.com/javase/7/docs/api/java/util/ListIterator.html)來迭代`LinkedList`元素。 ## 3\. `LinkedList`構造器 1. **`LinkedList()`**：初始化一個空的`LinkedList`實現。 2. **`LinkedListExample(Collection c)`**：初始化一個`LinkedList`，其中包含指定集合的??元素，并按集合的迭代器返回它們的順序。 ## 4\. `LinkedList`方法 1. **`boolean add(Object o)`**：將指定的元素附加到列表的末尾。 2. **`void add(int index, Object element)`**：將指定元素插入列表中指定位置的索引處。 3. **`void addFirst(Object o)`**：將給定元素插入列表的開頭。 4. **`void addLast(Object o)`**：將給定元素附加到列表的末尾。 5. **`int size()`**：返回列表中的元素數 6. **`boolean contains(Object o)`**：如果列表包含指定元素，則返回`true`，否則返回`false`。 7. **`boolean remove(Object o)`**：刪除列表中指定元素的首次出現。 8. **`Object getFirst()`**：返回列表中的第一個元素。 9. **`Object getLast()`**：返回列表中的最后一個元素。 10. **`int indexOf(Object o)`**：返回指定元素首次出現的列表中的索引；如果列表不包含指定元素，則返回 -1。 11. **`lastIndexOf(Object o)`**：返回指定元素最后一次出現的列表中的索引；如果列表不包含指定元素，則返回 -1。 12. **`Iterator iterator()`**：按適當的順序返回此列表中元素的迭代器。 13. **`Object[] toArray()`**：按正確順序返回包含此列表中所有元素的數組。 14. **`List subList(int fromIndex, int toIndex)`**：返回此列表中指定的`fromIndex`（包括）和`toIndex`（不包括）之間的視圖。 ## 5\. Java `LinkedList`示例 #### 5.1 添加，刪除，迭代 Java 程序演示鏈表類中基本方法的用法。 ```java import java.util.LinkedList; import java.util.ListIterator; public class LinkedListExample { public static void main(String[] args) { //Create linked list LinkedList<String> linkedList = new LinkedList<>(); //Add elements linkedList.add("A"); linkedList.add("B"); linkedList.add("C"); linkedList.add("D"); System.out.println(linkedList); //Add elements at specified position linkedList.add(4, "A"); linkedList.add(5, "A"); System.out.println(linkedList); //Remove element linkedList.remove("A"); //removes A linkedList.remove(0); //removes B System.out.println(linkedList); //Iterate ListIterator<String> itrator = linkedList.listIterator(); while (itrator.hasNext()) { System.out.println(itrator.next()); } } } ``` 程序輸出。 ```java [A, B, C, D] [A, B, C, D, A, A] [C, D, A, A] C D A A ``` #### 5.2 在數組和`LinkedList`之間轉換 Java 程序將`LinkedList`轉換為數組，將數組轉換為`Linkedlist`。 ```java LinkedList<String> linkedList = new LinkedList<>(); linkedList.add("A"); linkedList.add("B"); linkedList.add("C"); linkedList.add("D"); //1\. LinkedList to Array String array[] = new String[linkedList.size()]; linkedList.toArray(array); System.out.println(Arrays.toString(array)); //2\. Array to LinkedList LinkedList<String> linkedListNew = new LinkedList<>(Arrays.asList(array)); System.out.println(linkedListNew); ``` 程序輸出： ```java [A, B, C, D] [A, B, C, D] ``` #### 5.3 如何排序`LinkedList` 使用`Collections.sort()`方法對`LinkedList`排序的 Java 示例。請注意，對于對象的自定義排序，我們可以使用`Collections.sort(linkedList, comparator)`方法。 ```java LinkedList<String> linkedList = new LinkedList<>(); linkedList.add("A"); linkedList.add("C"); linkedList.add("B"); linkedList.add("D"); //Unsorted System.out.println(linkedList); //1\. Sort the list Collections.sort(linkedList); //Sorted System.out.println(linkedList); //2\. Custom sorting Collections.sort(linkedList, Collections.reverseOrder()); //Custom sorted System.out.println(linkedList); ``` 程序輸出： ```java [A, C, B, D] [A, B, C, D] [D, C, B, A] ``` ## 6\. `LinkedList`用例在任何桌面應用程序中，動作都可以記錄在鏈表中，并實現從上一次迭代的撤消和重做特性。可以使用鏈表對瀏覽器的“下一個”和“上一個”按鈕進行編程。鏈表（與哈希表配對）對于 LRU 緩存非常有用。 ## 7\. `LinkedList`性能在 Java `LinkedList`類中，由于不需要進行任何轉換，因此處理速度很快。因此，基本上，所有添加和刪除方法都提供非常好的性能`O(1)`。 * `add(E element)`方法是`O（1）`。 * `get(int index)`和`add(int index, E element)`方法的類型為`O(n)`。 * `remove(int index)`方法的值為`O(n)`。 * `Iterator.remove()`為`O(1)`。 * `ListIterator.add(E element)`為`O(1)`。應該首選`LinkedList`，因為沒有大量的元素隨機訪問，而有大量的添加/刪除操作。 ## 8\. `ArrayList`與`LinkedList` 讓我們列出`arraylist`和鏈表之間的一些值得注意的**差異**。 * `ArrayList`是使用動態可調整大小的數組的概念實現的。而`LinkedList` 是雙向鏈表實現。 * `ArrayList`允許隨機訪問其元素，而`LinkedList`則不允許。 * `LinkedList`還實現`Queue`接口，該接口添加了比 ArrayList 更多的方法，例如`offer()`，`peek()`，`poll()`等。 * 與`LinkedList`相比，[`ArrayList`](https://howtodoinjava.com/java-arraylist/) 的添加和刪除速度較慢，但??獲取速度較快，因為如果[數組](https://howtodoinjava.com/java-array/)在`LinkedList`中已滿，則無需調整數組大小并將內容復制到新數組中。 * `LinkedList`比`ArrayList`具有更多的內存開銷，因為在`ArrayList`中，每個索引僅保存實際對象，但是在`LinkedList`的情況下，每個節點都保存下一個和上一個節點的數據和地址。 ## 9\. 總結在此 **Java `LinkedList`教程**中，我們學習了什么是`LinkedList`，`LinkedList`和`ArrayList`之間的區別是什么，如何創建`LinkedList`，如何在 `LinkedList`中添加，刪除和搜索元素，以及如何遍歷`LinkedList`。讓我知道您的問題。學習愉快！參考： [`LinkedList` Java 文檔](https://docs.oracle.com/javase/10/docs/api/java/util/LinkedList.html)