上一篇博客我們介紹了List集合的一種典型實現 ArrayList，我們知道 ArrayList 是由數組構成的，本篇博客我們介紹 List 集合的另一種典型實現 LinkedList，這是一個由鏈表構成的數組，關于鏈表的介紹，在這篇博客中?我們也詳細介紹過，本篇博客我們將介紹 LinkedList 是如何實現的。

1、LinkedList 定義

　　LinkedList 是一個用鏈表實現的集合，元素有序且可以重復。

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

　　和 ArrayList 集合一樣，LinkedList 集合也實現了Cloneable接口和Serializable接口，分別用來支持克隆以及支持序列化。List 接口也不用多說，定義了一套 List 集合類型的方法規范。

　　注意，相對于 ArrayList 集合，LinkedList 集合多實現了一個 Deque 接口，這是一個雙向隊列接口，雙向隊列就是兩端都可以進行增加和刪除操作。

2、字段屬性

//鏈表元素（節點）的個數transient int size = 0;/***指向第一個節點的指針*/transient Node<E> first;/***指向最后一個節點的指針*/transient Node<E> last;

　　注意這里出現了一個 Node 類，這是 LinkedList 類中的一個內部類，其中每一個元素就代表一個 Node 類對象，LinkedList 集合就是由許多個 Node 對象類似于手拉著手構成。

1 private static class Node<E> { 2 E item;//實際存儲的元素 3 Node<E> next;//指向上一個節點的引用 4 Node<E> prev;//指向下一個節點的引用 5 6 //構造函數 7 Node(Node<E> prev, E element, Node<E> next) { 8 this.item = element; 9 this.next = next; 10 this.prev = prev; 11 } 12 } View Code

　　如下圖所示：

　　

　　上圖的 LinkedList 是有四個元素，也就是由 4 個 Node 對象組成，size=4，head 指向第一個elementA,tail指向最后一個節點elementD。

3、構造函數?

public LinkedList() {}public LinkedList(Collection<? extends E> c) {this();addAll(c);}

　　LinkedList 有兩個構造函數，第一個是默認的空的構造函數，第二個是將已有元素的集合Collection 的實例添加到 LinkedList 中，調用的是 addAll() 方法，這個方法下面我們會介紹。

　　注意：LinkedList 是沒有初始化鏈表大小的構造函數，因為鏈表不像數組，一個定義好的數組是必須要有確定的大小，然后去分配內存空間，而鏈表不一樣，它沒有確定的大小，通過指針的移動來指向下一個內存地址的分配。

4、添加元素

　?、?、addFirst(E e)

　　將指定元素添加到鏈表頭

　　

?

1 //將指定的元素附加到鏈表頭節點 2 public void addFirst(E e) { 3 linkFirst(e); 4 } 5 private void linkFirst(E e) { 6 final Node<E> f = first;//將頭節點賦值給 f 7 final Node<E> newNode = new Node<>(null, e, f);//將指定元素構造成一個新節點，此節點的指向下一個節點的引用為頭節點 8 first = newNode;//將新節點設為頭節點，那么原先的頭節點 f 變為第二個節點 9 if (f == null)//如果第二個節點為空，也就是原先鏈表是空 10 last = newNode;//將這個新節點也設為尾節點（前面已經設為頭節點了） 11 else 12 f.prev = newNode;//將原先的頭節點的上一個節點指向新節點 13 size++;//節點數加1 14 modCount++;//和ArrayList中一樣，iterator和listIterator方法返回的迭代器和列表迭代器實現使用。 15 } View Code

　　②、addLast(E?e)和add(E e)

　　將指定元素添加到鏈表尾

1 //將元素添加到鏈表末尾 2 public void addLast(E e) { 3 linkLast(e); 4 } 5 //將元素添加到鏈表末尾 6 public boolean add(E e) { 7 linkLast(e); 8 return true; 9 } 10 void linkLast(E e) { 11 final Node<E> l = last;//將l設為尾節點 12 final Node<E> newNode = new Node<>(l, e, null);//構造一個新節點，節點上一個節點引用指向尾節點l 13 last = newNode;//將尾節點設為創建的新節點 14 if (l == null)//如果尾節點為空，表示原先鏈表為空 15 first = newNode;//將頭節點設為新創建的節點（尾節點也是新創建的節點） 16 else 17 l.next = newNode;//將原來尾節點下一個節點的引用指向新節點 18 size++;//節點數加1 19 modCount++;//和ArrayList中一樣，iterator和listIterator方法返回的迭代器和列表迭代器實現使用。 20 } View Code

　?、?、add(int?index,?E?element)

　　將指定的元素插入此列表中的指定位置

　

//將指定的元素插入此列表中的指定位置public void add(int index, E element) {//判斷索引 index >= 0 && index <= size中時拋出IndexOutOfBoundsException異常 checkPositionIndex(index);if (index == size)//如果索引值等于鏈表大小linkLast(element);//將節點插入到尾節點elselinkBefore(element, node(index));}void linkLast(E e) {final Node<E> l = last;//將l設為尾節點final Node<E> newNode = new Node<>(l, e, null);//構造一個新節點，節點上一個節點引用指向尾節點llast = newNode;//將尾節點設為創建的新節點if (l == null)//如果尾節點為空，表示原先鏈表為空first = newNode;//將頭節點設為新創建的節點（尾節點也是新創建的節點）elsel.next = newNode;//將原來尾節點下一個節點的引用指向新節點size++;//節點數加1modCount++;//和ArrayList中一樣，iterator和listIterator方法返回的迭代器和列表迭代器實現使用。 }Node<E> node(int index) {if (index < (size >> 1)) {//如果插入的索引在前半部分Node<E> x = first;//設x為頭節點for (int i = 0; i < index; i++)//從開始節點到插入節點索引之間的所有節點向后移動一位x = x.next;return x;} else {//如果插入節點位置在后半部分Node<E> x = last;//將x設為最后一個節點for (int i = size - 1; i > index; i--)//從最后節點到插入節點的索引位置之間的所有節點向前移動一位x = x.prev;return x;}}void linkBefore(E e, Node<E> succ) {final Node<E> pred = succ.prev;//將pred設為插入節點的上一個節點final Node<E> newNode = new Node<>(pred, e, succ);//將新節點的上引用設為pred,下引用設為succsucc.prev = newNode;//succ的上一個節點的引用設為新節點if (pred == null)//如果插入節點的上一個節點引用為空first = newNode;//新節點就是頭節點elsepred.next = newNode;//插入節點的下一個節點引用設為新節點size++;modCount++;} View Code

　?、堋?span id="ze8trgl8bvbq" class="memberNameLink">addAll(Collection<? extends?E>?c)

　　按照指定集合的??迭代器返回的順序，將指定集合中的所有元素追加到此列表的末尾

　　此方法還有一個 addAll(int index, Collection<? extends E> c)，將集合 c 中所有元素插入到指定索引的位置。其實?

　　　　addAll(Collection<? extends?E>?c) ==??addAll(size, Collection<? extends E> c)

　　源碼如下：

1 //按照指定集合的??迭代器返回的順序，將指定集合中的所有元素追加到此列表的末尾。 2 public boolean addAll(Collection<? extends E> c) { 3 return addAll(size, c); 4 } 5 //將集合 c 中所有元素插入到指定索引的位置。 6 public boolean addAll(int index, Collection<? extends E> c) { 7 //判斷索引 index >= 0 && index <= size中時拋出IndexOutOfBoundsException異常 8 checkPositionIndex(index); 9 10 Object[] a = c.toArray();//將集合轉換成一個 Object 類型的數組 11 int numNew = a.length; 12 if (numNew == 0)//如果添加的集合為空，直接返回false 13 return false; 14 15 Node<E> pred, succ; 16 if (index == size) {//如果插入的位置等于鏈表的長度，就是將原集合元素附加到鏈表的末尾 17 succ = null; 18 pred = last; 19 } else { 20 succ = node(index); 21 pred = succ.prev; 22 } 23 24 for (Object o : a) {//遍歷要插入的元素 25 @SuppressWarnings("unchecked") E e = (E) o; 26 Node<E> newNode = new Node<>(pred, e, null); 27 if (pred == null) 28 first = newNode; 29 else 30 pred.next = newNode; 31 pred = newNode; 32 } 33 34 if (succ == null) { 35 last = pred; 36 } else { 37 pred.next = succ; 38 succ.prev = pred; 39 } 40 41 size += numNew; 42 modCount++; 43 return true; 44 } View Code

　　看到上面向 LinkedList 集合中添加元素的各種方式，我們發現LinkedList 每次添加元素只是改變元素的上一個指針引用和下一個指針引用，而且沒有擴容。，對比于 ArrayList ，需要擴容，而且在中間插入元素時，后面的所有元素都要移動一位，兩者插入元素時的效率差異很大，下一篇博客會對這兩者的效率，以及何種情況選擇何種集合進行分析。

　　還有，每次進行添加操作，都有modCount++ 的操作，

5、刪除元素

　　刪除元素和添加元素一樣，也是通過更改指向上一個節點和指向下一個節點的引用即可，這里就不作圖形展示了。

　　①、remove()和removeFirst()

　　從此列表中移除并返回第一個元素

1 //從此列表中移除并返回第一個元素 2 public E remove() { 3 return removeFirst(); 4 } 5 //從此列表中移除并返回第一個元素 6 public E removeFirst() { 7 final Node<E> f = first;//f設為頭結點 8 if (f == null) 9 throw new NoSuchElementException();//如果頭結點為空，則拋出異常 10 return unlinkFirst(f); 11 } 12 private E unlinkFirst(Node<E> f) { 13 // assert f == first && f != null; 14 final E element = f.item; 15 final Node<E> next = f.next;//next 為頭結點的下一個節點 16 f.item = null; 17 f.next = null; // 將節點的元素以及引用都設為 null，便于垃圾回收 18 first = next; //修改頭結點為第二個節點 19 if (next == null)//如果第二個節點為空（當前鏈表只存在第一個元素） 20 last = null;//那么尾節點也置為 null 21 else 22 next.prev = null;//如果第二個節點不為空，那么將第二個節點的上一個引用置為 null 23 size--; 24 modCount++; 25 return element; 26 } View Code

　?、?、removeLast()

　　從該列表中刪除并返回最后一個元素

1 //從該列表中刪除并返回最后一個元素 2 public E removeLast() { 3 final Node<E> l = last; 4 if (l == null)//如果尾節點為空，表示當前集合為空，拋出異常 5 throw new NoSuchElementException(); 6 return unlinkLast(l); 7 } 8 9 private E unlinkLast(Node<E> l) { 10 // assert l == last && l != null; 11 final E element = l.item; 12 final Node<E> prev = l.prev; 13 l.item = null; 14 l.prev = null; //將節點的元素以及引用都設為 null，便于垃圾回收 15 last = prev;//尾節點為倒數第二個節點 16 if (prev == null)//如果倒數第二個節點為null 17 first = null;//那么將節點也置為 null 18 else 19 prev.next = null;//如果倒數第二個節點不為空，那么將倒數第二個節點的下一個引用置為 null 20 size--; 21 modCount++; 22 return element; 23 } View Code

　?、?、remove(int?index)

　　刪除此列表中指定位置的元素

1 //刪除此列表中指定位置的元素 2 public E remove(int index) { 3 //判斷索引 index >= 0 && index <= size中時拋出IndexOutOfBoundsException異常 4 checkElementIndex(index); 5 return unlink(node(index)); 6 } 7 E unlink(Node<E> x) { 8 // assert x != null; 9 final E element = x.item; 10 final Node<E> next = x.next; 11 final Node<E> prev = x.prev; 12 13 if (prev == null) {//如果刪除節點位置的上一個節點引用為null（表示刪除第一個元素） 14 first = next;//將頭結點置為第一個元素的下一個節點 15 } else {//如果刪除節點位置的上一個節點引用不為null 16 prev.next = next;//將刪除節點的上一個節點的下一個節點引用指向刪除節點的下一個節點（去掉刪除節點） 17 x.prev = null;//刪除節點的上一個節點引用置為null 18 } 19 20 if (next == null) {//如果刪除節點的下一個節點引用為null（表示刪除最后一個節點） 21 last = prev;//將尾節點置為刪除節點的上一個節點 22 } else {//不是刪除尾節點 23 next.prev = prev;//將刪除節點的下一個節點的上一個節點的引用指向刪除節點的上一個節點 24 x.next = null;//將刪除節點的下一個節點引用置為null 25 } 26 27 x.item = null;//刪除節點內容置為null，便于垃圾回收 28 size--; 29 modCount++; 30 return element; 31 } View Code

　?、?、remove(Object o)

　　如果存在，則從該列表中刪除指定元素的第一次出現

　　此方法本質上和 remove(int index) 沒多大區別，通過循環判斷元素進行刪除，需要注意的是，是刪除第一次出現的元素，不是所有的。

1 public boolean remove(Object o) { 2 if (o == null) { 3 for (Node<E> x = first; x != null; x = x.next) { 4 if (x.item == null) { 5 unlink(x); 6 return true; 7 } 8 } 9 } else { 10 for (Node<E> x = first; x != null; x = x.next) { 11 if (o.equals(x.item)) { 12 unlink(x); 13 return true; 14 } 15 } 16 } 17 return false; 18 } View Code

?6、修改元素

　　通過調用?set(int?index,?E?element) 方法，用指定的元素替換此列表中指定位置的元素。

public E set(int index, E element) {//判斷索引 index >= 0 && index <= size中時拋出IndexOutOfBoundsException異常 checkElementIndex(index);Node<E> x = node(index);//獲取指定索引處的元素E oldVal = x.item;x.item = element;//將指定位置的元素替換成要修改的元素return oldVal;//返回指定索引位置原來的元素}

　　這里主要是通過 node(index) 方法獲取指定索引位置的節點，然后修改此節點位置的元素即可。

7、查找元素

　?、?、getFirst()

　　返回此列表中的第一個元素

1 public E getFirst() { 2 final Node<E> f = first; 3 if (f == null) 4 throw new NoSuchElementException(); 5 return f.item; 6 } View Code

　　②、getLast()

　　返回此列表中的最后一個元素

1 public E getLast() { 2 final Node<E> l = last; 3 if (l == null) 4 throw new NoSuchElementException(); 5 return l.item; 6 } View Code

　　③、get(int index)

　　返回指定索引處的元素

1 public E get(int index) { 2 checkElementIndex(index); 3 return node(index).item; 4 } View Code

　?、?、indexOf(Object o)

　　返回此列表中指定元素第一次出現的索引，如果此列表不包含元素，則返回-1。

1 //返回此列表中指定元素第一次出現的索引，如果此列表不包含元素，則返回-1。 2 public int indexOf(Object o) { 3 int index = 0; 4 if (o == null) {//如果查找的元素為null(LinkedList可以允許null值) 5 for (Node<E> x = first; x != null; x = x.next) {//從頭結點開始不斷向下一個節點進行遍歷 6 if (x.item == null) 7 return index; 8 index++; 9 } 10 } else {//如果查找的元素不為null 11 for (Node<E> x = first; x != null; x = x.next) { 12 if (o.equals(x.item)) 13 return index; 14 index++; 15 } 16 } 17 return -1;//找不到返回-1 18 } View Code

8、遍歷集合

　?、佟⑵胀?for 循環

LinkedList<String> linkedList = new LinkedList<>(); linkedList.add("A"); linkedList.add("B"); linkedList.add("C"); linkedList.add("D"); for(int i = 0 ; i < linkedList.size() ; i++){System.out.print(linkedList.get(i)+" ");//A B C D } View Code

　　代碼很簡單，我們就利用 LinkedList 的 get(int index) 方法，遍歷出所有的元素。

　　但是需要注意的是， get(int index) 方法每次都要遍歷該索引之前的所有元素，這句話這么理解：

　　比如上面的一個 LinkedList 集合，我放入了 A,B,C,D是個元素?？偣残枰拇伪闅v：

　　第一次遍歷打印 A：只需遍歷一次。

　　第二次遍歷打印 B：需要先找到 A，然后再找到 B 打印。

　　第三次遍歷打印 C：需要先找到 A，然后找到 B，最后找到 C 打印。

　　第四次遍歷打印 D：需要先找到 A，然后找到 B，然后找到 C，最后找到 D。

　　這樣如果集合元素很多，越查找到后面（當然此處的get方法進行了優化，查找前半部分從前面開始遍歷，查找后半部分從后面開始遍歷，但是需要的時間還是很多）花費的時間越多。那么如何改進呢？

　?、?、迭代器

1 LinkedList<String> linkedList = new LinkedList<>(); 2 linkedList.add("A"); 3 linkedList.add("B"); 4 linkedList.add("C"); 5 linkedList.add("D"); 6 7 8 Iterator<String> listIt = linkedList.listIterator(); 9 while(listIt.hasNext()){ 10 System.out.print(listIt.next()+" ");//A B C D 11 } 12 13 //通過適配器模式實現的接口，作用是倒敘打印鏈表 14 Iterator<String> it = linkedList.descendingIterator(); 15 while(it.hasNext()){ 16 System.out.print(it.next()+" ");//D C B A 17 } View Code

　　在 LinkedList 集合中也有一個內部類 ListItr，方法實現大體上也差不多，通過移動游標指向每一次要遍歷的元素，不用在遍歷某個元素之前都要從頭開始。其方法實現也比較簡單：

1 public ListIterator<E> listIterator(int index) { 2 checkPositionIndex(index); 3 return new ListItr(index); 4 } 5 6 private class ListItr implements ListIterator<E> { 7 private Node<E> lastReturned; 8 private Node<E> next; 9 private int nextIndex; 10 private int expectedModCount = modCount; 11 12 ListItr(int index) { 13 // assert isPositionIndex(index); 14 next = (index == size) ? null : node(index); 15 nextIndex = index; 16 } 17 18 public boolean hasNext() { 19 return nextIndex < size; 20 } 21 22 public E next() { 23 checkForComodification(); 24 if (!hasNext()) 25 throw new NoSuchElementException(); 26 27 lastReturned = next; 28 next = next.next; 29 nextIndex++; 30 return lastReturned.item; 31 } 32 33 public boolean hasPrevious() { 34 return nextIndex > 0; 35 } 36 37 public E previous() { 38 checkForComodification(); 39 if (!hasPrevious()) 40 throw new NoSuchElementException(); 41 42 lastReturned = next = (next == null) ? last : next.prev; 43 nextIndex--; 44 return lastReturned.item; 45 } 46 47 public int nextIndex() { 48 return nextIndex; 49 } 50 51 public int previousIndex() { 52 return nextIndex - 1; 53 } 54 55 public void remove() { 56 checkForComodification(); 57 if (lastReturned == null) 58 throw new IllegalStateException(); 59 60 Node<E> lastNext = lastReturned.next; 61 unlink(lastReturned); 62 if (next == lastReturned) 63 next = lastNext; 64 else 65 nextIndex--; 66 lastReturned = null; 67 expectedModCount++; 68 } 69 70 public void set(E e) { 71 if (lastReturned == null) 72 throw new IllegalStateException(); 73 checkForComodification(); 74 lastReturned.item = e; 75 } 76 77 public void add(E e) { 78 checkForComodification(); 79 lastReturned = null; 80 if (next == null) 81 linkLast(e); 82 else 83 linkBefore(e, next); 84 nextIndex++; 85 expectedModCount++; 86 } 87 88 public void forEachRemaining(Consumer<? super E> action) { 89 Objects.requireNonNull(action); 90 while (modCount == expectedModCount && nextIndex < size) { 91 action.accept(next.item); 92 lastReturned = next; 93 next = next.next; 94 nextIndex++; 95 } 96 checkForComodification(); 97 } 98 99 final void checkForComodification() { 100 if (modCount != expectedModCount) 101 throw new ConcurrentModificationException(); 102 } 103 } View Code

　　這里需要重點注意的是?modCount 字段，前面我們在增加和刪除元素的時候，都會進行自增操作 modCount，這是因為如果想一邊迭代，一邊用集合自帶的方法進行刪除或者新增操作，都會拋出異常。（使用迭代器的增刪方法不會拋異常）

final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}

　　比如：

1 LinkedList<String> linkedList = new LinkedList<>(); 2 linkedList.add("A"); 3 linkedList.add("B"); 4 linkedList.add("C"); 5 linkedList.add("D"); 6 7 8 Iterator<String> listIt = linkedList.listIterator(); 9 while(listIt.hasNext()){ 10 System.out.print(listIt.next()+" ");//A B C D 11 //linkedList.remove();//此處會拋出異常 12 listIt.remove();//這樣可以進行刪除操作 13 } View Code

　　迭代器的另一種形式就是使用 foreach 循環，底層實現也是使用的迭代器，這里我們就不做介紹了。

LinkedList<String> linkedList = new LinkedList<>(); linkedList.add("A"); linkedList.add("B"); linkedList.add("C"); linkedList.add("D"); for(String str : linkedList){System.out.print(str + ""); } View Code

9、迭代器和for循環效率差異

1 LinkedList<Integer> linkedList = new LinkedList<>(); 2 for(int i = 0 ; i < 10000 ; i++){//向鏈表中添加一萬個元素 3 linkedList.add(i); 4 } 5 long beginTimeFor = System.currentTimeMillis(); 6 for(int i = 0 ; i < 10000 ; i++){ 7 System.out.print(linkedList.get(i)); 8 } 9 long endTimeFor = System.currentTimeMillis(); 10 System.out.println("使用普通for循環遍歷10000個元素需要的時間："+ (endTimeFor - beginTimeFor)); 11 12 13 long beginTimeIte = System.currentTimeMillis(); 14 Iterator<Integer> it = linkedList.listIterator(); 15 while(it.hasNext()){ 16 System.out.print(it.next()+" "); 17 } 18 long endTimeIte = System.currentTimeMillis(); 19 System.out.println("使用迭代器遍歷10000個元素需要的時間："+ (endTimeIte - beginTimeIte));

　　打印結果為：

　　

　　一萬個元素兩者之間都相差一倍多的時間，如果是十萬，百萬個元素，那么兩者之間相差的速度會越來越大。下面通過圖形來解釋：

　　普通for循環：每次遍歷一個索引的元素之前，都要訪問之間所有的索引。

　　

　　迭代器：每次訪問一個元素后，都會用游標記錄當前訪問元素的位置，遍歷一個元素，記錄一個位置。

　　

?

參考文檔：https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html#

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的JDK1.8源码(六)——java.util.LinkedList 类的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。