java集合 linkedlist的原理及使用 -ag凯发k8国际
1.linkedlist的概述
2.linkedlist的常用方法
3.linkedlist的三种便利方式
4.linkedlist的总结
linkedlist和arraylist一样是集合list的实现类,虽然较之arraylist,其使用场景并不多,但同样有用到的时候,那么接下来,我们来认识一下它。
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五大应用场景一章已经有说明
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变量指向上一个节点。
1.get方法
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方法
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;elsel.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);elselinkbefore(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;elsepred.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迭代器
通过普通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()取值后删除的方法也能达到部分的遍历效果。
本文参考:java集合 linkedlist的原理及使用
总结
以上是ag凯发k8国际为你收集整理的java集合 linkedlist的原理及使用的全部内容,希望文章能够帮你解决所遇到的问题。
- 上一篇: system.arraycopy()和
- 下一篇: java集合入门总结