截屏2021-07-05 下午5.00.26.png

  1. public class LinkedList<E>
  2.     extends AbstractSequentialList<E>
  3.     implements List<E>, Deque<E>, Cloneable, java.io.Serializable {}

继承于 AbstractSequentialList ，本质上面与继承 AbstractList 没有什么区别，AbstractSequentialList 完善了 AbstractList 中没有实现的方法。
接口

  • Serializable：成员变量 Node 使用 transient 修饰，通过重写read/writeObject 方法实现序列化。
  • Cloneable：重写clone（）方法，通过创建新的LinkedList 对象，遍历拷贝数据进行对象拷贝。
  • Deque：实现了Collection 大家庭中的队列接口，说明他拥有作为双端队列的功能。

    1. 成员变量

    没有MAX_ARRAY_SIZE限制，是由于链表没有长度限制的原因。 ```java // 节点个数 transient int size = 0;

// 头结点 transient Node first;

// 尾结点 transient Node last;

  1. <a name="aXs65"></a>
  2. ## 2.内部类
  3. ```java
  4.     private static class Node<E> {
  5.         E item;
  6.         Node<E> next;
  7.         Node<E> prev;
  9.         // 构造方法，参数：前一个节点、元素值、后一个节点
  10.         Node(Node<E> prev, E element, Node<E> next) {
  11.                // 节点赋值
  12.             this.item = element;
  13.             // 连接下一个
  14.             this.next = next;
  15.             // 连接上一个
  16.             this.prev = prev;
  17.         }
  18.     }

节点有头尾指针，说明是个双向链表。LinkedList1.6版本及以前，只通过一个header头指针保存队列头和尾。之后头尾节点分开了，节点更名为Node。

2.构造方法

  1.      public LinkedList() {
  2.     }
  4.     public LinkedList(Collection<? extends E> c) {
  5.         this();
  6.         addAll(c);
  7.     }

3.方法

特有的方法主要是针对头尾进行操作。注意对节点下标的记录也是从0开始的。

3.1 添加方法

继承于AbstractList的方法

  • boolean add(E e)[AbstractList方法]：在尾部添加节点。底层调用了linkLast方法，有返回值true
  • boolean addAll(Collection<? extends E> c)[AbstractList方法]：在尾部添加集合节点。底层调用了addAll(index, c)方法。

继承于AbstractSequentialList的方法

  • void add(int index，E e)[AbstractSequentialList方法]：在指定位置添加节点。没有返回值
  • boolean addAll(int index, Collection<? extends E> c)[AbstractSequentialList方法]：在指定位置添加集合节点

实现接口Deque的方法：

  • void addFirst(E e)[Deque方法]：在头部添加节点。底层调用了linkFirst方法，没有返回值
  • void addLast(E e)[Deque方法]：在尾部添加节点。底层调用了linkLast方法，没有返回值
  • boolean offer(E e) [Deque方法]：底层调用的add(E e)方法，有返回值true。1.5
  • boolean offerFirst(E e)[Deque方法]：底层调用了addFirst方法，有返回值true。 1.6
  • boolean offerLast(E e)[Deque方法]：底层调用了addLast方法，有返回值true。1.6

源码：

  • add与addLast与offer与offerLast ```java public boolean add(E e) {

    1.   linkLast(e);
    2.   return true;

    }

    public void addLast(E e) {

    1.   linkLast(e);

    }

    public boolean offer(E e) {

    1.   return add(e);

    }

    public boolean offerLast(E e) {

    1.   addLast(e);
    2.   return true;

    }

  1. void linkLast(E e) {
  2.     // final修饰，不允许修改
  3.     final Node<E> l = last;  // 将尾结点赋给l
  4.     final Node<E> newNode = new Node<>(l, e, null); // 给newNode赋值，前驱指针指向l，后继指针指向null
  5.     last = newNode; // 移动尾指针
  6.     // 完善指针指向
  7.     if (l == null)
  8.         first = newNode; // 如果尾指针是空的，该节点是第一个节点，赋头指针
  9.     else
  10.         l.next = newNode; // 否则，连接l的next指针
  11.     size++; // 增加个数
  12.     modCount++;
  13. }
  2. - addFirst与offerFirst
  3. ```java
  4.    public void addFirst(E e) {
  5.         linkFirst(e);
  6.     }
  8.     private void linkFirst(E e) {
  9.         // final修饰，不允许修改
  10.         // 将头结点赋给f
  11.         final Node<E> f = first;
  12.         // 定义插入节点，前驱指针指向null，后继指针指向f
  13.         final Node<E> newNode = new Node<>(null, e, f);
  14.         // 移动头指针
  15.         first = newNode; 
  16.         // 完善指针指向
  17.         if (f == null)
  18.             last = newNode; // 如果尾指针是空的，该节点是第一个节点，对尾指针赋值
  19.         else
  20.             f.prev = newNode; // 连接f的pre指针
  21.         size++; // 增加个数
  22.         modCount++;
  23.     }

  • add(index, e): ```java public void add(int index, E element) {

    1.   // 检验index的合法性
    2.   checkPositionIndex(index);
    4.   // 如果是末尾，直接加入到末尾
    5.   if (index == size)
    6.       linkLast(element);
    7.   else
    8.       // 否则，在index处添加节点， node(index)方法找到添加的位置，参见3.2
    9.       linkBefore(element, node(index));

    }

  1. // succ节点是原来在index位置的节点
  2. void linkBefore(E e, Node<E> succ) {
  3.     // assert succ != null;
  4.     // 将succ节点的前驱结点指向pred
  5.     final Node<E> pred = succ.prev;
  6.     // 定义新节点，前驱结点指向pred，后继节点指向succ
  7.     final Node<E> newNode = new Node<>(pred, e, succ);
  8.     // 整理指针
  9.     // 连接succ的前驱指针
  10.     succ.prev = newNode;
  11.     // 如果该位置是第一个位置
  12.     if (pred == null)
  13.         // 赋给头指针
  14.         first = newNode;
  15.     else
  16.         // 否则，连接pred的后继指针
  17.         pred.next = newNode;
  18.     size++;
  19.     modCount++;
  20. }
  1. addAll(index, c)方法：思路同add(index，succ)方法。
  2. ```java
  3.    public boolean addAll(int index, Collection<? extends E> c) {
  4.         checkPositionIndex(index);
  6.         Object[] a = c.toArray();
  7.         int numNew = a.length;
  8.         if (numNew == 0)
  9.             return false;
  11.        //找pred指针，是否是末尾插入。
  12.         Node<E> pred, succ;
  13.         if (index == size) {
  14.             succ = null;
  15.             pred = last;
  16.         } else {
  17.             succ = node(index);
  18.             pred = succ.prev;
  19.         }
  20.         // 一次连接c中的节点
  21.         for (Object o : a) {
  22.             @SuppressWarnings("unchecked") E e = (E) o;
  23.             Node<E> newNode = new Node<>(pred, e, null);
  24.             // 判断是否是第一个位置
  25.             if (pred == null)
  26.                 first = newNode;
  27.             else
  28.                 pred.next = newNode;
  29.             pred = newNode;
  30.         }
  32.        // 如果是在末尾插入，定位尾指针
  33.         if (succ == null) {
  34.             last = pred;
  35.         } else {
  36.             // 否则，将c的尾节点与原队列的succ节点连接
  37.             pred.next = succ;
  38.             succ.prev = pred;
  39.         }
  41.         size += numNew;
  42.         modCount++;
  43.         return true;
  44.     }

3.2 get方法

继承于AbstractSequentialList的方法。
获得指定位置的节点的值

  1.     public E get(int index) {
  2.         // 检验index值是否合法
  3.         checkElementIndex(index);
  4.         return node(index).item;
  5.     }
  7.     // 返回找到的节点
  8.     Node<E> node(int index) {
  9.         // assert isElementIndex(index);
  10.         // 如果在链表的前半段，从前往后找
  11.         if (index < (size >> 1)) {
  12.             Node<E> x = first;
  13.             for (int i = 0; i < index; i++)
  14.                 x = x.next;
  15.             return x;
  16.         } else {
  17.             // 如果在链表的后半段，从后往前找
  18.             Node<E> x = last;
  19.             for (int i = size - 1; i > index; i--)
  20.                 x = x.prev;
  21.             return x;
  22.         }
  23.     }

3.3 修改方法set

继承于AbstractSequentialList的方法。
修改指定位置的节点的值，返回旧值

  1.     public E set(int index, E element) {
  2.         // 检验
  3.         checkElementIndex(index);
  4.         // node方法查找该位置的节点
  5.         Node<E> x = node(index);
  6.         // 更新新值并返回旧值
  7.         E oldVal = x.item;
  8.         x.item = element;
  9.         return oldVal;
  10.     }

3.4 删除方法

继承于AbstractSequentialList的方法：

  • E remove（int index）：根据index删除节点，返回删除节点的值。
  • boolean remove（Object o）：根据值删除节点，返回true/false

实现接口Deque的方法：

  • boolean remove()：删除头结点。底层调用的removeFirst方法。返回true/false。1.5
  • E removeFirst()：删除头结点，返回删除节点的值
  • E removeLast()：删除尾结点，返回删除节点的值。
  • boolean removeFirstOccurrence(Object o)：删除第一次出现的o节点，从头开始遍历。底层调用remove()方法。返回true/false。1.6
  • boolean removeLastOccurrence(Object o)：删除最后一次出现的o节点，从尾开始遍历。返回true/false。1.6

remove（int index）方法
定义前后节点，分别断前后指针（判断是否是头尾节点），清空值，个数-1，modCount++，返回删除节点的值

  1.     public E remove(int index) {
  2.         checkElementIndex(index);
  3.         // node方法找到index对应的节点
  4.         return unlink(node(index));
  5.     }
  7.     E unlink(Node<E> x) {
  8.         // assert x != null;
  9.         final E element = x.item;
  10.         // x的后继结点赋给next
  11.         final Node<E> next = x.next;
  12.         // x的前驱结点赋给prev
  13.         final Node<E> prev = x.prev;
  14.         // 如果prev是null，说明该节点是第一个节点
  15.         if (prev == null) {
  16.             // 头结点后移
  17.             first = next;
  18.         } else {
  19.             // 否则不是头结点，修改prev的next指针指向next节点
  20.             prev.next = next;
  21.             // x的prev指针置null
  22.             x.prev = null;
  23.         }
  25.         // 如果要删除的节点是尾结点
  26.         if (next == null) {
  27.             // 尾结点前移
  28.             last = prev;
  29.         } else {
  30.             // 否则不是尾结点，修改next的prev指针指向prev节点
  31.             next.prev = prev;
  32.             // x的next指针置为null
  33.             x.next = null;
  34.         }
  36.         // 清空x的值
  37.         x.item = null;
  38.         //个数-1
  39.         size--;
  40.         modCount++;
  41.         // 返回删除节点的值
  42.         return element;
  43.     }
  • remove（Object o）与removeFirstOccurrence(o)方法 ```java public boolean remove(Object o) {
    1.   // 遍历，调用unlink释放，如果不存在，返回false。从前往后找
    2.   if (o == null) {
    3.       for (Node<E> x = first; x != null; x = x.next) {
    4.           if (x.item == null) {
    5.               unlink(x);
    6.               return true;
    7.           }
    8.       }
    9.   } else {
    10.       for (Node<E> x = first; x != null; x = x.next) {
    11.           if (o.equals(x.item)) {
    12.               unlink(x);
    13.               return true;
    14.           }
    15.       }
    16.   }
    17.   return false;
    }
  1. remove与removeFirst方法
  2. ```java
  3.     public E remove() {
  4.         return removeFirst();
  5.     }
  7.     public E removeFirst() {
  8.         // 链表判空
  9.         final Node<E> f = first;
  10.         // 如果为null，抛出异常
  11.         if (f == null)
  12.             throw new NoSuchElementException();
  13.         return unlinkFirst(f);
  14.     }    
  16.     // 知道自己是头结点了。f就是要删的头结点
  17.     private E unlinkFirst(Node<E> f) {
  18.         // assert f == first && f != null;
  19.         final E element = f.item;
  20.         // f的下一个节点为头结点
  21.         final Node<E> next = f.next;
  22.         f.item = null;
  23.         // 断f的next指针
  24.         f.next = null; // help GC
  25.         first = next;
  26.         // 如果next是null，说明链表就一个头结点被删了
  27.         if (next == null)
  28.             // 尾结点置空
  29.             last = null;
  30.         else
  31.             // 断next的头指针，next就是新头节点
  32.             next.prev = null;
  33.         // 个数减1
  34.         size--;
  35.         modCount++;
  36.         // 返回删除的节点值
  37.         return element;
  38.     }

removeLast方法

  1.      public E removeLast() {
  2.         final Node<E> l = last;
  3.         if (l == null)
  4.             throw new NoSuchElementException();
  5.         return unlinkLast(l);
  6.     }
  8.     // 知道自己是尾结点，删除尾结点l
  9.     private E unlinkLast(Node<E> l) {
  10.         // assert l == last && l != null;
  11.         final E element = l.item;
  12.         // l的上一个节点就是新的尾结点
  13.         final Node<E> prev = l.prev;
  14.         l.item = null;
  15.         // 断l的prev指针
  16.         l.prev = null; // help GC
  17.         last = prev;
  18.         // 如果prev为空，就一个尾节点被删了，
  19.         if (prev == null)
  20.             // 头结点置null
  21.             first = null;
  22.         else
  23.             // 否则断prev的next指针，prev就是新的尾结点
  24.             prev.next = null;
  25.         size--;
  26.         modCount++;
  27.         // 返回删除的节点值
  28.         return element;
  29.     }

removeLastOccurrence（o）方法

  1.     public boolean removeLastOccurrence(Object o) {
  2.         // 从后往前遍历，调用unlink方法删除o，如果不存在，返回false
  3.         if (o == null) {
  4.             for (Node<E> x = last; x != null; x = x.prev) {
  5.                 if (x.item == null) {
  6.                     unlink(x);
  7.                     return true;
  8.                 }
  9.             }
  10.         } else {
  11.             for (Node<E> x = last; x != null; x = x.prev) {
  12.                 if (o.equals(x.item)) {
  13.                     unlink(x);
  14.                     return true;
  15.                 }
  16.             }
  17.         }
  18.         return false;
  19.     }

细节

  2.      private void checkElementIndex(int index) {
  3.         if (!isElementIndex(index))
  4.             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  5.     }
  7.     private void checkPositionIndex(int index) {
  8.         if (!isPositionIndex(index))
  9.             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  10.     }
  13.     /**
  14.      * Tells if the argument is the index of an existing element.
  15.      * remove方法
  16.      */
  17.     private boolean isElementIndex(int index) {
  18.         return index >= 0 && index < size;
  19.     }
  21.     /**
  22.      * Tells if the argument is the index of a valid position for an
  23.      * iterator or an add operation.
  24.      * add方法
  25.      */
  26.     private boolean isPositionIndex(int index) {
  27.         return index >= 0 && index <= size;
  28.     }

3.5 双端链表方法

实现Deque接口的方法：

  • 添加：(参见3.1)
    • boolean offer(E e) 1.5
    • boolean offerFirst(E e) 1.6
    • boolean offerLast(E e) 1.6
    • void push(E e) ：在头部加入节点，底层调用的addFirst(e)方法。 1.6。
  • 删除：
    • E poll():检索并删除头结点，底层与pollFirst方法相同 1.5
    • E pollFirst():检索并删除头结点 1.6
    • E pollLast():检索并删除尾结点 1.6
    • E pop():检索并删除头结点，如果为null抛出异常，底层调用removeFirst() 1.6
  • 查找：
    • E peek()：返回头结点的值，如果为空返回null。1.5
    • E peekFirst(): 返回头结点的值，如果为空返回null。1.6
    • E peekLast(): 返回尾结点的值，如果为空返回null。1.6

poll
全部都是判空然后调用，如果为null返回null，不会抛出异常（remove和pop方法返回异常）。

  1.     public E poll() {
  2.         final Node<E> f = first;
  3.         return (f == null) ? null : unlinkFirst(f);
  4.     }
  6.     public E pollFirst() {
  7.         final Node<E> f = first;
  8.         return (f == null) ? null : unlinkFirst(f);
  9.     }
  11.    public E pollLast() {
  12.         final Node<E> l = last;
  13.         return (l == null) ? null : unlinkLast(l);
  14.     }

pop

  1.    public E pop() {
  2.         return removeFirst();
  3.     }

push

  1.     public void push(E e) {
  2.         addFirst(e);
  3.     }

peek

  1.     public E peek() {
  2.         final Node<E> f = first;
  3.         return (f == null) ? null : f.item;
  4.     }
  6.     public E peekFirst() {
  7.         final Node<E> f = first;
  8.         return (f == null) ? null : f.item;
  9.     }
  11.     public E peekLast() {
  12.         final Node<E> l = last;
  13.         return (l == null) ? null : l.item;
  14.     }