关于源码分析:LnkedList源码

LinkedList 继承自 AbstrackSequentialList 并实现了 List 接口以及 Deque 双向队列接口，因而 LinkedList 岂但领有 List 相干的操作方法，也有队列的相干操作方法。
LinkedList 和 ArrayList 一样实现了序列化接口 Serializable 和 Cloneable 接口使其领有了序列化和克隆的个性。
继承了 AbstractSequentialList 抽象类，在遍历的时候，举荐应用迭代器进行遍历。

然而只反对浅克隆，在 LinkedList 类中，其中的外部类 Node 并没有被克隆，只是调用了 Object 类中的 clone 办法进行可克隆。

外围组成：用来存储数据的结点，在 LinkedList 中设计成了外部类。

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 次要成员变量有下边三个：

//LinkedList 中的节点个数
transient int size = 0;

//LinkedList 链表的第一个节点
transient Node<E> first;

//LinkedList 链表的最初一个节点
transient Node<E> last;

LinkedList 的构造方法只提供了两个：

/**
 * 空参数的结构因为生成一个空链表 first = last = null
 */
 public LinkedList() {}

/**
 * 传入一个汇合类，来结构一个具备肯定元素的 LinkedList 汇合
 * @param  c  其外部的元素将按程序作为 LinkedList 节点
 * @throws NullPointerException 如果 参数 collection 为空将抛出空指针异样
 */
public LinkedList(Collection<? extends E> c) {this();
   addAll(c);
}

带参数的构造方法，调用 addAll(c) 这个办法，

public boolean addAll(Collection<? extends E> c) {return addAll(size, c);
}

实际上这办法调用了 addAll(size, c) 办法，

/**
 * 在 index 节点前插入蕴含所有 c 汇合元素的节点。* 返回值示意是否胜利增加了对应的元素.
 */
public boolean addAll(int index, Collection<? extends E> c) {
   // 查看索引是否满足 0 =< index =< size 的要求
   checkPositionIndex(index);
    // 调用对应 Collection 实现类的 toArray 办法将汇合转为数组
   Object[] a = c.toArray();
   // 查看数组长度，如果为 0 则间接返回 false 示意没有增加任何元素
   int numNew = a.length;
   if (numNew == 0)
       return false;
   // 保留 index 以后的节点为 succ，以后节点的上一个节点为 pred
   Node<E> pred, succ;
   // 如果 index = size 示意在链表尾部插入
   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);
       // 如果 pred 为空示意 LinkedList 汇合中还没有元素
       // 生成的第一个节点将作为头节点 赋值给 first 成员变量
       if (pred == null)
           first = newNode;
       else
           pred.next = newNode;
       pred = newNode;
   }
   // 如果 index 地位的元素为 null 则遍历数组后 pred 所指向的节点即为新链表的末节点，赋值给 last 成员变量
   if (succ == null) {last = pred;} else {
       // 否则将 pred 的 next 索引指向 succ，succ 的 prev 索引指向 pred
       pred.next = succ;
       succ.prev = pred;
   }
   // 更新以后链表的长度 size 并返回 true 示意增加胜利
   size += numNew;
   //fast-fail
   modCount++;
   return true;
}

addAll(c)在内部独自调用时，将指定汇合的元素作为节点，增加到 LinkedList 链表尾部。

而 addAll(size, c) 能够将汇合元素插入到指定索引节点。

对于 checkPositionIndex办法这里想顺带剖析了，

LinkedList 中有两个办法用于查看角标越界，外部实现一样。

    private boolean isElementIndex(int index) {return index >= 0 && index < size;}



    private boolean isPositionIndex(int index) {return index >= 0 && index <= size;}

都是通过 index >= 0 && index <= size 判断。

LinkedList 能够不便的在头尾插入一个节点，而 add 办法默认在链表尾部增加节点：


 public void addFirst(E e) {linkFirst(e);
 }


 public void addLast(E e) {linkLast(e);
 }
    

 public boolean add(E e) {linkLast(e);
    return true;
 }





/**
 * 在指定 index 地位插入节点
 */
public void add(int index, E element) {
   // 查看角标是否越界
   checkPositionIndex(index);
   // 如果 index = size 代表是在尾部插入节点
   if (index == size)
       linkLast(element);
   else
       linkBefore(element, node(index));
}

能够看到默认是“尾插”，有返回值。

咱们能够看到 add 办法是有返回值的，这个能够留神下。

看来这一系办法都调用用了 linkXXX 办法。

 /**
  * 增加一个元素在链表的头节点地位
  */
private void linkFirst(E e) {
   // 增加元素之前的头节点
   final Node<E> f = first;
   // 以增加的元素为节点值构建新的头节点 并将 next 指针指向 之前的头节点
   final Node<E> newNode = new Node<>(null, e, f);
   // first 索引指向将新的节点
   first = newNode;
   // 如果增加之前链表空则新的节点也作为未节点
   if (f == null)
       last = newNode;
   else
       f.prev = newNode;// 否则之前头节点的 prev 指针指向新节点
   size++;
   modCount++;// 操作数 ++
}

/**
 * 在链表开端增加一个节点
 */
 void linkLast(E e) {
   final Node<E> l = last;// 保留之前的未节点
   // 构建新的未节点，并将新节点 prev 指针指向 之前的未节点
   final Node<E> newNode = new Node<>(l, e, null);
   //last 索引指向末节点
   last = newNode;
   if (l == null)// 如果之前链表为空则新节点也作为头节点
       first = newNode;
   else// 否则将之前的未节点的 next 指针指向新节点
       l.next = newNode;
   size++;
   modCount++;// 操作数 ++
}


/**
 * 返回一个非空节点，这个非空节点位于 index 地位
 */
 Node<E> node(int index) {// assert isElementIndex(index);
    // 如果 index < size/2 则从 0 开始寻找指定角标的节点
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
         // 如果 index >= size/2 则从 size-1 开始寻找指定角标的节点
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
 }

void linkBefore(E e, Node<E> succ) {
   // assert succ != null;
   // 因为 succ 肯定不为空，所以能够间接获取 prev 节点
   final Node<E> pred = succ.prev;
   // 新节点 prev 节点为 pred，next 节点为 succ
   final Node<E> newNode = new Node<>(pred, e, succ);
   // 原节点的 prev 指向新节点
   succ.prev = newNode;
   // 如果 pred 为空即头节点出插入了一个节点，则将新的节点赋值给 first 索引
   if (pred == null)
       first = newNode;
   else
       pred.next = newNode;// 否则 pred 的下一个节点改为新节点
   size++;
   modCount++;
}

/**
 *  删除头节点
 * @return 删除的节点的值 即 节点的 element
 * @throws NoSuchElementException 如果链表为空则抛出异样
 */
 public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
 }

/**
 *  删除尾节点
 *
 * @return  删除的节点的值 即 节点的 element
 * @throws NoSuchElementException  如果链表为空则抛出异样
 */
 public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
 }
 


/**
 * 删除指定索引地位的节点
 */
public E remove(int index) {checkElementIndex(index);
   return unlink(node(index));
}

/**
 * 删除从头节点其第一个与 o 雷同的节点
 */
public boolean remove(Object o) {
    // 区别对待 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;
}

/**
 * 移除头节点
 */
 private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    // 头节点的 element 这里作为返回值应用
    final E element = f.item;
    // 头节点下个节点
    final Node<E> next = f.next;
    // 开释头节点的 next 指针，和 element 下次 gc 的时候回收这个外部类
    f.item = null;
    f.next = null; // help GC
    // 将 first 索引指向新的节点
    first = next;
    // 如果 next 节点为空，即链表只有一个节点的时候，last 指向 null
    if (next == null)
        last = null;
    else
        next.prev = null; // 否则 next 的 prev 指针指向 null
    size--;// 扭转链表长度
    modCount++;// 批改操作数
    return element;// 返回删除节点的值
 }

/**
 * 移除未节点
 */
 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 索引指向新的未节点
    last = prev;
    // 链表只有一个节点的时候，first 指向 null
    if (prev == null)
       first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
 }

对于 unlink 的代码示意图：

/**
 * Unlinks non-null node x.
 */
E unlink(Node<E> x) {
   // assert x != null;
   final E element = x.item;
   // 保留 index 节点的前后两个节点
   final Node<E> next = x.next;
   final Node<E> prev = x.prev;
    // 如果节点为头节点，则做 unlinkFirst 雷同操作
   if (prev == null) {first = next;} else {// 否则将上一个节点的 next 指针指向下个节点
       prev.next = next;
       // 开释 index 地位 prev 指针
       x.prev = null;
   }
    // 如果节点为尾节点，则将 last 索引指向上个节点
   if (next == null) {last = prev;} else {// 否则下个节点 prev 指针指向上个节点
       next.prev = prev;
       x.next = null;
   }

   x.item = null;
   size--;
   modCount++;
   return element;
}

/**
* Removes all of the elements from this list.
* The list will be empty after this call returns.
*/
public void clear() {
   // 顺次革除节点，帮忙开释内存空间
   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++;
}

LinkedList 查问节点的办法，可分为依据指定的索引查问，获取头节点，获取未节点三种。

值得注意的是，依据索引去获取节点内容的效率并不高，所以如果查问操作多余增删操作的时候倡议用 ArrayList 去代替。

/**
* 依据索引查问
*
public E get(int index) {checkElementIndex(index);
   return node(index).item;
}

/**
* 返回 first 索引指向的节点的内容
*
* @return the first element in this list
* @throws NoSuchElementException 如果链表为空则抛出异样
*/
public E getFirst() {
   final Node<E> f = first;
   if (f == null)
       throw new NoSuchElementException();
   return f.item;
}

/**
* 返回 last 索引指向的节点的内容
*
* @return the last element in this list
* @throws NoSuchElementException 如果链表为空则抛出异样
*/
public E getLast() {
   final Node<E> l = last;
   if (l == null)
       throw new NoSuchElementException();
   return l.item;
}

LinkedList 只提供了 set(int index, E element) 一个办法

public E set(int index, E element) {
   // 判断角标是否越界
   checkElementIndex(index);
   // 采纳 node 办法查找对应索引的节点
   Node<E> x = node(index);
   // 保留节点原有的内容值
   E oldVal = x.item;
   // 设置新值
   x.item = element;
   // 返回旧的值
   return oldVal;
}

/* 
* 返回参数元素在链表的节点索引，如果有反复元素，那么返回值为从头节点起的第一雷同的元素节点索引，* 如果没有值为该元素的节点，则返回 -1；* 
* @param o element to search for
* @return 
*/
public int indexOf(Object o) {
   int index = 0;
  // 区别对待 null 元素，用 == 判断，非空元素用 equels 办法判断 
   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;
}

/**
** 返回参数元素在链表的节点索引，如果有反复元素，那么返回值为从尾节点起的第一雷同的元素节点索引，* 如果没有值为该元素的节点，则返回 -1；*
* @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;
}

调用 indexOf 从头结点开始查问元素地位遍历实现后若返回值 !=-1 则示意存在，反之不存在

public boolean contains(Object o) {return indexOf(o) != -1;
}

Deque 这个双端队列就厉害了, 它既能够实现栈的操作，也能够实现队列的操作，换句话说，实现了这个接口的类，既能够作为栈应用也能够作为队列应用。

咱们来看下 Queue 给咱们提供了的办法：

	头部	头部	尾部	尾部
插入	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
移除	removeFirst()	pollFirst()	remveLast()	pollLast
获取	getFirst()	peekFirst()	getLast()	peekLast

因为 Deque 接口继承 Queue 接口，当 Deque 当做队列应用时（FIFO），只须要在头部删除，尾部增加即可。咱们当初温习下 Queue 中的办法及区别：

Queue 的 offer 和 add 都是在队列中插入一个元素，具体区别在于，对于一些 Queue 的实现的队列是有大小限度的，因而如果想在一个满的队列中退出一个新项，多出的项就会被回绝。此时调用 add()办法会抛出异样，而 offer() 只是返回的 false。
remove() 和 poll() 办法都是从队列中删除第一个元素。remove()也将抛出异样，而 poll() 则会返回 null
element() 和 peek() 用于在队列的头部查问元素。在队列为空时，element() 抛出一个异样，而 peek() 返回 null。

// queue 的增加办法实现，public boolean add(E e) {linkLast(e);
   return true;
}
// Deque 的增加办法实现，public void addLast(E e) {linkLast(e);
} 
  
// queue 的增加办法实现，public boolean offer(E e) {return add(e);
}

// Deque 的增加办法实现，public boolean offerLast(E e) {addLast(e);
        return true;
}

很显著 LinkedList 的大小并没有限度，所以在 LinkedList 中他们的实现并没有实质性不同。

// Queue 删除元素的实现 removeFirst 会抛出 NoSuchElement 异样
public E remove() {return removeFirst();
}

// Deque 的删除办法实现
public E removeFirst() {
   final Node<E> f = first;
   if (f == null)
       throw new NoSuchElementException();
   return unlinkFirst(f);
}
    
// Queue 删除元素的实现 不会抛出异样 如果链表为空则返回 null 
public E poll() {
   final Node<E> f = first;
   return (f == null) ? null : unlinkFirst(f);
}

// Deque 删除元素的实现 不会抛出异样 如果链表为空则返回 null 
public E pollFirst() {
   final Node<E> f = first;
   return (f == null) ? null : unlinkFirst(f);
}

 // Queue 获取队列头部的实现 队列为空的时候回抛出异样
 public E element() {return getFirst();
 }
// Deque 获取队列头部的实现 队列为空的时候回抛出异样
public E getFirst() {
   final Node<E> f = first;
   if (f == null)
       throw new NoSuchElementException();
   return f.item;
}

// Queue 获取队列头部的实现 队列为空的时候返回 null
public E peek() {
   final Node<E> f = first;
   return (f == null) ? null : f.item;
}

// Deque 获取队列头部的实现 队列为空的时候返回 null
public E peekFirst() {
   final Node<E> f = first;
   return (f == null) ? null : f.item;
}

https://juejin.cn/post/684490…

关于源码分析:LnkedList源码

概述

LinkedList 双向链表实现及成员变量

构造方法

LinkedList 的增删改查

增加节点

linkXXX

node(int index)

linkBefore(E e, Node<E> succ)

删除节点

remove()

unlink()

clear 操作

查问节点

批改节点

元素查问

LinkedList 作为双向队列的增删改查

增加元素

删除元素

获取元素

参考链接