iPhone内置微信红包免费课堂

?找回密码
?立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 32|回复: 1
打印 上一主题 下一主题

LinkedList真的是查找慢增删快?

[复制链接]
  • TA的每日心情

    2019-6-11 11:04
  • 签到天数: 10 天

    [LV.3]偶尔看看II

    555

    主题

    635

    帖子

    3537

    积分

    管理员

    Rank: 9Rank: 9Rank: 9

    积分
    3537
    跳转到指定楼层
    楼主
    发表于 2019-9-14 20:17:13 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    测试结果
    废话不多说,先上测试结果。作者分别在ArrayList和LinkedList的头部、尾部和中间三个位置插入与查找100000个元素所消耗的时间来进行对比测试,下面是测试结果
    在这里说明一下测试的环境,尾部插入是在空表的基础上测试的,头部和中间位置插入是在已存在100000个元素的表上进行测试的
    测试结论
    • ArrayList的查找性能绝对是一流的,无论查询的是哪个位置的元素
    • ArrayList除了尾部插入的性能较好外(位置越靠后性能越好),其他位置性能就不如人意了
    • LinkedList在头尾查找、插入性能都是很棒的,但是在中间位置进行操作的话,性能就差很远了,而且跟ArrayList完全不是一个量级的

    源码分析
    我们把Java中的ArrayList和LinkedList就是分别对顺序表和双向链表的一种实现,所以在进行源码分析之前,我们先来简单回顾一下数据结构中的顺序表与双向链表中的关键概念
    • 顺序表:需要申请连续的内存空间保存元素,可以通过内存中的物理位置直接找到元素的逻辑位置。在顺序表中间插入or删除元素需要把该元素之后的所有元素向前or向后移动。
    • 双向链表:不需要申请连续的内存空间保存元素,需要通过元素的头尾指针找到前继与后继元素(查找元素的时候需要从头or尾开始遍历整个链表,直到找到目标元素)。在双向链表中插入or删除元素不需要移动元素,只需要改变相关元素的头尾指针即可。

    所以我们潜意识会认为:ArrayList查找快,增删慢。LinkedList查找慢,增删快。但实际上真的是这样的吗?我们一起来看看吧。
    测试程序
    测试程序代码基本没有什么营养,这里就不贴出来了,但是得把程序的运行结果贴出来,方便逐个分析。
    运行结果
    ArrayList尾部插入100000个元素耗时:26ms
    LinkedList尾部插入100000个元素耗时:28ms
    ArrayList头部插入100000个元素耗时:859ms
    LinkedList头部插入100000个元素耗时:15ms
    ArrayList中间插入100000个元素耗时:1848ms
    LinkedList中间插入100000个元素耗时:15981ms
    ArrayList头部读取100000个元素耗时:7ms
    LinkedList头部读取100000个元素耗时:11ms
    ArrayList尾部读取100000个元素耗时:12ms
    LinkedList尾部读取100000个元素耗时:9ms
    ArrayList中间读取100000个元素耗时:13ms
    LinkedList中间读取100000个元素耗时:11387ms
    ArrayList尾部插入
    add(E e)方法
    ? ? public boolean add(E e) {
    ? ?? ???// 检查是否需要扩容
    ? ?? ???ensureCapacityInternal(size + 1);??// Increments modCount!!
    ? ?? ???// 直接在尾部添加元素
    ? ?? ???elementData[size++] = e;
    ? ?? ???return true;
    ? ? }
    可以看出,对ArrayList的尾部插入,直接插入即可,无须额外的操作。
    LinkedList尾部插入
    LinkedList中定义了头尾节点
    ? ? /**
    ? ???* Pointer to first node.
    ? ???*/

    ? ? transient Node first;

    ? ? /**
    ? ???* Pointer to last node.
    ? ???*/

    ? ? transient Node last;
    add(E e)方法,该方法中调用了linkLast(E e)方法
    ? ? public boolean add(E e) {
    ? ?? ???linkLast(e);
    ? ?? ???return true;
    ? ? }
    linkLast(E e)方法,可以看出,在尾部插入的时候,并不需要从头开始遍历整个链表,因为已经事先保存了尾结点,所以可以直接在尾结点后面插入元素
    ? ? /**
    ? ???* Links e as last element.
    ? ???*/

    ? ? void linkLast(E e) {
    ? ?? ???// 先把原来的尾结点保存下来
    ? ?? ???final Node l = last;
    ? ?? ???// 创建一个新的结点,其头结点指向last
    ? ?? ???final Node newNode = new Node<>(l, e, null);
    ? ?? ???// 尾结点置为newNode
    ? ?? ???last = newNode;
    ? ?? ???if (l == null)
    ? ?? ?? ?? ?first = newNode;
    ? ?? ???else
    ? ?? ?? ?? ?// 修改原先的尾结点的尾结点,使其指向新的尾结点
    ? ?? ?? ?? ?l.next = newNode;
    ? ?? ???size++;
    ? ?? ???modCount++;
    ? ? }
    总结
    对于尾部插入而言,ArrayList与LinkedList的性能几乎是一致的
    ArrayList头部插入
    add(int index, E element)方法,可以看到通过调用系统的数组复制方法来实现了元素的移动。所以,插入的位置越靠前,需要移动的元素就会越多
    public void add(int index, E element) {
    ? ?? ???rangeCheckForAdd(index);

    ? ?? ???ensureCapacityInternal(size + 1);??// Increments modCount!!
    ? ?? ???// 把原来数组中的index位置开始的元素全部复制到index+1开始的位置(其实就是index后面的元素向后移动一位)
    ? ?? ???System.arraycopy(elementData, index, elementData, index + 1,
    ? ?? ?? ?? ?? ?? ?? ?? ? size - index);
    ? ?? ???// 插入元素
    ? ?? ???elementData[index] = element;
    ? ?? ???size++;
    ? ? }
    LinkedList头部插入
    add(int index, E element)方法,该方法先判断是否是在尾部插入,如果是调用linkLast()方法,否则调用linkBefore(),那么是否真的就是需要重头开始遍历呢?我们一起来看看
    ? ? public void add(int index, E element) {
    ? ?? ???checkPositionIndex(index);

    ? ?? ???if (index == size)
    ? ?? ?? ?? ?linkLast(element);
    ? ?? ???else
    ? ?? ?? ?? ?linkBefore(element, node(index));
    ? ? }
    在头尾以外的位置插入元素当然得找出这个位置在哪里,这里面的node()方法就是关键所在,这个函数的作用就是根据索引查找元素,但是它会先判断index的位置,如果index比size的一半(size >> 1,右移运算,相当于除以2)要小,就从头开始遍历。
    否则,从尾部开始遍历。从而可以知道,对于LinkedList来说,操作的元素的位置越往中间靠拢,效率就越低
    ? ? 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;
    ? ?? ???}
    ? ? }
    这个函数的工作就只是负责把元素插入到相应的位置而已,关键的工作在node()方法中已经完成了
    ? ? 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;
    ? ?? ???else
    ? ?? ?? ?? ?pred.next = newNode;
    ? ?? ???size++;
    ? ?? ???modCount++;
    ? ? }
    总结
    • 对于LinkedList来说,头部插入和尾部插入时间复杂度都是O(1)
    • 但是对于ArrayList来说,头部的每一次插入都需要移动size-1个元素,效率可想而知
    • 但是如果都是在最中间的位置插入的话,ArrayList速度比LinkedList的速度快将近10倍

    ArrayList、LinkedList查找
    • 这就没啥好说的了,对于ArrayList,无论什么位置,都是直接通过索引定位到元素,时间复杂度O(1)
    • 而对于LinkedList查找,其核心方法就是上面所说的node()方法,所以头尾查找速度极快,越往中间靠拢效率越低


    本帖子中包含更多资源

    您需要 登录 才可以下载或查看,没有帐号?立即注册

    x
    iPhone内置微信红包免费课堂 www.gkket.com

    该用户从未签到

    0

    主题

    11

    帖子

    53

    积分

    注册会员

    Rank: 2

    积分
    53
    沙发
    发表于 2019-9-15 08:08:11 | 只看该作者
    在遇到你之前我对人世间是否有技术大佬保有怀疑,现在我是彻底被你征服了
    iPhone内置微信红包免费课堂 www.gkket.com
    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    QQ|免责声明|本站介绍|iPhone内置微信红包免费课堂 ( 沪ICP备14007696号-3 )|网站地图

    GMT+8, 2019-9-23 09:13 , Processed in 0.085030 second(s), 36 queries .

    Powered by Discuz! X3.4

    ? 2001-2017 Comsenz Inc.

    快速回复 返回顶部 返回列表