源码阅读之LinkedList(JDK8)

时间:2021-11-06 15:24:38

inkedList概述

 LinkedList是List和Deque接口的双向链表的实现。实现了所有可选列表操作,并允许包括null值
 LinkedList既然是通过双向链表去实现的,那么它可以被当作堆栈、队列或双端队列进行操作。并且其顺序访问非常高效,而随机访问效率比较低

 注意,此实现不是同步的。 如果多个线程同时访问一个LinkedList实例,而其中至少一个线程从结构上修改了列表,那么它必须保持外部同步。这通常是通过同步那些用来封装列表的 对象来实现的。但如果没有这样的对象存在,则该列表需要运用{@link Collections#synchronizedList Collections.synchronizedList}来进行“包装”,该方法最好是在创建列表对象时完成,为了避免对列表进行突发的非同步操作。

List list = Collections.synchronizedList(new LinkedList(...));

  类中的iterator()方法和listIterator()方法返回的iterators迭代器是fail-fast的:当某一个线程A通过iterator去遍历某集合的过程中,若该集合的内容被其他线程所改变了;那么线程A访问集合时,就会抛出ConcurrentModificationException异常,产生fail-fast事件。

LinkedList的源码阅读

  • 底层结构

  源码阅读之LinkedList(JDK8)

  节点Node结构:

    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;
        }
    }

  LinkedList结构:

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
  //LinkedList包含的元素个数 transient
int size = 0; /** * Pointer to first node. 首节点 * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ 首节点和尾节点要么同时为null, 不可能一个为null,一个不为null transient Node<E> first; /** * Pointer to last node. 尾节点 * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node<E> last;
  • 构造函数

LinkedList提供了两种种方式的构造器,构造一个空列表、以及构造一个包含指定collection的元素的列表,这些元素按照该collection的迭代器返回的顺序排列的。

    public LinkedList() {
    }

   // 构造一个包含指定collection的元素的列表,这些元素按照该collection的迭代器返回的顺序排列的
   public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
  • 添加元素

  LinkedList提供了头插入addFirst(E e)、尾插入addLast(E e)、add(E e)、addAll(Collection<? extends E> c)、addAll(int index, Collection<? extends E> c)、add(int index, E element)这些添加元素的方法。

   // 添加
   public boolean add(E e) {
    // 在链表尾部插入 linkLast(e);
return true; }   // 插入 public void add(int index, E element) {
    // 插入范围检查 checkPositionIndex(index);     
if (index == size)
       // 在链表尾部添加 linkLast(element);
else
       // 在链表中间插入 linkBefore(element, node(index)); }   // 头插入 public void addFirst(E e) { linkFirst(e); }   // 尾插入 public void addLast(E e) { linkLast(e); }   

  /**
  * 按照指定collection的迭代器所返回的元素顺序,将该collection中的所有元素添加到此链表的尾部
  * 如果指定的集合添加到链表的尾部的过程中,集合被修改,则该插入过程的后果是不确定的。
  * 一般这种情况发生在指定的集合为该链表的一部分,且其非空。
  * @throws NullPointerException 指定集合为null
  */

    public boolean addAll(Collection<? extends E> c) {

    return addAll(size, c);
    }
    //从指定的位置开始,将指定collection中的所有元素插入到此链表中,新元素的顺序为指定collection的迭代器所返回的元素顺序
    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; //succ指向当前需要插入节点的位置,pred指向其前一个节点
        if (index == size) {//说明在列表尾部插入集合元素
            succ = null;
            pred = last;
        } else {
            succ = node(index); //得到索引index所对应的节点
            pred = succ.prev;
        }
     //指定collection中的所有元素依次插入到此链表中指定位置的过程
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
       //将元素值e,前继节点pred“封装”为一个新节点newNode Node
<E> newNode = new Node<>(pred, e, null); if (pred == null) //如果原链表为null,则新插入的节点作为链表首节点 first = newNode; else pred.next = newNode; pred = newNode; //pred指针向后移动,指向下一个需插入节点位置的前一个节点 }     //集合元素插入完成后,与原链表index位置后面的子链表链接起来 if (succ == null) { //说明之前是在列表尾部插入的集合元素 last = pred; //pred指向的是最后插入的那个节点 } else { pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true; }

 细读上面的代码linkLast,linkBefore,linkFirst,linkLast

    1. linkLast

   // 尾插入,即将节点值为e的节点设置为链表的尾节点
   void linkLast(E e) {
    // 获取当前尾结点引用 final Node
<E> l = last;
    //构建一个prev值为l,节点值为e,next值为null的新节点newNode final Node
<E> newNode = new Node<>(l, e, null);
    //将newNode作为尾节点 last
= newNode;
    //如果原尾节点为null,即原链表为null,则链表首节点也设置为newNode
if (l == null) first = newNode; else  //否则,原尾节点的next设置为newNode l.next = newNode; size++; modCount++; }

   当last==null时, fisrt 和 last 都是同一个node,该弄得的p和n都为null,不指向任何节点

源码阅读之LinkedList(JDK8)

 当last != null时,第一步,构建newNode的时候把newNode的p指向了原先的lastNode,第二步,把newNode复制给lastNode,第三步,把原先的lastNode的n指向newNode

 源码阅读之LinkedList(JDK8)

  2. linkBefore

   //中间插入,在非空节点succ之前插入节点值e
  void linkBefore(E e, Node<E> succ) {     //获取给定结点的上一个结点引用 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
++; }

当succ.pred != null时,开始的数据结构如下:

源码阅读之LinkedList(JDK8)

第一步,新构建一个newNode,把newNode的p指向succ的前一个节点,把newNode的n指向succ。

第二步,将succ节点的p指向 从succ.prev转移到newNode上。

第三步,将succ的前一个节点的n指向 从succ转移到newNode上。

源码阅读之LinkedList(JDK8)

当succ.pred == null时,和上面差不多,只是第三步的时候直接把newNode设置为首节点。

   3. linkFirst

   //头插入,即将节点值为e的节点设置为链表首节点
  private void linkFirst(E e) { final Node<E> f = first;
    //构建一个prev值为null,节点值为e,next值为f的新节点newNode final Node
<E> newNode = new Node<>(null, e, f);
     //将newNode作为首节点 first
= newNode;
     //如果原首节点为null,即原链表为null,则链表尾节点也设置为newNode
if (f == null) last = newNode; else  //否则,原首节点的prev设置为newNode f.prev = newNode; size++; modCount++; }

linkLast

// 尾插入,即将节点值为e的节点设置为链表的尾节点   
void linkLast(E e) {
    // 获取当前尾结点引用 final Node
<E> l = last;
    //构建一个prev值为l,节点值为e,next值为null的新节点newNode final Node
<E> newNode = new Node<>(l, e, null);
    //将newNode作为尾节点 last
= newNode;
     //如果原尾节点为null,即原链表为null,则链表首节点也设置为newNode
if (l == null) first = newNode; else //否则,原尾节点的next设置为newNode l.next = newNode; size++; modCount++; }
  • 删除元素

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

    
  // 删除首结点,返回存储的元素
  public E removeFirst() {
    // 获取首结点引用 final Node
<E> f = first; if (f == null) throw new NoSuchElementException();
    // 删除首结点,返回存储的元素
return unlinkFirst(f); }   // 删除尾结点,返回存储的元素 public E removeLast() {
    // 获取尾结点引用 final Node
<E> l = last; if (l == null) throw new NoSuchElementException();
    // 删除尾结点,返回存储的元素
return unlinkLast(l); }   //删除指定元素,默认从first节点开始,删除第一次出现的那个元素 public boolean remove(Object o) {
    //会根据是否为null分开处理。若值不是null,会用到对象的equals()方法
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 E remove(int index) {
    // 判断指定位置是否合法 checkElementIndex(index);
     // 删除指定位置的结点,返回之前元素
return unlink(node(index)); }   // 删除所有元素 public void clear() {
    //遍历链表,删除所有结点,方便gc回收垃圾
    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;
    // 元素数量置0 size
= 0; modCount++; }

细读remove里面的代码unlink,unlinkFirst,unlinkLast

  1. unlink

// 删除指定非空结点,返回存储的元素
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 {
       // 将前一个节点的next指向指定节点的后一个节点,并把指定节点的prev清空 prev.next
= next; x.prev = null; }      // 如果后一个节点为空,说明指定节点为尾节点,只需将指定节点的前一个节点设置为尾节点即可 if (next == null) { last = prev; } else {
       // 将后一个节点的prev指向指定节点的前一个节点,并把指定节点的next清空 next.prev
= prev; x.next = null; }      // 指定节点的存储元素清空 x.item = null;
     // 元素数量-1 size
--; modCount++; return element; }

初始状态:

源码阅读之LinkedList(JDK8)

第一步,将指定节点的前一个节点的next指向指定节点的后一个节点,然后将指定节点的prev清空。

第二步,将指定节点的后一个接的的prev指向指定节点的前一个节点,然后将指定节点的next清空。

源码阅读之LinkedList(JDK8)

 最后的效果

 源码阅读之LinkedList(JDK8)

 2. unlinkFirst

    
//  删除首结点,返回存储的元素,内部使用
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 // 原来首结点的后一个结点设为首结点
     first = next;
     // 如果首节点的后一个节点为空,说明容器里只有一个节点,所以删除了首节点,容器为空,首节点和尾节点都设置为null
if (next == null) last = null; else // 把新的首节点的prev清空
      next.prev
= null; size--; modCount++; return element; }

3. unlinkLast

    
// 删除尾结点,返回存储的元素,内部使用
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 // 原来尾结点的前一个结点设为尾结点
     last = prev;
     // 如果尾节点的前一个节点为空,则说明容器里只有一个元素,所以删除后,把首节点和尾节点都设置为空
if (prev == null) first = null; else // 把新的尾节点的next清空
       prev.next
= null; size--; modCount++; return element; }
  •  修改元素
    
// 修改指定位置的元素,返回之前元素
public E set(int index, E element) {
    // 判断指定位置是否合法 checkElementIndex(index);
    // 获取指定位置的结点 Node
<E> x = node(index);
     // 获取该结点存储的元素 E oldVal
= x.item;
     // 修改该结点存储的元素 x.item
= element;
    // 返回该结点存储的之前的元素
return oldVal; }
  • 查询元素

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

//返回列表首节点元素值
    public E getFirst() {
        final Node<E> f = first;
        if (f == null)  //如果首节点为null
            throw new NoSuchElementException();
        return f.item;
    }

    //返回列表尾节点元素值
    public E getLast() {
        final Node<E> l = last;
        if (l == null) //如果尾节点为null
            throw new NoSuchElementException();
        return l.item;
    }

    //判断列表中是否包含有元素值o,返回true当列表中至少存在一个元素值e,使得(o==null?e==null:o.equals(e))
    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

    //返回指定索引处的元素值
    public E get(int index) {
        checkElementIndex(index); //index >= 0 && index < size
        return node(index).item;  //node(index)返回指定索引位置index处的节点
    }
//正向查找,返回LinkedList中元素值Object o第一次出现的位置,如果元素不存在,则返回-1
    public int indexOf(Object o) {
        int index = 0;
        //由于LinkedList中允许存放null,因此下面通过两种情况来分别处理
        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;
    }

细看里面的一个node()方法,通过下标定位时先判断是在链表的上半部分还是下半部分,如果是在上半部分就从头开始找起,如果是下半部分就从尾开始找起,因此通过下标的查找和修改操作的时间复杂度是O(n/2)。

    //返回指定索引位置的节点
    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 {  //当index >= size/2时,从列表尾节点向前查找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
  • Fail-Fast机制

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

  • 遍历方式

LinkedList不提倡运用随机访问的方式进行元素遍历。

1)通过迭代器Iterator遍历:

    Iterator iter = list.iterator();
    while (iter.hasNext())
    {
        System.out.println(iter.next());
    }            

2)通过迭代器ListIterator遍历:

  ListIterator<String> lIter = list.listIterator();
  //顺向遍历
  while(lIter.hasNext()){
      System.out.println(lIter.next());
  }
  //逆向遍历
  while(lIter.hasPrevious()){
      System.out.println(lIter.previous());
  }

3)foreach循环遍历

    for(String str:list)
    {
        System.out.println(str);
    }