ArrayList、LinkedList集合源码

逃离我推掉我的手 2023-09-25 21:12 122阅读 0赞

### 一、ArrayList集合源码 ###

--------------------

#### 1、ArrayList的特点 ####

*  数据结构：基于数组实现，类型：object类型；
 *  存放元素：有序，可重复；
 *  线程是否安全：不安全，效率高。（没有加上锁机制）
 *  特点：查询快、增删慢；
    
     *  查询快：因为ArrayList底层是基于动态数组实现的，所存储的数据在内存中是连续的，可以通过下标获取元素，即get(index)方法，时间复杂度为O(1);
     *  增删慢: 数组长度是不可改变，需要频繁创建新数组，拷贝元素，销毁老数组（扩容、缩容）。

> Vector的特点：
> 
>  *  底层基于数组实现的；
>  *  查询快、增上慢；
>  *  线程同步，安全，效率低。

#### 2、时间复杂度 ####

*  O(1)：只需查询一次就能找到元素，例如：get(index)方法，基于下标查询；
 *  O(n)：需要从头查到尾部，例如：根据元素值查询；（如 链表）
 *  O(log n)：二叉树、红黑树。

#### 3、add方法与扩容机制 ####

##### 3.1 add方法实现 #####

package com.baidou.list;
    
    public class MyArrayList<T> {
        
        /**
         * 存放元素的数组
         */
        Object[] elementData;
    
        /**
         * elementData 存放元素的个数
         */
        private int size;
    
        /**
         * elementData 默认初始容量为10
         */
        private static final int DEFAULT_CAPACITY = 10;
    
    
        /**
         * 无参构造器
         */
        public MyArrayList() {
        
        }
    
    
        /**
         * 新增元素
         *
         * @param t 元素
         */
        public void add(T t) {
        
            // 默认的初始化
            if (elementData == null) {
        
                // 如果创建ArrayList集合时没有指定大小，默认初始长度为10
                elementData = new Object[DEFAULT_CAPACITY]; // CAPACITY:10
            }
            elementData[size++] = t;
        }
    
        /**
         * 获取元素
         *
         * @param index
         * @return
         */
        public T get(int index) {
        
            return (T) elementData[index];
        }
    
        public static void main(String[] args) {
        
            MyArrayList<String> arr = new MyArrayList<String>() {
        
                {
        
                    add("Hello");
                    add("world");
                }
            };
            String arr_Index0_Value = arr.get(0);
            System.out.println(arr_Index0_Value);
    
        }
    }

##### 3.2 扩容机制 #####

> 扩容：ArrayList每次扩容是原来的1.5倍。

1、源码分析：

*  调用链条：add()—>ensureCapacityInternal()—>calculateCapacity()—>ensureExplicitCapacity(?)—>**grow()**

public void add(int index, E element) {
        
        rangeCheckForAdd(index);
    
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
    
    // 模拟ArrayList存放第11个元素场景
    private void grow(int minCapacity) {
         //11
       
        // 原来容量 10
        int oldCapacity = elementData.length; 
        
        // 新的容量 10+(10/2)=15
        int newCapacity = oldCapacity + (oldCapacity >> 1); 
        
        if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //false   
        
        // 新的容器是否超过这个数值界限
        if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); //fase       
       
        // 扩容
        // 拷贝数组，数组长度为15
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

2、add方法，扩容原理实现：

public void add(T t) {
        
        // 默认的初始化
        if (elementData == null) {
        
            // 如果创建ArrayList集合时没有指定大小，默认长度为10
            elementData = new Object[DEFAULT_CAPACITY]; // CAPACITY:10
        }
    
        // 判断是否需要做扩容
        if (size + 1 > elementData.length) {
        
            // 原来容量
            int oldCapacity = elementData.length;
            // 新的容量
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            // 扩容
            elementData = Arrays.copyOf(elementData,newCapacity);
        }
    
        elementData[size++] = t;
    }

#### 4、remove方法与缩容机制 ####

1、源码分析：

//根据元素内容删,时间复杂度为O(n)
    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;
    }
    
    //缩容方法
    private void fastRemove(int index) {
        
        modCount++; //因为arraylist是非线程安全,需要记录增删操作
        
        // 模拟集合容量为15,元素个数为11,删除第十个元素
        
        // 计算删除index后面的元素有多少个
        //11-9-1=1;
        int numMoved = size - index - 1;
        if (numMoved > 0) 
     
         	// index后面的元素要向前移动1位
            System.arraycopy(elementData, index+1, elementData, index,numMoved);
                             
        elementData[--size] = null; // 把最后一个元素变为null
    }

2、remove方法，缩容原理实现：

// 根据内容删除元素
    public boolean remove(T t) {
        
        if (t == null) {
        
            // 如果删除元素内容为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 (t.equals(elementData[index])) {
        
                    fastRemove(index);
                    return true;
                }
            }
        }
    
        return false;
    }
    
    /**
    * 缩容实现
    *
    * @param index 删除元素的索引
    */
    private void fastRemove(int index) {
        
        // 计算删除index后面的元素有多少个
        int numMoved = size - index - 1;
        if (numMoved > 0) {
        
            // 把index后面的元素往前移动1位
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        }
        elementData[--size] = null; // 把最后一个元素变为null
    }

#### 5、modCount的作用 ####

> modCount:记录当前集合被修改的次数。 新增和删除modCount会++

例如：在多线程的情况下，A线程去遍历集合，B线程去存放数据，会抛出并发修改异常。

@Override
    public void forEach(Consumer<? super E> action) {
        
        Objects.requireNonNull(action);
        final int expectedModCount = modCount;
        @SuppressWarnings("unchecked")
        final E[] elementData = (E[]) this.elementData;
        final int size = this.size;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
        
            action.accept(elementData[i]);
        }
        // 如果当前的modCount和预期count值不一致时,会抛并发修改异常
        if (modCount != expectedModCount) {
        
            throw new ConcurrentModificationException();
        }
    }

![在这里插入图片描述][6a43df1056da46bfa2549630dd462c04.png]

### 二、LinkedList集合源码 ###

[6a43df1056da46bfa2549630dd462c04.png]: https://img-blog.csdnimg.cn/6a43df1056da46bfa2549630dd462c04.png