数据结构：顺序表与链表

特别提醒：虽然 ArrayList 中提供了常见的方法，但是我们仍需掌握方法的底层原理。

2.5 ArrayList 的遍历

ArrayList 可以使用三种方法进行遍历：

1. for 循环

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));
    }
}

2. for-each

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 接口。

3. 迭代器

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。

2.6 ArrayList 的自动扩容机制

ArrayList 内部持有一个数组，构造时设置的初始容量就是数组的大小，当 ArrayList 发现空间不够的时候，就会申请额外的空间，这就自动扩容机制。

自动扩容共有以下几步：

1. 发现空间不够之后，立刻创建一个更大的数组（为了防止申请空间过大浪费，ArrayList 的策略是每次扩容为原来大小的 1.5 倍）
2. 把旧数组中的元素拷贝到新的数组中
3. 添加新的元素
4. 自动释放旧数组

2.7 ArrayList 常用方法的具体实现代码（重点）

set 方法

![set 方法示意图]

lastIndexOf 方法

![lastIndexOf 方法示意图]

indexOf 方法

![indexOf 方法示意图]

clear 方法

![clear 方法示意图]

contains 方法

![contains 方法示意图]

toString 方法

![toString 方法示意图]

remove 方法

![remove 方法示意图]

get 方法

![get 方法示意图]

add 方法

![add 方法示意图]

自动扩容操作

![自动扩容操作示意图]

获取元素个数

![获取元素个数示意图]

提供构造方法

![提供构造方法示意图]

2.8 ArrayList 当前面临的问题

1. ArrayList 底层使用连续的空间，任意位置插入或删除元素时，需要将该位置后序元素整体往前或者往后搬移，故时间复杂度为 O(N)。
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈 1.5 倍的增长，势必会有一定的空间浪费。例如当前容量为 100，满了以后增容到 150，我们再继续插入了 5 个数据，后面没有数据插入了，那么就浪费了 45 个数据空间。

为了解决以上问题，于是我们引入了链表，可实际上链表真的会解决这些问题吗？还是会带来更多的问题呢？

3. LinkedList 与链表

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

3.1 链表的概念

![链表结构示意]

实际中链表的结构非常多样，以下情况组合起来就有 8 种链表结构：

1. 单向或双向
2. 带头或者不带头
3. 循环或者非循环

然有这么多的链表的结构，但是我们重点掌握两种：

1. 无头双向链表：在 Java 的集合框架库中 LinkedList 底层实现就是无头双向循环链表。
2. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

![无头单向非循环链表示意图]

3.2 LinkedList 简介

LinkedList 的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

在集合框架中，LinkedList 也实现了 List 接口，具体如下：

![LinkedList 接口图]

注意：

1. LinkedList 实现了 List 接口
2. LinkedList 的底层使用了双向链表
3. LinkedList 的任意位置插入和删除元素时效率比较高，时间复杂度为 O(1)

3.3 LinkedList 的构造

![LinkedList 构造示意图]

3.4 LinkedList 常见操作

![LinkedList 常见操作示意图]

3.5 LinkedList 常用方法的具体实现代码（重点）

4. ArrayList 和 LinkedList 的区别

![ArrayList 和 LinkedList 区别对比图]