它和另一个类一样, 都属于集合列表这种结构的实现种类。尽管在实际工作中比较它的用途不是特别多见的情形不算少。但是确实也有需要用到它的时候。所以现在大家一起来了解一下这个具体的东西是什么样的存在。它和那个东西一样, 都是叫做List的集合类的实现方式。虽然比起另一个来, 用到的情况确实不多。但是该用的时候还是有用的。那么接下来我们就好好了解一下它。一. 定义一个public static void main(String[] args) {List stringList new LinkedList();List tempList new ArrayList();tempList.add(牛魔王);tempList.add(蛟魔王);tempList.add(鹏魔王);tempList.add(狮驼王);tempList.add(猕猴王);tempList.add(禺贼王);tempList.add(美猴王);List stringList2 new LinkedList(tempList);}在上面的代码里面, 用了两种方法来做定义的这件事, 第一种方法是定义一个那种空白的集合对象, 第二种方法是可以把那些已经存在了的集合作为参数传进去, 让它们变成目标格式的对象, 接下来我们去查看底层源码。public class LinkedList extends AbstractSequentialList implements List, Deque, 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 first;/*** Pointer to last node.* Invariant: (first null last null) ||* (last.next null last.item ! null)*/transient Node 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 collections* iterator.** param c the collection whose elements are to be placed into this list* throws NullPointerException if the specified collection is null*/public LinkedList(Collectionextends E c) {this();addAll(c);}}它继承了 st 类, 另外它还实现了 List 接口。因为在 st 这个类里面, 已经写好了好多方法, 比如 get(int index)、set(int index, E )、add(int index, E ) 这些方法, 还有针对 (int index) 的那个方法。这几个方法就是大家平时在做集合操作的时候, 用得最频繁的那些东西。不过呢, 这些方法在子类当中全都已经被重新定义过了, 也就是说都已经重写了。与此同时, 那些本来应该是抽象的方法, 现在在子类里都有具体的实现代码了, 不再空着了。所以呢, 我们就回到了类这个地方。在这个类里, 它实际做了的定义动作去包含三个变量。对于first变量和last变量, 我们会发现它们是Node类的一个实体, 而Node类是一个静态内部类。关于静态内部类的详细解释, 在五大应用场景这一章节中, 我已经做过相关的说明了。private static class Node {E item;Node next;Node prev;Node(Node prev, E element, Node next) {this.item element;this.next next;this.prev prev;}}我们知道, 这个结构是通过双向链表来实现的, 而双向链表的实现, 又是由Node类来具体体现的, 在Node类里面, 有一个item变量, 它用来保存当前节点所对应的值, 还有一个next变量, 它用来指向后续的那个节点, 同时也会有一个prev变量, 它的作用是指向之前相邻的那一个节点。二. 常用方法1. get(int index)我们知道对于获取元素来说, 它并不是其擅长的事情, 并且它的处理效率相较于其他方式来说是低出非常多的一个状态, 所以接下来我要进行查看和分析, 看看究竟是为什么会产生这样的情况。public E get(int index) {checkElementIndex(index);return node(index).item;}/*** 返回一个指定索引的非空节点.*/Node node(int index) {// assert isElementIndex(index);if (index (size 1)) {Node x first;for (int i 0; i index; i)x x.next;return x;} else {Node x last;for (int i size - 1; i index; i--)x x.prev;return x;}}从上述代码当中, 我们能够看到 get(int index) 这个方法, 是通过 node(int index) 来实现的, 然后它具体的这种实现机制是:需要拿那个传进来的索引参数 index 和集合的长度 size 除以二的结果做一个比较, 要是发现 index 比那个商要小, 就会从第一个元素开始进行正向的循环, 直到把想要的东西找出来为止, 要是发现 index 比那个商要大, 就会从最后一个元素开始进行反向的循环, 直到把想要的东西找出来为止。也就是说, 因为越靠近中间位置的那些元素, 在通过调用带有整数类型参数索引的方法来执行遍历操作的过程当中, 被调用的次数会越来越多, 所以效率方面也会变得越来越低, 并且随着整个集合内部的容量变得越来越大, 这种依靠整数类型的参数索引去获取元素的性能表现, 也会出现非常明显的下降趋势, 以至于达到一种指数级别增长的速度, 因此在平时使用的时候, 我们是坚决不提倡大家采用这种方式来进行数据的读取工作的, 而是建议大家去使用开头和结尾相关的方法, 这样一来就可以直接用到该类里面定义的那两个分别代表第一个元素和最后一个元素的全局变量。2. add(E e) 和 add(int index, E )现在有许多人都在提, 说插入和删除这些操作, 它们的效率是算比较高的, 就拿用.add这个方法, 参数填上一个猪八戒这步动作来看一看, 它实际发生的是什么情况。我们在中找到了这个叫做add的那个方法, 它的源代码是这样写的, 第一个参数是一个叫E的e。public boolean add(E e) {linkLast(e);return true;}/*** 设置元素e为最后一个元素*/void linkLast(E e) {final Node l last;final Node newNode new Node(l, e, null);last newNode;if (l null)first newNode;elsel.next newNode;size;modCount;}很好理解情况1, 假如是空的, 那么添加进来的node就是first, 也就是last, 这个node的prev和next都得是null。情况2是: 假如内容不为空, 那么被添加进来的node就会变成last。Node的prev会指向以前的最后一个元素。Node的next则是null。同时以前的最后一个元素的next也会被更新为node。那么, 采用.add(1, “猪八戒”)这样的一种方法来讲元素增加到那个集合里面去, 这个情形下会如何呢?//在指定位置添加一个元素public void add(int index, E element) {checkPositionIndex(index);if (index size)linkLast(element);elselinkBefore(element, node(index));}/*** 在一个非空节点前插入一个元素*/void linkBefore(E e, Node succ) {// assert succ ! null;final Node pred succ.prev;final Node newNode new Node(pred, e, succ);succ.prev newNode;if (pred null)first newNode;elsepred.next newNode;size;modCount;}实际上, 我们从代码里能看到, 它和那个add(E e)方法的代码实现根本就没有什么本质的区别。双方都是通过新建一个Node实体, 然后同时给其指定前一个元素和后一个元素, 以此来做到这一点的。不同点在于需要调用node(int index)这个方法, 通过传入的参数index来定位到要插入的那个具体位置。这一步也是比较耗时的。这一点可以参考上面的get(int index)方法。其实呢, 看到这个地方, 所有的人也都心里头是明白的。插入效率高这一说法是比较相对的, 原因在于它能够省去在插入数据的时候, 因为可能需要对数组进行扩容以及移动数据元素而造成的那些开销, 不过需要指出的是, 数据扩容以及移动数据元素这些情况, 并不是处于时时刻刻都在发生的状态。3. ( o) 和 (int index)这里()和()就不多说了会用到类中定义的first和last变量非常简单我们看一下( o) 和 (int index)源码//删除某个对象public boolean remove(Object o) {if (o null) {for (Node x first; x ! null; x x.next) {if (x.item null) {unlink(x);return true;}}} else {for (Node 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 x) {final E element x.item;final Node next x.next;final Node 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;}其实实现方面都是非常简单的, 我们首先需要去找到那个目标删除节点, 如果是通过指定对象的方式来处理的话, 我们会调用一个接受对象作为参数的方法, 然后利用这个方法去遍历整个集合的每一个角落, 在遍历的过程中呢, 会使用等号这样的判断操作或者是使用其他专门的方法来进行比对验证, 而如果我们是通过指定索引的方式来处理的话, 那么我们就需要通过调用一个用来获取节点的特定方法进行定位查询。4. 遍历我们这里来主要地, 对那三种被用得比较多的遍历方式呢, 做一个简单的列举工作。咱们这里说的是那个普通的for循环, 还有那个增强的for循环, 最后还有一个迭代器的事儿。public static void main(String[] args) {LinkedList list getLinkedList();//通过快速随机访问遍历LinkedListlistByNormalFor(list);//通过增强for循环遍历LinkedListlistByStrengThenFor(list);//通过快迭代器遍历LinkedListlistByIterator(list);}/*** 构建一个LinkedList集合,包含元素50000个* return*/private static LinkedList getLinkedList() {LinkedList list new LinkedList();for (int i 0; i 50000; i){list.add(i);}return list;}/*** 通过快速随机访问遍历LinkedList*/private static void listByNormalFor(LinkedList 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 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 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);}这个操作的最后的产出内容具体如下。耗时达到1067 ms。3 ms等待的时间是2毫秒。我们来分析一下, 用普通的for循环, 并且通过随机访问的方式去执行代码, 它所花的时间远远比迭代器访问方式所用时间要多。这一点呢, 我们其实是可以理解它背后的原因的。因为在前面讲的那个带有参数索引的get方法里面, 就曾经说过这个情况了。那么接下来我们要搞明白的一个问题是, 为什么增强型的for循环能做到跟迭代器遍历效率差不多的表现。在使用了反编译工具之后, 得到了如下的代码。public static void listByStrengThenFor(LinkedList 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循环来进行遍历操作的时候, 程序内部实际上也是调用了迭代器, 并且在原有的逻辑基础之上, 多了一步将元素进行赋值的步骤。另外, 还有类似于那种先进行取值操作, 把值取出来之后再把数据删除的办法, 也能够达到某种程度上的遍历效果。三. 总结在本文当中, 我们是以Java8为基准点来开展工作的, 并且是从定义这个环节开始进行切入的, 之后的过程中会逐步地展开论述, 主要是从源码的角度出发来分析双向链表的整体结构是如何被一步一步构建起来的同时也对其里面所涉及到的一些常用方法进行了相关的分析工作, 这些方法主要包含有get以及add还有那些经常被用到的遍历的操作手段, 另外还比较简单地说明了一下为什么它在进行数据插入和删除操作的时候表现相对而言是比较高效的, 但是要是谈到取值这一方面的操作的话其性能表现得就比较低了一些啦, 当然这里面如果存在有不正确的地方, 还请大家积极地进行批评与指正, 希望能够通过这样的方式来实现共同进步的效果, 非常感谢大家关于 Java 集合的原理及使用详解的文章, 到这里就介绍完毕了, 大家想要寻找更多有关 Java 的内容, 可以继续往下浏览下面的这些文章, 或者去搜索我过去发布的文章, 希望以后能多多支持CSDN