ArrayList和LinkedList的区别、扩容机制以及底层的实现方式

2023-05-13 17:05:25 扩容 底层 区别

ArrayList和LinkedList区别、扩容机制及底层实现

ArrayList

ArrayList的底层实现为数组存储在内存中,线程不同步。可通过数组下标的形式进行查找,所以在查询方面的效率较为出色,常用在查询较多的情景下。

LinkedList

LinkedList的底层实现为链表形式,也为线程不同步。而链表的底层也决定了它在查询方面不如数组底层的ArrayList而在指定位置插入等修改操作下,性能优于ArrayList。

Vestor

另外还有Vestor,Vestor也是和ArrayList、LinkedList一样实现了java.util.List接口。最大的区别在于Vestor是线程同步的,所以在效率方面不如另外两者,适用于多线程项目中。

ArrayList的扩容机制


    public ArrayList(int initialCapacity) {
    super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
    this.elementData = new Object[initialCapacity];
    }

    
    public ArrayList() {
    this(10);
    }

翻阅源码会发现ArrayList初始化如果不指定大小的时候 初始大小为10。

    public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3)/2 + 1;
            if (newCapacity < minCapacity)
        newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
    }
    }

扩容的规则也在源码中有体现,扩容后的大小= 原始大小+原始大小/2 + 1。在进行插入等操作的时候,如果判断出大小不够,会依据此方法进行扩容。(以上是jdk1.6版本的源码,在JDK1.7中扩容规则进行了修改,改为了扩容后的大小= 原始大小+原始大小/2)

LinkedList的扩容机制

由于它的底层是用双向链表实现的,没有初始化大小,也没有扩容的机制。

ArrayList和LinkedList(常用方法、底层结构及扩容机制)

1.ArrayList解说

ArrayList初始长度为0(这里以jdk1.8为例),是一个Object类型的空数组,如下

当第一次调用add后,长度变为10

当数组首次扩容的10个空间用完需要扩容后,会第二次走grow方法来扩容(每次扩容为1.5倍)

总的来说:

ArrayList初始大小为10,每次1.5倍进行扩容;它的底层是用数组实现的,所以查询速度相对LinkedList要快。

2.LinkedList解说

(1)

* LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。

* LinkedList 实现 List 接口,能对它进行队列操作。

* LinkedList 实现 Deque 接口,即能将LinkedList当作双端队列使用。

* LinkedList 实现了Cloneable接口,即覆盖了函数clone(),能克隆。

* LinkedList 实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。

* LinkedList 是非同步的。

由于它的底层是用双向链表实现的,所以它对元素的增加、删除效率要比ArrayList好;它是一个双向链表,没有初始化大小,也没有扩容的机制,就是一直在前面或者后面新增就好。

(2)LinkedList底层的数据结构是基于双向循环链表的,且头结点中不存放数据,如下:

private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;

header是双向链表的头节点,它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量: previous, next, element。其中,previous是该节点的上一个节点,next是该节点的下一个节点,element是该

节点所包含的值。size是双向链表中节点实例的个数。

总之,addBefore(E e,Entry<E> entry)实现在entry之前插入由e构造的新节点。而add(E e)实现在header节点之前插入由e构造的新节点。为了便于理解,下面给出插入节点的示意图。

总结

以上为个人经验,希望能给大家一个参考,也希望大家多多支持。

相关文章