• LinkedList : 双向链表实现。
• ArrayList : 动态数组实现。

1. LinkedList

1. LinkedList内部使用双向链表实现，支持高效的插入和删除（特别是在两端）。
2. 由于实现了Deque接口，因此可以作为双端队列使用。
3. 随机访问性能较差，需要通过遍历实现。

LinkedList 继承 AbstractSequentialList 类，实现了 List, Deque, Cloneable, Serializable 接口。其内部由双链表实现。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, Serializable {
	// ...
}

1.1 单链表

单链表（Singly Linked List）是一种基础但重要的线性数据结构（A->B->C）。

1.1.1 定义单链表节点类

最好定义为静态私有内部类。

// 单链表节点类
class ListNode<E> {
    E data;           // 存储的数据
    ListNode<E> next; // 指向下一个节点的指针

    ListNode(E data) {
        this.data = data;
        this.next = null;
    }
}

1.1.2 定义单链表实现类

需要定义一个 head 指针。

// 单链表实现
public class SinglyLinkedList<E> {
    private ListNode<E> head;  // 链表头节点
    private int size;           // 链表大小

    public SinglyLinkedList() {
        head = null;
        size = 0;
    }
}

1.1.3 头部添加

/**
 * 假如原来是 B->C，head 指向 B
 * 现在向头部插入 A，变成 A->B->C，A 成为新的 head，A.next 需要指向 B，head 指向 A
 */
public void addFirst(E data) {
    ListNode<E> newNode = new ListNode<>(data);
    newNode.next = head;
    head = newNode;
    size ++;
}

1.1.4 尾部添加

/**
 * 刚创建 SinglyLinkedList 的时候，head 是 null
 * 如果 head 是 null，新插入的节点成为新的 head，head 指向新节点
 * 否则，假设已有 A->B，现插入 C，那么 head 指向 A，需要从 head 开始遍历直到最后一个节点 B，将最后一个节点 B 的 next 指向新节点 C
 */
public void addLast(E data) {
    ListNode<E> newNode = new ListNode<>(data);
    if(null == head) {
        head = newNode;
    } else {
        ListNode<E> current = head;
        while(null != current.next) {
            current = current.next;
        }
        current.next = newNode;
    }
    size ++;
}

1.1.5 头部移除

/**
 * 假设 SinglyLinkedList 是空的，那么 head 必然为 null，抛出一个 NoSuchElementException
 * 否则，假设已有 A->B->C，现在 head 指向 A，需要将 head 指向 B，并返回 A 值
 */
public E removeFirst() {
    if(null == head) {
        throw new NoSuchElementException("空链表");
    }

    E data = head.data;
    head = head.next;
    size --;

    return data;
}

1.1.6 尾部移除

/**
 * 假设 SinglyLinkedList 是空的，那么 head 必然为 null，抛出一个 NoSuchElementException
 * 否则，假设已有 A->B->C，现在 head 指向 A，定义两个指针 pre、 cur，需要从 head 开始遍历直到倒数第一个节点 C，将倒数第二个节点 B.next 设为 null
 */
public E removeLast() {
    if(null == head) {
        throw new NoSuchElementException("空链表");
    }

    ListNode<E> pre = null;
    ListNode<E> cur = head;
    while(null != cur.next) {
        pre = cur;
        cur = cur.next;
    }

    E data = cur.data;
    if(cur == head) {  // 链表只有一个节点
        head = null;
    } else {
        pre.next = null;
    }
    size --;
    
    return data;
}

1.1.7 获取大小

public int size() {
    return size;
}

1.2 双链表

双向链表（Doubly Linked List）是一种常见的线性数据结构（A<=>B<=>C），其中每个节点包含两个指针，分别指向前一个节点和后一个节点。
与单向链表相比，双向链表可以从任意一个节点访问前一个节点和后一个节点，但需要额外的空间来存储前驱指针。

1.2.1 定义双链表节点类

最好定义为静态私有内部类。

// 双链表节点类
class Node<E> {
    E data;         // 存储的数据
    Node<E> next;   // 后继节点
    Node<E> prev;   // 前驱节点
    
    Node(E data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }

    Node(E data, Node<E> prev, Node<E> next) {
        this.data = data;
        this.prev = prev;
        this.next = next;
    }
}

1.2.2 定义双链表实现类

需要定义一个 head 指针，一个 tail 指针。

public class DoublyLinkedList<E>  {
    private Node<E> head;  // 头节点
    private Node<E> tail;  // 尾节点
    private int size;      // 链表长度

    public DoublyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
}

1.2.3 获取大小

public int size() {
    return size;
}

1.2.4 判断为空

public boolean isEmpty() {
    return size == 0;
}

1.2.5 头部添加

/**
 * 假如原来是 B <=> C ，则 head 指向 B
 * 现在向头部插入 A，则 A.next 指向 B，B.prev 指向 A，最后 A 成为新的头部 head，A <=> B <=> C
 *
 * 假如链表是空的，则 head 为 null，tail 为 null
 * 现在向头部插入 A，则 A 既是头部 head，也是尾部 tail
 */
public void addFirst(E data) {
    Node<E> node = new Node<>(data);
    if(isEmpty()) {
        head = node;
        tail = node;
    } else {
        node.next = head;
        head.prev = node;
        head = node;
    }
    size ++;
}

1.2.6 尾部添加

/**
 * 假如原来是 A <=> B ，则 tail 指向 B
 * 现在向尾部插入 C，则 C.prev 指向 B，B.next 指向 C，最后 C 成为新的尾部 tail，A <=> B <=> C
 *
 * 假如链表是空的，则 head 为 null，tail 为 null
 * 现在向头部插入 C，则 C 既是头部 head，也是尾部 tail
 */
public void addLast(E data) {
    Node<E> node = new Node<>(data);
    if(isEmpty()) {
        head = node;
        tail = node;
    } else {
        tail.next = node;
        node.prev = tail;
        tail = node;
    }

    size ++;
}

1.2.7 获取指定位置节点

优化点：二分为向前遍历和向后遍历。

private Node getNode(int index) {
    if(index < 0 || index > size) {
        throw new IndexOutOfBoundsException("Invalid index: " + index);
    }

    Node<E> current;
    if(index < size / 2) {
        // 向后遍历
        current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
    } else {
        // 向前遍历
        current = tail;
        for (int i = size - 1; i > index; i--) {
            current = current.prev;
        }
    }

    return current;
}

1.2.8 指定位置添加

public void add(int index, E data) {
    if(index < 0 || index > size) {
        throw new IndexOutOfBoundsException("Invalid index: " + index);
    }

    if(index == 0) {
        addFirst(data);
    } else if(index == size) {
        addLast(data);
    } else {
        Node<E> current = getNode(index);
        Node<E> node = new Node<>(data, current.prev, current);
        current.prev.next = node;
        current.prev = node;
        size ++;
    }
}

1.2.9 头部移除

public E removeFirst() {
    if(isEmpty()) {
        throw new NoSuchElementException("List is Empty.");
    }

    E data = head.data;
    if(head == tail) {
        head = tail = null;
    } else {
        head = head.next;
        head.prev = null;
    }
    size --;
    
    return data;
}

1.2.10 尾部移除

public E removeLast() {
    if(isEmpty()) {
        throw new NoSuchElementException("List is Empty.");
    }

    E data = tail.data;
    if(head == tail) {
        head = tail = null;
    } else {
        tail = tail.prev;
        tail.next = null;
    }
    size --;

    return data;
}

1.2.11 指定位置移除

public E remove(int index) {
    if(index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Invalid index: " + index);
    }

    E data;
    if(index == 0){
        data = this.removeFirst();
    } else if(index == size - 1) {
        data = this.removeLast();
    } else {
        Node<E> current = getNode(index);
        data = current.data;

        current.prev.next = current.next;
        current.next.prev = current.prev;

        current.prev = null;
        current.next = null;

        size --;
    }

    return data;
}

1.2.12 获取指定位置元素

public E get(int index) {
    Node<E> node = getNode(index);
    return node.data;
}

1.2.13 更新指定位置元素

public E set(int index, E data) {
    Node<E> node = getNode(index);
    E oldVal = node.data;
    node.data = data;
    return oldVal;
}

2. ArrayList

基于 动态数组（Dynamic Array） 实现的。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, Serializable {
	// ...
}

2.1 动态数组

2.1.1 定义实现类

• 实现 Iterable 迭代器、Serializable 序列化。
• ReentrantReadWriteLock 并发控制锁保证线程安全。

public class SimplifiedArrayList<E> implements Iterable<E>, Serializable {
    private static final int DEFAULT_CAPACITY = 10;
    private transient Object[] elementData;  // 声明为transient，自定义序列化
    private int size;
    private transient int modCount = 0;      // 结构性修改计数器
    private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();  // 并发控制锁

    // 构造方法
    public SimplifiedArrayList() {
        this.elementData = new Object[DEFAULT_CAPACITY];
    }

    public SimplifiedArrayList(int initialCapacity) {
        this.elementData = new Object[initialCapacity];
    }
}

2.1.2 扩容机制

对数组动态扩容。

• 将原数组长度（假设是7），转成二进制即 0111；
• 右移1位后 0011，即十进制的3；
• 7 + 3，新数组长度 10。

// 核心扩容机制
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);  // 1.5倍扩容
    if (newCapacity < minCapacity) newCapacity = minCapacity;
    elementData = Arrays.copyOf(elementData, newCapacity);
}

2.1.3 添加

ReentrantReadWriteLock 并发同步锁保证添加操作的线程安全。

// 线程安全的添加操作
public void add(E e) {
    lock.writeLock().lock();  // 写锁
    try {
        modCount++;
        if (size == elementData.length) grow(size + 1);
        elementData[size++] = e;
    } finally {
        lock.writeLock().unlock();
    }
}

2.1.4 获取

ReentrantReadWriteLock 并发同步锁保证获取操作的线程安全。

// 线程安全的获取操作
@SuppressWarnings("unchecked")
public E get(int index) {
    lock.readLock().lock();  // 读锁
    try {
        if (index >= size || index < 0) 
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        return (E) elementData[index];
    } finally {
        lock.readLock().unlock();
    }
}

2.1.5 删除

ReentrantReadWriteLock 并发同步锁保证删除操作的线程安全。

// 线程安全的删除操作
public E remove(int index) {
    lock.writeLock().lock();
    try {
        modCount++;
        E oldValue = get(index);
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        }
        elementData[--size] = null;  // 清除引用
        return oldValue;
    } finally {
        lock.writeLock().unlock();
    }
}

2.1.6 迭代器实现

// 迭代器实现（支持快速失败机制）
@Override
public Iterator<E> iterator() {
    return new Itr();
}

private class Itr implements Iterator<E> {
    int cursor;             // 下一个元素索引
    int lastRet = -1;       // 最后访问元素索引
    int expectedModCount = modCount;  // 迭代器创建时的modCount

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();  // 检查并发修改
        if (cursor >= size) throw new NoSuchElementException();
        lastRet = cursor;
        return (E) elementData[cursor++];
    }

    public void remove() {
        if (lastRet < 0) throw new IllegalStateException();
        checkForComodification();
        
        try {
            SimplifiedArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

2.1.7 序列化

// 自定义序列化（优化空间利用率）
private void writeObject(ObjectOutputStream s) throws IOException {
    s.defaultWriteObject();  // 序列化非transient字段
    s.writeInt(size);        // 写入实际元素数量
    
    // 仅序列化有效元素
    for (int i = 0; i < size; i++) {
        s.writeObject(elementData[i]);
    }
}

private void readObject(ObjectInputStream s) 
    throws IOException, ClassNotFoundException {
    s.defaultReadObject();   // 反序列化非transient字段
    int size = s.readInt();   // 读取元素数量
    
    // 重建数组
    elementData = new Object[size];
    for (int i = 0; i < size; i++) {
        elementData[i] = s.readObject();
    }
}

• JAR包反编译工具 : Java Decompiler
• 截图录屏 : Snagit Editor