Java 入门指南：List 接口

Collection 接口提供了一系列用于操作和管理集合的方法，包括添加、删除、查询、遍历等。它是所有集合类的根接口，包括 List、Set、Queue 等。

![[Collection UML.png]]

Collection 接口常见方法

add(E element)：向集合中添加元素。
addAll(Collection col)：将 col 中的所有元素添加到集合中
boolean remove(Object obj)：通过元素的equals方法判断是否是要删除的那个元素，只删除找到的第一个元素
boolean removeAll(Collection col)：取两集合差集
boolean retain(Collection col)：把交集的结果存在当前的集合中，不影响col
boolean contains(Object obj)：判断集合中是否包含指定的元素。
boolean containsAll(Collection col)：调用元素的equals方法来比较的。用两个两个集合的元素逐一比较
size()：返回集合中的元素个数。
isEmpty()：判断集合是否为空。
clear()：清空集合中的所有元素。
iterator()：返回用于遍历集合的迭代器。
hashCode()：获取集合对象的哈希值
Object[] toArray()：转换成对象数组

List 接口

List 接口是 Java 集合框架（Java Collections Framework）中的一个重要接口，它继承自 Collection 接口。List 接口的特点主要包括：

有序性：List 集合中的元素是有序的，即元素的添加顺序和取出顺序一致。
可重复性：List 集合中的元素可以重复。
索引支持：List 集合中的每个元素都对应一个整数型的索引，可以通过索引来访问元素。

List 接口底层以数组方式进行对象存储，允许存放null元素

不建议添加 null 值，null 值无意义，会让代码难以维护比如忘记做判空处理就会导致空指针异常

与 Collection 接口不同，List 接口中的元素是按照插入的顺序进行排序的，可以根据索引访问和操作集合中的元素。它允许集合中存在相同的元素。

List 接口常用方法

![[List Methods.png]]

List 常见实现类

JDK API中提供了多个 List 接口的实现类，常用的有 ArrayList、LinkedList 和 Vector 等。

ArrayList：基于动态数组实现，适用于对元素的随机访问，但在列表的头部或中部插入、删除元素时性能较差，因为需要移动其他元素。
LinkedList：基于双向链表实现，适用于频繁的插入和删除操作，尤其是在列表的头部或尾部进行操作时。但在随机访问元素时性能较差，因为需要从头或尾开始遍历链表。
Vector：与 ArrayList 类似，但它是线程安全的，即支持多线程环境下的并发访问。然而，由于线程安全的实现带来了额外的性能开销，因此在单线程环境下通常不推荐使用 Vector。

ArrayList

ArrayList 是基于动态数组实现的 List，它使用数组来存储元素，具有快速的随机访问和修改能力。可以高效地通过索引访问和更新元素，适用于频繁访问元素的场景。

![[ArrayList Class.png]]

ArrayList 继承于 AbstractList ，实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。

ArrayList 类的定义

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

List : 表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。
RandomAccess ：这是一个标志接口，表明实现这个接口的 List 集合是支持 快速随机访问 的。在 ArrayList 中，我们即可以通过元素的索引快速获取元素对象，这就是快速随机访问。
Cloneable ：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作。
Serializable : 表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输，非常方便。

ArrayList 特点

动态调整大小：ArrayList 内部使用数组来存储元素，当元素数量超过当前数组容量时，ArrayList 会自动增加内部数组的大小，以容纳更多的元素。

在添加大量元素前，应用程序也可以使用ensureCapacity操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。
随机访问：由于 ArrayList 基于数组实现，可以通过索引快速访问和修改元素。通过 get(index) 方法可以获取指定索引位置的元素
通过 set(index, element) 方法可以替换指定索引位置的元素。
动态添加和删除：ArrayList 提供了多个方法来添加和删除元素，如 add(element)、add(index, element)、remove(index)、remove(element) 等。添加和删除元素时，ArrayList 会自动调整数组的大小。
支持迭代：ArrayList 实现了 Iterable 接口，因此可以使用增强的 for 循环或者迭代器来遍历 ArrayList 中的元素。
不是线程安全的：ArrayList 不是线程安全的，如果在多线程环境中使用 ArrayList 需要考虑线程同步的问题。

ArrayList 三种构造方法

ArrayList()：构造一个默认大小为10容量的空列表。

List list = new ArrayList();

JDK 1.7：直接创建一个初始容量为10的数组
JDK 1.8：一开始创建一个长度为0的数组，当添加第一个元素时再创建一个始容量为10的数组

ArrayList(int initialCapacity)：构造一个大小为指定 initialCapacity容量的空列表。

List list = new ArrayList(initCapacity);

ArrayList(Collection c)：构造一个和参数 c 相同元素的ArrayList对象

List col = new ArrayList(6);
col.add("1");
List list = new ArrayList(col);

ArrayList 扩容机制

ArrayList 的扩容机制是动态的，可以根据需要自动增加容量。这种机制使得 ArrayList 能够有效地管理内存，并且在大多数情况下提供了良好的性能。

ArrayList 的初始容量默认为10。如果在创建 ArrayList 时指定了初始容量，那么将使用指定的容量。例如：

ArrayList<String> list = new ArrayList<>(20);  // 初始容量为20

当向 ArrayList 添加元素导致其容量不足时，ArrayList 会自动增加容量。ArrayList 的扩容策略如下：

默认扩容比例：默认情况下，ArrayList 的容量每次增加原来的50%（即扩容为原来的1.5倍）。
扩容操作：扩容操作通过调用 ensureCapacityInternal 方法完成。

下面通过源码分析 ArrayList 的扩容过程：

public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;
}private void ensureCapacityInternal(int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}ensureExplicitCapacity(minCapacity);
}private void ensureExplicitCapacity(int minCapacity) {modCount++;// 检查是否需要扩容if (minCapacity - elementData.length > 0)grow(minCapacity);
}private void grow(int minCapacity) {// overflow-conscious codeint 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);// minCapacity is usually close to size, so this is a win:elementData = Arrays.copyOf(elementData, newCapacity);
}

源代码解析：

add方法：add 方法首先调用 ensureCapacityInternal 来确保有足够的容量来存储新增的元素。
ensureCapacityInternal方法：如果 elementData 是默认的空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则将最小容量设置为10或指定的初始容量。然后调用 ensureExplicitCapacity 方法。
ensureExplicitCapacity方法：如果最小容量大于当前容量，则调用 grow 方法来扩容。
grow方法：根据当前容量计算新的容量（默认为原容量的1.5倍），如果新的容量仍然不足以满足最小容量的要求，则直接设置为最小容量。如果新的容量超过了 MAX_ARRAY_SIZE（即 Integer.MAX_VALUE - 8），则调用 hugeCapacity 方法来防止溢出。

ArrayList 使用示例

import java.util.ArrayList;
import java.util.List;public class ArrayListExample {public static void main(String[] args) {// 创建一个 ArrayListList<String> names = new ArrayList<>();// 添加元素names.add("Alice");names.add("Bob");names.add("Charlie");// 访问元素System.out.println(names.get(0));  // 输出: Alice// 修改元素names.set(1, "David");System.out.println(names);  // 输出: [Alice, David, Charlie]// 插入元素names.add(1, "Eve");System.out.println(names);  // 输出: [Alice, Eve, David, Charlie]// 删除元素names.remove(2);System.out.println(names);  // 输出: [Alice, Eve, Charlie]// 查找元素System.out.println(names.indexOf("Eve"));  // 输出: 1}
}

LinkedList

LinkedList 是基于双向链表实现的 List，它使用链表来存储元素，具有高效的插入和删除操作。不同于 ArrayList，LinkedList 在插入和删除元素时没有数组的扩容和复制开销，适用于频繁插入和删除元素的场景。

![[LinkedList类图.png]]

LinkedList 继承了 AbstractSequentialList ，而 AbstractSequentialList 又继承于 AbstractList 。所以 LinkedList 会有大部分方法和 ArrayList 相似。

LinkedList的定义

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

List : 表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。
Deque ：继承自 Queue 接口，具有双端队列的特性，支持从两端插入和删除元素，方便实现栈和队列等数据结构。
Cloneable ：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作。
Serializable : 表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输，非常方便。

为什么没有实现RandomAccess接口？
由于 LinkedList 底层数据结构是链表，内存地址不连续，只能通过指针来定位，不支持随机快速访问，所以不能实现 RandomAccess 接口。

LinkedList 特点

双向链表：LinkedList 内部使用双向链表来存储元素，每个节点都包含一个指向前一个节点和后一个节点的引用。这使得在链表中添加、删除元素比较高效，因为只需要调整相邻节点的引用。
动态添加和删除：LinkedList 提供了多个方法来添加和删除元素，如 add(element)、addFirst(element)、addLast(element)、remove(element)、removeFirst()、removeLast() 等。添加和删除元素时，只需要调整节点的引用，不需要像数组那样移动元素。
支持队列和栈操作：由于 LinkedList 实现了 Deque 接口，可以将 LinkedList 作为队列（先进先出）或栈（后进先出）来使用。例如，可以使用 offer(element) 和 poll() 方法来实现队列操作，使用 push(element) 和 pop() 方法来实现栈操作。
随机访问效率较低：由于 LinkedList 是基于链表实现的，在随机访问时需要从头节点或尾节点开始依次遍历链表，因此访问效率相对较低。
不是线程安全的：LinkedList 不是线程安全的，如果在多线程环境中使用 LinkedList 需要考虑线程同步的问题。

LinkedList 两种构造方法

LinkedList()：构造一个空的 LinkedList 对象。
LinkedList(Collection col)：构造一个和参数 col 相同元素的 LinkedList 对象

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

LinkedList 内的元素

LinkedList 中的元素是通过 Node 定义的：

private static class Node<E> {E item;       // 节点值Node<E> next; // 后继节点Node<E> prev; // 前驱结点Node(Node<E> prev, E item, Node<E> next) {this.item = item;this.next = next;this.prev = prev;}
}

LinkedList 类的方法

方法	功能说明
void addFirst(Object obj)	在链表头部插入一个元素
void addLast(Object obj)	在链表尾部添加一个元素
Object getFirst()	获取第一个元素
Object getlast()	获取最后一个元素
Object removeFirst()	删除头元素
Object removeLast()	删除尾元素
Object peek()	获取但不移除第一个元素
Object poll()	获取并移除第一个元素

LinkedList 中的栈操作

void push(element): 将指定的元素添加到链表的开头，作为栈的顶部元素。
void pop(): 移除并返回链表的第一个元素，即栈的顶部元素。

LinkedList 中的队列操作

boolean offer(element): 将指定的元素添加到链表的末尾，作为队列的尾部元素。
poll(): 移除并返回链表的第一个元素，即队列的头部元素。

LinkedList 使用示例

import java.util.LinkedList;
import java.util.List;public class LinkedListExample {public static void main(String[] args) {// 创建一个 LinkedListList<String> names = new LinkedList<>();// 添加元素names.add("Alice");names.add("Bob");names.add("Charlie");// 访问元素System.out.println(names.get(0));  // 输出: Alice// 修改元素names.set(1, "David");System.out.println(names);  // 输出: [Alice, David, Charlie]// 插入元素names.add(1, "Eve");System.out.println(names);  // 输出: [Alice, Eve, David, Charlie]// 删除元素names.remove(2);System.out.println(names);  // 输出: [Alice, Eve, Charlie]// 查找元素System.out.println(names.indexOf("Eve"));  // 输出: 1}
}

LinkedList 和 ArrayList 的区别

是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
底层数据结构： ArrayList 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。）
插入和删除是否受元素位置的影响
- ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。
  
  如果要在指定位置 i 插入和删除元素的话（add(int index, E element)），时间复杂度就为 O(n)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的 (n-i) 个元素都要执行向后位/向前移一位的操作。
- LinkedList 采用链表存储，所以在头尾插入或者删除元素不受元素位置的影响（add(E e)、addFirst(E e)、addLast(E e)、removeFirst()、 removeLast()），时间复杂度为 O(1)
如果是要在指定位置 i 插入和删除元素的话（add(int index, E element)，remove(Object o),remove(int index)），时间复杂度为 O(n) ，因为需要先移动到指定位置再插入和删除。
是否支持快速随机访问： LinkedList 不支持高效的随机元素访问， ArrayList（实现了 RandomAccess 接口）支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
内存空间占用：
- ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间
- LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

Vector

Vector 与 ArrayList 类似，也是基于动态数组实现的 List，不同的是 Vector 是线程安全的。可以在多线程环境中可以安全地使用。

由于线程安全的需要，使用 Vector 可能会带来一些额外的开销，在性能要求较高的场景下或单线程环境下，可以优先选择 ArrayList。

Vector 的四种构造方法

Vector()：构造一个构造一个元素个数为 0 的 Vector 对象，为其分配默认大小的容量。
Vector(int size)：构造一个构造一个元素个数为 0 的 Vector 对象，为其分配大小为 size 的初始容量。
Vector(Collection c)：构造一个和参数 c 相同元素的 Vector 对象
Vector(int initalcapacity, int capacityincrement)：构造一个构造一个元素个数为 0 的Vector对象，为其分配大小为 initalcapacity 的初始容量。并指定 vector 中的元素个数达到初始容量时，vector 会自动增加大小为 capacityincrement 的容量

Vector 底层源码

vector底层源码绝大数和ArrayList相同，但扩容机制略有区别，Vector 每次扩容是前一次容量的二倍

Vector 使用示例

import java.util.Vector;
import java.util.List;public class VectorExample {public static void main(String[] args) {// 创建一个 VectorList<String> names = new Vector<>();// 添加元素names.add("Alice");names.add("Bob");names.add("Charlie");// 访问元素System.out.println(names.get(0));  // 输出: Alice// 修改元素names.set(1, "David");System.out.println(names);  // 输出: [Alice, David, Charlie]// 插入元素names.add(1, "Eve");System.out.println(names);  // 输出: [Alice, Eve, David, Charlie]// 删除元素names.remove(2);System.out.println(names);  // 输出: [Alice, Eve, Charlie]// 查找元素System.out.println(names.indexOf("Eve"));  // 输出: 1}
}

Stack 类

在 Java 中，java.util.Stack 是 Stack 类的具体实现。它是 Vector 类的一个子类，因此继承了 Vector 的所有特性，并在此基础上提供了一些额外的方法来支持栈的操作。

添加和删除元素：
- push(element)：将元素压入栈顶。
- pop()：弹出栈顶的元素，并将其从栈中删除。
获取栈顶元素：
- peek()：获取栈顶的元素，但不将其从栈中删除。
判断栈是否为空：
- empty()：检查栈是否为空，如果为空则返回 true，否则返回 false。
查询元素位置：
- search(element)：返回元素在栈中的位置（从栈顶开始计数），如果元素不存在，则返回 -1。

由于 Stack 是基于 Vector 实现的，它并不是完全线程安全的。

如果在多线程环境中使用栈，建议使用 java.util.concurrent.ConcurrentLinkedDeque 或其他线程安全的栈实现类，或者使用 synchronized 进行同步，以确保同一时间只有一个线程可以修改栈中的元素。

Stack 使用示例

import java.util.Stack;public class StackExample {public static void main(String[] args) {// 创建一个 StackStack<String> stack = new Stack<>();// 添加元素stack.push("Alice");stack.push("Bob");stack.push("Charlie");// 访问栈顶元素System.out.println("Top element: " + stack.peek());  // 输出: Top element: Charlie// 获取并移除栈顶元素String topElement = stack.pop();System.out.println("Popped element: " + topElement);  // 输出: Popped element: Charlie// 再次访问栈顶元素System.out.println("New top element: " + stack.peek());  // 输出: New top element: Bob// 检查栈是否为空System.out.println("Is the stack empty? " + stack.isEmpty());  // 输出: Is the stack empty? false// 获取栈的大小System.out.println("Size of the stack: " + stack.size());  // 输出: Size of the stack: 2// 遍历栈中的所有元素while (!stack.isEmpty()) {System.out.println(stack.pop());  // 依次输出: Bob, Alice}}
}