本文介绍了线性表的概念，详细对比了基于数组的顺序表（ArrayList）和基于链表的链表（LinkedList）。内容涵盖两者的构造、常用操作、遍历方式、底层扩容机制及源码实现原理。重点分析了 ArrayList 在插入删除时的搬移开销与空间浪费问题，以及 LinkedList 在任意位置操作的效率优势，帮助读者理解两种数据结构的核心区别与适用场景。
在集合框架中，List 是一个接口。从数据结构的角度看，List 就是一个线性表，即 n 个具有相同类型元素的有限序列，在该序列上可以执行增删改查以及变量等操作。
常见的线性表：顺序表、链表、栈、队列……
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
线性结构规定：一个元素只能有一个前驱，一个后继。如果有多个前驱或后继，就不是线性结构。
注意：List 是个接口，并不能直接用来实例化。
如果要使用，必须去实例化 List 的实现类。在集合框架中，ArrayList 和 LinkedList 都实现了 List 接口。
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
在集合框架中，ArrayList 是一个普通的类，实现了 List 接口。
![顺序表结构示意]
注意：
| 方法 | 解释 |
|---|---|
| ArrayList() | 无参构造 |
| ArrayList(int initialCapacity) | 指定顺序表初始容量 |
public static void main(String[] args) {
List<Integer> l1 = new ArrayList<>(); // 实例化一个空表，推荐写法
List<Integer> l2 = new ArrayList<>(10); // 实例化一个初始容量为 10 的空表
List<Integer> l3 = new ArrayList<>(l2); // 实例化出的 l3，与 l2 中的元素一致
}
ArrayList 虽然提供的方法比较多，但是常用方法如下所示，需要用到其他方法时，可以查看 JAVA 帮助手册。
| 方法 | 解释 |
|---|---|
| boolean add(E e) | 尾插 e |
| void add(int index, E e) | 把 e 插入到 index 位置 |
| E remove(int index) | 删除 index 位置的元素 |
| E get(int index) | 获取 index 位置的元素 |
| E set(int index, E e) | 将 index 位置元素设置为 e |
| void clear() | 清空 |
| boolean contains(Object o) | 判断 o 是否在线性表中 |
| int indexOf(Object o) | 返回第一个 o 所在的下标 |
| int lastIndexOf(Object o) | 返回最后一个 o 所在下标 |
特别提醒：虽然 ArrayList 中提供了常见的方法，但是我们仍需掌握方法的底层原理。
ArrayList 可以使用三种方法进行遍历：
public static void main(String[] args) {
List<Integer> l1 = new ArrayList<>();
l1.add(1);
l1.add(2);
l1.add(3);
l1.add(4);
l1.add(5);
l1.add(6);
for (int i = 0; i < l1.size(); i++) {
System.out.println(l1.get(i));
}
}
public static void main(String[] args) {
List<String> l2 = new ArrayList<>();
l2.add("1");
l2.add("2");
l2.add("3");
l2.add("4");
for (String l : l2) {
System.out.println(l);
}
}
注意：并不是所有的类都能写进 for-each 循环中，写进 for-each 循环中的类要求必须实现 Iterable 接口。
public static void main(String[] args) {
List<String> l3 = new ArrayList<>();
l3.add("1");
l3.add("2");
l3.add("3");
l3.add("4");
Iterator<String> iterator = l3.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
ArrayList 最常使用的遍历方式是：for 循环 以及 foreach。
ArrayList 内部持有一个数组，构造时设置的初始容量就是数组的大小，当 ArrayList 发现空间不够的时候，就会申请额外的空间，这就自动扩容机制。
自动扩容共有以下几步：
set 方法
![set 方法示意图]
lastIndexOf 方法
![lastIndexOf 方法示意图]
indexOf 方法
![indexOf 方法示意图]
clear 方法
![clear 方法示意图]
contains 方法
![contains 方法示意图]
toString 方法
![toString 方法示意图]
remove 方法
![remove 方法示意图]
get 方法
![get 方法示意图]
add 方法
![add 方法示意图]
自动扩容操作
![自动扩容操作示意图]
获取元素个数
![获取元素个数示意图]
提供构造方法
![提供构造方法示意图]
为了解决以上问题，于是我们引入了链表，可实际上链表真的会解决这些问题吗？还是会带来更多的问题呢？
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。
![链表结构示意]
实际中链表的结构非常多样，以下情况组合起来就有 8 种链表结构：
然有这么多的链表的结构，但是我们重点掌握两种：
![无头单向非循环链表示意图]
LinkedList 的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
在集合框架中，LinkedList 也实现了 List 接口，具体如下：
![LinkedList 接口图]
注意：
![LinkedList 构造示意图]
![LinkedList 常见操作示意图]
![ArrayList 和 LinkedList 区别对比图]
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online