开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 系统运维 -> ArrayList vs LinkedList 源码学习 -> 正文阅读

[系统运维]ArrayList vs LinkedList 源码学习

ArrayList vs LinkedList 源码学习

PS：想了解两者区别的可直接看第三部分-ArrayList vs LinkedList

一、ArrayList

1. 三个特性

ArrayList 继承了 AbstractList 类，实现了 List, RandomAccess, Cloneable, Serializable 接口
ArrayList 底层数据结构是数组队列，可以动态扩容。
ArrayList 线程不安全（线程安全的版本为 CopyOnWriteArrayList）

2. 五个参数

添加元素后的数组容量（默认） private static final int DEFAULT_CAPACITY = 10
数组创建： transient Object[] elementData
数组最大长度：private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
记录ArrayList修改次数：protected transient int modCount = 0（父类AbstractList 中定义）
检查并发修改异常：int expectedModCount = modCount（私有内部类Itr中定义）

PS：初始化的数组容量为0，一旦添加了第一个元素后，容量就变为了10。

3. 几个方法

add()

作用：增加元素
先判断是否需要扩容，然后添加到数组的末尾

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

remove()

作用：删除元素，有两种删除方法
两种方法内部都使用了数组拷贝，即cow策略

// 删除指定下标的元素，返回旧值
public E remove(int index) {
		// 检查index是否越界
        rangeCheck(index);

		// 记录ArrayList的修改次数
        modCount++;
        E oldValue = elementData(index);
		
		// 需要拷贝的元素个数
        int numMoved = size - index - 1;
        if (numMoved > 0)
        	// System类下的arraycopy方法，属于native方法
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }
    
// 删除指定元素，返回boolean值
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;
    }
    
// 第二种remove内部调用了fastRemove()方法
private void fastRemove(int index) {
        modCount++;
        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
    }

PS：注意如果对象为null不能用 equals 来判断，一定会返回 false，要用 == 来判断！！！

set()

作用：修改元素，会返回旧值

public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

get()

作用：查找元素，没啥好说的

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

        return elementData(index);
    }

rangeCheck()

发现几个方法内部调用了rangeCheck()方法，这里了解一下。由源码可见，它是用来判断参数是否越界的，越界则报错IndexOutOfBoundsException

private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

grow()

作用：扩容

内部调用了hugeCapacity()方法

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // 新数组的容量 = 旧数组的容量 + 旧数组的容量/2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //  MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
        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);
    }

hugeCapacity()

若minCapacity > MAX_ARRAY_SIZE，newCapacity = Integer.MAX_VALUE，否则 = MAX_ARRAY_SIZE

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

4. 几个注意点

ArrayList不能在for遍历中修改元素，而要用迭代器！！！

ArrayList底层是数组，删除元素时，会将指定元素后面的元素向前移动，并且指针会下一次遍历后会忽略下一个可能同样的元素，导致元素没有删除干净。

源码见上面的remove()方法，这里通过一个案例解释上面这句话

public class TestArrayList {
    // 删除列表中所有值为3的元素
    public static void main(String[] args) {
    
        ArrayList<Integer> list = new ArrayList<>();
        
        list.add(2);
        list.add(3);
        list.add(3);
        list.add(4);
        list.add(1);
        list.add(3);
        list.add(6);
        list.add(4);

        // 写法一：能得到正确结果[2, 4, 1, 6, 4]
        Iterator iterator = list.iterator();
        while (iterator.hasNext()) {
            if (iterator.next().equals(3)) {
            	iterator.remove();
            // 使用迭代器遍历，就不能再调用list中的remove方法，要用迭代器内部的remove方法！
//                list.remove(iterator.next()); //ConcurrentModificationException
            }
        }

        // 写法二：能得到正确结果[2, 4, 1, 6, 4]
        for (int i = list.size()-1;i >= 0;i--){
            if (list.get(i).equals(3)){
                list.remove(i);
           }
        }

        // 写法三：结果错误 [2, 3, 4, 1, 6, 4]
        // 第二个3没有删除干净
       for (int i = 0;i < list.size();i++){
            if (list.get(i).equals(3)){
                list.remove(i);
            }
        }

        // 写法四：报异常ConcurrentModificationException
        // 错误原因：for each(增强for循环写法)实际上是对Iterator、hasNext、next方法进行简写！
        for (Integer s : list) {
            if (s.equals(3)) {
            	// 调用了list的remove()方法，而在迭代器遍历中会有一个checkForComodification操作，检查modCount是否等于expectedModCount，不等于就会报ConcurrentModificationException
                list.remove(s);
            }
        }
        
        System.out.println(list);
    }
}

探究：迭代器遍历

ArrayList内部有一个匿名类Itr实现了Iterator接口，并提供了remove()方法，看源码

由源码的第二段代码可以看出，这个remove方法中调用了ArrayList中的remove方法，并且在私有内部类Itr中定义了expectedModCount变量。（modCount变量在父类AbstractList中定义）

modCount在前面的代码中也见到了，它用来记录ArrayList修改的次数，而变量expectedModCount，这个变量的初值与modCount相等（int expectedModCount = modCount）。

从源码中可见，在执行ArrayList.this.remove(lastRet)方法之前调用了检查次数方法checkForComodification()，这个方法做的事情很简单（如下图）：如果expectedModCount和modCount不相等，那么就抛出异常ConcurrentModificationException。

我们用for循环并调用ArrayList的remove方法时，删除元素后modCount会增加（即modCount++;），而expectedModCount不变，这样就造成expectedModCount ！= modCount，那么就会抛出ConcurrentModificationException。

若调用的是内部类Itr中的remove方法删除元素，在这个方法中有：expectedModCount = modCount这样一句代码，所以当我们每删除一次元素，就同步一次，所以执行checkForComodification()时，就不会报错。

PS：如果换到多线程中，迭代器不能保证两个线程修改的一致性，结果具有不确定性！

ArrayList的线程安全版本

CopyOnWriteArrayList
Collections.synchronizedList()

List<String> list = new ArrayList<>();
List<String> synchronizedList = Collections.synchronizedList(list);

ArrayList的容量

如果通过无参构造的话，ArrayList初始容量为0，添加元素后容量变为10。当元素个数等于数组长度，并且需要继续添加元素时，才会进行扩容（1.5倍扩容，copeOf()方法）
在这里插入图片描述

二、LinkedList

1. 三个特性

LinkedList 底层是双向链表结构
LinkedList 继承了AbstractSequentialList类，实现了List、Deque、Cloneable、Serializable接口
- LinkedList 可以当做双向队列使用，内部定义了首节点和末尾节点，每次操作时都会更新，可以直接在首尾操作LinkedList
LinkedList 线程不安全（线程安全版本为 ConcurrentLinkedQueue）

2. 五个参数

链表初始化长度：transient int size = 0
链表中的第一个节点：transient Node<E> first;
链表中的最后一个节点：transient Node<E> last;
记录链表修改次数：protected transient int modCount = 0（在父类AbstractSequentialList的父类AbstractList中定义）
链表存储的节点为 Node<E>

private static class Node<E> {
		//值item
        E item;
        // 后继next
        Node<E> next;
        // 前驱prev
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

3. 几个方法

add()

作用：向链表尾部添加元素

内部调用了linkLast()方法

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

linkLast()

作用：向链表尾部添加元素

void linkLast(E e) {
		// l指向链表尾部节点
        final Node<E> l = last;
        // newNode指向新元素，并设置前驱节点为l，后继节点为null
        final Node<E> newNode = new Node<>(l, e, null);
        // 把链表的尾部节点设置为newNode
        last = newNode;
        // 如果尾部节点为kong，那么设置链表的首节点为newNode（链表此时就只有一个元素）
        if (l == null)
            first = newNode;
        else
        	// 设置链表原本的尾部节点的后继节点为newNode
            l.next = newNode;
        // 链表容量+1
        size++;
        // 链表修改次数+1
        modCount++;
    }

addFirst() & addLast()

addFirst()：在链表首部添加元素
addLast()：等价于add()，内部调用了linkLast()

public void addFirst(E e) {
        linkFirst(e);
    }
    
public void addLast(E e) {
        linkLast(e);
    }

linkFirst()

作用：在链表首部添加元素

private void linkFirst(E e) {
		// f指向链表中的首节点
        final Node<E> f = first;
        // newNode 记录要添加的节点，并将其前驱置为null，后继置为f
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        // 若链表原先无元素，那么newNode既是first也是last 
        if (f == null)
            last = newNode;
        else
        	// 设置f的前驱为 newNode
            f.prev = newNode;
        size++;
        modCount++;
    }

get()

作用：取元素

内部调用了node()方法

public E get(int index) {
		// 先检查index是否越界
        checkElementIndex(index);
        // 返回node的值item
        return node(index).item;
    }

getFirst() & getLast()

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()

作用：当get元素的时候，根据指定的index，遍历一遍LinkedLIst
这里node方法优化了遍历效率！判断index在前半部分，还是后半部分，再去遍历，最后返回元素！

Node<E> node(int index) {
        // assert isElementIndex(index);
		// size >> 1 等价于size /= 2
        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;
        }
    }

4. 一个注意点

LinkedList的线程安全版本

List list = Collections.synchronizedList(new LinkedList());
将 LinkedList 全部换成 ConcurrentLinkedQueue

PS：LinkedList实现了Deque，可以当做队列来使用！

三、ArrayList vs LinkedList

二者区别从以下几个角度来讨论

数据结构
- ArrayList - 数组
- LinkedList - 链表
时间效率
- ArrayList 在查找和修改方面效率更高
  - 不涉及到扩容：ArrayList 在中间位置新增元素、尾部新增元素的时候比 LinkedList 好很多，只有头部新增元素的时候比 LinkedList 差（因为数组复制）。
  - 如果涉及到数组扩容的话，ArrayList 的性能就没那么可观了，因为扩容的时候也要复制数组。
- LinkedList 在添加和删除方面效率更高
遍历
- for 循环遍历的时候，ArrayList 花费的时间远小于 LinkedList
  - 每for一次，LinkedList 需要调用node()方法，前 / 后遍历一遍
- 迭代器遍历的时候，两者性能差不多
扩容
- ArrayList 可以动态扩容，在添加元素的时候，发现容量满了 s == elementData.length，就按照原来数组的 1.5 倍进行扩容，再将原有的数组复制到新分配的内存地址上，即
  int newCapacity = oldCapacity + (oldCapacity >> 1)
  elementData = Arrays.copyOf(elementData, newCapacity)
- LinkedList 不扩容
内存空间
- ArrayList - 动态扩容在list的结尾预留一定容量，这会导致部分内存浪费
- LinkedList - 每个Node节点除了存放值，还存放了前驱和后继指针，也造成了内存的浪费
RandomAccess 接口
- ArrayList 实现了RandomAccess 接口（不需要遍历，可以通过下标直接访问到内存地址）
- LinkedList 采用线性数据存储方式，所以需要移动指针从前往后依次查找（没实现RandomAccess 接口）
transient 反序列化
- ArrayList 对于浪费的空间不进行序列化，只针对数组中元素个数，而不是数组长度（transient Object[] elementData）
- LinkedList 则没有这方法的设计（不需要）