列表
列表（list）是一个抽象的数据结构概念，它表示元素的有序集合，支持元素访问、修改、添加、删除和遍历等操作，无须使用者考虑容量限制的问题。列表可以基于链表或数组实现。
- 链表天然可以看作一个列表，其支持元素增删查改操作，并且可以灵活动态扩容。
- 数组也支持元素增删查改，但由于其长度不可变，因此只能看作一个具有长度限制的列表。
当使用数组实现列表时，长度不可变的性质会导致列表的实用性降低。这是因为我们通常无法事先确定需要存储多少数据，从而难以选择合适的列表长度。若长度过小，则很可能无法满足使用需求；若长度过大，则会造成内存空间浪费。
为解决此问题，我们可以使用动态数组（dynamic array）来实现列表。它继承了数组的各项优点，并且可以在程序运行过程中进行动态扩容。
实际上，许多编程语言中的标准库提供的列表是基于动态数组实现的，例如 Python 中的 list 、Java 中的 ArrayList 、C++ 中的 vector 和 C# 中的 List 等。在接下来的讨论中，我们将把“列表”和“动态数组”视为等同的概念。
列表常用操作
初始化列表
我们通常使用“无初始值”和“有初始值”这两种初始化方法：
java
/* 初始化列表 */
// 无初始值
List<Integer> nums1 = new ArrayList<>();
// 有初始值（注意数组的元素类型需为 int[] 的包装类 Integer[]）
Integer[] numbers = new Integer[] { 1, 3, 2, 5, 4 };
List<Integer> nums = new ArrayList<>(Arrays.asList(numbers));访问元素
列表本质上是数组，因此可以在 𝑂(1) 时间内访问和更新元素，效率很高。
java
/* 访问元素 */
int num = nums.get(1); // 访问索引 1 处的元素
/* 更新元素 */
nums.set(1, 0); // 将索引 1 处的元素更新为 0插入与删除元素
相较于数组，列表可以自由地添加与删除元素。在列表尾部添加元素的时间复杂度为 𝑂(1) ，但插入和删除元素的效率仍与数组相同，时间复杂度为 𝑂(𝑛) 。
java
/* 清空列表 */
nums.clear();
/* 在尾部添加元素 */
nums.add(1);
nums.add(3);
nums.add(2);
nums.add(5);
nums.add(4);
/* 在中间插入元素 */
nums.add(3, 6); // 在索引 3 处插入数字 6
/* 删除元素 */
nums.remove(3); // 删除索引 3 处的元素遍历列表
与数组一样，列表可以根据索引遍历，也可以直接遍历各元素。
java
/* 通过索引遍历列表 */
int count = 0;
for (int i = 0; i < nums.size(); i++) {
count += nums.get(i);
}
/* 直接遍历列表元素，增强for循环 */
for (int num : nums) {
count += num;
}拼接列表
给定一个新列表 nums1 ，我们可以将其拼接到原列表的尾部。
java
/* 拼接两个列表 */
List<Integer> nums1 = new ArrayList<>(Arrays.asList(new Integer[] { 6, 8, 7, 10, 9 }));
nums.addAll(nums1); // 将列表 nums1 拼接到 nums 之后排序列表
完成列表排序后，我们便可以使用在数组类算法题中经常考查的“二分查找”和“双指针”算法。
java
/* 排序列表 */
Collections.sort(nums); // 排序后，列表元素从小到大排列列表实现
许多编程语言内置了列表，例如 Java、C++、Python 等。它们的实现比较复杂，各个参数的设定也非常考究，例如初始容量、扩容倍数等。感兴趣的读者可以查阅源码进行学习。
为了加深对列表工作原理的理解，我们尝试实现一个简易版列表，包括以下三个重点设计。
- 初始容量：选取一个合理的数组初始容量。在本示例中，我们选择 10 作为初始容量。
- 数量记录：声明一个变量
size，用于记录列表当前元素数量，并随着元素插入和删除实时更新。根据此变量，我们可以定位列表尾部，以及判断是否需要扩容。 - 扩容机制：若插入元素时列表容量已满，则需要进行扩容。先根据扩容倍数创建一个更大的数组，再将当前数组的所有元素依次移动至新数组。在本示例中，我们规定每次将数组扩容至之前的 2 倍。
java
public class ArrayList<E> {
/**
* 每次列表扩大的倍数
*/
private static final int EXTEND_RATIO = 2;
/**
* 列表容量
*/
private int capacity = 10;
/**
* 数组（存储列表元素）
*/
private Object[] elementData;
/**
* 列表长度（当前元素数量）
*/
private int size = 0;
public ArrayList() {
elementData = new Object[capacity];
}
/**
* 获取列表长度（当前元素数量）
*
* @return 列表长度（当前元素数量）
*/
public int size() {
return size;
}
/**
* 访问元素
*
* @param index 索引
* @return 元素
*/
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("索引越界");
}
return elementData(index);
}
/**
* 更新元素
*
* @param index 索引
* @param element 元素
*/
public void set(int index, E element) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("索引越界");
}
elementData[index] = element;
}
/**
* 在列表末尾添加元素
*
* @param element 元素
*/
public void add(E element) {
// 元素数量超出容量时，触发扩容机制
if (size == capacity) {
extendCapacity();
}
elementData[size++] = element;
}
/**
* 在列表指定位置插入元素
*
* @param index 索引
* @param element 元素
*/
public void insert(int index, E element) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("索引越界");
}
// 元素数量超出容量时，触发扩容机制
if (size == capacity) {
extendCapacity();
}
// 列表中的元素整体向后移动一位
System.arraycopy(elementData, index, elementData, index + 1, size - index);
// 插入新元素
elementData[index] = element;
// 列表长度加 1
size++;
}
/**
* 删除指定位置的元素并返回该元素
*
* @param index 索引
* @return 被删除的元素
*/
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("索引越界");
}
// 记录被删除的元素
E num = elementData(index);
// 列表中的元素整体向前移动一位
System.arraycopy(elementData, index + 1, elementData, index, size - index - 1);
// 列表长度减 1
size--;
// 返回被删除的元素
return num;
}
/**
* 将列表转换为数组
*
* @return 数组
*/
public Object[] toArray() {
// 仅转换有效长度范围内的列表元素
Object[] res = new Object[size];
// 将有效长度范围内的元素复制到新数组中
System.arraycopy(elementData, 0, res, 0, size);
return res;
}
/**
* 列表扩容
*/
private void extendCapacity() {
// 新数组容量为原数组容量的 extendRatio 倍
int newCapacity = capacity * EXTEND_RATIO;
// 创建一个长度为原数组 extendRatio 倍的新数组
Object[] newArr = new Object[newCapacity];
// 将原数组中的所有元素复制到新数组中
System.arraycopy(elementData, 0, newArr, 0, size);
// 原数组引用指向新数组
elementData = newArr;
// 新数组容量设置为原数组容量的 extendRatio 倍
capacity = newCapacity;
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
}java
class ArrayListTest {
@Test
public void test() {
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(3);
list.add(2);
list.add(5);
list.add(4);
Assertions.assertArrayEquals(new Integer[]{1, 3, 2, 5, 4}, list.toArray());
Assertions.assertEquals(2, list.get(2));
Assertions.assertEquals(5, list.remove(3)); // 1, 3, 2, 4
Assertions.assertEquals(4, list.size());
list.set(3, 6);
Assertions.assertEquals(6, list.get(3)); // 1, 3, 2, 6
list.insert(4, 7); // 1, 3, 2, 6, 7
list.insert(0, 8); // 8, 1, 3, 2, 6, 7
Assertions.assertArrayEquals(new Integer[]{8, 1, 3, 2, 6, 7}, list.toArray());
}
}