LinkedList源码分析（基于Java8）
生活随笔
收集整理的這篇文章主要介紹了
LinkedList源码分析（基于Java8）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
- LinkedList是一個實現了List接口和Deque接口的雙端鏈表
- 有關索引的操作可能從鏈表頭開始遍歷到鏈表尾部，也可能從尾部遍歷到鏈表頭部，這取決于看索引更靠近哪一端。
- LinkedList不是線程安全的，如果想使LinkedList變成線程安全的，可以使用如下方式：
iterator()和listIterator()返回的迭代器都遵循fail-fast機制。
從上圖可以看出LinkedList與ArrayList的不同之處
- ArrayList直接繼承自AbstractList
- LinkedList繼承自AbstractSequentialList，然后再繼承自AbstractList。另外還實現了Dequeu接口，雙端隊列。
內部結構
LinkedList內部是一個雙端鏈表的結構
LinkedList的結構
從上圖可以看出，LinkedList內部是一個雙端鏈表結構，有兩個變量，first指向鏈表頭部，last指向鏈表尾部。
成員變量
size表示當前鏈表中的數據個數
下面是Node節點的定義，LinkedList的靜態內部類
從Node的定義可以看出鏈表是一個雙端鏈表的結構。
構造方法
LinkedList有兩個構造方法，一個用于構造一個空的鏈表，一個用已有的集合創建鏈表
添加
因為LinkedList即實現了List接口，又實現了Deque，所以LinkedList既可以添加將元素添加到尾部，也可以將元素添加到指定索引位置，還可以添加添加整個集合；另外既可以在頭部添加，又可以在尾部添加。
分別從List接口和Deque接口介紹。
List接口的添加
add(E e)
add(E e)用于將元素添加到鏈表尾部，實現如下:
public boolean add(E e) {linkLast(e);return true;}void linkLast(E e) {final Node<E> l = last;//指向鏈表尾部final Node<E> newNode = new Node<>(l, e, null);//以尾部為前驅節點創建一個新節點last = newNode;//將鏈表尾部指向新節點if (l == null)//如果鏈表為空，那么該節點既是頭節點也是尾節點first = newNode;else//鏈表不為空，那么將該結點作為原鏈表尾部的后繼節點l.next = newNode;size++;//增加尺寸modCount++; }從上面代碼可以看到，就是一個鏈表尾部添加一個雙端節點的操作，但是需要注意對鏈表為空時頭節點的處理。
add(int index,E e)
add(int index,E e)用于在指定位置添加元素
1. 檢查index的范圍，否則拋出異常
2. 如果插入位置是鏈表尾部，那么調用linkLast方
3. 如果插入位置是鏈表中間，那么調用linkBefore
看一下linkBefore的實現
在看linkBefore之前，先看一下node(int index)方法，該方法返回指定位置的節點
node(int index)將根據index是靠近頭部還是尾部選擇不同的遍歷方向
一旦得到了指定索引位置的節點，再看linkBefore()
linkBefore()方法在第二個參數節點前插入一個新節點
linkBefore#第一步
linkBefore#第二步
linkBefore#第三步
linkBefore主要分三步
1. 創建newNode節點，將newNode的后繼指針指向succ，前驅指針指向pred
2. 將succ的前驅指針指向newNode
3. 根據pred是否為null，進行不同操作。
- 如果pred為null，說明該節點插入在頭節點之前，要重置first頭節點
- 如果pred不為null，那么直接將pred的后繼指針指向newNode即可
addAll
addAll有兩個重載方法
- 一個參數的方法表示將集合元素添加到鏈表尾部
- 兩個參數的方法指定了開始插入的位置
1. 檢查index索引范圍
2. 得到集合數據
3. 得到插入位置的前驅和后繼節點
4. 遍歷數據，將數據插入到指定位置
Deque接口的添加
addFirst(E e)
將元素添加到鏈表頭部
public void addFirst(E e) {linkFirst(e);}private void linkFirst(E e) {final Node<E> f = first;final Node<E> newNode = new Node<>(null, e, f);//新建節點，以頭節點為后繼節點first = newNode;//如果鏈表為空，last節點也指向該節點if (f == null)last = newNode;//否則，將頭節點的前驅指針指向新節點elsef.prev = newNode;size++;modCount++;}在頭節點插入一個節點使新節點成為新節點，但是和linkLast一樣需要注意當鏈表為空時，對last節點的設置
addLast(E e)
將元素添加到鏈表尾部，與add()方法一樣
public void addLast(E e) {linkLast(e); }offer(E e)
將數據添加到鏈表尾部，其內部調用了add(E e)方法
public boolean offer(E e) {return add(e); }offerFirst(E e)方法
將數據插入鏈表頭部，與addFirst的區別在于
- 該方法可以返回特定的返回值
- addFirst的返回值為void。
offerLast(E e)方法
offerLast()與addLast()的區別和offerFirst()和addFirst()的區別一樣
添加操作總結
LinkedList由于實現了List和Deque接口，所以有多種添加方法，總結一下
- 將數據插入到鏈表尾部
- boolean add(E e):
- void addLast(E e)
- boolean offerLast(E e)
- 將數據插入到鏈表頭部
- void addFirst(E e)
- boolean offerFirst(E e)
- 將數據插入到指定索引位置
- boolean add(int index,E e)
2檢索
2.1 根據位置取數據
2.1.1 get(int index)
獲取任意位置的,get(int index)方法根據指定索引返回數據，如果索引越界，那么會拋出異常
/*** Returns the element at the specified position in this list.** @param index index of the element to return* @return the element at the specified position in this list* @throws IndexOutOfBoundsException {@inheritDoc}*/public E get(int index) {checkElementIndex(index);return node(index).item;}1.檢查index邊界，index>=0&&index
2.返回指定索引位置的元素
2.1.2 獲得位置為0的頭節點數據
LinkedList中有多種方法可以獲得頭節點的數據,區別在于對鏈表為空時的處理，是拋異常還是返回null
主要方法有getFirst()、element()、peek()、peekFirst()
其中getFirst()和element()方法將會在鏈表為空時，拋出異常
從代碼可以看到，element()方法的內部就是使用getFirst()實現的。它們會在鏈表為空時，拋NoSuchElementException
下面再看peek()和peekFirst()
當鏈表為空時，peek()和peekFirst()方法返回null
2.1.3 獲得位置為size-1的尾節點數據
獲得尾節點數據的方法有
- getLast()
getLast()在鏈表為空時，會拋NoSuchElementException，
- peekLast()
只是會返回null
peekLast()
2.2 根據對象得到索引
- 第一個匹配的索引
從前往后遍歷 - 最后一個匹配的索引
從后往前遍歷
2.2.1 indexOf()
/*** 返回第一個匹配的索引* in this list, or -1 if this list does not contain the element.* More formally, returns the lowest index {@code i} such that* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,* or -1 if there is no such index.** @param o element to search for* @return the index of the first occurrence of the specified element in* this list, or -1 if this list does not contain the element*/public int indexOf(Object o) {int index = 0;if (o == null) {//從頭往后遍歷for (Node<E> x = first; x != null; x = x.next) {if (x.item == null)return index;index++;}} else {//從頭往后遍歷for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item))return index;index++;}}return -1;}可以看到，LinkedList可包含null，遍歷方式都是從前往后，一旦匹配了，就返回索引
2.2.2 lastIndexOf()
返回最后一個匹配的索引，實現為從后往前遍歷
/*** Returns the index of the last occurrence of the specified element* in this list, or -1 if this list does not contain the element.* More formally, returns the highest index {@code i} such that* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,* or -1 if there is no such index.** @param o element to search for* @return the index of the last occurrence of the specified element in* this list, or -1 if this list does not contain the element*/public int lastIndexOf(Object o) {int index = size;if (o == null) {for (Node<E> x = last; x != null; x = x.prev) {index--;if (x.item == null)return index;}} else {for (Node<E> x = last; x != null; x = x.prev) {index--;if (o.equals(x.item))return index;}}return -1;}2.3 檢查是否包含某對象
contains(Object o)
檢查對象o是否存在于鏈表中
從代碼可以看到contains()方法調用了indexOf()方法，只要返回結果不是-1，那就說明該對象存在于鏈表中
2.4 檢索操作總結
檢索操作分為按照位置得到對象以及按照對象得到位置兩種方式，其中按照對象得到位置的方法有indexOf()和lastIndexOf()；按照位置得到對象有如下方法：
- 根據任意位置得到數據的get(int index)方法，當index越界會拋出異常
- 獲得頭節點數據
- getFirst()和element()方法在鏈表為空時會拋出NoSuchElementException
- peek()和peekFirst()方法在鏈表為空時會返回null
- 獲得尾節點數據
- getLast()在鏈表為空時會拋出NoSuchElementException
- peekLast()在鏈表為空時會返回null
3刪除
- 按照位置刪除
- 返回是否刪除成功的標志
- 返回被刪除的元素
- 按照對象刪除
3.1 刪除指定對象
remove(Object o)
一次只刪除一個匹配的對象，如果刪除了匹配對象，返回true，否則false
由于LinkedList可以存儲null，所以對刪除對象以是否為null做區分
然后從鏈表頭開始遍歷，一旦匹配，就會調用unlink()方法將該節點從鏈表中移除
下面是unlink()
/*** Unlinks non-null node x.*/E unlink(Node<E> x) {// assert x != null;final E element = x.item;final Node<E> next = x.next;//得到后繼節點final Node<E> prev = x.prev;//得到前驅節點//刪除前驅指針if (prev == null) {first = next;如果刪除的節點是頭節點,令頭節點指向該節點的后繼節點} else {prev.next = next;//將前驅節點的后繼節點指向后繼節點x.prev = null;}//刪除后繼指針if (next == null) {last = prev;//如果刪除的節點是尾節點,令尾節點指向該節點的前驅節點} else {next.prev = prev;x.next = null;}x.item = null;size--;modCount++;return element;} unlink第一步第一步：得到待刪除節點的前驅節點和后繼節點
unlink第二步
第二步：刪除前驅節點
unlink第三步
第三步：刪除后繼節點
經過三步，待刪除的結點就從鏈表中脫離了。需要注意的是刪除位置是頭節點或尾節點時候的處理，上面的示意圖沒有特別指出。
3.2 按照位置刪除對象
3.2.1 刪除任意位置的對象
- boolean remove(int index)
刪除任意位置的元素，刪除成功將返回true，否則false
1. 檢查index范圍，屬于[0,size）
2. 將索引出節點刪除
3.2.2 刪除頭節點的對象
- remove()、removeFirst()、pop()
在鏈表為空時將拋出NoSuchElementException
remove()和pop()內部調用了removeFirst()
而removeFirst()在鏈表為空時將拋出NoSuchElementException
- poll()和,pollFirst()
在鏈表為空時將返回null
poll()和pollFirst()的實現代碼是相同的，在鏈表為空時將返回null
3.2.3 刪除尾節點的對象
- removeLast()
可以看到removeLast()在鏈表為空時將拋出NoSuchElementException
- pollLast()
可以看到pollLast()在鏈表為空時會返回null，而不是拋出異常
3.3 刪除操作總結
刪除操作由很多種方法
按照指定對象刪除
boolean remove(Object o)，一次只會刪除一個匹配的對象
按照指定位置刪除
- 刪除任意位置的對象
E remove(int index),當index越界時會拋出異常 - 刪除頭節點位置的對象
- 在鏈表為空時拋出異常
E remove()、E removeFirst()、E pop() - 在鏈表為空時返回null
E poll()、E pollFirst()
- 在鏈表為空時拋出異常
- 刪除尾節點位置的對象
- 在鏈表為空時拋出異常
E removeLast() - 在鏈表為空時返回null
E pollLast()
- 在鏈表為空時拋出異常
4迭代器
LinkedList的iterator()內部調用了其listIterator()方法，所以可只分析listIterator()方法listIterator()提供了兩個重載方法。
iterator()方法和listIterator()方法的關系如下
public Iterator<E> iterator() {return listIterator();}public ListIterator<E> listIterator() {return listIterator(0);}public ListIterator<E> listIterator(int index) {checkPositionIndex(index);return new ListItr(index);}從上面可以看到三者的關系是iterator()——>listIterator(0)——>listIterator(int index)
最終都會調用listIterator(int index)，其中參數表示迭代器開始的位置
ListIterator是一個可以指定任意位置開始迭代，并且有兩個遍歷方法
下面直接看ListItr
private class ListItr implements ListIterator<E> {private Node<E> lastReturned;private Node<E> next;private int nextIndex;private int expectedModCount = modCount;//保存當前modCount，確保fail-fast機制ListItr(int index) {// assert isPositionIndex(index);next = (index == size) ? null : node(index);//得到當前索引指向的next節點nextIndex = index;}public boolean hasNext() {return nextIndex < size;}//獲取下一個節點public E next() {checkForComodification();if (!hasNext())throw new NoSuchElementException();lastReturned = next;next = next.next;nextIndex++;return lastReturned.item;}public boolean hasPrevious() {return nextIndex > 0;}//獲取前一個節點，將next節點向前移public E previous() {checkForComodification();if (!hasPrevious())throw new NoSuchElementException();lastReturned = next = (next == null) ? last : next.prev;nextIndex--;return lastReturned.item;}public int nextIndex() {return nextIndex;}public int previousIndex() {return nextIndex - 1;}public void remove() {checkForComodification();if (lastReturned == null)throw new IllegalStateException();Node<E> lastNext = lastReturned.next;unlink(lastReturned);if (next == lastReturned)next = lastNext;elsenextIndex--;lastReturned = null;expectedModCount++;}public void set(E e) {if (lastReturned == null)throw new IllegalStateException();checkForComodification();lastReturned.item = e;}public void add(E e) {checkForComodification();lastReturned = null;if (next == null)linkLast(e);elselinkBefore(e, next);nextIndex++;expectedModCount++;}public void forEachRemaining(Consumer<? super E> action) {Objects.requireNonNull(action);while (modCount == expectedModCount && nextIndex < size) {action.accept(next.item);lastReturned = next;next = next.next;nextIndex++;}checkForComodification();}final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}}構造器中，得到了當前位置的節點，就是變量next
next()返回當前節點的值并將next指向其后繼節點
previous()返回當前節點的前一個節點的值并將next節點指向其前驅節點
由于Node是一個雙端節點，所以這兒用了一個節點就可以實現從前向后迭代和從后向前迭代
另外在ListIterator初始時，exceptedModCount保存了當前的modCount，如果在迭代期間，有操作改變了鏈表的底層結構，那么再操作迭代器的方法時將會拋出ConcurrentModificationException。
5 例子
由于LinkedList是一個實現了Deque的雙端隊列，所以LinkedList既可以當做Queue，又可以當做Stack，下面的例子將LinkedList成Stack
public class LinkedStack<E> {private LinkedList<E> linkedList;public LinkedStack() {linkedList = new LinkedList<E>();}//壓入數據public void push(E e) {linkedList.push(e);}//彈出數據，在Stack為空時將拋出異常public E pop() {return linkedList.pop();}//檢索棧頂數據，但是不刪除public E peek() {return linkedList.peek();}}在將LinkedList當做Stack時，使用pop()、push()、peek()方法需要注意的是LinkedList內部是將鏈表頭部當做棧頂，鏈表尾部當做棧底，也就意味著所有的壓入、攤入操作都在鏈表頭部進行
6總結
LinkedList是基于雙端鏈表的List，其內部的實現源于對鏈表的操作
- 適用于頻繁增加、刪除的情況
- 該類不是線程安全的
- 由于LinkedList實現了Queue接口，所以LinkedList不止有隊列的接口，還有棧的接口，可以使用LinkedList作為隊列和棧的實現
總結
以上是生活随笔為你收集整理的LinkedList源码分析（基于Java8）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： C++ using namespace
- 下一篇： Linux文件系统和挂载点理解