首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Java数据结构LinkedList底层源码解析整理

Java数据结构LinkedList底层源码解析整理

作者头像
挨踢小子部落阁
发布2019-07-22 08:26:37
6450
发布2019-07-22 08:26:37
举报

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;
        }
    }
  • E item:E是泛型,item就是list.add()方法的参数,即集合中的每个元素,都保存在其Node结点的item参数中。
  • Node next:它指向当前结点的下一个结点。
  • Node 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);
  • 耗时:28531毫秒
  • 注意:数据量只有5千万,少了十倍,性能反而慢了20多倍。这是为何?

内存分配的开销

上一篇讲过,list.add(1)并没有创建对象。而LinkedList集合中存储的是Node,通过Node的item来存储添加的1,因此LinkedList创建了5千万个Node对象。创建对象需要占用内存,当程序发现内存不够用就去分配内存。等分配的内存用完了又不够了,就又去分配,反复分配内存的开销才是真正的性能杀手。要想解决这个问题,可在eclipse中打开运行配置,设置jvm参数:-Xms7g,初始分配堆内存7g,一次性分配足够大的空间,就不用反复分配了。以后章节测试都会设置这个参数,不再解释。如下图

注意:vm参数7g是根据数据量来设定的,同时还要调大eclipse的内存。如果是5亿数据还得设的更大,我个人电脑内存有限,所以只测了5千万数据量。如果数据量不大,也可以设置一个较小的vm参数如100m。再次运行

  • 耗时:668毫秒
  • 数据量比ArrayList少10倍,耗时却差不太多,性能明显低于ArrayList。原因其实上面已经说了,LinkedList创建了5千万个对象,而且还要维护结点之间的next和prev参数,而ArrayList不需要。下图是分别执行5千万数据量时,任务管理器中的内存走势图,可以明显看出LinkedList额外创建对象的内存开销。在java程序中,内存运行状况对时间性能的影响,往往比分析时间复杂度还更加重要。

从头部添加

上一篇说过,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);
  • ArrayList耗时:765毫秒
  • LinkedList耗时:8毫秒

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耗时:343毫秒
  • LinkedList耗时:4971毫秒

ArrayList又比LinkedList快了10倍,为何?

查询的性能

  • LinkedList在添加时,首先要查找到添加的位置。如果位置在前半区,就从first结点开始,通过next一个个往后找。如果位置在后半区,就从last结点开始,通过prev一个个往前找。也就是说,离first或last最近的结点最容易找到,所以从头部和尾部添加性能最高。而离first和last最远的中间节点,就是LinkedList性能最低的位置。
  • ArrayList从头部添加的时候,需要移动的元素是最多的,也就是性能最低的。而从中间添加的时候,需要移动的元素处于平均数,所以反而性能还提高了。ArrayList添加时也要查找位置,但由于其使用数组,查询任意位置都是瞬间完成的,不存在性能问题。

删除的性能

删除结点时,会删除其前后链路,然后让其前后结点互相建立链路。删除和添加的原理是一样的,两头快,中间慢。

特性

  • 双端链表:记录了头结点和尾结点,处理离头尾越近的数据,性能越高,中间最慢。
  • 每个结点需要创建node对象:由此决定了其最高性能无法超越数组。

应用场景

  • 默认添加性能不如ArrayList,查询性能更不如,所以在大众场景无法取代ArrayList。
  • 擅长在头部及尾部操作,真正适用的场景是栈和队列,即先进后出和先进先出,它们只处理头部和尾部数据,而不会去处理中间的数据。比如生产者和消费者模式,如不了解请自行百度。

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,性能特点和前面说的一样。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-07-18,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 挨踢小子 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档