https://www.bilibili.com/video/BV1ZT4y1377x

ArrayList 缺点

• list.add(2, 100) 指定位置添加元素。会把索引以后的元素都向后移动一个位置，总共要移动size减去指定索引 次， 如果空间不够还需要扩容。
• list.remove(2) 指定位置元素删除。会把索引以后的元素都向前移动一个位置。
• ArrayList 扩容： 创建新数组，销毁旧数组，拷贝旧得数组元素，都比较耗内存。

新数组是原数组长度的1.5倍，随着ArrayList的扩大，扩容1.5倍就会浪费内存空间。

LinkedList API

链表

链表的分类

链表的分类： 单向链表，双向链表，循环链表。

单向链表

• element：用来存放元素
• next：用来指向下一个节点元素
• 通过每个结点的指针指向下一个结点从而链接起来的结构，最后一个节点的next指向null。

双向链表：

• element：存放元素
• pre：用来指向前一个元素
• next：指向后一个元素
• 双向链表是包含两个指针的，pre指向前一个节点，next指向后一个节点，但是第一个节点head的pre指向null，最后一个节点的tail指向null。

循环列表

单项循环列表

• element、next 跟前面一样。
• 在单向链表的最后一个节点的next会指向头节点，而不是指向null，这样存成一个环

双向循环链表

element、pre、next 相同
第一个节点的pre指向最后一个节点，最后一个节点的next指向第一个节点，也形成一个“环”。

Node节点

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

Node节点包含三部分： 存储的数据，指向前一个node的地址，指向后一个的地址。

链表的结构

链表的添加元素的过程
链表的删除元素的过程
链表的查找元素的过程

LinkedList源码阅读

LinkedList是双向链表

构造器

public LinkedList() {
}

把集合转成数组，再把数组中的每一个元素转为node，并记录下头结点和尾结点。

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}
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;
        // succ的前驱节点
        Node<E> pred, succ;
        // 如果index与size相同
        if (index == size) {
            // succ的前驱节点直接赋值为最后节点
            // succ赋值为null，因为index在链表最后
            succ = null;
            pred = last;
        } else {
            // 取出index上的节点
            succ = node(index);
            pred = succ.prev;
        }
        // 遍历插入集合
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            // 创建新节点 前驱节点为succ的前驱节点，后续节点为null
            Node<E> newNode = new Node<>(pred, e, null);
            // succ的前驱节点为空，则表示succ为头，则重新赋值第一个结点
            if (pred == null)
                first = newNode;
            else
                // 构建双向链表
                pred.next = newNode;
            // 将前驱节点移动到新节点上，继续循环
            pred = newNode;
        }
        // index位置上为空 赋值last节点为pred，因为通过上述的循环pred已经走到最后了
        if (succ == null) {
            last = pred;
        } else {
            // 构建双向链表
            // 从这里可以看出插入集合是在succ[index位置上的节点]之前
            pred.next = succ;
            succ.prev = pred;
        }
        // 元素总数更新
        size += numNew;
        // 修改次数自增
        modCount++;
        return true;
    }

add 一个元素

默认从尾部添加元素。

public boolean add(E e) {
        linkLast(e);
        return true;
}
void linkLast(E e) {
    final Node<E> l = last; // 以前的last节点就是新增元素的前一个节点
    // 添加在尾部，后一个元素就是null
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    // 如果没有新增前last节点为null，说明linkedList是空的，新增的元素就是第一元素，也同时是最后一个元素
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;  // size加1
    modCount++; // 修改记录数加1
}

指定位置添加一个元素

这个是LinkedList的优势。

public void add(int index, E element) {
    //检查索引
    checkPositionIndex(index);
    //判断index是不是尾部位置
    if (index == size)
        //直接添加到尾部节点
        linkLast(element);
    else
        // element 要插入的节点
        // node(index) 原index位置的节点
        linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
    // 原index的前继节点 pred
    final Node<E> pred = succ.prev;
    // newNode = pred <-- e --> 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++;
}

remove一个元素

默认移除头部元素。

public E remove() {
    return removeFirst();
}
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(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
        // 将头节点的前驱节点赋值为null
        next.prev = null;
    // 元素总数自减
    size--;
    // 修改次数自增
    modCount++;
    // 返回删除的节点数据
    return element;
}

LinkedList实现了Deque

Deque （double ended queue）是双端队列。可以从队列的开始操作，也可以从队列的尾部操作
队列是FIFO.
栈是LIFO.
LinkedList 既可以支持队列操作，也支持栈操作。

package java.util;
public interface Queue<E> extends Collection<E> {
    boolean add(E e);
    boolean offer(E e);
    E remove();
    E poll();
    E element();
    E peek();
}

package java.util;
public interface Deque<E> extends Queue<E> {
    //栈和队列只是双端队列的特殊情况，它们的方法都可以使用双端队列的方法替代，
    //使用不同的名称和方法，概念上更为清晰。
    void addFirst(E e);
    void addLast(E e);
    boolean offerFirst(E e);
    boolean offerLast(E e);
    E removeFirst();
    E removeLast();
    E pollFirst();
    E pollLast();
    E getFirst();
    E getLast();
    E peekFirst();
    E peekLast();
    boolean removeFirstOccurrence(Object o);
    boolean removeLastOccurrence(Object o);
    // *** Queue methods ***
    boolean add(E e);
    boolean offer(E e);
    E remove();
    E poll();
    E element();
    E peek();
    // *** Stack methods ***
    void push(E e);
    E pop();
    // *** Collection methods ***
    boolean remove(Object o);
    boolean contains(Object o);
    public int size();
    Iterator<E> iterator();
    Iterator<E> descendingIterator();
}

Queue里面的方法，Queue扩展了Collection，它的主要操作有三个（每个操作2个方法，针对队列长度是否受限制对应是否抛异常—-有些队列的是有长度限制的，本例的LinkedList实现queue没长度限制）：

• 在尾部添加元素 (add, offer)：
• add()会在长度不够时抛出异常：IllegalStateException; offer()则不会,只返回false
• 查看头部元素 (element, peek)，返回头部元素，但不改变队列
• element()会在没元素时抛出异常：NoSuchElementException; peek()返回null;
  
• 删除头部元素 (remove, poll)，返回头部元素，并且从队列中删除
• remove()会在没元素时抛出异常：NoSuchElementException; poll()返回null; ```java import java.util.*;

public class Demo {

public static void main(String[] args) {
    Queue<String> queue = new LinkedList<>();
    queue.offer("a");
    queue.offer("b");
    queue.offer("c");
    while (queue.peek() != null){
        System.out.println(queue.poll());
    }
}

}

**Java中有一个类Stack，用于表示栈，但这个类已经过时了。Java中没有单独的栈接口，栈相关方法包括在了表示双端队列的接口Deque中，主要有三个方法**<br />**
- push表示入栈，在头部添加元素，栈的空间可能是有限的，如果栈满了，push会抛出异常IllegalStateException。
- pop表示出栈，返回头部元素，并且从栈中删除，如果栈为空，会抛出异常NoSuchElementException。
- peek查看栈头部元素，不修改栈，如果栈为空，返回null。 
```java
import java.util.*;
public class Demo {
    public static void main(String[] args) {
        Deque<String> queue = new LinkedList<>();
        queue.push("a");
        queue.push("b");
        queue.push("c");
        while (queue.peek() != null){
            System.out.println(queue.peek());
            System.out.println(queue.pop());
        }
    }
}

c c b b a a

栈和队列只是双端队列的特殊情况，它们的方法都可以使用双端队列的方法替代，使用不同的名称和方法，概念上更为清晰。

LinkedList的迭代器ListIterator

Iterator 只能从前往后遍历元素。

package java.util;
import java.util.function.Consumer;
public interface Iterator<E> {
    boolean hasNext();
    E next();
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

ListIterator 支持从后往前遍历和修改元素。

package java.util;
public interface ListIterator<E> extends Iterator<E> {
    // Query Operations
    boolean hasNext();
    E next();
    // 以下方法是ListIterator增强的功能
    boolean hasPrevious(); 
    E previous();
    int nextIndex();
    int previousIndex();
    // Modification Operations
    void remove();
    void set(E e);
    void add(E e);
}

AbstractSequentialList 部分源码

package java.util;
public abstract class AbstractSequentialList<E> extends AbstractList<E> {
    // Iterators
    public Iterator<E> iterator() {
        return listIterator();
    }
}

AbstractList 部分源码

public ListIterator<E> listIterator() {
    return listIterator(0);
}

LinkedList部分源码

    public ListIterator<E> listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);
    }
    // LinkedList内部类
    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();
        }
    }

LinkedList通过迭代器遍历元素性能比通过索引遍历的性能高很多倍。

import java.util.Iterator;
import java.util.LinkedList;
import java.util.UUID;
public class Demo {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        int length = 10000;
        for (int i = 0; i < length; i++) {
            linkedList.add(UUID.randomUUID().toString());
        }
        long start = System.currentTimeMillis();
        for (int i = 0; i < length; i++) {
            linkedList.get(i);
        }
        long end = System.currentTimeMillis();
        System.out.println("通过索引访问耗时：" + (end - start));
        start = System.currentTimeMillis();
        Iterator<String> iterator = linkedList.iterator();
        while (iterator.hasNext()){
            iterator.next();
        }
        end = System.currentTimeMillis();
        System.out.println("通过迭代器访问耗时：" + (end - start));
    }
}

通过索引访问耗时：197 通过迭代器访问耗时：1

原因：索引访问每次都要从头或者未查找，而ListIterator会有游标记录下一个元素的值和下一个元素的索引。

LinkedList的迭代器DescendingIterator

    public Iterator<E> descendingIterator() {
        return new DescendingIterator();
    }
    /**
     * Adapter to provide descending iterators via ListItr.previous
     */
    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();
        }
    }

从后向前遍历。