Java基于JDK 1.8的LinkedList源碼詳析

 更新時間:2018年11月01日 15:46:07   作者:阿呆哥哥   我要評論

這篇文章主要給大家介紹了關于Java基于JDK 1.8的LinkedList源碼的相關資料,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧

前言

上周末我們一起分析了ArrayList的源碼并進行了一些總結,因為最近在看Collection這一塊的東西,下面的圖也是大致的總結了Collection里面重要的接口和類,如果沒有意外的話后面基本上每一個都會和大家一起學習學習,所以今天也就和大家一起來看看LinkedList吧!

 

2,記得首次接觸LinkedList還是在大學Java的時候,當時說起LinkedList的特性和應用場景:LinkedList基于雙向鏈表適用于增刪頻繁且查詢不頻繁的場景,線程不安全的且適用于單線程(這點和ArrayList很像)。然后還記得一個很深刻的是可以用LinkedList來實現棧和隊列,那讓我們一起看一看源碼到底是怎么來實現這些特點的

2.1 構造函數

public class LinkedList<E>
 extends AbstractSequentialList<E>
 implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
 transient int size = 0;
 transient Node<E> first;
 transient Node<E> last;
 
 public LinkedList() {
 }
 
 public LinkedList(Collection<? extends E> c) {
 this();
 addAll(c);
 }
 
 public boolean addAll(Collection<? extends E> c) {
 return addAll(size, c);
 }
 
 public boolean addAll(int index, Collection<? extends E> c) {
 checkPositionIndex(index);
 
 Object[] a = c.toArray();
 int numNew = a.length;
 if (numNew == 0)
  return false;
 
 Node<E> pred, succ;
 if (index == size) {
  succ = null;
  pred = last;
 } else {
  succ = node(index);
  pred = succ.prev;
 }
 
 for (Object o : a) {
  @SuppressWarnings("unchecked") E e = (E) o;
  Node<E> newNode = new Node<>(pred, e, null);
  if (pred == null)
  first = newNode;
  else
  pred.next = newNode;
  pred = newNode;
 }
 
 if (succ == null) {
  last = pred;
 } else {
  pred.next = succ;
  succ.prev = pred;
 }
 
 size += numNew;
 modCount++;
 return true;
 }
 
 private static class Node<E> {
 E item;
 Node<E> next;
 Node<E> prev;
 
 Node(Node<E> prev, E element, Node<E> next) {
  this.item = element;
  this.next = next;
  this.prev = prev;
 }
 }
 
 Node<E> node(int index) {
 // assert isElementIndex(index);
 
 if (index < (size >> 1)) {
  Node<E> x = first;
  for (int i = 0; i < index; i++)
  x = x.next;
  return x;
 } else {
  Node<E> x = last;
  for (int i = size - 1; i > index; i--)
  x = x.prev;
  return x;
 }
 } 
 
}

首先我們知道常見的構造是LinkedList()和LinkedList(Collection<? extends E> c)兩種,然后再來看看我們繼承的類和實現的接口

LinkedList 集成AbstractSequentialList抽象類,內部使用listIterator迭代器來實現重要的方法
LinkedList 實現 List 接口,能對它進行隊列操作。
LinkedList 實現 Deque 接口,即能將LinkedList當作雙端隊列使用。
LinkedList 實現了Cloneable接口,即覆蓋了函數clone(),能克隆。
LinkedList 實現java.io.Serializable接口,這意味著LinkedList支持序列化,能通過序列化去傳輸。

可以看到,相對于ArrayList,LinkedList多實現了Deque接口而少實現了RandomAccess接口,且LinkedList繼承的是AbstractSequentialList類,而ArrayList繼承的是AbstractList類。那么我們現在有一個疑問,這些多實現或少實現的接口和類會對我們LinkedList的特點產生影響嗎?這里我們先將這個疑問放在心里,我們先走正常的流程,先把LinkedList的源碼看完(主要是要解釋這些東西看Deque的源碼,還要去看Collections里面的邏輯,我怕扯遠了)

  第5-7行:定義記錄元素數量size,因為我們之前說過LinkedList是個雙向鏈表,所以這里定義了鏈表鏈表頭節點first和鏈表尾節點last

  第60-70行:定義一個節點Node類,next表示此節點的后置節點,prev表示側節點的前置節點,element表示元素值

  第22行:檢查當前的下標是否越界,因為是在構造函數中所以我們這邊的index為0,且size也為0

  第24-29行:將集合c轉化為數組a,并獲取集合的長度;定義節點pred、succ,pred用來記錄前置節點,succ用來記錄后置節點

    第70-89行:node()方法是獲取LinkedList中第index個元素,且根據index處于前半段還是后半段 進行一個折半,以提升查詢效率

  第30-36行:如果index==size,則將元素追加到集合的尾部,pred = last將前置節點pred指向之前結合的尾節點,如果index!=size表明是插入集合,通過node(index)獲取當前要插入index位置的節點,且pred = succ.prev表示將前置節點指向于當前要插入節點位置的前置節點

  第38-46行:鏈表批量增加,是靠for循環遍歷原數組,依次執行插入節點操作,第40行以前置節點 和 元素值e,構建new一個新節點;第41行如果前置節點是空,說明是頭結點,且將成員變量first指向當前節點,如果不是頭節點,則將上一個節點的尾節點指向當前新建的節點;第45行將當前的節點為前置節點了,為下次添加節點做準備。這些走完基本上我們的新節點也都創建出來了,可能這塊代碼有點繞,大家多看看

  第48-53行:循環結束后,判斷如果后置節點是null, 說明此時是在隊尾添加的,設置一下隊列尾節點last,如果不是在隊尾,則更新之前插入位置節點的前節點和當前要插入節點的尾節點

  第55-56行:修改當前集合數量、修改modCount記錄值

  ok,雖然說是分析的構造函數的源碼,但是把node(int index)、addAll(int index, Collection<? extends E> c)方法也都看了,所以來小結一下:鏈表批量增加,是靠for循環遍歷原數組,依次執行插入節點操作;通過下標index來獲取節點Node是采用的折半法來提升效率的

2.2 增加元素

常見的方法有以下三種

linkedList.add(E e)
linkedList.add(int index, E element)
linkedList.addAll(Collection<? extends E> c)

來看看具體的源碼

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++;
}
 
public void add(int index, E element) {
 checkPositionIndex(index);
 
 if (index == size)
  linkLast(element);
 else
  linkBefore(element, node(index));
 }
 
 void linkBefore(E e, Node<E> succ) {
 // assert succ != null;
 final Node<E> pred = succ.prev;
 final Node<E> newNode = new Node<>(pred, e, succ);
 succ.prev = newNode;
 if (pred == null)
  first = newNode;
 else
  pred.next = newNode;
 size++;
 modCount++;
 }
 
public boolean addAll(Collection<? extends E> c) {
 return addAll(size, c);
 }

  第2、6-16行:創建一個newNode它的prev指向之前隊尾節點last,并記錄元素值e,之前的隊尾節點last的next指向當前節點,size自增,modcount自增

  第18-20,27-38行:首先去檢查下標是否越界,然后判斷如果加入的位置剛好位于隊尾就和我們add(E element)的邏輯一樣了,如果不是則需要通過 node(index)函數定位出當前位于index下標的node,再通過linkBefore()函數創建出newNode將其插入到原先index位置

  第40-42行:就是我們在構造函數中看過的批量加入元素的方法

  OK,添加元素也很簡單,如果是在隊尾進行添加的話只需要創建一個新Node將其前置節點指向之前的last,如果是在隊中添加節點,首選拆散原先的index-1、index、index+1之間的聯系,新建節點插入進去即可。

2.3 刪除元素

常見方法有以下這幾個方法

linkedList.remove(int index)
linkedList.remove(Object o)
linkedList.remove(Collection<?> c)

源碼如下

public E remove(int index) {
 checkElementIndex(index);
 return unlink(node(index));
 }
 
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;
 }
 
public boolean remove(Object o) {
 if (o == null) {
  for (Node<E> x = first; x != null; x = x.next) {
  if (x.item == null) {
   unlink(x);
   return true;
  }
  }
 } else {
  for (Node<E> x = first; x != null; x = x.next) {
  if (o.equals(x.item)) {
   unlink(x);
   return true;
  }
  }
 }
 return false;
 }
 
 public boolean removeAll(Collection<?> c) {
 Objects.requireNonNull(c);
 boolean modified = false;
 Iterator<?> it = iterator();
 while (it.hasNext()) {
  if (c.contains(it.next())) {
  it.remove();
  modified = true;
  }
 }
 return modified;
 }

  第1-4,6-30行:首先根據index通過方法值node(index)來確定出集合中的下標是index的node,咋們主要看unlink()方法,代碼感覺很多,其實只是將當前要刪除的節點node的頭結點的尾節點指向node的尾節點、將node的尾結點的頭節點指向node的頭節點,可能有點繞(哈哈),看一下代碼基本上就可以理解了,然后將下標為index的node置空,供GC回收

  第32-49行:首先判斷一下當前要刪除的元素o是否為空,然后進行for循環定位出當前元素值等于o的節點node,然后再走的邏輯就是上面我們看到過的unlink()方法,也很簡單,比remove(int index) 多了一步

  第51-62行:這一塊因為涉及到迭代器Iterator,而我們LinkedList使用的是ListItr,這個后面我們將迭代器的時候一起講,不過大致的邏輯是都可以看懂的,和我們的ArrayList的迭代器方法的含義一樣的,可以先那樣理解

  ok,小結一下, 按下標刪,也是先根據index找到Node,然后去鏈表上unlink掉這個Node。 按元素刪,會先去遍歷鏈表尋找是否有該Node,考慮到允許null值,所以會遍歷兩遍,然后再去unlink它。

2.5 修改元素

public E set(int index, E element) {
 checkElementIndex(index);
 Node<E> x = node(index);
 E oldVal = x.item;
 x.item = element;
 return oldVal;
 }

只有這一種方法,首先檢查下標是否越界,然后根據下標獲取當前Node,然后修改節點中元素值item,超級簡單

2.6 查找元素

public E get(int index) {
 checkElementIndex(index);//判斷是否越界 [0,size)
 return node(index).item; //調用node()方法 取出 Node節點,
}
 
 
 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;
 }
 
 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;
 }

獲取元素的源碼也很簡單,主要是通過node(index)方法獲取節點,然后獲取元素值,indexOf和lastIndexOf方法的區別在于一個是從頭向尾開始遍歷,一個是從尾向頭開始遍歷

2.7 迭代器

public Iterator<E> iterator() {
  return listIterator();
 }
 
public ListIterator<E> listIterator() {
  return listIterator(0);
 }
 
public ListIterator<E> listIterator(final int index) {
  rangeCheckForAdd(index);
 
  return new ListItr(index);
 }
 
private class ListItr extends Itr implements ListIterator<E> {
  ListItr(int index) {
   cursor = index;
  }
 
  public boolean hasPrevious() {
   return cursor != 0;
  }
 
  public E previous() {
   checkForComodification();
   try {
    int i = cursor - 1;
    E previous = get(i);
    lastRet = cursor = i;
    return previous;
   } catch (IndexOutOfBoundsException e) {
    checkForComodification();
    throw new NoSuchElementException();
   }
  }
 
  public int nextIndex() {
   return cursor;
  }
 
  public int previousIndex() {
   return cursor-1;
  }
 
  public void set(E e) {
   if (lastRet < 0)
    throw new IllegalStateException();
   checkForComodification();
 
   try {
    AbstractList.this.set(lastRet, e);
    expectedModCount = modCount;
   } catch (IndexOutOfBoundsException ex) {
    throw new ConcurrentModificationException();
   }
  }
 
  public void add(E e) {
   checkForComodification();
 
   try {
    int i = cursor;
    AbstractList.this.add(i, e);
    lastRet = -1;
    cursor = i + 1;
    expectedModCount = modCount;
   } catch (IndexOutOfBoundsException ex) {
    throw new ConcurrentModificationException();
   }
  }
 }

可以看到,其實最后使用的迭代器是使用的ListIterator類,且集成自Itr,而Itr類就是我們昨天ArrayList內部使用的類,hasNext()方法和我們之前的一樣,判斷不等于size大小,然后next()獲取元素主要也是E next = get(i);這行代碼,這樣就又走到我們之前的獲取元素的源碼當中,獲得元素值。

OK,這樣我們上面的基本方法都看完了,再來看看我們上面遺留的問題,首先來看Deque接口有什么作用,我們來一起看看

Deque 是 Double ended queue (雙端隊列) 的縮寫,讀音和 deck 一樣,蛋殼。
Deque 繼承自 Queue,直接實現了它的有 LinkedList, ArayDeque, ConcurrentLinkedDeque 等。
Deque 支持容量受限的雙端隊列,也支持大小不固定的。一般雙端隊列大小不確定。
Deque 接口定義了一些從頭部和尾部訪問元素的方法。比如分別在頭部、尾部進行插入、刪除、獲取元素。  

public interface Deque<E> extends Queue<E> {
 void addFirst(E e);//插入頭部,異常會報錯
 boolean offerFirst(E e);//插入頭部,異常不報錯
 E getFirst();//獲取頭部,異常會報錯
 E peekFirst();//獲取頭部,異常不報錯
 E removeFirst();//移除頭部,異常會報錯
 E pollFirst();//移除頭部,異常不報錯
 
 void addLast(E e);//插入尾部,異常會報錯
 boolean offerLast(E e);//插入尾部,異常不報錯
 E getLast();//獲取尾部,異常會報錯
 E peekLast();//獲取尾部,異常不報錯
 E removeLast();//移除尾部,異常會報錯
 E pollLast();//移除尾部,異常不報錯
}

Deque也就是一個接口,上面是接口里面的方法,然后了解Deque就必須了解Queue

public interface Queue<E> extends Collection<E> {
 //往隊列插入元素,如果出現異常會拋出異常
 boolean add(E e);
 //往隊列插入元素,如果出現異常則返回false
 boolean offer(E e);
 //移除隊列元素,如果出現異常會拋出異常
 E remove();
 //移除隊列元素,如果出現異常則返回null
 E poll();
 //獲取隊列頭部元素,如果出現異常會拋出異常
 E element();
 //獲取隊列頭部元素,如果出現異常則返回null
 E peek();
}

然后我們知道LinkedList實現了Deque接口,也就是說可以使用LinkedList實現棧和隊列的功能,讓寫寫看

package com.ysten.leakcanarytest;
 
import java.util.Collection;
import java.util.LinkedList;
 
/**
 * desc : 實現棧
 * time : 2018/10/31 0031 19:07
 *
 * @author : wangjitao
 */
public class Stack<T>
{
 private LinkedList<T> stack;
 
 //無參構造函數
 public Stack()
 {
  stack=new LinkedList<T>();
 }
 //構造一個包含指定collection中所有元素的棧
 public Stack(Collection<? extends T> c)
 {
  stack=new LinkedList<T>(c);
 }
 //入棧
 public void push(T t)
 {
  stack.addFirst(t);
 }
 //出棧
 public T pull()
 {
  return stack.remove();
 }
 //棧是否為空
 boolean isEmpty()
 {
  return stack.isEmpty();
 }
 
 //打印棧元素
 public void show()
 {
  for(Object o:stack)
   System.out.println(o);
 }
}

測試功能

public static void main(String[] args){
  Stack<String> stringStack = new Stack<>();
  stringStack.push("1");
  stringStack.push("2");
  stringStack.push("3");
  stringStack.push("4");
  stringStack. show();
 }

打印結果如下:

4
3
2
1

隊列的實現類似的,大家可以下來自己寫一下,然后繼續我們的問題,實現Deque接口和實現RandomAccess接口有什么區別,我們上面看了Deque接口,實現Deque接口可以擁有雙向鏈表功能,那我們再來看看RandomAccess接口

 public interface RandomAccess {
 }

發現什么都沒有,原來RandomAccess接口是一個標志接口(Marker),然而實現這個接口有什么作用呢?

答案是只要List集合實現這個接口,就能支持快速隨機訪問,然而又有人問,快速隨機訪問是什么東西?有什么作用?

google是這樣定義的:給可以提供隨機訪問的List實現去標識一下,這樣使用這個List的程序在遍歷這種類型的List的時候可以有更高效率。僅此而已。

這時候看一下我們Collections類中的binarySearch方法

int binarySearch(List<? extends Comparable<? super T>> list, T key) {
  if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
   return Collections.indexedBinarySearch(list, key);
  else
   return Collections.iteratorBinarySearch(list, key);
 }

可以看到這時候去判斷了如果當前集合實現了RandomAccess接口就會走Collections.indexedBinarySearch方法,那么我們來看一下Collections.indexedBinarySearch()方法和Collections.iteratorBinarySearch()的區別是什么呢?

int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {
  int low = 0;
  int high = list.size()-1;
 
  while (low <= high) {
   int mid = (low + high) >>> 1;
   Comparable<? super T> midVal = list.get(mid);
   int cmp = midVal.compareTo(key);
 
   if (cmp < 0)
    low = mid + 1;
   else if (cmp > 0)
    high = mid - 1;
   else
    return mid; // key found
  }
  return -(low + 1); // key not found
 }
 
 
 
int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)
 {
  int low = 0;
  int high = list.size()-1;
  ListIterator<? extends Comparable<? super T>> i = list.listIterator();
 
  while (low <= high) {
   int mid = (low + high) >>> 1;
   Comparable<? super T> midVal = get(i, mid);
   int cmp = midVal.compareTo(key);
 
   if (cmp < 0)
    low = mid + 1;
   else if (cmp > 0)
    high = mid - 1;
   else
    return mid; // key found
  }
  return -(low + 1); // key not found
 }

通過查看源代碼,發現實現RandomAccess接口的List集合采用一般的for循環遍歷,而未實現這接口則采用迭代器

,那現在讓我們以LinkedList為例子看一下,通過for循環、迭代器、removeFirst和removeLast來遍歷的效率(之前忘記寫這一塊了,順便一塊先寫了對于LinkedList那種訪問效率要高一些)

迭代器遍歷

LinkedList linkedList = new LinkedList();
for(int i = 0; i < 100000; i++){
   linkedList.add(i);
}
// 迭代器遍歷
 long start = System.currentTimeMillis();
 Iterator iterator = linkedList.iterator();
 while(iterator.hasNext()){
  iterator.next();
 }
 long end = System.currentTimeMillis();
 System.out.println("Iterator:"+ (end - start) +"ms");

打印結果:Iterator:28ms

for循環get遍歷

// 順序遍歷(隨機遍歷)
 long start = System.currentTimeMillis();
 for(int i = 0; i < linkedList.size(); i++){
   linkedList.get(i);
}
long end = System.currentTimeMillis();
System.out.println("for :"+ (end - start) +"ms");

打印結果   for :6295ms

使用增強for循環

long start = System.currentTimeMillis();
for(Object i : linkedList);
long end = System.currentTimeMillis();
System.out.println("增強for :"+ (end - start) +"ms");

輸出結果 增強for :6ms

removeFirst來遍歷

long start = System.currentTimeMillis();
while(linkedList.size() != 0){
   linkedList.removeFirst();
}
long end = System.currentTimeMillis();
System.out.println("removeFirst :"+ (end - start) +"ms");

輸出結果 removeFirst :3ms

綜上結果可以看到,遍歷LinkedList時,使用removeFirst()或removeLast()效率最高,而for循環get()效率最低,應避免使用這種方式進行。應當注意的是,使用removeFirst()或removeLast()遍歷時,會刪除原始數據,若只單純的讀取,應當選用迭代器方式或增強for循環方式。

ok,上述的都是只針對LinkedList而言測試的,然后我們接著上面的RandomAccess接口來講,看看通過對比ArrayList的for循環和迭代器遍歷看看訪問效率

ArrayList的for循環

long start = System.currentTimeMillis();
for (int i = 0; i < arrayList.size(); i++) {
   arrayList.get(i);
}
 long end = System.currentTimeMillis();
 System.out.println("for :"+ (end - start) +"ms");

輸出結果  for  :3ms

ArrayList的迭代遍歷

long start = System.currentTimeMillis();
Iterator iterable = arrayList.iterator() ;
while (iterable.hasNext()){
   iterable.next();
}
 long end = System.currentTimeMillis();
 System.out.println("for :"+ (end - start) +"ms");

輸出結果 for  :6ms

所以讓我們來綜上對比一下

ArrayList
    普通for循環:3ms
    迭代器:6ms
LinkedList
    普通for循環:6295ms  
    迭代器:28ms

從上面數據可以看出,ArrayList用for循環遍歷比iterator迭代器遍歷快,LinkedList用iterator迭代器遍歷比for循環遍歷快,所以對于不同的List實現類,遍歷的方式有所不用,RandomAccess接口這個空架子的存在,是為了能夠更好地判斷集合是否ArrayList或者LinkedList,從而能夠更好選擇更優的遍歷方式,提高性能!

(在這里突然想起在去年跳槽的時候,有家公司的面試官問我,list集合的哪一種遍歷方式要快一些,然后我說我沒有每個去試過,結果那位大佬說的是for循環遍歷最快,還叫我下去試試,現在想想,只有在集合是ArrayList的時候for循環才最快,對于LinkedList來說for循環反而是最慢的,那位大佬,你欠我一聲對不起(手動斜眼微笑))

3,上面把我們該看的點都看了,那么我們再來總結總結:

LinkedList 是雙向列表,鏈表批量增加,是靠for循環遍歷原數組,依次執行插入節點操作。

ArrayList基于數組, LinkedList基于雙向鏈表,對于隨機訪問, ArrayList比較占優勢,但LinkedList插入、刪除元素比較快,因為只要調整指針的指向。針對特定位置需要遍歷時,所以LinkedList在隨機訪問元素的話比較慢。

LinkedList沒有實現自己的 Iterator,使用的是 ListIterator。

LinkedList需要更多的內存,因為 ArrayList的每個索引的位置是實際的數據,而 LinkedList中的每個節點中存儲的是實際的數據和前后節點的位置。

LinkedList也是非線程安全的,只有在單線程下才可以使用。為了防止非同步訪問,Collections類里面提供了synchronizedList()方法。

總結

以上就是這篇文章的全部內容了,希望本文的內容對大家的學習或者工作具有一定的參考學習價值,如果有疑問大家可以留言交流,謝謝大家對腳本之家的支持。

相關文章

最新評論

时时彩包赢公式0369