集合源码阅读：LinkedList

╰+攻爆jí腚メ 2023-07-13 05:55 1阅读 0赞

[前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到教程。][Link 1]

# LinkedList -- 增删快。
    
    # 1.继承关系：
    
       public class LinkedList<E>
           extends AbstractSequentialList<E>
           implements List<E>, Deque<E>, Cloneable, java.io.Serializable
            
        
    # 2. 属性：
    
        // 默认容量
        transient int size = 0;
        
        // 首字节
        transient Node<E> first;
    
        // 尾字节
        transient Node<E> last;
     
        
    # 3.方法：
    
       // 无参构造函数
       public LinkedList() {
       }
    
       // 返回包含指定集合元素的构造
       public LinkedList(Collection<? extends E> c) {
           this();
           addAll(c);
       }
    
       // 添加第一个元素
       private void linkFirst(E e) {
           // 定义 f ，赋值为首节点。
           final Node<E> f = first;
           // 定义新节点 newNode ，设置其后一节点为原首节点：f。
           final Node<E> newNode = new Node<>(null, e, f);
           // 把原首节点赋值为新节点：newNode。
           first = newNode;
           if (f == null)
               //　集合中无元素则，则新节点也是最后一节点。
               last = newNode;
           else
           　　// 设置 f 的前一节点为新节点。（final 修饰的变量其引用指针不可改，但其属性可改。）
               f.prev = newNode;
           size++;
           modCount++;
       }
    
       // 添加最后一个元素
       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;
           // 集合元素加1。
           size++;
           // 集合修改次数加1。
           modCount++;
       }
    
       // 在指定的非空节点前添加元素
       void linkBefore(E e, Node<E> succ) {
           // succ 不为空。定义 pred ，赋值为 succ 的前一节点。
           final Node<E> pred = succ.prev;
           // 定义新节点 newNode，前一节点为：pred，后一节点为 succ。
           final Node<E> newNode = new Node<>(pred, e, succ);
           // 设置 succ 前一节点为 newNode 。
           succ.prev = newNode;
           if (pred == null)
               first = newNode;
           else
               // 设置 pred 的后一节点为新节点：newNode。
               pred.next = newNode;
           size++;
           modCount++;
       }
    
       // 删除第一个节点
       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;
       }
    
       // 删除最后一个节点
       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;
       }
    
       // 删除非空节点
       E unlink(Node<E> x) {
           // assert x != null;
           // 把要删除的元素 x 赋值给 element，用于返回。
           final E element = x.item;
           // 定义 next，赋值为ｘ的后一节点。
           final Node<E> next = x.next;
           // 定义 prev，赋值为 x 的前一节点。
           final Node<E> prev = x.prev;
           // 无前节点，则 x 的后一节点为首节点。
           if (prev == null) {
               first = next;
           } else {
               // 设置（ｘ的前一节点）prev 的后一节点为ｘ的后一节点： next。（跳过 x 节点）
               prev.next = next;
               // x 的前节点置空。
               x.prev = null;
           }
           //　不存在ｘ的后一节点，则最后节点为ｘ的前节点。
           if (next == null) {
               last = prev;
           } else {
               // 设置（ｘ的后一节点）next 的前一节点为ｘ的前一节点。（跳过 x 节点）
               next.prev = prev;
               // x 的后节点置空。
               x.next = null;
           }
           // x 本身的值置空。
           x.item = null;
           // 集合元数个数减1。
           size--;
           modCount++;
           return element;
       }
    
       // 查第一个节点。
       public E getFirst() {
           final Node<E> f = first;
           if (f == null)
               throw new NoSuchElementException();
           return f.item;
       }
    
       // 查最后一节点。
       public E getLast() {
           final Node<E> l = last;
           if (l == null)
               throw new NoSuchElementException();
           return l.item;
       }
    
       // 删除并返回第一个节点
       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);
       }
    
       // 新增第一个节点。
       public void addFirst(E e) {
           linkFirst(e);
       }
    
       // 新增最后一节点
       public void addLast(E e) {
           linkLast(e);
       }
    
       // 查是否存在指定节点
       public boolean contains(Object o) {
           return indexOf(o) != -1;
       }
    
       // 查集合中元素个数
       public int size() {
           return size;
       }
    
       // 新增最后一节点，并返回该节点。
       public boolean add(E e) {
           linkLast(e);
           return true;
       }
    
       // 删除第一个和指定节点匹配的节点，指定节点不存在则不变。
       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;
       }
    
       // 在原集合尾部追加指定的集合。
       public boolean addAll(Collection<? extends E> c) {
           return addAll(size, c);
       }
    
       // 在指定位置插入指定的集合。index：元素在集合中的位置
       public boolean addAll(int index, Collection<? extends E> c) {
           // 查 index 对应节点是否在元素中，不在则抛异常
           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 {
               // 不断2分查找，至找到 index 对应节点。
               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;
       }
    
       // 删除全部节点。有节点被引用也会释放内存。
       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++;
       }
    
       // 查指定位置节点
       public E get(int index) {
           // 检查 index （ 即：>0，< size）
           checkElementIndex(index);
           return node(index).item;
       }
    
       // 替换指定位置节点。返回旧节点。
       public E set(int index, E element) {
           checkElementIndex(index);
           Node<E> x = node(index);
           E oldVal = x.item;
           x.item = element;
           return oldVal;
       }
    
       // 指定位置插入指定节点
       public void add(int index, E element) {
           checkPositionIndex(index);
    
           if (index == size)
               linkLast(element);
           else
               linkBefore(element, node(index));
       }
    
       // 删除指定位置节点。
       public E remove(int index) {
           checkElementIndex(index);
           return unlink(node(index));
       }
    
       // 检查索引是否有效。
       private boolean isElementIndex(int index) {
           return index >= 0 && index < size;
       }
    
       // 检查索引是否有效。
       private boolean isPositionIndex(int index) {
           return index >= 0 && index <= size;
       }
    
       // 构造提示信息。
       private String outOfBoundsMsg(int index) {
           return "Index: "+index+", Size: "+size;
       }
    
       private void checkElementIndex(int index) {
           if (!isElementIndex(index))
               throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
       }
    
       private void checkPositionIndex(int index) {
           if (!isPositionIndex(index))
               throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
       }
    
       // 查指定非空节点。（不断2分查找）
       Node<E> node(int index) {
           // assert isElementIndex(index);
    
           if (index < (size >> 1)) {
               Node<E> x = first;
               for (int i = 0; i < index; i++)
                   x = x.next;
               return x;
           } else {
               Node<E> x = last;
               for (int i = size - 1; i > index; i--)
                   x = x.prev;
               return x;
           }
       }
    
       // 正向检查指定节点是否存在。不存在返回-1。
       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;
       }
    
       // 反向检查指定节点是否存在。不存在返回-1。
       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;
       }
    
       // 查首节点
       public E peek() {
           final Node<E> f = first;
           return (f == null) ? null : f.item;
       }
    
       // 查首节点，集合为空则抛异常。
       public E element() {
           return getFirst();
       }
    
       // 查并删除首节点。
       public E poll() {
           final Node<E> f = first;
           return (f == null) ? null : unlinkFirst(f);
       }
    
       // 查并删除首节点，集合为空则抛异常。
       public E remove() {
           return removeFirst();
       }
    
       // 追加尾节点。
       public boolean offer(E e) {
           return add(e);
       }
    
       // 新增首节点。
       public boolean offerFirst(E e) {
           addFirst(e);
           return true;
       }
    
       // 追加尾节点。
       public boolean offerLast(E e) {
           addLast(e);
           return true;
       }
    
       // 查首节点。
       public E peekFirst() {
           final Node<E> f = first;
           return (f == null) ? null : f.item;
        }
    
       // 查尾节点
       public E peekLast() {
           final Node<E> l = last;
           return (l == null) ? null : l.item;
       }
    
       // 查并删除首节点。
       public E pollFirst() {
           final Node<E> f = first;
           return (f == null) ? null : unlinkFirst(f);
       }
    
       // 查并删除尾节点。
       public E pollLast() {
           final Node<E> l = last;
           return (l == null) ? null : unlinkLast(l);
       }
    
       // 新增首节点
       public void push(E e) {
           addFirst(e);
       }
    
       // 删除并返回首节点。
       public E pop() {
           return removeFirst();
       }
    
       // 正向删除指定节点。节点不存在则集合不变，返回 false 。
       public boolean removeFirstOccurrence(Object o) {
           return remove(o);
       }
    
       // 反向删除指定节点。节点不存在则集合不变，返回 false 。
       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;
       }
    
       // 返回迭代器
       public ListIterator<E> listIterator(int index) {
           checkPositionIndex(index);
           return new ListItr(index);
       }
    
       private class ListItr implements ListIterator<E> {
           private Node<E> lastReturned;
           private Node<E> next;
           private int nextIndex;
           private int expectedModCount = modCount;
    
           ListItr(int index) {
               // assert isPositionIndex(index);
               next = (index == size) ? null : node(index);
               nextIndex = index;
           }
    
           public boolean hasNext() {
               return nextIndex < size;
           }
    
           public E next() {
               checkForComodification();
               if (!hasNext())
                   throw new NoSuchElementException();
    
               lastReturned = next;
               next = next.next;
               nextIndex++;
               return lastReturned.item;
           }
    
           public boolean hasPrevious() {
               return nextIndex > 0;
           }
    
           public E previous() {
               checkForComodification();
               if (!hasPrevious())
                   throw new NoSuchElementException();
    
               lastReturned = next = (next == null) ? last : next.prev;
               nextIndex--;
               return lastReturned.item;
           }
    
           public int nextIndex() {
               return nextIndex;
           }
    
           public int previousIndex() {
               return nextIndex - 1;
           }
    
           public void remove() {
               checkForComodification();
               if (lastReturned == null)
                   throw new IllegalStateException();
    
               Node<E> lastNext = lastReturned.next;
               unlink(lastReturned);
               if (next == lastReturned)
                   next = lastNext;
               else
                   nextIndex--;
               lastReturned = null;
               expectedModCount++;
           }
    
           public void set(E e) {
               if (lastReturned == null)
                   throw new IllegalStateException();
               checkForComodification();
               lastReturned.item = e;
           }
    
           public void add(E e) {
               checkForComodification();
               lastReturned = null;
               if (next == null)
                   linkLast(e);
               else
                   linkBefore(e, next);
               nextIndex++;
               expectedModCount++;
           }
    
           public void forEachRemaining(Consumer<? super E> action) {
               Objects.requireNonNull(action);
               while (modCount == expectedModCount && nextIndex < size) {
                   action.accept(next.item);
                   lastReturned = next;
                   next = next.next;
                   nextIndex++;
               }
               checkForComodification();
           }
    
           final void checkForComodification() {
               if (modCount != expectedModCount)
                   throw new ConcurrentModificationException();
           }
       }
    
       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;
           }
       }
    
       /**
        * @since 1.6
        */
       public Iterator<E> descendingIterator() {
           return new DescendingIterator();
       }
    
       // 返回降序迭代器。
       private class DescendingIterator implements Iterator<E> {
           private final ListItr itr = new ListItr(size());
           public boolean hasNext() {
               return itr.hasPrevious();
           }
           public E next() {
               return itr.previous();
           }
           public void remove() {
               itr.remove();
           }
       }
    
       @SuppressWarnings("unchecked")
       private LinkedList<E> superClone() {
           try {
               return (LinkedList<E>) super.clone();
           } catch (CloneNotSupportedException e) {
               throw new InternalError(e);
           }
       }
    
       // 浅clone 。
       public Object clone() {
           LinkedList<E> clone = superClone();
    
           // Put clone into "virgin" state
           clone.first = clone.last = null;
           clone.size = 0;
           clone.modCount = 0;
    
           // Initialize clone with our elements
           for (Node<E> x = first; x != null; x = x.next)
               clone.add(x.item);
           return clone;
       }
    
       // 转为 Object 数组
       public Object[] toArray() {
           Object[] result = new Object[size];
           int i = 0;
           for (Node<E> x = first; x != null; x = x.next)
               result[i++] = x.item;
           return result;
       }
    
       // 拷贝原集合元素到指定数组。
       @SuppressWarnings("unchecked")
       public <T> T[] toArray(T[] a) {
           if (a.length < size)
               a = (T[])java.lang.reflect.Array.newInstance(
                                   a.getClass().getComponentType(), size);
           int i = 0;
           Object[] result = a;
           for (Node<E> x = first; x != null; x = x.next)
               result[i++] = x.item;
    
           if (a.length > size)
               a[size] = null;
    
           return a;
       }
    
       private static final long serialVersionUID = 876323262645176354L;
    
       // 写出到流，序列化。
       private void writeObject(java.io.ObjectOutputStream s)
           throws java.io.IOException {
           // Write out any hidden serialization magic
           s.defaultWriteObject();
    
           // Write out size
           s.writeInt(size);
    
           // Write out all elements in the proper order.
           for (Node<E> x = first; x != null; x = x.next)
               s.writeObject(x.item);
       }
    
       // 从流读入，反序列化。
       @SuppressWarnings("unchecked")
       private void readObject(java.io.ObjectInputStream s)
           throws java.io.IOException, ClassNotFoundException {
           // Read in any hidden serialization magic
           s.defaultReadObject();
    
           // Read in size
           int size = s.readInt();
    
           // Read in all elements in the proper order.
           for (int i = 0; i < size; i++)
               linkLast((E)s.readObject());
       }
    
       // 创建拆分器
       @Override
       public Spliterator<E> spliterator() {
           return new LLSpliterator<E>(this, -1, 0);
       }
    
       static final class LLSpliterator<E> implements Spliterator<E> {
           static final int BATCH_UNIT = 1 << 10;  // batch array size increment
           static final int MAX_BATCH = 1 << 25;  // max batch array size;
           final LinkedList<E> list; // null OK unless traversed
           Node<E> current;      // current node; null until initialized
           int est;              // size estimate; -1 until first needed
           int expectedModCount; // initialized when est set
           int batch;            // batch size for splits
    
           LLSpliterator(LinkedList<E> list, int est, int expectedModCount) {
               this.list = list;
               this.est = est;
               this.expectedModCount = expectedModCount;
           }
    
           final int getEst() {
               int s; // force initialization
               final LinkedList<E> lst;
               if ((s = est) < 0) {
                   if ((lst = list) == null)
                       s = est = 0;
                   else {
                       expectedModCount = lst.modCount;
                       current = lst.first;
                       s = est = lst.size;
                   }
               }
               return s;
           }
    
           public long estimateSize() { return (long) getEst(); }
    
           public Spliterator<E> trySplit() {
               Node<E> p;
               int s = getEst();
               if (s > 1 && (p = current) != null) {
                   int n = batch + BATCH_UNIT;
                   if (n > s)
                       n = s;
                   if (n > MAX_BATCH)
                       n = MAX_BATCH;
                   Object[] a = new Object[n];
                   int j = 0;
                   do { a[j++] = p.item; } while ((p = p.next) != null && j < n);
                   current = p;
                   batch = j;
                   est = s - j;
                   return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);
               }
               return null;
           }
    
           public void forEachRemaining(Consumer<? super E> action) {
               Node<E> p; int n;
               if (action == null) throw new NullPointerException();
               if ((n = getEst()) > 0 && (p = current) != null) {
                   current = null;
                   est = 0;
                   do {
                       E e = p.item;
                       p = p.next;
                       action.accept(e);
                   } while (p != null && --n > 0);
               }
               if (list.modCount != expectedModCount)
                   throw new ConcurrentModificationException();
           }
    
           public boolean tryAdvance(Consumer<? super E> action) {
               Node<E> p;
               if (action == null) throw new NullPointerException();
               if (getEst() > 0 && (p = current) != null) {
                   --est;
                   E e = p.item;
                   current = p.next;
                   action.accept(e);
                   if (list.modCount != expectedModCount)
                       throw new ConcurrentModificationException();
                   return true;
               }
               return false;
           }
    
           public int characteristics() {
               return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
           }
       }

[Link 1]: https://www.captainai.net/jiangyu1013/