环境和版本
简介
类图
属性
构造方法
添加到头尾节点
添加多个元素
删除多个元素
查找单个元素
或者指定位置的元素
设置指定位置元素
转换为数组
求hash值
判断相等
清空链表
序列化和反序列化
克隆
创建子数组
创建 Iterator 迭代器
总结

环境和版本

Mac M1
IDEA 2021
Zulu Open JDK

简介
LinkedList，基于节点实现的双向链表的List，每个节点都指向前一个和后一个节点从而形成链表(关于链表，参见本章节数组和链表)
相比ArrayList来说，日常开发使用LinkedList相对较少，一般只会用在增加的场景下

类图
下面三个接口和ArrayList实现的接口一致
- java.util.List 接口
- java.io.Serializable 接口
- java.lang.Cloneable 接口
少于ArrayList的接口：java.util.RandomAccess接口，LinkedList 不同于 ArrayList 的很大一点，不支持随机访问。此接口详解参见(标记接口篇)
多于ArrayList的接口：java.util.Deque接口，提供双端队列的功能，LinkedList支持快速在头尾添加元素和读取元素，所以很容易实现此功能。
继承了 java.util.AbstractSequentialList，是 java.util.AbstractList的子类
LinkedList 和 ArrayList，都为了结合自身的特性，更加高效的实现，多选择了重写了 AbstractSequentialList 的方法
不过一般情况下，对于支持随机访问数据的继承 AbstractList 抽象类，不支持的继承 AbstractSequentialList 抽象类

属性
LinkedList一共有3个属性，如下图

通过Node节点指向前后节点，从而形成双向链表
first和last属性：链表的头尾节点引用
- 在初始化的时候，first和last都为null，因此暂时没有Node节点
- 在添加完首个元素之后，创建对于的Node节点node1前后指向null，first和last节点指向此Node节点
- 继续添加一个节点之后，创建对应的Node节点node2，其prev=node1和next=null，而node1的prev=null和next=node2，此时，first保持不变，指向node1，last发生改变，指向node2

size属性：链表的节点数量，通过它进行计数，避免每次需要List大小的时候，需要从头到尾遍历。

// 大小
transient int size = 0;
// 第一个节点
transient Node<E> first;
// 最后一个节点
transient Node<E> last;
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;
  }
}

构造方法

```java public LinkedList() { }

public LinkedList(Collection<? extends E> c) { this(); addAll(c); }

<a name="zCoZq"></a>
# 添加单个元素
```java
public boolean add(E e) {
    // 添加元素到末尾
    linkLast(e);
    return true;
}
void linkLast(E e) {
    // 拿到末尾的引用
    final Node<E> l = last;
    // 创建一个新的节点
    final Node<E> newNode = new Node<>(l, e, null);
    // 将新创建的节点赋值给last
    last = newNode;
    // 如果l==null，说明第一次添加，么有元素
    if (l == null)
        first = newNode;
    else
        // 否则，l的下一个元素就是新的元素
        l.next = newNode;
    size++;
    modCount++;
}
// 指定位置添加元素
public void add(int index, E element) {
    // 添加位置是否越界
    checkPositionIndex(index);
    // 如果index 和 size相等，则添加到最后一个
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}
// 拿到index位置的元素
Node<E> node(int index) {
    // assert isElementIndex(index);
    // 如果index 小于 size / 2 则从头节点开始遍历
    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;
    }
}
// 添加index位置元素
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    // 拿到index节点的前驱节点
    final Node<E> pred = succ.prev;
    // 创建新加入节点
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 原index位置节点的前一个节点指向新节点
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

添加到头尾节点

因为LinkedList实现了Deque接口，所以它实现了 addFirst(E e) 和 addLast(E e) 方法，分别添加元素到链表的头尾 ```java public void addFirst(E e) { linkFirst(e); }

public void addLast(E e) { linkLast(e); }

public boolean offerFirst(E e) { addFirst(e); return true; }

public boolean offerLast(E e) { addLast(e); return true; }

// 添加到头节点 private void linkFirst(E e) { // 取出头节点的引用 final Node f = first; // 构建新的头节点 final Node newNode = new Node<>(null, e, f); // 新的节点为头节点 first = newNode; // 尾节点也是空 if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; }


- 因为LinkedList实现了Queue接口，所以其实现了push(E e)，和offer(E e)方法，添加元素到链表的头尾
```java
public void push(E e) {
    addFirst(e);
}
public boolean offer(E e) {
    return add(e);
}

添加元素，分3种情况
- 添加元素到队头
- 添加元素到队尾
- 添加元素到中间
  添加多个元素
```java // 添加集合数据 public boolean addAll(Collection<? extends E> c) { // 添加到index位置也就是size位置，添加到最后 return addAll(size, c); }

// index 下标 // c 需要添加的元素数据集合 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;
}

// 如果 succ 为 null ，说明插入队尾，则直接修改 last 指向最后一个 pred
if (succ == null) {
    last = pred;
} else {
    // 如果 succ 非 null ，说明插入到 succ 的前面
    pred.next = succ;
    succ.prev = pred;
}

size += numNew;
modCount++;
return true;

}

<a name="Vr4Dz"></a>
# 移除单个元素
```java
public E remove(int index) {
    // 检查下标
    checkElementIndex(index);
    // node(index) 获取需要移除的节点
    return unlink(node(index));
}

// 移除
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;

    // 如果前驱节点为null，说明删除的是第一个元素
    if (prev == null) {
        first = next;
    } else {
        // 否则前驱节点的下一个节点是next
        prev.next = next;
        // 当前节点的上一个节点设置为null
        x.prev = null;
    }

    // 如果当前节点的下一个节点为null，说明删除的是最后一个节点
    if (next == null) {
        // 将last节点指向前一个节点
        last = prev;
    } else {
        // 否则下一个节点的前一个节点指向当前节点的前一个节点
        next.prev = prev;
        // 当前的下一个节点设置为null
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

// 删除元素
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 removeFirstOccurrence(Object o) {
    return remove(o);
}

// 删除最后一个出现的节点
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 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
        next.prev = null;
    size--;
    modCount++;
    return element;
}

// 移除最后的节点
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(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;
}

// ================================= Queue 接口 =================================
// 移除头节点
// 但是当头节点为null的时候不会抛出异常
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

// 这个方法，如果队列为空，还是会抛出 NoSuchElementException 异常
public E pop() {
    return removeFirst();
}

// ================================= Deque 接口 =================================
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);
}

删除多个元素

// AbstractCollection#removeAll
// 移除在c的元素
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;
    Iterator<?> it = iterator();
    // 迭代器删除
    while (it.hasNext()) {
        if (c.contains(it.next())) {
            it.remove();
            modified = true;
        }
    }
    return modified;
}

// 移除不在c的元素
public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;
    Iterator<E> it = iterator();
    while (it.hasNext()) {
        if (!c.contains(it.next())) {
            it.remove();
            modified = true;
        }
    }
    return modified;
}

查找单个元素

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

public boolean contains(Object o) {
    return indexOf(o) != -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 get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

// 获取链表的头元素
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;
}

// 因为LinkedList实现了Deque接口
// 获取链表的头结点元素
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

public E element() {
    return getFirst();
}
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

设置指定位置元素

// index 下标
// 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;
}

转换为数组

// 转换为数组
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;
}

// 转换为泛型数组
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;
}

求hash值

public int hashCode() {
    int hashCode = 1;
    for (E e : this)
        hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
    return hashCode;
}

判断相等

public boolean equals(Object o) {
    if (o == this)
        return true;
    if (!(o instanceof List))
        return false;

    ListIterator<E> e1 = listIterator();
    ListIterator<?> e2 = ((List<?>) o).listIterator();
    while (e1.hasNext() && e2.hasNext()) {
        E o1 = e1.next();
        Object o2 = e2.next();
        if (!(o1==null ? o2==null : o1.equals(o2)))
            return false;
    }
    return !(e1.hasNext() || e2.hasNext());
}

清空链表

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

序列化和反序列化

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

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

克隆

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

private LinkedList<E> superClone() {
    try {
        return (LinkedList<E>) super.clone();
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }
}

创建子数组

public List<E> subList(int fromIndex, int toIndex) {
    // 根据判断 RandomAccess 接口，判断是否支持随机访问
    return (this instanceof RandomAccess ?
            new RandomAccessSubList<>(this, fromIndex, toIndex) :
            new SubList<>(this, fromIndex, toIndex));
}

创建 Iterator 迭代器

// AbstractSequentialList.java
public Iterator<E> iterator() {
    return listIterator();
}

// AbstractList.java
public ListIterator<E> listIterator() {
    return listIterator(0);
}

public ListIterator<E> listIterator(final int index) {
    rangeCheckForAdd(index);

    return new ListItr(index);
}

private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        cursor = index;
    }

    public boolean hasPrevious() {
        return cursor != 0;
    }

    public E previous() {
        checkForComodification();
        try {
            int i = cursor - 1;
            E previous = get(i);
            lastRet = cursor = i;
            return previous;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }

    public int nextIndex() {
        return cursor;
    }

    public int previousIndex() {
        return cursor-1;
    }

    public void set(E e) {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            AbstractList.this.set(lastRet, e);
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    public void add(E e) {
        checkForComodification();

        try {
            int i = cursor;
            AbstractList.this.add(i, e);
            lastRet = -1;
            cursor = i + 1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

总结

返回结果	抛出异常
添加	#add(…)、#offset(…)
删除	#remove(int index)、#remove(E e)、#poll(E e)	#remove()
查找	#get(int index)、#peek()	#poll()

Base-Java

🎉 List-LinkedList