signed

QiShunwang

“诚信为本、客户至上”

ArrayList、LinkedList基本与原理

2021/5/15 1:03:47   来源:

List

ArrayList

ArrayList的底层是基于动态数组实现

    transient Object[] elementData; 
    private int size;

常用的方法

        ArrayList<String> arrayList = new ArrayList<>();    //或者ArrayList<String> arrayList = new ArrayList<>(4);
        arrayList.add("a"); //添加元素,在数组“尾部”添加 速度快
        arrayList.add(0,"c");   //添加元素,在数组“中间”添加 速度慢
        System.out.println(arrayList.get(0));   //获取指定下标的元素
        arrayList.remove("a");  //删除指定元素,通过遍历
        arrayList.remove(0);    //删除指定下标的元素
        arrayList.set(0,"b");   //修改

深入原理

初始化

ArrayList<String> arrayList = new ArrayList<>();

当调用ArrayList的无参构造器时,数组容量为0的Object数组;
当调用add()方法添加第一个数据时,才会分配容量,默认容量为10

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

ArrayList<String> arrayList = new ArrayList<>(10);

当调用ArrayList的有参构造器时,会创建一个指定大小的Object数组;

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

add方法、扩容

    public boolean add(E e) {
        // 检查当前容量是否还可以容纳一个元素,不够则扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 添加到数组末尾
        // 这个语句可以分解为
        // elementData[size] = e;
        // size += 1;
        elementData[size++] = e;
        return true;
    }
  1. 在使用无参构造器初始化ArrayList时,便会创建一个空的数组;

  2. 当调用add()方法添加第一个数据时,便会对数组进行扩容(调用Arrays.copyOf方法),默认容量为10;

  3. 若添加数据后的容量 超出 当前数组长度,则进行扩容,扩容之后的容量为之前容量的1.5倍


https://blog.csdn.net/zhouhengzhe/article/details/108319369

把原数组的数据,原封不动的复制到新数组中,然后把ArrauList的地址指向新数组
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fEgSRtqY-1621011446037)(https://note.youdao.com/yws/res/85142/74452E4097A64D99AAF89E5C4DF3DD38)]

1.7的时候是初始化就创建一个容量为10的数组,1.8后是初始化先创建一个空数组,第一次add时才扩容为10;

LinkedList

LinkedList是通过双向链表实现的

    transient int size = 0;

    transient Node<E> first;

    transient Node<E> last;

常用方法

LinkedList基本使用与ArrayList相同;

        LinkedList<String> linkedList = new LinkedList<>(); //注意,LinkedList没有有参构造器
        linkedList.add("a");
        linkedList.set(0,"b");  //效果等同linkedList.add(0,"c");
        linkedList.remove(0);
        linkedList.remove("c");
        System.out.println(linkedList.get(0));  

remove

remove操作分2种,一种是根据下标删除,一种是根据元素内容删除;
根据元素内容删除时,需要遍历全部元素;

根据下标删除remove(int index)

若index < size/2,则从头遍历,否则从尾部遍历;

get(int ndex)

若index < size/2,则从头遍历,否则从尾部遍历;

ArrayList与LinkedList对比

ArrayList在使用无参构造器时,默认初始化一个容量为10的数组,当添加元素后 元素个数 大于 现有容量,则按1.5倍容量扩容,扩容 消耗性能,所以初始化时最后指定容量;

LinkedList是双向链表,当指定下标 添加、删除元素时,若index < size/2则从头节点遍历,否则从尾节点开始遍历;
当指定下标添加(不是修改指定下标元素)或者删除元素时,只需修改指针即可

ArrayList
  1. 指定下标删除元素 list.remove(int index)
  2. 指定下标添加元素 list.add(int index,E e)
  3. 指定下标查询快 list.get(int index)
LinkedList
  1. 指定下标删除元素 list.remove(int index)
  2. 指定下标添加元素 list.add(int index,E e)
  3. 指定下标查询慢 list.get(int index)
    需要先定位到元素所在

List与线程安全

Collections.synchronizedList()

ArrayList 与 LinkendList都不是线程安全的,但可以通过 java.util.Collections.synchronizedList(List list) 方法,获取一个线程安全的 List 实例对象;

Collections.synchronizedList(List list) 方法源码

public static <T> List<T> synchronizedList(List<T> list) {
        return (list instanceof RandomAccess ?
                new SynchronizedRandomAccessList<>(list) :
                new SynchronizedList<>(list));
}

当传入的 list 是 ArrayList 时,返回 SynchronizedRandomAccessList 对象;传入 LinkedList 时,返回 SynchronizedList 对象。

get、set、add 等操作都添加了synchronized锁;

        public E get(int index) {
            synchronized (mutex) {return list.get(index);}
        }
        public E set(int index, E element) {
            synchronized (mutex) {return list.set(index, element);}
        }
        public void add(int index, E element) {
            synchronized (mutex) {list.add(index, element);}
        }
        public E remove(int index) {
            synchronized (mutex) {return list.remove(index);}
        }

CopyOnWriteArrayList


坑点

迭代器

增强for循环 的 原理就是 迭代器,这点与普通的for循环有着本质的区别;

https://juejin.cn/post/6844903569095671816

在迭代器中,不能对list进行增删操作,只能查询;
即list的add、remove会报ConcurrentModificationException异常
public static void main(String[] args) {
        ArrayList<String> strings = new ArrayList<String>();
        strings.add("a");
        strings.add("b");

        for (String string : strings) {
            if ("e".equals(string)) {
                strings.remove(string);
            }
        }
    }
    
    
Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:859)
	at java.util.ArrayList$Itr.next(ArrayList.java:831)
	at main.java.mo.basic.ConcurrentModificationExceptionTest.main(ConcurrentModificationExceptionTest.java:17)
Iterator实现类有2个重要的方法hasNext()和next()

 Iterator中有一个expectedModCount属性与list的modCount属性同步,当list执行remove时会modCount++,而Iterator中有expectedModCount却不会变化;
 
 当 Iterator调用next()方法,会使用checkForComodification做校验,modCount与 expectedModCount不同就会报错;

解决方法,使用普通的for循环,不要使用迭代器;