Node结构
LinkedList集合中的每一个元素都是一个结点,将多个结点链接到一起,就是链表结构。以下是结点Node的源码,它是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;
}
}
LinkedList结构
在eclipse中调试以下代码
list = new LinkedList();
System.out.println("断点1");
list.add(1);
list.add(2);
list.add(3);
System.out.println("断点2");
断点 1,创建一个空的LinkedList,下图可以看到其四个参数,modCount和size在ArrayList中也有,这两个我们不关心。重点关注first和last,用来存储链表的第一个节点和最后一个节点。那么,如何找到中间的节点?
断点 2,添加了三个元素,此时first结点的next参数会指向第二个结点,即标识 373。而373的next参数又会指向第三个结点,即标识371。也就是说,链表结构可以从第一个结点找到第二个,再从第二个结点找到第三个,但是从第一个结点无法找到第三个,不能跳着找。很显然,这样一个一个的查找方式比ArrayList的数组查找方式要慢的多 。
添加的性能
上一篇测过,ArrayList添加5亿数据量仅耗时1080毫秒,现在就来看一下LinkedList能否打破ArrayList的纪录。
int size=50000000;
List list = new LinkedList();
long t1 = System.currentTimeMillis();
for(int i=0;i<size;i++){
list.add(1);
}
long t2 = System.currentTimeMillis();
System.out.println(t2-t1);
内存分配的开销
上一篇讲过,list.add(1)并没有创建对象。而LinkedList集合中存储的是Node,通过Node的item来存储添加的1,因此LinkedList创建了5千万个Node对象。创建对象需要占用内存,当程序发现内存不够用就去分配内存。等分配的内存用完了又不够了,就又去分配,反复分配内存的开销才是真正的性能杀手。要想解决这个问题,可在eclipse中打开运行配置,设置jvm参数:-Xms7g,初始分配堆内存7g,一次性分配足够大的空间,就不用反复分配了。以后章节测试都会设置这个参数,不再解释。如下图
注意:vm参数7g是根据数据量来设定的,同时还要调大eclipse的内存。如果是5亿数据还得设的更大,我个人电脑内存有限,所以只测了5千万数据量。如果数据量不大,也可以设置一个较小的vm参数如100m。再次运行
从头部添加
上一篇说过,ArrayList从位置0添加数据,性能会很低。LinkedList表现又会如何?由于性能低下,现在把size改小到10万,分别测试它们
int size=100000;
List list = new ArrayList(size); //测试ArrayList
//List list = new LinkedList(); //测试LinkedList
long t1 = System.currentTimeMillis();
for(int i=0;i<size;i++){
list.add(0,1);
}
long t2 = System.currentTimeMillis();
System.out.println(t2-t1);
LinkedList性能高出10倍。如下图,LinkedList在结点1和结点2之间添加一个结点,只要修改它们的next和prev参数,分别指向新结点即可,而ArrayList却要移动n个元素。LinkedList终于找到了存在的价值
从中间添加
我们再换一个位置添加,比如说中间,看是什么效果。将list.add(0,1);改成list.add(i/2,1)
int size=100000;
List list = new ArrayList(size); //测试ArrayList
//List list = new LinkedList(); //测试LinkedList
long t1 = System.currentTimeMillis();
for(int i=0;i<size;i++){
list.add(i/2,1);
}
long t2 = System.currentTimeMillis();
System.out.println(t2-t1);
ArrayList又比LinkedList快了10倍,为何?
查询的性能
删除的性能
删除结点时,会删除其前后链路,然后让其前后结点互相建立链路。删除和添加的原理是一样的,两头快,中间慢。
特性
应用场景
Deque
LinkedList实现了Deque接口,专门用于处理栈和队列的场景。
//声明双端队列
Deque deque = new LinkedList();
deque.addFirst(1); //从队列头部添加数据
deque.addLast(1); //从队列尾部添加数据
deque.pollFirst(); //从队列头部取出数据
deque.pollFirst(); //从队列尾部取出数据
//声明栈
Deque deque = new LinkedList();
deque.push(1); //从栈顶添加数据
deque.pop(); //从栈顶取出数据
如上,这两种场景内部结构仍然是LinkedList,性能特点和前面说的一样。