概述

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

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

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

外围组成：用来存储数据的结点，在 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 的增删改查

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

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

linkXXX

咱们能够看到 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++;// 操作数 ++
}

node(int index)

/**
 * 返回一个非空节点，这个非空节点位于 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;
    }
 }

linkBefore(E e, Node<E> succ)

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

删除节点

remove()

/**
 *  删除头节点
 * @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;
}

unlink()

/**
 * 移除头节点
 */
 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;
}

clear 操作

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

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

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

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

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

1. Queue 的 offer 和 add 都是在队列中插入一个元素，具体区别在于，对于一些 Queue 的实现的队列是有大小限度的，因而如果想在一个满的队列中退出一个新项，多出的项就会被回绝。此时调用 add()办法会抛出异样，而 offer() 只是返回的 false。
2. remove() 和 poll() 办法都是从队列中删除第一个元素。remove()也将抛出异样，而 poll() 则会返回 null
3. 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…