专栏首页洁癖是一只狗性能优化-集合类(ArrayList和LinkedList)

性能优化-集合类(ArrayList和LinkedList)

集合类是日常开发经常使用的,而ArrayList和LinkedList是使用相当频繁的集合类,在面试中也是频繁出现,但是我们真的了解这里面的原理呢,

一提到这两个集合类,大多数的人都会说ArrayList的插入和删除性能优于LinkedList,而LinkedList的查找性能优于ArrayList,但是真的是这样吗?

今天我们就从数据结构,源码,以及实现原理验证一下上面的言论是否正确.

ArrayList和Vector,linkedList都继承AbstractList抽象类,而AbstractList实现了List接口,同时继承了AbstractCollection抽象类,

而ArrayList,Vector和LinkedList都有各自的实现,ArrayList和Vector都使用数组实现,LinkedList使用双向链表实现

ArrayList实现类

ArrayList实现List接口,继承了AbstractList抽象类,底层使用数组实现,实现动态扩容机制.

ArrayList实现了Cloneable接口和Serializable接口,所以实现克隆和序列化.

ArrayList还实现了RandomAccess接口,这个接口仅仅是一个空类,他的作用就是标识,只要实现了他的List接口,都可以实现快速访问。

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList属性

//默认初始化容量
private static final int DEFAULT_CAPACITY = 10;
//对象数组
transient Object[] elementData; 
//数组长度
private int size;

这三个属性没有任何的多线程关键字修饰,但是唯一特殊就是对象数组有一个transient修饰,他的作用就是该字段则标识该属性不能别序列化,但是我们发现Arraylist实现了序列化接口,这是怎么回事呢,

这是因为ArraList是基于数组实现的,而数组也是基于动态扩增的,并不是所有被分配的内存空间都存储了数据。

如果在使用外部序列化的时候,会序列化整个数组,但是为了防止序列化没有存储数据的内容空间被序列化,内部实现了两个私有方法writeObject和readObject开自我完成序列化和反序列化,从而在序列化与反序列化节省了内存,因此使用transient是为了防止外部序列化.

ArrayList新增元素

ArrayList新增元素的方法有两种,一种是直接将元素加到数组的末尾,另外一种就是添加元素到任何位置

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
return true;
    }

public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

两个方法的相同之处,就是在添加元素之前,先确认容量大小,如果容量够大,就不用进行扩容,如果不够,就会按照原来的数组的1.5倍大小进行扩展,扩展之后在将数组复制到新分配的内存地址.

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

// overflow-conscious code
if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

当然,两个方法不同之处,添加任意位置的时候,都会进行元素的重新排序,而将元素添加数组的末尾,在没有发生扩容下,不会有元素复制排序的过程.

因此在添加大量新元素的时候,且容量不扩容的情况下,性能并不会变差.

ArrayList删除元素

删除元素和添加任意元素的方法是有些相同,Arraylist每一次删除,都会进行数组的重组,且删除越靠前的元素,数组的重组开销就越大.

 public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

int numMoved = size - index - 1;
if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

return oldValue;
    }

ArrayList遍历元素

基于数组实现,所以获取元素的时候是非常快的,

  public E get(int index) {
        rangeCheck(index);

return elementData(index);
    }

    E elementData(int index) {
return (E) elementData[index];
    }

LinkedList是如何实现的

LinkedList和ArrayList的实现差异比较大,LinkedList是基于双向链表数据结构实现的,LinkedList定义了一个Node结构,如下

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;
        }
    }

元素内容item, 前指针prev,后指针next,有Node的节点对象连接成的双向链表,但是在1.7JDK之前是定义了一个Entry结构的header属性,默认创建一个空Entry用来做header属性,前后指针指向自己,形成一个双向链表,

而在1.7JDK之后就按照上面的node实现,但是去掉了header属性,而替代的是Node机构的first和last属性,这样做的好处就是

  1. first/last可以清楚的表达链表的链头和链尾
  2. first/last初始化LinkedList节省了new一个Entry
  3. first/last使删除和插入操作更加快捷

LinkedList实现类

Linkedlsit实现List接口Deque接口,同时继承了AbstractSequentialList,LinkedList既有List类型也有队列的特性,他也是想了Cloneable和Serializabe接口,同ArrayList一样可以实现克隆和序列化,但是没有实现RandomAccess,因此不能随机快速访问,且LinkedList存储的内存地址不是连续的,而是用指针实现定位不连续地址的.

LinkedList属性

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

上面三个属性都使用了transient修饰,说明不能被序列化,这样做是因为如果序列化不仅仅是对链头和链尾进行序列化,因此也会使用readObject和writeObject进行序列化和反序列化.

LinkedList新增新元素

默认add(E e) 是添加元素到队尾,首先是将last放到一个临时node,然后声明一个新的Node,将last引用指向新的元素,在把之前的last指向新的节点

public boolean add(E e) {
        linkLast(e);
return true;
    }

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;
else
            l.next = newNode;
        size++;
        modCount++;
    }

而LinkedList新增节点到任意位置时候,如果我们添加到两个元素之间,添加元素只会修改前后节点的前后指针,指针指向新的节点元素,索引LinkedList添加的元素的性能很明显比ArrayList好.

LinkedList删除元素

删除元素我们要进行循环遍历,如果是在链表的前半段或后半段的位置,就会在从前向后或从后向前查找,因此如果元素靠前或靠后,删除元素的效率非常高效,但是对于拥有大量元素,且删除的位置在中间,效率就比较低

LinkedList遍历元素

遍历元素和删除元素的操作基本类似,通过分前后半段循环查找对应的元素,所以这种情况找元素是非常低效的,特别是在for循环遍历的时候,每一次遍历都要遍历半个List,索引在LinkedList遍历的时候,我们可以使用iterator方式迭代遍历.

总结

  • ArrayList是数组实现,而数组是一组内存空间连续的,添加到元素到头部的时候,需要重组头部以后的数据,效率较低,LinedList是基于链表实现,在添加元素的时候,如果查找的元素在前半段或后半段的时候,响应的从前或从后进行查找,因此LinkedList添加头部效率比较高
  • Arraylist添加元素到中间位置的时候,也需要部分数据的重组,效率较低,但是LinkedList添加到中间位置的时候,需要遍历元素是最多的操作,效率是最低的
  • 添加元素到尾部的时候,在没有扩容的情况下ArrayList效率高于LinkedList的,而LinkedList不需要查找元素,但是需要重新new一个对象,以及变化指针对象的过程,所以效率低于ArrayList
  • LinkedList循环遍历每一次都会遍历整个List,所以影响遍历的效率,ArrayList是基于数组,且实现了RandomAccess,意味可以实现快速随机访问他,所以for循环效率非常高,linkelist的迭代循环和ArrayList迭代循环性能相当,所以LinkedList在切记使用for循环遍历

本文分享自微信公众号 - 洁癖是一只狗(rookie-dog),作者:洁癖汪

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python流程控制语句详细解读 含代码

    今天我们详细的讲讲Python流程控制语句。包括if条件判断,while循环以及break和continue等。下一篇我们主讲Python中的序列,包括列...

    小土豆Yuki
  • 序列化与反序列化

    现今的后台服务大多是微服务架构,每个服务按照业务进行拆分,实现了服务之间的解耦,而服务之间要记性接口调用实现,服务支架要进行数据对象共享,就要把服务对象转成二进...

    小土豆Yuki
  • 自动化运维实践 | Ansible介绍

    Ansible是一个部署一群远程主机的工具。这里“远程主机”是指任何可以通过SSH登录的主机,所以它既可以是远程虚拟机或物理机,也可以是本地主机。Ansible...

    小土豆Yuki
  • Java中ArrayList与LinkedList的区别

    Java中ArrayList与LinkedList的区别 一般大家都知道ArrayList和LinkedList的区别:       1. ArrayList的...

    nnngu
  • Rainbow:整合DQN六种改进的深度强化学习方法!

    在2013年DQN首次被提出后,学者们对其进行了多方面的改进,其中最主要的有六个,分别是: Double-DQN:将动作选择和价值估计分开,避免价值过高估计 D...

    石晓文
  • OpenStack命令创建网络

    [root@controller ~]# neutron net-create provider-666 neutron CLI is deprecated a...

    院长技术
  • 浅谈Java中的equals和==

      为什么第4行和第5行的输出结果不一样?==和equals方法之间的区别是什么?如果在初学Java的时候这个问题不弄清楚,就会导致自己在以后编写代码时出现一些...

    Java团长
  • 【Java学习笔记之二十九】Java中的"equals"和"=="的用法及区别

    Java中的"equals"和"=="的用法及区别 在初学Java时,可能会经常碰到下面的代码: 1 String str1 = new String("hel...

    Angel_Kitty
  • 机器之心年度盘点:2017年人工智能领域度备受关注的科研成果

    机器之心
  • Java 限制泛型

    A<? extends anyClass> a;//泛型必须是anyClass的子类,且不能做增加和改写操作,只可读取

    用户2965768

扫码关注云+社区

领取腾讯云代金券