JDK8的LinkedList源码学习笔记

正文:

首先,LinkedList的继承和实现了的类和接口:

LinkedList实现的接口

LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。同时实现了Deque接口,即能将LinkedList当作双端队列使用。

另外实现了Cloneable接口,Serializable接口。 接下来看LinkedList的构造方法:

/**
    * Constructs an empty list.
    */
   public LinkedList() {
   }

   /**
    * Constructs a list containing the elements of the specified
    * collection, in the order they are returned by the collection's
    * iterator.
    *
    * @param  c the collection whose elements are to be placed into this list
    * @throws NullPointerException if the specified collection is null
    */
   public LinkedList(Collection<? extends E> c) {
       this();
       addAll(c);
   }

LinkedList提供了两个构造方法,第一个是默认无参的,第二个是带Collection的类型参数:

  • 使用this()调用默认的构造方法

成员变量分析

/**
    * 当前有多少个节点
    */
transient int size = 0;
   /**
    * 第一个节点.
    * Invariant: (first == null && last == null) ||
    *            (first.prev == null && first.item != null)
    */
   transient Node<E> first;

   /**
    * 最后一个节点.
    * Invariant: (first == null && last == null) ||
    *            (last.next == null && last.item != null)
    */
   transient Node<E> last;

核心方法分析

1. addAll()方法

addAll有两个重载函数,addAll(Collection<? extends E>)型和addAll(int, Collection<? extends E>)型,我们平时习惯调用的addAll(Collection<? extends E>)型会转化为addAll(int, Collection<? extends E>)型,所以我们着重分析此函数即可

public boolean addAll(int index, Collection<? extends E> c) {
	//JDK8将对index的判断封装了一个方法checkPositionIndex(index);
	//这个就不用说了,集合转为数组
       Object[] a = c.toArray();
       int numNew = a.length;
       if (numNew == 0)
           return false;
	//succ指向当前需要插入节点的位置,pred指向其前一个节点
       Node<E> pred, succ;
	//在列表尾部插入的时候
       if (index == size) {
           succ = null;
           pred = last;
       } else {
	//若不是在尾部插入时候则先去根据索引查询对应的元素可见该块最下面的node()方法
           succ = node(index);
           pred = succ.prev;
       }
	//遍历collection中的所有元素将其依次插入到此链表中指定位置
       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;
   }

/**
    * 根据index返回对应元素.
    */
   Node<E> node(int index) {
       // assert isElementIndex(index);
	//若index<size/2正序移位获取索引位置
       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;
       }
   }

2. removeXXX()方法

LinkedList提供了头删除removeFirst()、尾删除removeLast()、remove(int index)、remove(Object o)、clear()这些删除元素的方法。

/**
    * Removes and returns the first element from this list.
    */
public E removeFirst() {
       final Node<E> f = first;
       if (f == null)
           throw new NoSuchElementException();
       return unlinkFirst(f);
   }

   /**
    * Removes and returns the last element from this list.
    */
   public E removeLast() {
       final Node<E> l = last;
       if (l == null)
           throw new NoSuchElementException();
       return unlinkLast(l);
   }
/**
    * Unlinks non-null first node f.
    * 删除非空的首节点f.
    */
   private E unlinkFirst(Node<E> f) {
       // assert f == first && f != null;
       final E element = f.item;
       final Node<E> next = f.next;
       f.item = null;
       f.next = null; // help GC
	//将原首节点的next节点设置为首节点
       first = next;
       if (next == null)
           last = null;
       else
           next.prev = null;
       size--;
       modCount++;
       return element;
   }

   /**
    * Unlinks non-null last node l.
    * 删除非空的尾节点f.
    */
   private E unlinkLast(Node<E> l) {
       // assert l == last && l != null;
       final E element = l.item;
       final Node<E> prev = l.prev;
       l.item = null;
       l.prev = null; // help GC
	//将原尾节点的prev节点设置为尾节点
       last = prev;
       if (prev == null)
           first = null;
       else
           prev.next = null;
       size--;
       modCount++;
       return element;
   }


/**
    * Remove.
    */
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;
   }
/**
    * 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--; //size-1
       modCount++;
       return element;
   }

/**
    * Removes all of the elements from this list.
    * 清空所有节点.
    */
   public void clear() {
       // Clearing all of the links between nodes is "unnecessary", but:
       // - helps a generational GC if the discarded nodes inhabit
       //   more than one generation
       // - is sure to free memory even if there is a reachable Iterator
       for (Node<E> x = first; x != null; ) {
           Node<E> next = x.next;
           x.item = null;
           x.next = null;
           x.prev = null;
           x = next;
       }
       first = last = null;
       size = 0;
       modCount++;
   }

3. set()方法

//很容易分析,先检查index,然后根据index返回对应元素,最后将元素-->x.item
public E set(int index, E element) {
       checkElementIndex(index);
       Node<E> x = node(index);
       E oldVal = x.item;
       x.item = element;
       return oldVal;
   }

4. getXXX()方法

LinkedList提供了getFirst()、getLast()、contains(Object o)、get(int index)、indexOf(Object o)、lastIndexOf(Object o)这些查找元素的方法。

/**
    * Returns the first element in this list.
    */
   public E getFirst() {
       final Node<E> f = first;
       if (f == null)
           throw new NoSuchElementException();
       return f.item;
   }
/**
    * Returns the last element in this list.
    */
   public E getLast() {
       final Node<E> l = last;
       if (l == null)
           throw new NoSuchElementException();
       return l.item;
   }
public boolean contains(Object o) {
       return indexOf(o) != -1;
   }
/**
    * 正向查找,返回LinkedList中元素值Object o第一次出现的位置,如果元素不存在,则返回-1
    */
   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中元素值Object o最后一次出现的位置,如果元素不存在,则返回-1
   public int lastIndexOf(Object o) {
       int index = size;
	//LinkedList可以为null
       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;
   }
/**
    * 根据index获取当前元素.
    */
   public E get(int index) {
       checkElementIndex(index);
       return node(index).item;
   }

5. Queue操作

Queue操作提供了peek()、element()、poll()、remove()、offer(E e)这些方法。

//获取但不移除此队列的头;如果此队列为空,则返回 null
   public E peek() {
       final Node<E> f = first;
       return (f == null) ? null : f.item;
   }

   //获取但不移除此队列的头;如果此队列为空,则抛出NoSuchElementException异常
   public E element() {
       return getFirst();
   }

   //获取并移除此队列的头,如果此队列为空,则返回 null
   public E poll() {
       final Node<E> f = first;
       return (f == null) ? null : unlinkFirst(f);
   }

   //获取并移除此队列的头,如果此队列为空,则抛出NoSuchElementException异常
   public E remove() {
       return removeFirst();
   }

   //将指定的元素值(E e)插入此列表末尾
   public boolean offer(E e) {
       return add(e);
   }

6. Deque操作

Deque操作提供了offerFirst(E e)、offerLast(E e)、peekFirst()、peekLast()、pollFirst()、pollLast()、push(E e)、pop()、removeFirstOccurrence(Object o)、removeLastOccurrence(Object o)这些方法。

//将指定的元素值(E e)插入此列表末尾
   public boolean offer(E e) {
       return add(e);
   }

   // Deque operations

   //将指定的元素插入此双端队列的开头
   public boolean offerFirst(E e) {
       addFirst(e);
       return true;
   }

   //将指定的元素插入此双端队列的末尾
   public boolean offerLast(E e) {
       addLast(e);
       return true;
   }

   //获取,但不移除此双端队列的第一个元素;如果此双端队列为空,则返回 null
   public E peekFirst() {
       final Node<E> f = first;
       return (f == null) ? null : f.item;
    }

   //获取,但不移除此双端队列的最后一个元素;如果此双端队列为空,则返回 null
   public E peekLast() {
       final Node<E> l = last;
       return (l == null) ? null : l.item;
   }

   //获取并移除此双端队列的第一个元素;如果此双端队列为空,则返回 null
   public E pollFirst() {
       final Node<E> f = first;
       return (f == null) ? null : unlinkFirst(f);
   }

   //获取并移除此双端队列的最后一个元素;如果此双端队列为空,则返回 null
   public E pollLast() {
       final Node<E> l = last;
       return (l == null) ? null : unlinkLast(l);
   }

   //将一个元素推入此双端队列所表示的堆栈(换句话说,此双端队列的头部)
   public void push(E e) {
       addFirst(e);
   }

   //从此双端队列所表示的堆栈中弹出一个元素(换句话说,移除并返回此双端队列的头部)
   public E pop() {
       return removeFirst();
   }

   //从此双端队列移除第一次出现的指定元素,如果列表中不包含次元素,则没有任何改变
   public boolean removeFirstOccurrence(Object o) {
       return remove(o);
   }

   //从此双端队列移除最后一次出现的指定元素,如果列表中不包含次元素,则没有任何改变
   public boolean removeLastOccurrence(Object o) {
       //由于LinkedList中允许存放null,因此下面通过两种情况来分别处理
       if (o == null) {
           for (Node<E> x = last; x != null; x = x.prev) { //逆向向前
               if (x.item == null) {
                   unlink(x);
                   return true;
               }
           }
       } else {
           for (Node<E> x = last; x != null; x = x.prev) {
               if (o.equals(x.item)) {
                   unlink(x);
                   return true;
               }
           }
       }
       return false;
   }

LinkedList同样也采用了快速失败的机制,通过记录modCount参数来实现。在面对并发的修改时,迭代器很快就会完全失败,而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

晚安~

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏鸿的学习笔记

用Scala实现一个简单的双向队列

对列表的任何操作不会影响本身的列表,列表一旦创建便不会发生改变,这会使得我们更好的推导数据的变化。作为一门Scalable的语言,Scala允许使用者也可以开发...

7510
来自专栏吾爱乐享

java之学习LinkedList的特有功能及案例分析

13120
来自专栏编程

详解栈及其实现

转自:melonstreet http://www.cnblogs.com/QG-whz/p/5170418.html 栈的特点 栈(Stack)是一种线性存储...

23360
来自专栏ml

C++ 高级语法学习与总结(代码实例)

    C++11增加了许多的特性,auto就是一个很明显的例子。  还有就是typedid()获取数据变量的类型     看下面简短的代码:         ...

35660
来自专栏Java 源码分析

LinkedList 源码分析

LinkedList 源码分析 1. 在阅读源码时做了大量的注释,并且做了一些测试分析源码内的执行流程,由于博客篇幅有限,并且代码阅读起来没有 IDE 方便,...

28340
来自专栏desperate633

LeetCode 20. Valid Parentheses题目分析代码

给定一个字符串所表示的括号序列,包含以下字符: '(', ')', '{', '}', '[' and ']', 判定是否是有效的括号序列。

9020
来自专栏公众号_薛勤的博客

Java过滤掉字符串中的html标签、style标签、script标签

11020
来自专栏Java帮帮-微信公众号-技术文章全总结

Java面试系列13

一、说出一些常用的类,包,接口,请各举5个 常用的类:BufferedReader BufferedWriter FileReader FileWirter ...

28630
来自专栏行者常至

009.多线程-AtomicInteger

版权声明:本文为博主原创文章,允许转载,请标明出处。

8320
来自专栏架构之路

判断栈的出栈顺序合法性

栈的出栈顺序合法性是指给定一系列元素,如1 - N,按照从小到大的方式入栈,每个元素的出栈时机不定。题目给定一个出栈顺序,我们来判断这个出栈顺序有没有可能发生。...

30630

扫码关注云+社区

领取腾讯云代金券