线性表分为顺序表和链表。顺序表基于数组，支持随机访问但插入删除需移动元素；链表基于节点引用，插入删除效率高但无随机访问能力。本文对比了 ArrayList 和 LinkedList 的底层结构、常用操作及扩容机制，分析了各自的时间复杂度与空间浪费问题，帮助理解 Java 集合框架中 List 接口的两种核心实现。
在集合框架中，List 是一个接口。从数据结构的角度看，List 就是一个线性表，即 n 个具有相同类型元素的有限序列，在该序列上可以执行增删改查以及变量等操作。
常见的线性表：顺序表、链表、栈、队列……
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
线性结构规定：一个元素只能有一个前驱，一个后继。如果有多个前驱或后继，就不是线性结构。
注意：List 是个接口，并不能直接用来实例化。
如果要使用，必须去实例化 List 的实现类。在集合框架中，ArrayList 和 LinkedList 都实现了 List 接口。
ArrayList ⇒ 顺序表 LinkedList ⇒ 链表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
在集合框架中，ArrayList 是一个普通的类，实现了 List 接口，具体框架图如下：
注意：
*1. ArrayList 是以泛型方式实现的，使用时必须要先实例化 2. ArrayList 底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表
| 方法 | 解释 |
|---|---|
| ArrayList() | 无参构造 |
| ArrayList(int initialCapatity) | 指定顺序表初始容量 |
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 发现空间不够的时候，就会申请额外的空间，这就自动扩容机制。
自动扩容共有以下几步：
*1. 发现空间不够之后，立刻创建一个更大的数组（为了防止申请空间过大浪费，ArrayList 的策略是每次扩容为原来大小的 1.5 倍） *2. 把旧数组中的元素拷贝到新的数组中 *3. 添加新的元素 4. 自动释放旧数组
set 方法
lastIndexOf 方法
indexOf 方法
clear 方法
contains 方法
toString 方法
remove 方法
get 方法
add 方法
自动扩容操作
获取元素个数
提供构造方法
1. ArrayList 底层使用连续的空间，任意位置插入或删除元素时，需要将该位置后序元素整体往前或者往后搬移，故时间复杂度为 O（N）。
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈 1.5 倍的增长，势必会有一定的空间浪费。例如当前容量为 100，满了以后增容到 150，我们再继续插入了 5 个数据，后面没有数据插入了，那么就浪费了 45 个数据空间。
为了解决以上问题，于是我们引入了链表，可实际上链表真的会解决这些问题吗？还是会带来更多的问题呢？
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。
实际中链表的结构非常多样，以下情况组合起来就有 8 种链表结构：
然有这么多的链表的结构，但是我们重点掌握两种：
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
LinkedList 的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
在集合框架中，LinkedList 也实现了 List 接口，具体如下：
注意：
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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