Java技能培训：List集合源码分析

小灰灰 2023-10-16 12:10 30阅读 0赞

### 　一、ArrayList集合 ###

#### 　　1.数据结构特点 ####

ArrayList底层数据结构是一个数组,查询元素速度快,增删速度稍慢

#### 　　2.几个概念: ####

(1)DEFAULT\_CAPACITY: 表示数组的初始大小,默认10

(2)size: 表示当前数组的大小

(3)modCount: 统计当前数组元素被修改的次数,只要修改,就+1

#### 　　3.空参构造方法初始化 ####

#### 　　4.第一次添加元素扩容原理 ####

public boolean add(E e) {
            //确保数组大小是否足够,不够执行扩容,size为当前数组的大小
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            //直接把元素e保存到数组中
            elementData[size++] = e;
            return true;
        }

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        //如果是空数组{}
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //在最小容量minCapacity和DEFAULT_CAPACITY(10)选择一个较大的值
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    private void ensureExplicitCapacity(int minCapacity) {
        //记录修改次数
        modCount++;
        //如果我们期望的最小容量>数组目前的长度就扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //oldCapacity >> 1: 是把oldCapacity/2的意思
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果扩容后的值<我们期望的值,扩容后的值等于我们期望的值
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果扩容后的值>jvm所能分配的数组的最大值,那么就用Integer的最大值
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //通过复制数组扩容
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

### 　　注意: ###

1.扩容的规则并不是翻倍,是原来容量大小的1.5倍

2.ArrayList中数组的最大长度是Integer.MAX\_VALUE,超过这个值,JVM就不会给数组分配内存空间了

3.新增元素时,并没有对值进行严格的校验,所以ArrayList是允许null值的

### 　　二、LinkeList集合 ###

#### 　　1.数据结构特点: ####

LinkedList底层数据结构是一个双向链表,链表中的每个节点都可以查找前一个节点或者向后查找后一个节点

#### 　　2.几个概念: ####

(1)链表每个节点叫做Node,Node有prev属性,代表前一个节点的地址,next属性代表后一个节点的地址

(2)first是双向链表的头节点,它的前一个节点是null

(3)last是双向链表的尾节点,它的后一个节点是null

(4)链表中如果没有数据,first和last都null

(5)因为是双向链表,只要内存空间足够大,链表的大小是没有限制的

#### 　　3.链表中的元素(节点)叫做Node,是LinkedList集合的私有静态内部类,代码如下: ####

private static class Node<E> {
            E item;//节点数据
            Node<E> next;//下一个节点的地址
            Node<E> prev;//前一个节点的地址
            //初始化参数顺序是: 前一个节点地址,节点本身的数据,后一个节点地址
            Node(Node<E> prev, E element, Node<E> next) {
                this.item = element;
                this.next = next;
                this.prev = prev;
            }
        }

#### 　　4.add添加节点(从链表尾部添加) ####

public boolean add(E e) {
        linkLast(e);
        return true;//链表节点数据可以重复,所以add方法始终返回true
    }

//从尾部添加节点
    void linkLast(E e) {
        //把尾节点地址存储在l中
        final Node<E> l = last;
        //创建新的节点,参数含义如下
        //l是新节点的前一个节点的地址,当前值是尾节点地址值
        //e是当前新增节点中保存的数据,当前新增节点的下一个节点是null,因为是在末尾添加
        final Node<E> newNode = new Node<>(l, e, null);
        //last指向新增节点(新增节点作为尾节点)
        last = newNode;
        //如果链表为空(第一次添加节点)(l是尾节点,尾节点为空,链表即空),头部和尾部都是指向同一个节点,都是新建的节点
        if (l == null)
            first = newNode;
        else
            //链表不是空(非第一次添加节点),把添加新节点之前的尾节点的下一个节点指向新添加的节点
            l.next = newNode;
        //节点数+1
        size++;
        //链表的实际修改次数+1
        modCount++;
    }

#### 5.get(int index)查询节点 ####

public E get(int index) {
            checkElementIndex(index);//检查索引值是否越界
            return node(index).item;
        }
        private void checkElementIndex(int index) {
            if (!isElementIndex(index))
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
        private boolean isElementIndex(int index) {
            return index >= 0 && index < size;
        }
        核心根据索引获取节点数据的方法
        链表查询某个节点是比较慢的,需要挨个查找才可以

根据链表索引位置查询元素
    Node<E> node(int index) {
        //如果index处于链表的前半部分,从头开始查,size>>1 是 size/2的意思
        if (index < (size >> 1)) {
           
            Node<E> x = first;
            //知道for循环到index的前一个node停止
            for (int i = 0; i < index; i++)            
                x = x.next;
            return x;
        } else {
            //如果index处于链表的后半部分,从尾开始查
            Node<E> x = last;
            //知道for循环到index的后一个node停止
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

从源码中发现,LinkedList并没有采用从头循环到尾的做法,而是采取了简单二分查找法,

首先看index是在链表的左半部分还是右半部分.如果是在左半部分,就从左侧开始找,

如果实在链表的有伴部分,就从右侧开始找.这种方式,循环的次数至少降低了一半,提高查询性能。

本文版权归黑马程序员Java培训学院所有，欢迎转载，转载请注明作者出处。谢谢!

作者：黑马程序员Java培训学院

首发：Java技能培训：List集合源码分析