LinkedList 介绍
还是和 ArrayList 同样的套路, 顾名思义, linked, 那必然是基于链表实现的, 链表是一种线性的储存结构, 将储存的数据存放在一个存储单元里面, 并且这个存储单元里面还维护了下一个存储单元的地址. 在 LinkedList 的链表储存单元中, 不仅存放了下一个存储单元的地址, 还存放了上一个单元的储存地址, 因为 Linked 是双向链表, 双向链表就是可以通过链表中任意一个存储单元可以获取到上一个存储单元和下一个存储单元.
先看一下这个神秘的储存单元, 在 LinkedList 的内部类中声明:
- private static class Node<E> {
- E item;
- Node<E> next;
- Node<E> prev;
- Node(Node<E> prev, E element, Node<E> next) {
- this.item = element;
- this.next = next;
- this.prev = prev;
- }
- }
Node 就是 LinkedList 的储存单元, 在 JDK1.6 中叫 Entry, 不过结构还是一样的, 里面有三个变量一个带这三个参数的构造方法, 这三个变量分别是
1.item: 存储在存储单元 Node 中的元素
2.next: 下一个存储单元
3.prev: 下一个存储单元
LinkedList 的关注点
1. 是否允许为空: 是
2. 是否允许重复数据: 是
3. 是否有序: 是
4. 是否线程安全: 否
和之前讲的 ArrayList 的四个关注点一模一样
LinkedList 的声明:
- public class LinkedList<E>
- extends AbstractSequentialList<E>
- implements List<E>, Deque<E>, Cloneable, java.io.Serializable
- {
- transient int size = 0;
- transient Node<E> first;
- transient Node<E> last;
- ...
- }
LinkedList 除了实现 List,Cloneable 和 Serializable 接口外还实现了 Deque 接口, 说明 LinkedList 具有队列的特性, 可以当做队列使用
举个简单的小栗子:
- List<String> list= new LinkedList<>();
- list.add("11");
- list.add("22");
- list.add("33");
LinkedList 提供了两种构造方法, 例子使用的是第一种也是最常用的无参构造器:
- public LinkedList() {
- }
这个构造方法没有执行其他任何的操作, 这与 jdk1.6 有所不同, jdk1.6 中声明了一个 header 节点, 然后执行了 header.next = header.previous = header,jdk1.8 中声明了 first 和 last 两个节点, 但是构造的时候没有操作这两个节点.
第二种构造器和 ArrayList 一样提供了一个传入集合的构造方法 public LinkedList(Collection<? extends E> c)
添加元素
接着看第二行 list.add("11") 做了什么:
- public boolean add(E e) {
- linkLast(e);
- return true;
- }
- void linkLast(E e) {
- final Node<E> l = last;
- final Node<E> newNode = new Node<>(l, e, null);
- last = newNode;
- if (l == null)
- first = newNode;
- else
- l.next = newNode;
- size++;
- modCount++;
- }
LinkedList 的 add 方法执行的是 linkLast 方法, linkLast 方法就是把元素 e 链接成列表的最后一个元素,
1. 首先声明一个变量 l, 将这个 l 指向 last 也就是列表最后一个节点
2.new 一个新的 Node 节点 newNode, 这个 newNode 就是新增元素的储存单元, 根据之前给的 Node 的构造方法, 它创建了一个上一个节点为 l 节点, 储存元素为你新增的元素 e, 下一个节点为 null 的储存单元
3. 将代表列表最后一个节点的 last 变量指向新的节点 newNode, 也就是将列表的最后一个储存单元变成了新的 newNode 节点
4. 如果 l==null, 也就是列表最后一个节点是 null, 那么列表第一个节点也是 newNode, 也就是说如果列表是空, newNode 就是第一个也是目前唯一一个储存单元, 它既是头也是尾. 如果之前的最后一个储存单元不是 null, 就将之前的储存单元的下一个节点地址改为新增的储存单元
可能说的比较绕比较抽象, 画图表示一下:
假设 null 的内存地址是 0x0000, 新增元素 "11" 的存储单元地址是 0x0001, 元素 "22" 储存单元地址是 0x0002, 元素 "33" 储存单元地址是 0x0003, 每一步修改的地方我都用红色标记出来
查找元素
LinkedList 查找元素也是使用的 get 方法, 当然也有别的方法, 先看一下 get 方法怎么写的:
- public E get(int index) {
- checkElementIndex(index); //index>= 0 && index <size
- return node(index).item;
- }
- Node<E> node(int index) {
- if (index <(size>> 1)) {
- Node<E> x = first;
- for (int i = 0; i <index; i++)
- x = x.next;
- return x;
- } else {
- Node<E> x = last;
- for (int i = size - 1; i> index; i--)
- x = x.prev;
- return x;
- }
- }
LinkedList 查找元素也是先检查下标, 检查的判断已经写在第二行的备注中, 然后通过 node() 方法去寻找元素
查询对应下标节点的时候首先用了一个判断, 这个判断很有意思, 它判断指定下标 index 是否小于元素个数的一半, 如果小于一半也就是你指定的下标位于列表前半段它就从列表第一个节点开始遍历, 通过循环获取每个节点的 next 节点, 如果大于一半位于列表后半段就从列表最后一个节点开始遍历, 循环获取每个节点的 prev 节点, 这样做的好处就是假如列表有 1000 个元素, get(999) 就得遍历 999 次才能找到元素, 这就是双向链表的好处, 通过维护前置节点, 虽然增加了编程复杂度, 也消耗了更多的空间, 却能提升查找效率.
注: 即便 LinkedList 使用了这种巧妙的思想, 但是查找速度还是不及 ArrayList 的随机访问模式, 毕竟需要遍历
删除元素
LinkedList 删除元素和 ArrayList 一样支持按照下标删除和按照元素删除, 举个例子:
- List<String> list = new LinkedList<>();
- list.add("11");
- list.add("22");
- list.add("33");
- list.remove(1);
看看 remove 方法代码:
- public E remove(int index) {
- checkElementIndex(index);
- return unlink(node(index));
- }
- E unlink(Node<E> x) {
- // assert x != null;
- final E element = x.item;
- final Node<E> next = x.next;
- final Node<E> prev = x.prev;
- if (prev == null) {
- first = next;
- } else {
- prev.next = next;
- x.prev = null;
- }
- if (next == null) {
- last = prev;
- } else {
- next.prev = prev;
- x.next = null;
- }
- x.item = null;
- size--;
- modCount++;
- return element;
- }
先检查下标, 然后通过 node 方法找到指定下标的元素, 交给 unlink 方法去执行删除的操作, 说一下 unlink 的步骤
1. 先获取当前节点 x 的元素, 当前节点 x 的下一个储存单元节点 next 和上一个储存单元的节点 prev
2. 如果上一个储存单元为 null, 那说明当前节点是链表的第一个节点, 所以需要把代表第一个节点的 first 变量指向当前 x 节点的 next 节点, 如果下一个储存单元为 null, 当前节点为链表的最后一个节点, 同样的需要把 last 节点指向 x 节点的 prev 节点
3. 如果既不是第一个节点也不是最后一个节点这种特殊情况, 也就是执行两个 else 里面的操作, 先把 x 节点的上一个节点的 next 指向 x 节点的下一个节点, 并且把 x.prev 赋值 null, 然后把 x 节点的下一个节点的 prev 指向 x 的上一个节点, 并且把 x.next 赋值 null
4. 最后把当前 x 节点的元素赋值 null, 元素个数减一
经过步骤 2 和步骤 3, 成功的切断了 x 节点这个储存单元与上下节点的联系, 经过步骤 234 把 x 节点的 prev,element,next 全部变成了 null, 让 GC 去回收它, 这个步骤有点绕画图了解一下 remove 方法的执行:
假设元素'11'的储存单元的地址是 0x0001, 元素'22'的储存单元的地址是 0x0002, 元素'33'的储存单元的地址是 0x0003, 现在 first 指向 0x0001,last 指向 0x0003, 执行 list.remove(1) 操作, 修改的地方我用红色字体标记
插入元素
与 ArrayList 一样的, Linked 同样提供了在指定下标插入元素的方法, 之所以放在删除之后讲是因为插入元素和删除执行的操作有些类似, 举个例子:
- 1 List<String> list = new LinkedList<>();
- 2 list.add("11");
- 3 list.add("33");
- 5 list.add(1,"22");
直接看第四行 list.add(1,"22") 执行了什么:
- public void add(int index, E element) {
- checkPositionIndex(index);
- if (index == size)
- linkLast(element);
- else
- linkBefore(element, node(index));
- }
还是先检查如果插入的下标 (index>= 0 && index <= size), 如果下标正好是元素的个数就相当于往链表最后插入一个元素, 执行之前介绍过的 linkLast 方法, 大部分情况插入都是往链表中间插入元素执行 linkBefore 方法:
- void linkBefore(E e, Node<E> succ) {
- // assert succ != null;
- final Node<E> pred = succ.prev;
- final Node<E> newNode = new Node<>(pred, e, succ);
- succ.prev = newNode;
- if (pred == null)
- first = newNode;
- else
- pred.next = newNode;
- size++;
- modCount++;
- }
往列表中间插入元素的话会先使用 node 方法查到对应下标的储存单元节点, 记录此节点的前置节点 prev, 然后新建一个前置节点为 index 下标原储存单元前置节点, 元素为 e, 后置节点为 index 下标原储存单元的储存单元节点, 如果前置节点为 nulll, 就将 first 节点指向新建的节点, 否则将 index 下标原储存单元的前置节点改为新增的节点 newNode, 如图:
假设元素'11'的储存单元的地址是 0x0001, 元素'33'的储存单元的地址是 0x0002, 新插入的元素'22'的储存单元的地址是 0x0002, 现在 first 指向 0x0001,last 指向 0x0002, 执行 list.add(1,"22") 操作, 修改的地方我用红色字体标记
图上半部分是插入前, 图下半部分是插入后, 抛开插入和删除的储存单元不谈, 这两个操作都是改变上一个储存单元节点的 next 地址和下一个储存单元的 prev 地址, 是不是很相似? 所以只要理解了 LinkedList 的这种结构, LinkedList 这些操作也是很好理解的.
拿 ArrayList 对比总结一下 LinkedList
1. 查找元素的速度, 如果是按照下标查找那么 ArrayList 效率肯定是高于 LinkedList 的, ArrayList 支持随机访问, 而 LinkedList 需要遍历
2. 顺序添加元素, 虽然 LinkedList 顺序添加也比较方便, 但是需要 new 对象并且需要修改一些储存单元的引用, 而 ArrayList 的数组是事先 new 好的, 只需要往指定位置插入元素就行, 所以大部分情况下 ArrayList 优于 LinkedList, 特殊情况 ArrayList 添加元素需要扩容了, 随着元素数量的增加, ArrayList 扩容会越来越慢
3. 删除插入的速度, LinkedList 删除插入操作效率几乎是固定的, 先寻址, 后修改前后 Node 的 next,prev 引用地址, 而 ArrayList 寻址较快, 慢在复制数组元素, 所以如果插入, 删除的元素是在数据结构的前半段尤其是非常靠前的位置的时候, LinkedList 的效率将大大快过 ArrayList; 越往后, ArrayList 要批量 copy 的元素越来越少, 速度会越来越快, 所以删除插入操作并不能说谁一定快
4. 遍历元素, 前面说过 ArrayList 是实现了 RandomAccess 接口的支持随机访问, 而 LinkedList 是没有实现这个接口的, 所以 ArrayList 在使用普通 for 循环会更快, 而 LinkedList 使用 foreach 循环会更快, 那么它们使用各自最快的遍历方式谁更快呢?
我们做个测试:
- public class TestList {
- private static int size = 100000;
- public static void loop(List<Integer> list){
- long startTime = System.currentTimeMillis();
- for (int i = 0; i <size; i++) {
- list.get(i);
- }
- System.out.println(list.getClass().getSimpleName() + "for 循环遍历时间:" + (System.currentTimeMillis() - startTime) + "ms");
- startTime = System.currentTimeMillis();
- for (Integer i: list) {
- }
- System.out.println(list.getClass().getSimpleName() + "foreach 循环遍历时间:" + (System.currentTimeMillis() - startTime) + "ms");
- }
- public static void main(String[] args) {
- List<Integer> arrayList = new ArrayList<>();
- List<Integer> linkedList = new LinkedList<>();
- for (int i = 0; i < size; i++) {
- arrayList.add(i);
- linkedList.add(i);
- }
- loop(arrayList);
- loop(linkedList);
- }
- }
执行多次的结果:
ArrayListfor 循环遍历时间: 3ms
ArrayListforeach 循环遍历时间: 4ms
LinkedListfor 循环遍历时间: 4638ms
LinkedListforeach 循环遍历时间: 3ms
ArrayListfor 循环遍历时间: 2ms
ArrayListforeach 循环遍历时间: 4ms
LinkedListfor 循环遍历时间: 4753ms
LinkedListforeach 循环遍历时间: 2ms
ArrayListfor 循环遍历时间: 3ms
ArrayListforeach 循环遍历时间: 4ms
LinkedListfor 循环遍历时间: 4520ms
LinkedListforeach 循环遍历时间: 2ms
从执行测试程序的时候就可以看出来, LinkedList 使用普通 for 循环遍历出奇的慢, 而在使用 foreach 遍历的时候 LinkedList 遍历明显更快, 甚至略优于 ArrayList 的 foreach 遍历, 所以在数据量比较大的情况下, 千万不要使用普通 for 循环遍历 LinkedList
来源: https://www.cnblogs.com/saltiest/p/11432703.html