一文吃透ArrayList&LinkedList的前世与今生

柏炎

发布于 2022-08-23 14:13:14

1740

发布于 2022-08-23 14:13:14

前言

Hello,everyone.前面给大家带来了两篇java基础的HashMap跟ConcurrentHashMap，从阅读量跟点赞方面反响都不错。顺水推舟一下，今天给大家带来老生常谈的ArrayList与LinkedList。List结构相比较与Map而言都是比较简单的数据结构,所以打算两个数据结构放在一起给大家介绍。同样的，会给大家，由浅入深的做介绍，并且比较一下这两种数据结构的差异，让大家在工作与面试中能够清楚的明白使用他们的场景。

【一文吃透ConcurrentHashMap的前世与今生】：https://juejin.cn/post/6960898411314823204?utm_source=gold_browser_extension 【一文吃透hashmap的前世与今生】：https://cloud.tencent.com/developer/article/2079820

一.ArrayList

1.1.关键概念介绍

ArrayList是日常工作中使用list类型的集合最高频的数据结构。他的内部数据结构为数组，通过hash定位，查询效率为O（1），新增插入效率为O（n），线程不安全。

1.2.关键变量介绍

//arraylist默认数组大小
private static final int DEFAULT_CAPACITY = 10;

//空参构造方法，是一个空数组【官方注释】
private static final Object[] EMPTY_ELEMENTDATA = {};

//空数组，这里为什么要定义两个，且往后看【官方注释】
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//数组内容，被transient，不被序列化，那序列话怎么做的呢，切往后看
transient Object[] elementData;

//list已存在的元素大小
private int size;

//父类AbstractList属性，与hashMap文章处介绍一致，防止多线程并发，本文不再解析，可查看前言hashmap文章链接
protected transient int modCount = 0;

1.3.核心方法介绍

1.3.1.构造方法

//指定容量的构造方法
public ArrayList(int initialCapacity) {
        //如果传入的变量大于0，则直接指定数组大小为传入的变量值
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
        //等于0，则使用默认的空数组
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
        //否则抛出异常
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

//默认空参方法，直接赋值一个空数组
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//传入Collection变量，先转换成数组，然后调用Arrays.copyOf，保证元素的顺序与传入的Collection一致
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

1.3.2.add方法

//将元素添加到list的尾部
public boolean add(E e) {
        //保证数组容量大小足够
    ensureCapacityInternal(size + 1);
    //在数组尾部插入元素，size++先使用size，在将存在的元素个数加一
    elementData[size++] = e;
    return true;
}

//在list指定索引位置插入元素
public void add(int index, E element) {
        //校验插入的索引是否越界
    rangeCheckForAdd(index);
        //保证数组容量大小足够
    ensureCapacityInternal(size + 1);
    //指定位子开始到结束的位子的元素调用赋值方法进行往后移动一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
     //在list指定索引位置插入元素     
    elementData[index] = element;
    //索引添加
    size++;
}

add方法整体比较简单，没有什么复杂的逻辑，核心思想几种在ensureCapacityInternal方法与 System.arraycopy方法，我们来看看究竟是何方神圣。

1.3.2.1.ensureCapacityInternal

//确认容量
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

//容量计算，这里就体现出DEFAULTCAPACITY_EMPTY_ELEMENTDATA与EMPTY_ELEMENTDATA差别，DEFAULTCAPACITY_EMPTY_ELEMENTDATA是在属性变量使用的，EMPTY_ELEMENTDATA
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

这里我们来解释一下变量介绍里面DEFAULTCAPACITY_EMPTY_ELEMENTDATA与EMPTY_ELEMENTDATA的区别。

如果使用空参构造函数new ArrayList()，添加一个元素后，elementData.length=10，初始化容量较大；
如果使用有参构造函数new ArrayList(0)或者new ArrayList(空Collection)，添加一个元素后，elementData.length=10，初始化容量较大；
如果使用有参构造函数new ArrayList(0)时，添加一个元素后，elementData.length=1，初始化比较小；

private void ensureExplicitCapacity(int minCapacity) {
    //放置多线程并发添加数据
    modCount++;

    // 如果最小容量小于当前数组已有的长度，进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

//扩容
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    //新容量为原长度的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
               //保证最大数组容量
        newCapacity = hugeCapacity(minCapacity);
       //将旧数组拷贝至新的目标长度的数组，内部调用native方法
    elementData = Arrays.copyOf(elementData, newCapacity);
}

1.3.2.2.System.arraycopy

jdk的native方法，数组拷贝，效率很高，底层调用c/c++

1.3.3.get方法

public E get(int index) {
        //数组越界校验
    rangeCheck(index);
        //直接根据数组下标取值
    return elementData(index);
}

1.3.4.remove方法

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


public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

方法比较简单，不写注释了，就是将目标元素删除，然后数组往左移动一位。

1.4.小结

1.ArrayList内部是Object[]数组，不同的构造器，初始化容量不同，空参或者空集合添加第一个元素时为0，有参构造方法添加第一个元素时，根据实际情况进行初始化，初始化容量较小。

2.添加元素会先进行计算目标容量，如果容量不足进行扩容，每次新的扩容后的数组长度是原数组长度的1.5倍。

3.ArrayList适合查询多，添加删除少的场景。

4.ArrayList集合不是线程安全的。

二.LinkedList

2.1.关键概念介绍

LinkedList底层链表结构的集合，与ArrayList相反，它的查找速度慢，增删比较快。

2.2.关键变量介绍

//集合元素个数
transient int size = 0;

//指向第一个节点
transient Node<E> first;

//指向最后一个节点
transient Node<E> last;

//同样继承自父类，表示linkedList线程不安全
protected transient int modCount = 0;

2.3.核心方法介绍

2.3.1.构造方法

//空参构造方法
public LinkedList() {
}

//集合构造方法
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

public boolean addAll(int index, Collection<? extends E> c) {
        //校验索引是否满足要求
    checkPositionIndex(index);
        //集合转数组
    Object[] a = c.toArray();
    //检查数组长度，如果为 0 则直接返回 false 表示没有添加任何元素
    int numNew = a.length;
    if (numNew == 0)
        return false;
        // 保存 index 当前的节点为 succ，当前节点的上一个节点为 pred
    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }
 // 遍历数组将对应的元素包装成节点添加到链表中
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        //如果 pred 为空表示 LinkedList 集合中还没有元素
       //生成的第一个节点将作为头节点 赋值给 first 成员变量
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }
// 如果 index 位置的元素为 null 则遍历数组后 pred 所指向的节点即为新链表的末节点，赋值给 last 成员变量
    if (succ == null) {
        last = pred;
    } else {
    // 否则将 pred 的 next 索引指向 succ ，succ 的 prev 索引指向 pred
        pred.next = succ;
        succ.prev = pred;
    }
 // 更新当前链表的长度 size 并返回 true 表示添加成功
    size += numNew;
    modCount++;
    return true;
}

2.3.2.add方法

//添加元素
public boolean add(E e) {
    linkLast(e);
    return true;
}

//从头部插入
 public void addFirst(E e) {
    linkFirst(e);
 }

//加在链表尾部
 public void addLast(E e) {
    linkLast(e);
 }

//尾部添加
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++;
}
//头增加
private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

比较简单，对于添加的元素，借助成员变量队尾的指针在链表尾部添加一个节点。

2.3.3.get方法

//根据索引查找
public E get(int index) {
        //校验索引是否越界
    checkElementIndex(index);
    //获取索引值
    return node(index).item;
}

//返回头节点
public E getFirst() {
   final Node<E> f = first;
   if (f == null)
       throw new NoSuchElementException();
   return f.item;
}

//返回结尾节点
public E getLast() {
   final Node<E> l = last;
   if (l == null)
       throw new NoSuchElementException();
   return l.item;
}

Node<E> node(int index) {
    //二分法判断索引靠近头索引还是尾部索引，从靠近的一侧开始遍历
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

2.3.4.remove方法

remove方法支持的比较多，这里不做具体展开的，整体逻辑跟get方法与add方法的结合来看就能看的东西，差不多是链表的遍历，拼接

2.4.小结

LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
LinkedList增删快，查找慢。
LinkedList 是非同步的。

三.ArrayList与LinkedList对比

1.ArrayList底层数据结构是数组，LinkedList底层数据结构是双向列表 2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。 3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。

当然这个不是绝对的，上述结论是在基于数据量大的情况下而言 1.如果新增删除的数据在队尾，并且不需要扩容的情况下，ArrayList的性能甚至高于LinkedList 2.查找的数据在队头或者队尾，两者的效率是一样的，因为LinkedList维护了队尾与队头的指针，可以直接获取数据 3.新增和删除当数据量较小时，大约小于30的时候，两者效率差不多，没有显著区别；当数据量较大时，大约在容量的1/10处开始，LinkedList的效率就开始没有ArrayList效率高了，特别到一半以及后半的位置插入时，LinkedList效率明显要低于ArrayList，而且数据量越大，越明显。文中也说了，ArrayList的数组拷贝基于C的native方法实现，性能较高，而LinkedList方法在新增修改时需要新建或删除节点，并且维护指针的关系，大数据量后将会显得比较吃力

4.subList方法在两个类中都有存在，不建议使用，都是对原有集合的一个引用。数据与结构性修改都会导致双向影响。对子集合数据修改了，影响到父集合却不知道，这是研发过程中使用subList常常会犯的错误。

四.参考

1.https://juejin.cn/post/6844903842534916103

2.https://juejin.cn/post/6844903586095169549

3.https://blog.csdn.net/eson_15/article/details/51145788

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021-05-13，如有侵权请联系 cloudcommunity@tencent.com 删除

java

本文分享自作者个人站点/博客前往查看

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

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度