Collection 集合源码剖析（下）-阿里云开发者社区

LinkedList源码剖析

LinkedList res = new LinkedList<>();

LinkedList同时实现了List接口和Deque接口，所以说我们既可以将其视为一个容器，又可以将其视为一个队列乃至栈

LinkedList底层通过双向链表实现

LinkedList通过first和last引用分别指向链表的第一个和最后一个元素。注意这里没有所谓的哑元，当链表为空的时候first和last都指向null。

LinkedList它的内部定义了一个私有的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;
    }
}

三个构造器

transient是Java语言的关键字，用来表示一个成员变量不是该对象序列化的一部分

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);
}
/**
 * Links e as first element.
 */
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}
/**
 * Links e as last element.
 */
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

getFirst() 获取第一个元素

只要对LinkedList一设置值，那么last 和first就会被赋值

/**
    * Returns the first element in this list.
    *
    * @return the first element in this list
    * @throws NoSuchElementException if this list is empty
    */
   public E getFirst() {
       final Node<E> f = first;
       if (f == null)
           throw new NoSuchElementException();
       return f.item;
   }

getLast() 获取最后一个元素:

/**
   * Returns the last element in this list.
   *
   * @return the last element in this list
   * @throws NoSuchElementException if this list is empty
   */
  public E getLast() {
      final Node<E> l = last;
      if (l == null)
          throw new NoSuchElementException();
      return l.item;
  }

删除元素（如下）

removeFirst(), removeLast(), remove(e), remove(index)

从源码中我们可以得出,如果需要删除某个节点，那么就将这个节点传入，或者传入该节点的索引

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;
   }
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; // GC
       size--;
       modCount++;
       return element;
   }

对于removeFirst 和 removeLast

public E removeFirst() {
       final Node<E> f = first;
       if (f == null)
           throw new NoSuchElementException();
       return unlinkFirst(f);
   }
   /**
    * Unlinks non-null first node 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
       first = next;
       if (next == null)
           last = null;
       else
           next.prev = null;
       size--;
       modCount++;
       return element;
   }

public E removeLast() {
       final Node<E> l = last;
       if (l == null)
           throw new NoSuchElementException();
       return unlinkLast(l);
   }
   /**
    * Unlinks non-null last node l.
    */
   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
           prev.next = null;
       size--;
       modCount++;
       return element;
   }

add方法

对于Add方法，官网给出了两类添加的方法，一种是直接添加到链表的末尾。还有一种是插入链表。

public boolean add(E e) {
       linkLast(e);
       return true;
   }
   /**
    * Links e as last element.
    */
   void linkLast(E e) {
       final Node<E> l = last;
       final Node<E> newNode = new Node<>(l, e, null);
       last = newNode;
       if (l == null)
           first = newNode;
       else
           l.next = newNode;
       size++;
       modCount++;
   }

public void add(int index, E element) {
    //先检查索引位置是否越界
        checkPositionIndex(index);
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
  void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        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++;
    }

addAll()

同样，addAll也是有两种构造器，第一个是将另一个集合全部添加到链表的末尾，另一个是将另一个集合添加到指定的位置

public boolean addAll(Collection<? extends E> c) {
       return addAll(size, c);
   }
   /**
    * Inserts all of the elements in the specified collection into this
    * list, starting at the specified position.  Shifts the element
    * currently at that position (if any) and any subsequent elements to
    * the right (increases their indices).  The new elements will appear
    * in the list in the order that they are returned by the
    * specified collection's iterator.
    *
    * @param index index at which to insert the first element
    *              from the specified collection
    * @param c collection containing elements to be added to this list
    * @return {@code true} if this list changed as a result of the call
    * @throws IndexOutOfBoundsException {@inheritDoc}
    * @throws NullPointerException if the specified collection is null
    */
   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;
       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);
           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;
   }

Set方法

对于set方法，就像源码中提及的那样，如果判断索引位置数组下标没有越界，那么就直接赋值即可

/**
  * Replaces the element at the specified position in this list with the
  * specified element.
  *
  * @param index index of the element to replace
  * @param element element to be stored at the specified position
  * @return the element previously at the specified position
  * @throws IndexOutOfBoundsException {@inheritDoc}
  */
 public E set(int index, E element) {
     checkElementIndex(index);
     Node<E> x = node(index);
     E oldVal = x.item;
     x.item = element;
     return oldVal;
 }

get方法

获取数据索引位置数据，检查是否越界。如果没有，然后返回即可

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

Clear()

/**
 * Removes all of the elements from this list.
 * The list will be empty after this call returns.
 */
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++;
}

查看元素（indexOf / lastIndexOf）

和ArrayList集合一样，indexOf作用就是为了返回元素首次出现的位置

而lastIndexOf就是返回元素最后出现的位置

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;
}
/**
 * Returns the index of the last occurrence of the specified element
 * in this list, or -1 if this list does not contain the element.
 * More formally, returns the highest index {@code i} such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
 * or -1 if there is no such index.
 *
 * @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;
}
Queue<Integer> queue = new LinkedList<>();

使用接口对象名 = new 类名; 方式实例化的对象只能调用接口中有的方法，而不能调用类中特有的方法。

而使用类名对象名 = new 类名;方式创建出来的对象可以调用所有的方法

对于LinkedList() 它同样可以实现队列

方法有

peek() —– 返回队列的头部
element() —–返回队列的头部【此方法与 peek 的不同之处仅在于，如果此队列为空，它会抛出异常。】
poll() ——出列
offer() —– 入列【使用容量受限队列时，此方法通常更可取， add后者只能通过引发异常来插入元素。】
add() ——入列
remove() —– 删除队列的头部

public E peek() { 
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}
/**
 * Retrieves, but does not remove, the head (first element) of this list.
 *
 * @return the head of this list
 * @throws NoSuchElementException if this list is empty
 * @since 1.5
 检索但不删除此队列的头部。 此方法与 peek 的不同之处仅在于，如果此队列为空，它会抛出异常。
 */
public E element() {
    return getFirst();
}
/**
 * Retrieves and removes the head (first element) of this list.
 *
 * @return the head of this list, or {@code null} if this list is empty
 * @since 1.5
 */
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
/**
 * Retrieves and removes the head (first element) of this list.
 *
 * @return the head of this list
 * @throws NoSuchElementException if this list is empty
 * @since 1.5
 检索并删除此队列的头部，如果此队列为空，则返回 null 。
返回值:
此队列的头部，或者 null 如果此队列为空
 */
public E remove() {
    return removeFirst();
}
/**
 * Adds the specified element as the tail (last element) of this list.
 *
 * @param e the element to add
 * @return {@code true} (as specified by {@link Queue#offer})
 * @since 1.5
 */
public boolean offer(E e) {
    return add(e);
}

Deque双端队列

它在queue的基础上又增加了特殊情况，也就是返回值

此接口定义访问双端元素的方法。提供了插入、删除和检查元素的方法。这些方法中的每一个都以两种形式存在：一种在操作失败时引发异常，另一种返回特殊值（ null 或 false，具体取决于操作）。后一种形式的插入操作专门设计用于容量受限 Deque 的实现;在大多数实现中，插入操作不会失败。

详见源码

/**
    * Inserts the specified element at the front of this list.
    *
    * @param e the element to insert
    * @return {@code true} (as specified by {@link Deque#offerFirst})
    * @since 1.6
    */
   public boolean offerFirst(E e) {
       addFirst(e);
       return true;
   }
   /**
    * Inserts the specified element at the end of this list.
    *
    * @param e the element to insert
    * @return {@code true} (as specified by {@link Deque#offerLast})
    * @since 1.6
    */
   public boolean offerLast(E e) {
       addLast(e);
       return true;
   }
   /**
    * Retrieves, but does not remove, the first element of this list,
    * or returns {@code null} if this list is empty.
    *
    * @return the first element of this list, or {@code null}
    *         if this list is empty
    * @since 1.6
    */
   public E peekFirst() {
       final Node<E> f = first;
       return (f == null) ? null : f.item;
    }
   /**
    * Retrieves, but does not remove, the last element of this list,
    * or returns {@code null} if this list is empty.
    *
    * @return the last element of this list, or {@code null}
    *         if this list is empty
    * @since 1.6
    */
   public E peekLast() {
       final Node<E> l = last;
       return (l == null) ? null : l.item;
   }
   /**
    * Retrieves and removes the first element of this list,
    * or returns {@code null} if this list is empty.
    *
    * @return the first element of this list, or {@code null} if
    *     this list is empty
    * @since 1.6
    */
   public E pollFirst() {
       final Node<E> f = first;
       return (f == null) ? null : unlinkFirst(f);
   }
   /**
    * Retrieves and removes the last element of this list,
    * or returns {@code null} if this list is empty.
    *
    * @return the last element of this list, or {@code null} if
    *     this list is empty
    * @since 1.6
    */
   public E pollLast() {
       final Node<E> l = last;
       return (l == null) ? null : unlinkLast(l);
   }
   /**
    * Pushes an element onto the stack represented by this list.  In other
    * words, inserts the element at the front of this list.
    *
    * <p>This method is equivalent to {@link #addFirst}.
    *
    * @param e the element to push
    * @since 1.6
    */
   public void push(E e) {
       addFirst(e);
   }
   /**
    * Pops an element from the stack represented by this list.  In other
    * words, removes and returns the first element of this list.
    *
    * <p>This method is equivalent to {@link #removeFirst()}.
    *
    * @return the element at the front of this list (which is the top
    *         of the stack represented by this list)
    * @throws NoSuchElementException if this list is empty
    * @since 1.6
    */
   public E pop() {
       return removeFirst();
   }
   /**
    * Removes the first occurrence of the specified element in this
    * list (when traversing the list from head to tail).  If the list
    * does not contain the element, it is unchanged.
    *
    * @param o element to be removed from this list, if present
    * @return {@code true} if the list contained the specified element
    * @since 1.6
    */
   public boolean removeFirstOccurrence(Object o) {
       return remove(o);
   }
   /**
    * Removes the last occurrence of the specified element in this
    * list (when traversing the list from head to tail).  If the list
    * does not contain the element, it is unchanged.
    *
    * @param o element to be removed from this list, if present
    * @return {@code true} if the list contained the specified element
    * @since 1.6
    */
   public boolean removeLastOccurrence(Object o) {
       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;

参考来源: https://pdai.tech/md/java/collection/java-collection-Queue&Stack.html

Collection 集合源码剖析（下）