数据结构：链表
1. 链表
1.1 链表的概念
我们知道顺序表的缺点很明显，那就是当频繁的插入和删除时，会导致大量的频繁的移动元素，这显然就会消耗时间。
那么链表就很好的解决了这个问题，链表也称为线性表的链式存储结构，其特征就是其中的元素不需要考虑相邻位置，每个元素都知道下一个元素的位置，这样，我们只需要知道第一个元素的地址就能遍历所有元素。
1.2 链表的结构
如图所示，常见的链表是这样表示的，一个元素会存放下个元素的地址，这样就不需要在空间上相邻排序，也能找到下个点。
1.3 链表的表示方法
如图，用Java可以这样表示一个链表，每个节点存放一个值val和下一个点的地址next。
当我们要指定一个点为头节点时，可以让head = next，比如这样：
ListNode head = next;这样一来，我们就算确定了头节点，然后就可以进行插入和删除，修改查找等工作了。
我们以插入节点为例：
使用头插法，就是当我们插入数据时，先让该数据的下一个数据的地址指向head，更新 head 为 newNode，使新节点成为新的头节点，这样就完成了一个点的插入。接下来再插入的时候就同理，把新的点的next地址指向head，再把整个节点给head。这样一来每次插入点点都在head处，也就是最前面。
通过debug可以看到整个插入的过程。
当我们明白了链表的结构，除了实现头插法，我们还可以写出其他的方法实现，比如尾插法，任意位置插入，查找，删除等等。
1.4 其他链表
我们前面说的链表是有头的单向非循环链表，其实链表还分很多种情况，比如，单向双向，有头无头，循环非循环等等。
其实常用到的也就两种：
无头单向非循环链表：结构简单，一般不会单独用来存数据
无头双向链表：其在Java的集合框架库中LinkedList底层实现就是无头双向循环链表
这些我们可以自己实现也可以直接使用Java中的LinkedList。
2. LinkedList的结构
LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
其结构如下：
在集合框架中LinkedList实现了List接口。
3. LinkedList的使用
我们可以直接调用LinkedList类来直接使用其接口
| 方法 | 对应解释 |
| boolean add(E e) | 尾插e |
| void add(int index, E element) | 尾插e到index位置 |
| boolean addAll(Collection<? extends E> c) | 尾插c中的元素 |
| E remove(int index) | 删除index位置元素 |
| boolean remove(Object o) | 删除遇到的第一个o |
| E get(int index) | 获取index位置元素 |
| E set(int index, E element) | 将index位置元素设为elem |
| void clear() | 清空 |
| boolean contains(Object o) | o是否在表中 |
| int indexOf(Object o) | 返回第一个o所在的下标 |
| int lastIndexOf(Object o) | 返回最后一个o所在的下标 |
| List<E> subList(int fromIndex, int toIndex) | 截取部分list |
4. ArrayList 和 LinkedList的区别
在区别方面：
1. 遍历：ArrayList的遍历方式有三种：for循环下标，for each循环，迭代器；而LinkedList的遍历方式有两种，没有for循环下标，因为其存放地址的特性，无法获取下标。
2. 存储空间上：ArrayList物理上一定连续；而LinkedList逻辑上连续，但物理上不一定连续。
3. 随机访问：ArrayList 支持O(1)；LinkedList 不支持：O(N)。
4. 头插：ArrayList需要搬移元素，效率低O(N)；LinkedList只需修改引用的指向，时间复杂度为O(1)。
5. 插入：ArrayList空间不够时需要扩容；LinkedList没有容量的概念。
6. 应用场景：ArrayList元素高效存储+频繁访问；LinkedList任意位置插入和删除频繁。
5. 总结
通过ArrayList 和 LinkedList，我们知道了顺序表在物理结构上存在两种不同的存储方式，两种方式各有千秋。本质是要理解链表的底层结构，在空间上不需要相邻，只需要知道下一个元素的位置就能找到。