為不同的目的創建不同的數據結構。你可能知道ArrayList(如果還不知道,我們建議你先閱讀一下)。在本文中,我們將了解LinkedList並了解此集合的用途。如果您查看 LinkedList Java 8(或該語言的更高版本)類代碼源(在 Oracle 網站或您的 IDE 中,如果是 IDEA:類名上的 crtl+B),您將看到下一個聲明:
因此,LinkedList 是這兩者的實現,它允許我們創建一個雙向隊列,該隊列由包括 null 在內的任何對象組成。鍊錶是元素的集合。我們在類的代碼源中可以看到,這次要注意字段:
由於LinkedList實際上是一個雙向結構,我們可以很容易地從兩側添加或刪除元素。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
目前,代碼中最重要的信息是LinkedList實現了List和Deque接口。List 接口保持添加項目的順序,並允許通過索引訪問項目。“普通” Queue支持在末尾添加元素,從頭提取元素。Deque 是一個雙向隊列,它支持從兩側添加和刪除元素。您可以將其視為堆棧和隊列的組合。
transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;
每個元素,通常我們稱之為Node,包含一個對象和對兩個相鄰對象的引用——前一個和下一個。因此,它在使用內存方面不是很有效。 
鍊錶構造器
回到代碼源,我們可以發現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()返回一個數組,其中包含列表中從第一個元素到最後一個元素的所有元素。
- 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)意味著操作發生在常數時間內,獨立於項目的數量。鍊錶時間複雜度
鍊錶Java操作 | 算法有效性 |
---|---|
得到(整數索引) | O(n),平均- n/4步,其中 n 是LinkedList大小 |
添加(E元素) | O(1) |
添加(整數索引,E元素) | O(n),平均 — n/4步;if index = 0 then O(1),所以如果你需要在列表的開頭添加一些東西, LinkedList<E> 可能是一個不錯的選擇 |
刪除(整數索引) | O(n),平均 — n/4步 |
迭代器.remove() | O(1)這是使用LinkedList<E>的主要原因 |
ArrayList 時間複雜度
鍊錶操作 | 算法有效性 |
---|---|
得到(整數索引) | O(1) ,使用ArrayList<E> 的主要原因之一 |
添加(E元素) | O(n)是最壞的情況,因為必須調整數組的大小並進行複制,但是在實踐中,它並沒有那麼糟糕 |
添加(整數索引,E元素) | O(n),平均n/2步 |
刪除(整數索引) | O(n),平均n/2步 |
迭代器.remove() | O(n),平均n/2步 |
ListIterator.add(E 元素) | O(n),平均n/2步 |
何時使用 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。以下是解決這些任務的一些步驟:- 創建一個具有兩個屬性 data 和 next 的Node類。Next 是對下一個節點的引用。
- 創建具有兩個屬性 head 和 tail 的FirstLast類。
- 創建一個add()方法以將新節點添加到列表中。首先檢查列表是否為空(head == null)。如果是,則 head 和 tail 指的是新節點。如果鍊錶不為空,新節點會被添加到末尾,所以tail的next屬性指的是添加的節點,新節點成為鍊錶的尾部。
GO TO FULL VERSION