• Java集合之ArrayList与LinkedList


    前言

    对于Java程序员,可以说对于 ArrayList 和 LinkedList 可谓是十分熟悉了

    对于ArrayList和LinkedList,他们都是List接口的一个实现类,并且我们知道他们的实现方式各不相同,例如ArrayList底层实现是一个数组,而LinkedList底层实现是链表,对于数组来说,插入慢但是查询快,而对于链表来说查询慢,插入快

    今天我们就来分析分析他们的源码

    ArrayList

    我们先看一看ArrayList的类图。他继承于AbstractList,而这个类是List类的的骨架,可以说这个类是List类的基石

    成员属性

    /**
    序列化ID
    **/
    private static final long serialVersionUID = 8683452581122892189L;
    /**
    默认容量
    **/
    private static final int DEFAULT_CAPACITY = 10;
    /**
    如果传入的容量为0,那么将使用这个空元素数组
    **/
    private static final Object[] EMPTY_ELEMENTDATA = {};
    /**
    默认空元素数组,长度为0,传入元素时会初始化为默认元素大小
    **/
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    /**
    真正存储数据的数组
    **/
    transient Object[] elementData;
    /**
    列表中元素的个数
    **/
    private int size;
    复制代码

    这里需要主要关注的成员属性为 size 和 elementData ,一个是元素个数,一个是真正存储数据的数组

    构造函数

    /**
    指定数组长度构造
    **/
    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);
        }
    }
    /**
    空参构造
    **/
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    /**
    传入一个集合,将该集合的元素初始化到ArrayList种
    **/
    public ArrayList(Collection 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;
        }
    }
    复制代码

    扩容机制

    我们知道ArrayList是一个动态数组,但是他的底层实现是一个数组,那他是怎样保证动态的呢?

    ArrayList每次添加元素之前,都会检查添加元素后的元素个数是否超过数组长度,如果超出,那么就会进行扩容,而数组扩容通过一个公开的方法实现,我们也可以手动进行扩容

    public void ensureCapacity(int minCapacity) {
            //判断数组是否等于默认空数组,不等于则给minExpand赋值为10
            int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                ? 0 : DEFAULT_CAPACITY;
            //判断参数是否大于minExpand大于的时候才会去扩容
            if (minCapacity > minExpand) {           
                ensureExplicitCapacity(minCapacity);
            }
        }
        private void ensureExplicitCapacity(int minCapacity) {
            modCount++;//记录数组修改次数 + 1
            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);
            //数据拷贝
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    复制代码

    我们可以发现每次扩容,ArrayList都会扩容1.5倍,通过位运算完成计算扩容大小的,我们知道,扩容之后进行数据迁移这个操作是很费时间的,比如我们有10w条数据,这样的话,进行数据迁移的时候,我们会耗费很长时间,所以我们建议再初始化的时候就定义一个容量,这样可以让ArrayList的效率提高很多

    add方法

    //添加元素到尾部
    public boolean add(E e) {
        //检查是否需要扩容
        ensureCapacityInternal(size + 1); 
        //将元素添加到数组末尾,并把size++
        elementData[size++] = e;
        return true;
    }
    //添加元素到指定索引
    public void add(int index, E element) {
        //检查index是否越界
        rangeCheckForAdd(index);
        //检查是否需要扩容
        ensureCapacityInternal(size + 1);
        //将index以及之后的元素向后挪动一位
        //这样index就能添加元素了
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        //添加元素到index的位置
        elementData[index] = element;
        size++;
    }
    //将集合c的元素添加到list中
    public boolean addAll(Collection c) {
        //把c转换为数组
        Object[] a = c.toArray();
        //拿到c的长度
        int numNew = a.length;
        //检查是否需要扩容
        ensureCapacityInternal(size + numNew);  // Increments modCount
        //将a数组拷贝到原来数组的末尾
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }
    //将集合c的元素从index位置开始添加到list中
    public boolean addAll(int index, Collection c) {
        //检查index是否越界
        rangeCheckForAdd(index);
        //将c转换为数组
        Object[] a = c.toArray();
        //获取数组a的长度
        int numNew = a.length;
        //检查是否需要扩容
        ensureCapacityInternal(size + numNew);  // Increments modCount
        //计算需要移动的长度
        int numMoved = size - index;
        if (numMoved > 0)
            //向后移动
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
        将数组a拷贝到原数组中
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }
    复制代码

    get方法

    public E get(int index) {
        //检查index是否越界
        rangeCheck(index);
        //返回对应数组中指定索引的元素
        return elementData(index);
    }
    复制代码

    remove方法

    //删除指定索引的元素
    public E remove(int index) {
        //判断index是否越界
        rangeCheck(index);
        //将数组修改次数+1
        modCount++;
        //拿到对应索引的元素
        E oldValue = elementData(index);
        计算移动位置
        int numMoved = size - index - 1;
        if (numMoved > 0)
            //移动数组
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //size-1,并把尾部元素置为null,这里把尾部置为null主要是为了让GC起作用
        elementData[--size] = null;
    
        return oldValue;
    }
    //删除第一个满足o.equals(elementData[index]的元素
    public boolean remove(Object o) {
        if (o == null) {
            //如果o为null使用==进行判断
            //从索引为0的元素开始寻找
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            //否则使用equals判断
            //从索引为0的元素开始寻找
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    复制代码

    小结

    Collections.synchronizedList(list)
    

    LinkedList

    对于LinkedList,它同样继承与AbstractList,在前面已经说过了,AbstractList是List的骨架,我们还可以看到它实现了Deque,所以LinkedList既可以看做一个链表也可以看做是一个队列,同样也可以看做一个栈,所以LinkedList比较全能

    Node类

    我们知道LinkedList是一个双向链表,那么肯定有一个个的Node,所以我们先来看一看Node类

    private static class Node {
        E item;
        Node next;
        Node prev;
    
        Node(Node prev, E element, Node next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
    复制代码

    这部分代码比较简单就简单说一下,Node节点有三个成员属性,分别是value,前驱指针,后继指针,以及一个全参构造方法

    成员属性

    /**
    元素个数
     */
    transient int size = 0;
    /**
    指向链表头结点
     */
    transient Node first;
    /**
    指向链表尾节点
     */
    transient Node last;
    /**
    序列化ID
     */
    private static final long serialVersionUID = 876323262645176354L;
    复制代码

    构造函数

    //空参构造,没什么好说的
    public LinkedList() {
    }
    //将集合c的元素添加到链表中
    public LinkedList(Collection c) {
        //调用空参构造
        this();
        //调用addAll()这个方法在下面讲述
        addAll(c);
    }
    复制代码

    添加

    public boolean add(E e) {
        linkLast(e);//添加元素到末尾
        return true;
    }
    //将元素添加到指定index位置
    public void add(int index, E element) {
        //检查索引是否大于size或者小于0
        checkPositionIndex(index);
        //如果索引位置和size相等添加到末尾
        if (index == size)
            linkLast(element);
        else
            //添加到指定位置
            linkBefore(element, node(index));
    }
    public void addFirst(E e) {
        linkFirst(e);//添加元素到头部
    }
    public void addLast(E e) {
        linkLast(e);//添加元素到末尾
    }
    //添加到头部
    private void linkFirst(E e) {
         //拿到头指针
        final Node f = first;
        //new一个Node节点,值为e,next为头指针,pre为null
        final Node newNode = new Node<>(null, e, f);
        //将头指针替换为新的
        first = newNode;
        //将f的pre修改为现在的头指针
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }
    //添加到末尾
    void linkLast(E e) {
        //拿到尾指针
        final Node l = last;
        //new一个Node节点,值为e,next为null,pre为尾指针
        final Node newNode = new Node<>(l, e, null);
        //替换尾指针
        last = newNode;
        //将l的next修改为现在的尾指针
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
    //将集合c的元素添加到list中
    public boolean addAll(Collection c) {
        //从尾部开始添加
        return addAll(size, c);
    }
    //真正的addAll方法
    public boolean addAll(int index, Collection c) {
        //检查index正确
        checkPositionIndex(index);
        //先把c转换为数组
        Object[] a = c.toArray();
        //拿到c的长度
        int numNew = a.length;
        if (numNew == 0)
            return false;
        //定义两个指针,一个前驱一个后继
        Node pred, succ;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }
        //遍历数组a
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            //new一个Node节点,值为e,前驱为pred,后继为null
            Node newNode = new Node<>(pred, e, null);
            //pred为null,证明前驱为null,当前节点为链表的头结点
            if (pred == null)
                first = newNode;
            else
                //前驱节点后继指针指向头结点
                pred.next = newNode;
            //前驱节点后移
            pred = newNode;
        }
        //succ为null证明index索引位于链表最后
        if (succ == null) {
            last = pred;
        } else {
            //pred的后继节点为succ
            pred.next = succ;
            //succ的前驱节点为pred
            succ.prev = pred;
        }
    
        size += numNew;
        modCount++;
        return true;
    }
    复制代码

    获取

    //这个方法是Node类的方法,我们可以看到上面的addAll方法也使用了这个方法
    //这个方法作用是返回指定索引的非空节点
    Node node(int index) {
        //判断该索引位于前半段还是后半段
        if (index < (size >> 1)) {
            Node x = first;
            //前半段:从头部向后搜索
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node x = last;
            //后半段:从尾部向前搜索
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
    //获取index位置的元素
    public E get(int index) {
        //检查索引是否正常
        checkElementIndex(index);
        return node(index).item;
    }
    //获取头部元素
    public E getFirst() {
        final Node f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }
    //获取尾部元素
    public E getLast() {
        final Node l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }
    复制代码

    删除

    //删除index位置的元素
    public E remove(int index) {
        //检查索引是否大于size或者小于0
        checkElementIndex(index);
        //删除index位置的元素
        return unlink(node(index));
    }
    //删除头部元素,这个方法是Node类的方法
    private E unlinkFirst(Node f) {
        //拿到头节点的值
        final E element = f.item;
        //拿到头结点的next值
        final Node next = f.next;
        //将头结点的值置为null(帮助GC)
        f.item = null;
        //将头结点的next置为null(帮助GC)
        f.next = null;
        //将头结点修改为next
        first = next;
        if (next == null)
            //此时链表没有元素了
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }
    //删除尾部元素,这个方法是Node类的方法
    private E unlinkLast(Node l) {
        //拿到尾节点的值
        final E element = l.item;
        //拿到尾节点的前驱
        final Node prev = l.prev;
        //将尾结点的值置为null(帮助GC)
        l.item = null;
        //将尾结点的next置为null(帮助GC)
        l.prev = null;
        //将尾指针修改为prev
        last = prev;
        if (prev == null)
            //此时链表没有元素了
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }
    复制代码

    小结

    • 虽然说链表的删除的效率为O(1),但是在LinkedList中我们需要先利用node方法查询到指定节点的位置,然后再去删除,所以千万不要误认为LinkedList的remove方法是O(1)
    • LinkedList删除头部和尾部的元素效率为O(1)

    欢迎大家关注公众号「马小乐学技术」查看更多精彩分享文章,主要包括源码分析、实际应用、架构思维、职场分享、产品思考、面经资料等等,同时欢迎大家加我微信「sy200316x」一起交流学习 

  • 相关阅读:
    Linux--线程 共享内存空间
    Centos - DBMS(MariaDB)服务搭建
    sed 命令
    GBase XDM API 错误处理调用(上)
    云计算介绍
    填坑之路!SpringBoot导包坑之spring-boot-starter-parent
    三门问题的 Python 实验数据 & 直观但非严谨的证明
    学生HTML个人网页作业作品 HTML+CSS+JavaScript环保页面设计与实现制作
    【笔试题】【day17】
    全景分割(Panoptic Segmentation)(CVPR 2019)
  • 原文地址:https://blog.csdn.net/YYniannian/article/details/126259731