JDK1.8-List

一.ArrayList

1.数据结构

ArrayList底层数据结构是一个Object[]数组，底层数组的默认初始化容量为10。

    // 初始容量为 10
    private static final int DEFAULT_CAPACITY = 10;
    //空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};
    //默认的空数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    //存放元素的对象数组
    transient Object[] elementData;
    //集合中元素的个数
    private int size;
    //最大容量
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

1.在jdk1.8中ArrayList底层先创建一个长度为0的数组

//如果在创建集合的时候指定了长度，那么就会创建一个指定长度的数组。
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;
    }

2.在第一次添加元素时，会初始化一个长度为10的数组

2.扩容

扩容会传入一个minCapacity(最小容量)，若当前有size个元素，有元素的最后一个下标是size-1，所以我们当前一定要保证下标为size的空间是存在的，还要保证size+1 后的空间是存在的，所以最小容量的定义为size+1。
因为当ArrayList容量使用完之后，就会自动创建当前容量1.5倍的新数组，并将原数组中所有元素拷贝过去，但是，如果新数组的长度小于最小容量，那么将以最小容量作为新数组的长度，如果新数组的长度大于Integer的最大值-8，就会以Integer的最大值作为新数组的长度，这会导致效率降低。
优化：可以使用构造方法ArrayList(int initialCapacity)或者ensureCapacity(int initialCapacity)直接提供一个初始化容量，避免刚开始就一直扩容，造成效率降低。

3.构造方法

//创建一个指定初始化容量为 initialCapactity 的空列表
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);
        }
    }
//创建一个空列表，第一次添加会将容量初始化为10
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
//创建一个包含指定集合中所有元素的列表
    public ArrayList(Collection<? extends E> c) {
        // Collection 转为数组赋给 elementData
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            //如果数组不是空，将元素复制进集合
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            //否则存入一个空数组.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

4.特点

(1).优点

向ArrayList末尾添加元素(使用add()方法)时，效率较高。
因为底层是数组的原因所以查询效率高。

(2).缺点

扩容会造成效率降低(可以通过指定初始化容量，在一定程度上得到改善)
数组很难存储大数据量(很难找到一块很大的连续内存空间)
如果向ArrayList中间添加元素，需要移动元素，会影响效率。

5.常用内部方法

(1).add方法

//直接将元素添加到数组的末尾
public boolean add(E e) {
        //容量校验
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //从数组的末尾存入元素
        elementData[size++] = e;
        return true;
    }
//将元素添加到下标为index的位置
public void add(int index, E element) {
        //判断index是否合理
        rangeCheckForAdd(index);
        //容量校验
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //将index后的元素后移，将index的位置空出来，插入数据
        System.arraycopy(elementData, index, elementData, index + 1,size - index);
        elementData[index] = element;
        size++;
    }
//
private void ensureCapacityInternal(int minCapacity) {
/*
首先是判断现在的ArrayList是不是空的。
如果是空的，最小容量就取默认容量与最小容量的最大值
*/
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //判断是否扩容
        ensureExplicitCapacity(minCapacity);
    }
//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
        //操作次数++
        modCount++;
        // overflow-conscious code
        //minCapactity为size+1，如果他超过了底层数组的长度,就会触发扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

(2).grow方法

private void grow(int minCapacity) {
        // overflow-conscious code
        //暂存存储数组的长度
        int oldCapacity = elementData.length;
        /*
        定义扩容后数组的长度
        长度为旧数组长度+旧数组长度/2 也就是扩容1.5倍。
        */
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果扩容后的数组长度比最小容量还要小，那么直接让最小容量作为扩容后数组长度
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        /*
        MAX_ARRAY_SIZE为Integer的最大值-8
        如果扩容后的数组长度+8比Integer的最大值还大
        那么调用hugeCapacity方法
        */
        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);
    }

(3).hugeCapacity方法

private static int hugeCapacity(int minCapacity) {
        //最小容量是不能小于0的
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        //如果最小容量大于Integer的最大值-8就取Integer的最大值，否则就取Integer的最大值-8;
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

(4).indexOf方法

//用以判断一个元素是否在集合中，存在就返回该元素索引,否则返回-1
public int indexOf(Object o) {
        //如果元素为null
        if (o == null) {
            for (int i = 0; i < size; i++)
                //找到第一个为null的元素返回他的索引
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                //如果不为null，则返回第一个值匹配的索引
                if (o.equals(elementData[i]))
                    return i;
        }
        //如果找不到就返回-1
        return -1;
    }
//与indexof相似，lastIndexOf是反向遍历返回的是最后出现元素的索引
public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

(5).get方法

public E get(int index) {
        //检验index是否合理
        rangeCheck(index);
        //获取元素
        return elementData(index);
    }
//检验index是否合理
private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
//获取元素
E elementData(int index) {
        return (E) elementData[index];
    }

(6).set方法

//将索引为index的元素修改为element，并返回旧元素
public E set(int index, E element) {
        //检验index是否合理
        rangeCheck(index);
        //暂存索引为index的元素
        E oldValue = elementData(index);
        //修改索引为index的元素
        elementData[index] = element;
        //返回旧元素
        return oldValue;
    }

(7).remove方法

//通过索引删除，并且返回删除值
public E remove(int index) {
        //检验index是否合理
        rangeCheck(index);
        //操作次数++
        modCount++;
        //暂存删除数据
        E oldValue = elementData(index);
        //计算需要移动多少位数组
        int numMoved = size - index - 1;
        //如果需要移动的次数大于0，就将index后一位的元素集体前移一位
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,numMoved);
        //清空最后一位
        elementData[--size] = null; // clear to let GC do its work
        //删除删除的元素
        return oldValue;
    }
//通过元素删除，返回是否删除成功
public boolean remove(Object o) {
        if (o == null) {
        //如果元素为null，删除第一个为null的元素
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                //调用fastRemove删除
                    fastRemove(index);
                    return true;
                }
        } else {
        //从头遍历，删除数组中第一个等于o的元素。
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        //数组中没有该元素返回false
        return false;
    }
//跳过边界查找，没有返回值的快速删除
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
    }

二.LinkedList

1.数据结构

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;
        }
    }

2.特点

LinkedList也有下标，但是它的底层是使用的链表，所以内存不一定是连续的。
可以使用get(int index)方法，返回链表中第 index 个元素，每次查找都是从头/尾结点开始遍历。
增删效率较高，查询效率较低，多用于增删操作较多的场景。

3.常用内部方法

(1).get方法

public E get(int index) {
        //判断index是否合理
        checkElementIndex(index);
        //调用node方法返回第index个元素的值
        return node(index).item;
    }
//node方法
Node<E> node(int index) {
        // assert isElementIndex(index);
        /*
        基于底层是双向链表的特性，在检索时并不会傻傻的从第一个结点开始遍历，
        底层会判断查询的索引有没有超过链表长度的一半，
        如果没有从头遍历，如果超过了从尾部遍历
        */
        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;
        }
    }

(2).add方法

public boolean add(E e) {
        linkLast(e);//使用尾插法添加元素e
        return true;
    }
//尾插法
void linkLast(E e) {
        //保存最后一个元素的指针
        final Node<E> l = last;
        //新建一个newNode结点作为尾结点
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        //当链表为空时，newNode就是第一个结点first
        if (l == null)
            first = newNode;
        //当链表不为空，最后一个结点的next指向newNode；
        else
            l.next = newNode;
        //链表长度++
        size++;
        //修改次数++
        modCount++;
    }

(3).addAll方法

public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
public boolean addAll(int index, Collection<? extends E> c) {
        //校验index是否合理
        checkPositionIndex(index);
        //调用toArray方法，将集合拷贝为一个数组
        Object[] a = c.toArray();
        //获取数组的长度
        int numNew = a.length;
        //如果数组是空的，返回
        if (numNew == 0)
            return false;
        /*
        定义两个结点
        pred 来存储前一个节点的引用
        succ存储当前节点
        */
        Node<E> pred, succ;
        //如果索引index等于链表长度，那么直接从末尾添加结点
        if (index == size) {
            succ = null;
            pred = last;
        } else {
        //否则就从索引处添加结点
            succ = node(index);
            pred = succ.prev;
        }
        //遍历数组元素进行添加操作
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            //将集合元素 的prev指向pred
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
            //如果是空链表，那么newNode就是头结点
                first = newNode;
            else
            //否者pred的后继就是newNode
                pred.next = newNode;
            pred = newNode;
        }
        //如果当前这个结点是空的
        if (succ == null) {
            //pred结点为最后一个结点
            last = pred;
        } else {
            //否则pred的下一个引用指向succ
            pred.next = succ;
            //尾节点的上一个引用指向pred
            succ.prev = pred;
        }
        //原来的size+新添加的数组长度 就是新链表的size
        size += numNew;
        //操作次数++
        modCount++;
        return true;
    }
//内部结点类构造方法
Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }

(4).remove方法

//根据索引删除结点
public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }
//根据元素删除结点
public boolean remove(Object o) {
        //单独处理null
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
            //遍历到为null的元素，移除掉
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
            //遍历到值等于o的结点直接移除掉
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
//使用unlink方法拿掉结点
E unlink(Node<E> x) {
        //断言x不为空
        // assert x != null;
        final E element = x.item; //暂存x结点
        final Node<E> next = x.next;//暂存x的后继结点
        final Node<E> prev = x.prev;//暂存x的前驱结点
        if (prev == null) {
        //如果x是头结点，把x的后继结点设为头节点
            first = next;
        } else {
            //跳过x结点
            prev.next = next;
            //断开x结点的前驱
            x.prev = null;
        }
        if (next == null) {
        //如果x结点是尾结点，将x的前驱结点设置为尾结点
            last = prev;
        } else {
            //跳过x结点
            next.prev = prev;
            //断开x结点的后继
            x.next = null;
        }
        //将x结点的值清空
        x.item = null;
        //链表长度--
        size--;
        //操作次数++
        modCount++;
        //之前有做暂存，将被删除的结点返回回去
        return element;
    }

(5).set方法

public E set(int index, E element) {
        //校验index是否合理
        checkElementIndex(index);
        //找到索引为index的结点
        Node<E> x = node(index);
        //保存x结点的值
        E oldVal = x.item;
        //将x结点的值设为element
        x.item = element;
        //将之前的值返回
        return oldVal;
    }

lc27.移除元素

JDK1.8-Set

bigWer

Comments | NOTHING

取消回复

bigWer