目录

常见的 List 操作

1. 创建 List

2.访问元素

3. 修改元素

4. 删除元素

5. 遍历 List

6. 获取 List 的大小

7. 检查 List 是否包含某个元素

ArrayList vs LinkedList

ArrayList 源码详解

一、属性解析

二、构造方法解析

三、核心方法解析

add(E e)：在列表末尾添加指定元素。

add(int index, E element)：在指定位置插入指定元素。

ensureCapacityInternal(int minCapacity)：检查内部数组是否有足够的容量

grow(int minCapacity)：进行扩容操作。

get函数，获取对应下标的数据。

remove函数，删除ArrayList当中的数据。

set方法，这个方法主要是用于设置指定下标的数据，这个方法比较简单。

迭代器Iterator

LinkedList源码详解

一、链表的基本概念

二、LinkedList的类定义与属性

三、LinkedList的构造方法

四、Node的静态内部类

五、添加元素的方法

六、删除元素的方法

七、查找元素的方法

八、迭代器

Vector源码解析

Vector类中有几个关键的字段：

构造方法

扩容机制

线程安全

迭代器

添加和删除元素

查找元素

---

在Java中，List 是一个有序集合，它允许我们存储重复的元素，并且这些元素是按照插入的顺序进行存储的。List 接口是 Collection 接口的一个子接口，提供了更多的方法来操作元素。Java 中最常用的 List 实现类是 ArrayList

常见的 List 操作

以下是一些常见的 List 操作和它们的示例代码：

1. 创建 List

import java.util.ArrayList;
import java.util.List;public class Main {public static void main(String[] args) {// 使用 ArrayList 创建一个 ListList<String> list = new ArrayList<>();// 添加元素到 Listlist.add("Apple");list.add("Banana");list.add("Cherry");// 打印 ListSystem.out.println(list);}
}

2.访问元素

• 通过索引访问元素：

String firstElement = list.get(0); // 获取第一个元素
System.out.println(firstElement); // 输出: Apple

3. 修改元素

• 通过索引修改元素：

list.set(1, "Blueberry"); // 将第二个元素修改为 Blueberry
System.out.println(list); // 输出: [Apple, Blueberry, Cherry]

4. 删除元素

通过索引删除元素：
list.remove(2); // 删除第三个元素
System.out.println(list); // 输出: [Apple, Blueberry]
通过值删除元素：
list.remove("Blueberry"); // 删除值为 Blueberry 的元素
System.out.println(list); // 输出: [Apple]

5. 遍历 List

• 使用增强型 for 循环：

  for (String fruit : list) {System.out.println(fruit);
  }

• 使用迭代器 Iterator：

  import java.util.Iterator;Iterator<String> iterator = list.iterator();
  while (iterator.hasNext()) {String fruit = iterator.next();System.out.println(fruit);
  }

• 使用 ListIterator（支持前后遍历）：

  import java.util.ListIterator;ListIterator<String> listIterator = list.listIterator();
  while (listIterator.hasNext()) {String fruit = listIterator.next();System.out.println(fruit);
  }// 从后向前遍历
  while (listIterator.hasPrevious()) {String fruit = listIterator.previous();System.out.println(fruit); // 注意顺序会是反向的
  }

6. 获取 List 的大小

int size = list.size();
System.out.println("Size of list: " + size);

7. 检查 List 是否包含某个元素

boolean containsApple = list.contains("Apple");
System.out.println("List contains Apple: " + containsApple);

ArrayList vs LinkedList

• ArrayList 是基于数组实现的，因此它的随机访问速度非常快（时间复杂度为 O(1)），但在插入和删除元素时可能需要移动大量的元素（平均时间复杂度为 O(n)）。

• LinkedList 是基于链表实现的，因此它的插入和删除操作非常高效（时间复杂度为 O(1)，但前提是知道索引，否则需要遍历到指定位置），但随机访问元素较慢（时间复杂度为 O(n)）。

ArrayList 源码详解

ArrayList是Java集合框架中比较常用的数据结构，它继承自AbstractList，实现了List接口。

一、属性解析

ArrayList中有几个关键的属性：

1. DEFAULT_CAPACITY：默认的初始容量，值为10。
2. EMPTY_ELEMENTDATA：一个空的数组，用于在用户初始化代码的时候传入容量为0时使用。
3. DEFAULTCAPACITY_EMPTY_ELEMENTDATA：另一个空数组，用于在默认构造器中，赋值给底层数组elementData。这两个空数组的作用主要是用于区分是通过哪个构造函数来进行初始化的。
4. elementData：底层数组，真正存储元素的地方。
5. size：表示集合中ArrayList含有元素的个数。
6. MAX_ARRAY_SIZE：标记数组的最大容量，值为Integer.MAX_VALUE-8。
7. modCount：记录对List操作的次数，主要用于实现fail-fast机制。

二、构造方法解析

ArrayList提供了三种构造器：

1. 无参构造器：

   public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
   }

   使用无参构造器时，将DEFAULTCAPACITY_EMPTY_ELEMENTDATA变量赋值给elementData，即把elementData初始化为一个空数组。此时没有对数组容量进行分配，具体分配是在第一次增加元素时进行的。

2. 指定初始容量的构造器：

   public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);}
   }

   当传入的容量大小大于0时，elementData赋值为一个指定容量的数组；当传入的容量等于0时，elementData赋值为EMPTY_ELEMENTDATA；其他情况下，抛出异常。

3. 提供一个Collection集合的构造器：

   public ArrayList(Collection<? extends E> c) {elementData = c.toArray();if ((size = elementData.length) != 0) {if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);} else {// replace with empty array.this.elementData = EMPTY_ELEMENTDATA;}
   }

   将传入的集合转化为数组，赋值给elementData，并计算集合的大小size。如果size不为0，则判断保证此刻数组elementData的类型和Object[]类型相同，若不同，则拷贝一个Object[]类型的数组赋值给elementData。若size为0，将elementData赋值为EMPTY_ELEMENTDATA。

三、核心方法解析

1. add(E e)：在列表末尾添加指定元素。

   public boolean add(E e) {ensureCapacityInternal(size + 1); // 扩容elementData[size++] = e;return true;
   }

2. add(int index, E element)：在指定位置插入指定元素。

   public void add(int index, E element) {rangeCheckForAdd(index); // 检查索引是否越界ensureCapacityInternal(size + 1); // 扩容System.arraycopy(elementData, index, elementData, index + 1, size - index); // 移动元素elementData[index] = element; // 插入新元素size++; // 更新size
   }

3. ensureCapacityInternal(int minCapacity)：检查内部数组是否有足够的容量

   private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
   }

4. grow(int minCapacity)：进行扩容操作。

   private void grow(int minCapacity) {int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量为旧容量的1.5倍if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);elementData = Arrays.copyOf(elementData, newCapacity); // 拷贝数组
   }

5. get函数，获取对应下标的数据。

   public E get(int index) {// 进行数组下标的检查，如果下标超过 ArrayList 中数据的个数，则抛出异常// 注意这里是容器当中数据的个数 不是数组的长度rangeCheck(index);return elementData(index);
   }private void rangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
   }E elementData(int index) {// 返回对应下标的数据return (E) elementData[index];
   }

6. remove函数，删除ArrayList当中的数据。

   // 通过下标删除数据，这个函数的意义是删除下标为 index 的数据
   public E remove(int index) {// 首先检查下标是否合法，如果不合法，抛出下标越界异常rangeCheck(index);modCount++;E oldValue = elementData(index);// 因为删除某个数据，需要将该数据后面的数据往数组前面移动// 这里需要计算需要移动的数据的个数int numMoved = size - index - 1;if (numMoved > 0)// 通过拷贝移动数据// 这个函数的意义是将 index + 1和其之后的数据整体移动到 index// 的位置System.arraycopy(elementData, index+1, elementData, index,numMoved);// 因为最后一个数据已经拷贝到前一个位置了，所以可以设置为 null// 可以做垃圾回收了elementData[--size] = null; return oldValue;
   }// 这个函数的意义是删除容器当中的第一个等于 o 的数据
   public boolean remove(Object o) {if (o == null) {for (int index = 0; index < size; index++)if (elementData[index] == null) {fastRemove(index);return true;}} else {for (int index = 0; index < size; index++)if (o.equals(elementData[index])) {fastRemove(index);return true;}}return false;
   }// 这个方法和第一个 remove 方法原理一致
   private void fastRemove(int index) {modCount++;int numMoved = size - index - 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--size] = null; // clear to let GC do its work
   }

7. set方法，这个方法主要是用于设置指定下标的数据，这个方法比较简单。

   public E set(int index, E element) {rangeCheck(index);E oldValue = elementData(index);elementData[index] = element;return oldValue;
   }

8. 迭代器Iterator

   Iterator的初始化方法：
   private class Itr implements Iterator<E> {int cursor;       // index of next element to returnint lastRet = -1; // index of last element returned; -1 if no suchint expectedModCount = modCount;Itr() {}
   }

   Iterator重要方法

public boolean hasNext() {// 这个 size 是外部类 ArrayList 当中的 size 表示的是 ArrayList// 当中数据元素的个数，cursor 的初始值为 0 每调用一个 next cursor// 的值就+1，当等于 size 是容器当中的数据已经遍历完成了 hasNext 就返回 false 了return cursor != size;
}@SuppressWarnings("unchecked")
public E next() {// 这个方法主要是用于检测在数据迭代的过程当中 ArrayList 是否发生 `结构修改`// 如果发生结构修改就抛出 ConcurrentModificationException 异常checkForComodification();int i = cursor;if (i >= size)throw new NoSuchElementException();Object[] elementData = ArrayList.this.elementData;if (i >= elementData.length)throw new ConcurrentModificationException();// 更改 cursor 的值 并将其设置为下一个返回元素的下标 这一点我们在// 字段分析的时候已经谈到过了cursor = i + 1;// 返回数据 表达式 lastRet = i 的返回值为 i // 这个表达式不仅将 lastRet 的值赋值为 i 同时返回 i// 因此可以返回下标为 i 的数据return (E) elementData[lastRet = i];
}// 这个方法主要是用于检测在数据迭代的过程当中 ArrayList 是否发生 `结构修改`
// 如果发生结构修改就抛出 ConcurrentModificationException 异常
final void checkForComodification() {// 如果发生 `结构修改` 那么 modCount 的值会++ 那么就和 expectedModCount 不相等了// expectedModCount 初始化的时候令其等于 expectedModCountif (modCount != expectedModCount)throw new ConcurrentModificationException();
}

Iterator中的remove方法

public void remove() {if (lastRet < 0)throw new IllegalStateException();// 进行合法性检查，看是否需要抛出异常checkForComodification();try {// 调用 ArrayList 的remove方法实现ArrayList.this.remove(lastRet);cursor = lastRet;lastRet = -1;// 因为 remove 会改变 modCount 的值，因此需要将 expectedModCount 重新赋值expectedModCount = modCount;} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}
}

LinkedList源码详解

LinkedList是Java集合框架中的一个重要类，它实现了List接口，基于链表结构存储元素。

一、链表的基本概念

在深入LinkedList源码之前，有必要先了解链表的基本概念。链表是一种由一系列非连续的节点组成的存储结构，每个节点包含数据部分和指向下一个节点的指针。根据指针的数量和指向方式，链表可以分为单向链表、单向循环链表、双向链表和双向循环链表。

• 单向链表：每个节点只有一个指向下一个节点的指针（next），最后一个节点的next指向null。
• 单向循环链表：与单向链表类似，但最后一个节点的next指向头节点（head），形成一个环。
• 双向链表：每个节点有两个指针，pre指向前一个节点，next指向下一个节点。第一个节点（head）的pre指向null，最后一个节点（tail）的next指向null。
• 双向循环链表：与双向链表类似，但第一个节点的pre指向最后一个节点，最后一个节点的next指向第一个节点，也形成一个环。
• 

LinkedList是基于双向循环链表设计的。

二、LinkedList的类定义与属性

LinkedList类是一个实现了List接口的类，它使用了一个静态内部类Node来表示链表中的节点。Node类包含三个属性：item（存储节点的数据）、prev（指向前一个节点的指针）和next（指向下一个节点的指针）。

LinkedList类本身包含以下主要属性：

• size：表示链表中元素的个数。
• first：指向链表的头节点（head）。
• last：指向链表的尾节点（tail）。

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

三、LinkedList的构造方法

LinkedList提供了两个构造方法：

1. 无参构造方法：创建一个空的LinkedList实例，即first和last都为null，size为0。
2. 接收Collection的构造方法：创建一个包含指定Collection元素的LinkedList实例。这个构造方法会遍历传入的Collection，将其中的元素依次添加到新创建的LinkedList中。

public LinkedList(){}public LinkedList(Collection<? extends E> c){this();//无参构造函数addAll();//添加集合中所有元素
}

四、Node的静态内部类

Node是LinkedList的一个静态内部类，用于表示链表中的每个节点。它包含三个字段：item（存储元素）、next（指向下一个节点）、prev（指向前一个节点）。Node的构造函数需要这三个参数来初始化一个节点。

private static class Node<E>{E item;Node<E> prev;Node<E> next;Node(Node<E> prev, E element,Node<E> next){this.item=element;this.prev=prev;this.next=next;}
}

五、添加元素的方法

LinkedList提供了多种添加元素的方法，包括：

这些方法在底层都是通过操作节点的next和prev指针来实现的。例如，add(E e)方法会创建一个新节点，并将其设置为当前尾节点的后继节点，同时更新尾节点引用。

• add(E e)：在链表尾部添加元素。
• add(int index, E element)：在指定位置插入元素。
• addFirst(E e)：在链表头部插入元素。
• addLast(E e)：在链表尾部插入元素（与add(E e)方法相同）。

从尾部添加（add）

// 从尾部开始添加节点
void linkLast(E e) {// 把尾节点数据暂存final Node<E> l = last;// 新建新的节点，初始化入参含义：// l 是新节点的前一个节点，当前值是尾节点值// e 表示当前新增节点，当前新增节点后一个节点是 nullfinal Node<E> newNode = new Node<>(l, e, null);// 新建节点添加到尾部last = newNode;//如果链表为空（l 是尾节点，尾节点为空，链表即空），头部和尾部是同一个节点，都是新建的节点if (l == null)first = newNode;//否则把前尾节点的下一个节点，指向当前尾节点。elsel.next = newNode;    size++;//集合元素数量增加1modCount++;//实际修改次数增加1
}

从头部添加（addFirst）

// 从头部添加
private void linkFirst(E e) {// 头节点赋值给临时变量final Node<E> f = first;// 新建节点，前一个节点指向null，e 是新建节点，f 是新建节点的下一个节点，目前值是头节点的值final Node<E> newNode = new Node<>(null, e, f);// 新建节点成为头节点first = newNode;// 头节点为空，就是链表为空，头尾节点是一个节点if (f == null)last = newNode;//上一个头节点的前一个节点指向当前节点elsef.prev = newNode;size++;modCount++;
}

指定位置添加

public void add(int index,E element){checkPositionIndex(index);if(index==size)linkLast(element);elselinkBefore(element,node(index));
}

六、删除元素的方法

LinkedList提供了删除元素的方法，包括：

• remove()：删除并返回链表的第一个元素。
• removeFirst()：删除并返回链表的第一个元素。
• removeLast()：删除并返回链表的最后一个元素。
• remove(Object o)：删除链表中第一个匹配的元素。

这些方法在底层也是通过操作节点的next和prev指针来实现的。例如，removeFirst()方法会断开第一个节点与链表的连接，并更新头节点引用。

从头部删除

//从头删除节点 f 是链表头节点
private E unlinkFirst(Node<E> f) {// 拿出头节点的值，作为方法的返回值final E element = f.item;// 拿出头节点的下一个节点final Node<E> next = f.next;//帮助 GC 回收头节点f.item = null;f.next = null;// 头节点的下一个节点成为头节点first = next;//如果 next 为空，表明链表为空if (next == null)last = null;//链表不为空，头节点的前一个节点指向 nullelsenext.prev = null;//修改链表大小和版本size--;modCount++;return element;
}

删除指定元素，需要判断元素是否为null。

• 如果为null，就使用x.item == null语句判断。
• 如果不为null，就使用o.equals(x.item)语句判断。

E unlink(Node<E> x) {// assert x != null;// 记录节点element、next和prevfinal E element = x.item;final Node<E> next = x.next;final Node<E> prev = x.prev;// prev为null，next 赋为首节点 if (prev == null) {first = next;} else {// prev的next指向next节点prev.next = next;// x节点prev置为nullx.prev = null;}// next为null，prev赋为尾节点if (next == null) {last = prev;} else {// next的prev指向prevnext.prev = prev;// x节点next置为nullx.next = null;}// x.item置为nullx.item = null;// 长度自减size--;modCount++;return element;
}

七、查找元素的方法

LinkedList提供了按索引查找元素的方法get(int index)。由于链表不是基于数组的，因此查找元素需要遍历链表。为了提高效率，LinkedList在查找时会先比较索引值与链表长度的一半，然后从离目标位置更近的一端开始遍历。

先校验 index 的有效性
在查找时，先比较 index 与 (size >> 1)，即 index 与 size 中间值比较。
如果 index 较小，则从 first 开始往 last 方向遍历；
如果 index 较大，则从 last 开始往 first 方向遍历

// 根据链表索引位置查询节点
Node<E> node(int index) {// 如果 index 处于队列的前半部分，从头开始找，size >> 1 是 size 除以 2 的意思。if (index < (size >> 1)) {Node<E> x = first;// 直到 for 循环到 index 的前一个 node 停止for (int i = 0; i < index; i++)x = x.next;return x;} else {// 如果 index 处于队列的后半部分，从尾开始找Node<E> x = last;// 直到 for 循环到 index 的后一个 node 停止for (int i = size - 1; i > index; i--)x = x.prev;return x;}
}

八、迭代器

// 双向迭代器
private class ListItr implements ListIterator<E> {private Node<E> lastReturned;//上一次执行 next() 或者 previos() 方法时的节点位置private Node<E> next;//下一个节点private int nextIndex;//下一个节点的位置//expectedModCount：期望版本号；modCount：目前最新版本号private int expectedModCount = modCount;…………
}

从头到尾

// 判断还有没有下一个元素
public boolean hasNext() {return nextIndex < size;// 下一个节点的索引小于链表的大小，就有
}
​
// 取下一个元素
public E next() {//检查期望版本号有无发生变化checkForComodification();if (!hasNext())//再次检查throw new NoSuchElementException();// next 是当前节点，在上一次执行 next() 方法时被赋值的。// 第一次执行时，是在初始化迭代器的时候，next 被赋值的lastReturned = next;// next 是下一个节点了，为下次迭代做准备next = next.next;nextIndex++;return lastReturned.item;
}

从尾到头

// 如果上次节点索引位置大于 0，就还有节点可以迭代
public boolean hasPrevious() {return nextIndex > 0;
}
// 取前一个节点
public E previous() {checkForComodification();if (!hasPrevious())throw new NoSuchElementException();// next 为空场景：1:说明是第一次迭代，取尾节点(last);2:上一次操作把尾节点删除掉了// next 不为空场景：说明已经发生过迭代了，直接取前一个节点即可(next.prev)lastReturned = next = (next == null) ? last : next.prev;// 索引位置变化nextIndex--;return lastReturned.item;
}

迭代器删除

public void remove() {checkForComodification();// lastReturned 是本次迭代需要删除的值，分以下空和非空两种情况：// lastReturned 为空，说明调用者没有主动执行过 next() 或者 previos()，直接报错// lastReturned 不为空，是在上次执行 next() 或者 previos()方法时赋的值if (lastReturned == null)throw new IllegalStateException();Node<E> lastNext = lastReturned.next;//删除当前节点unlink(lastReturned);// next == lastReturned 的场景分析：从尾到头递归顺序，并且是第一次迭代，并且要删除最后一个元素的情况下// 这种情况下，previous() 方法里面设置了 lastReturned = next = last,所以 next 和 lastReturned会相等if (next == lastReturned)// 这时候 lastReturned 是尾节点，lastNext 是 null，所以 next 也是 null，这样在 previous() 执行时，发现 next 是 null，就会把尾节点赋值给 nextnext = lastNext;elsenextIndex--;lastReturned = null;expectedModCount++;
}

Vector源码解析

Vector类中有几个关键的字段：

• protected Object[] elementData;：这是一个Object数组，用于存储Vector中的元素。
• protected int elementCount;：这是一个整数，表示Vector中当前存储的元素数量。
• protected int capacityIncrement;：这是一个整数，表示Vector扩容时的增长系数。如果未指定，则在扩容时将容量翻倍。
• protected transient int modCount = 0;：这是一个修改计数，用于在迭代过程中检测Vector是否被修改。

构造方法

Vector提供了多个构造方法：

1. public Vector(int initialCapacity, int capacityIncrement)：创建一个具有指定初始容量和扩容增长系数的Vector。
2. public Vector(int initialCapacity)：创建一个具有指定初始容量和默认扩容增长系数（0，表示扩容时容量翻倍）的Vector。
3. public Vector()：创建一个具有默认初始容量（10）和默认扩容增长系数（0）的Vector。
4. public Vector(Collection<? extends E> c)：创建一个包含指定集合元素的Vector。

扩容机制

当Vector需要添加新元素但当前容量不足时，会触发扩容机制。扩容的核心方法是grow(int minCapacity)：

• 首先计算新的容量newCapacity。如果指定了capacityIncrement，则新容量为当前容量加上capacityIncrement；否则，新容量为当前容量的两倍。
• 如果新容量仍然小于所需的最小容量minCapacity，则新容量更新为minCapacity。
• 如果新容量超过了Integer.MAX_VALUE - 8（这是虚拟机为数组保留的一些头信息），则调用hugeCapacity(int minCapacity)方法处理超大容量的情况。
• 最后，使用Arrays.copyOf方法将原数组复制到新数组中。

线程安全

Vector是线程安全的，因为它的大部分公共方法都使用synchronized关键字进行了同步。这意味着在同一时刻只有一个线程可以执行这些方法，从而避免了并发修改问题。然而，这种同步机制也带来了性能上的开销。

迭代器

Vector提供了Enumeration<E>和Iterator<E>两种迭代器。Enumeration是Java早期版本的迭代器接口，而Iterator是Java 2引入的更强大的迭代器接口。Vector的迭代器是快速失败（fail-fast）的，如果在迭代器创建后Vector的结构被修改（除了调用迭代器本身的remove或add方法），则迭代器将抛出ConcurrentModificationException异常。

添加和删除元素

• public synchronized boolean add(E e)：在Vector的尾部添加新元素。
• public synchronized void add(int index, E element)：在Vector的指定位置插入新元素。
• public synchronized boolean remove(Object o)：移除Vector中第一个匹配的元素。
• public synchronized E remove(int index)：移除Vector中指定位置的元素。

查找元素

• public synchronized E get(int index)：根据索引获取Vector中的元素。
• public synchronized boolean contains(Object o)：检查Vector中是否包含指定元素。