LinkedList 和 ArrayList 一样是集合 List 的实现类, 虽然较之 ArrayList, 其使用场景并不多, 但同样有用到的时候, 那么接下来, 我们来认识一下它.
一. 定义一个 LinkedList
- public static void main(String[] args) {
- List<String> stringList = new LinkedList<>();
- List<String> tempList = new ArrayList<>();
- tempList.add("牛魔王");
- tempList.add("蛟魔王");
- tempList.add("鹏魔王");
- tempList.add("狮驼王");
- tempList.add("猕猴王");
- tempList.add("禺贼王");
- tempList.add("美猴王");
- List<String> stringList2 = new LinkedList<>(tempList);
- }
上面代码中采用了两种方式来定义 LinkedList, 可以定义一个空集合, 也可以传递已有的集合, 将其转化为 LinkedList. 我们看一下源码
- public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
- transient int size = 0;
- /**
- * Pointer to first node.
- * Invariant: (first == null && last == null) ||
- * (first.prev == null && first.item != null)
- */
- transient Node<E> first;
- /**
- * Pointer to last node.
- * Invariant: (first == null && last == null) ||
- * (last.next == null && last.item != null)
- */
- transient Node<E> last;
- /**
- * Constructs an empty list.
- */
- public LinkedList() {
- }
- /**
- * Constructs a list containing the elements of the specified
- * collection, in the order they are returned by the collection's
- * iterator.
- *
- * @param c the collection whose elements are to be placed into this list
- * @throws NullPointerException if the specified collection is null
- */
- public LinkedList(Collection<? extends E> c) {
- this();
- addAll(c);
- }
- }
LinkedList 继承了 AbstractSequentialList 类, 实现了 List 接口, AbstractSequentialList 中已经实现了很多方法, 如 get(int index),set(int index, E element),add(int index, E element) 和 remove(int index), 这些方法是我们集合操作时使用最多的, 不过这些方法在 LinkedList 中都已经被重写了, 而抽象方法在 LinkedList 中有了具体实现. 因此我们回到 LinkedList 类
LinkedList 类中定义了三个变量
size: 集合的长度
first: 双向链表头部节点
last: 双向链表尾部节点
针对 first 变量和 last 变量, 我们看到是 Node 类的实体, 这是一个静态内部类, 关于静态内部类的讲解, 我们在 static 五大应用场景 https://www.cnblogs.com/LiaHon/p/11075178.html 一章已经有说明
- 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;
- }
- }
我们知道 LinkedList 是通过双向链表实现的, 而双向链表就是通过 Node 类来体现的, 类中通过 item 变量保存了当前节点的值, 通过 next 变量指向下一个节点, 通过 prev 变量指向上一个节点.
二. LinkedList 常用方法
1. get(int index)
我们知道随机读取元素不是 LinkedList 所擅长的, 读取效率比起 ArrayList 也低得多, 那么我来看一下为什么
- public E get(int index) {
- checkElementIndex(index);
- return node(index).item;
- }
- /**
- * 返回一个指定索引的非空节点.
- */
- Node<E> node(int index) {
- // assert isElementIndex(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;
- }
- }
从上述代码中我们可以看到 get(int index)方法是通过 node(int index)来实现的, 它的实现机制是:
比较传入的索引参数 index 与集合长度 size/2, 如果是 index 小, 那么从第一个顺序循环, 直到找到为止; 如果 index 大, 那么从最后一个倒序循环, 直到找到为止. 也就是说越靠近中间的元素, 调用 get(int index 方法遍历的次数越多, 效率也就越低, 而且随着集合的越来越大, get(int index)执行性能也会指数级降低. 因此在使用 LinkedList 的时候, 我们不建议使用这种方式读取数据, 可以使用 getFirst(),getLast()方法, 将直接用到类中的 first 和 last 变量.
2. add(E e) 和 add(int index, E element)
大家都在说 LinkedList 插入, 删除操作效率比较高, 以 stringList.add("猪八戒")为例来看到底发生了什么?
在 LinkedList 中我们找到 add(E e)方法的源码
- public boolean add(E e) {
- linkLast(e);
- return true;
- }
- /**
- * 设置元素 e 为最后一个元素
- */
- 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++;
- }
很好理解:
情况 1: 假如 stringList 为空, 那么添加进来的 node 就是 first, 也是 last, 这个 node 的 prev 和 next 都为 null;
情况 2: 假如 stringList 不为空, 那么添加进来的 node 就是 last,node 的 prev 指向以前的最后一个元素, node 的 next 为 null; 同时以前的最后一个元素的 next.
而如果通过 stringList.add(1, "猪八戒")这种方式将元素添加到集合中呢?
- // 在指定位置添加一个元素
- public void add(int index, E element) {
- checkPositionIndex(index);
- if (index == size)
- linkLast(element);
- else
- linkBefore(element, node(index));
- }
- /**
- * 在一个非空节点前插入一个元素
- */
- 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++;
- }
其实从代码中看到和 add(E e)的代码实现没有本质区别, 都是通过新建一个 Node 实体, 同时指定其 prev 和 next 来实现, 不同点在于需要调用 node(int index)通过传入的 index 来定位到要插入的位置, 这个也是比较耗时的, 参考上面的 get(int index)方法.
其实看到这里, 大家也都明白了.
LinkedList 插入效率高是相对的, 因为它省去了 ArrayList 插入数据可能的数组扩容和数据元素移动时所造成的开销, 但数据扩容和数据元素移动却并不是时时刻刻都在发生的.
3. remove(Object o) 和 remove(int index)
这里 removeFirst()和 removeLast()就不多说了, 会用到类中定义的 first 和 last 变量, 非常简单, 我们看一下 remove(Object o) 和 remove(int index)源码
- // 删除某个对象
- public boolean remove(Object o) {
- if (o == null) {
- for (Node<E> x = first; x != null; x = x.next) {
- if (x.item == null) {
- unlink(x);
- return true;
- }
- }
- } else {
- for (Node<E> x = first; x != null; x = x.next) {
- if (o.equals(x.item)) {
- unlink(x);
- return true;
- }
- }
- }
- return false;
- }
- // 删除某个位置的元素
- public E remove(int index) {
- checkElementIndex(index);
- return unlink(node(index));
- }
- // 删除某节点, 并将该节点的上一个节点 (如果有) 和下一个节点 (如果有) 关联起来
- E unlink(Node<E> x) {
- 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;
- }
其实实现都非常简单, 先找到要删除的节点, remove(Object o)方法遍历整个集合, 通过 == 或 equals 方法进行判断; remove(int index)通过 node(index)方法.
4. LinkedList 遍历
我们主要列举一下三种常用的遍历方式,
普通 for 循环, 增强 for 循环, Iterator 迭代器
- public static void main(String[] args) {
- LinkedList<Integer> list = getLinkedList();
- // 通过快速随机访问遍历 LinkedList
- listByNormalFor(list);
- // 通过增强 for 循环遍历 LinkedList
- listByStrengThenFor(list);
- // 通过快迭代器遍历 LinkedList
- listByIterator(list);
- }
- /**
- * 构建一个 LinkedList 集合, 包含元素 50000 个
- * @return
- */
- private static LinkedList<Integer> getLinkedList() {
- LinkedList list = new LinkedList();
- for (int i = 0; i <50000; i++){
- list.add(i);
- }
- return list;
- }
- /**
- * 通过快速随机访问遍历 LinkedList
- */
- private static void listByNormalFor(LinkedList<Integer> list) {
- // 记录开始时间
- long start = System.currentTimeMillis();
- int size = list.size();
- for (int i = 0; i <size; i++) {
- list.get(i);
- }
- // 记录用时
- long interval = System.currentTimeMillis() - start;
- System.out.println("listByNormalFor:" + interval + "ms");
- }
- /**
- * 通过增强 for 循环遍历 LinkedList
- * @param list
- */
- public static void listByStrengThenFor(LinkedList<Integer> list){
- // 记录开始时间
- long start = System.currentTimeMillis();
- for (Integer i : list) { }
- // 记录用时
- long interval = System.currentTimeMillis() - start;
- System.out.println("listByStrengThenFor:" + interval + "ms");
- }
- /**
- * 通过快迭代器遍历 LinkedList
- */
- private static void listByIterator(LinkedList<Integer> list) {
- // 记录开始时间
- long start = System.currentTimeMillis();
- for(Iterator iter = list.iterator(); iter.hasNext();) {
- iter.next();
- }
- // 记录用时
- long interval = System.currentTimeMillis() - start;
- System.out.println("listByIterator:" + interval + "ms");
- }
执行结果如下:
- listByNormalFor:1067 ms
- listByStrengThenFor:3 ms
- listByIterator:2 ms
通过普通 for 循环随机访问的方式执行时间远远大于迭代器访问方式, 这个我们可以理解, 在前面的 get(int index)方法中已经有过说明, 那么为什么增强 for 循环能做到迭代器遍历差不多的效率?
通过反编译工具后得到如下代码
- public static void listByStrengThenFor(LinkedList<Integer> list)
- {
- long start = System.currentTimeMillis();
- Integer localInteger;
- for (Iterator localIterator = list.iterator(); localIterator.hasNext();
- localInteger = (Integer)localIterator.next()) {}
- long interval = System.currentTimeMillis() - start;
- System.out.println("listByStrengThenFor:" + interval + "ms");
- }
很明显了, 增强 for 循环遍历时也调用了迭代器 Iterator, 不过多了一个赋值的过程.
还有类似于 pollFirst(),pollLast()取值后删除的方法也能达到部分的遍历效果.
三. 总结
本文基于 java8 从定义一个 LinkList 入手, 逐步展开, 从源码角度分析 LinkedList 双向链表的结构是如何构建的, 同时针对其常用方法进行分析, 包括 get,add,remove 以及常用的遍历方法, 并简单的说明了它的插入, 删除操作为何相对高效, 而取值操作性能相对较低, 若有不对之处, 请批评指正, 望共同进步, 谢谢!
来源: http://www.bubuko.com/infodetail-3107942.html