17-手写List框架
in 004-源码分析 with 0 comment
List

17-手写List框架

in 004-源码分析 with 0 comment

List

1 集合框架介绍

集合框架简图

  1. List集合是有序集合，集合中的元素可以重复，访问集合中的元素可以根据元素的索引来访问。
  2. Set集合是无序集合，集合中的元素不可以重复，访问集合中的元素只能根据元素本身来访问（也是集合里元素不允许重复的原因）。
    Map集合中保存Key-value对形式的元素，访问时只能根据每项元素的key来访问其value。

2 纯手写List框架

List集合代表一个有序集合，集合中每个元素都有其对应的顺序索引。List集合允许使用重复元素，可以通过索引来访问指定位置的集合元素。
List接口继承于Collection接口，它可以定义一个允许重复的有序集合。因为List中的元素是有序的，所以我们可以通过使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。
List接口为Collection直接接口。List所代表的是有序的Collection，即它用某种特定的插入顺序来维护元素顺序。用户可以对列表中每个元素的插入位置进行精确地控制，同时可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。实现List接口的集合主要有：ArrayList、LinkedList、Vector、Stack。

3 ArrayList实现

3.1 Arraylist底层基于数组实现

image.png

3.2 Arraylist底层默认数组初始化大小为10个object数组

image.png

3.3 添加元素后大于当前数组的长度，则进行扩容,将数组的长度增加原来数组的一半。

3.4 手写Arraylist底层框架

3.4.1 自定List接口

public interface ExtList<E> {

    int size();

    boolean add(E e);

    void add(int index, E e);

    E get(int index);

    E remove(int index);

    boolean remove(E e);
}

3.4.2 实现List接口

public class ExtArrayList<E> implements ExtList<E> {

    private static final int DEFAULT_CAPACITY = 10;

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    private static final Object[] EMPTY_ELEMENTDATA = {};

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    private transient Object[] elementData;

    /**
     * 实际容量大小
     */
    private int size;

    public ExtArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    public ExtArrayList(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);
        }
    }

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    @Override
    public boolean add(E e) {
        // 1.判断实际存放的容量是否大于elementData
        ensureCapacityInternal(size + 1);
        // 2.使用下标进行赋值
        elementData[size++] = e;
        return true;
    }

    @Override
    public void add(int index, E e) {
        // 1.判断实际存放的容量是否大于elementData
        ensureCapacityInternal(size + 1);
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        // 2.使用下标进行赋值
        elementData[index] = e;
        size++;
    }


    /**
     * 判断实际存放的容量是否大于elementData
     *
     * @param minCapacity 最小为size+1
     * @return void
     * @throws
     * @author zhouxinlei
     * @date 2019-12-24 14:43:09
     */
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private void ensureExplicitCapacity(int minCapacity) {
        if (minCapacity - elementData.length > 0) {
            grow(minCapacity);
        }
    }


    private void grow(int minCapacity) {

        //原数组容量大小
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //最小扩容容量
        if (newCapacity - minCapacity < 0) {
            newCapacity = minCapacity;
        } else if (newCapacity - MAX_ARRAY_SIZE > 0) {
            newCapacity = hugeCapacity(minCapacity);
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    E elementData(int index) {
        return (E) elementData[index];
    }

    @Override
    public E get(int index) {
        //判断数组是否越界
        rangeCheck(index);
        return elementData(index);
    }

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

    private String outOfBoundsMsg(int index) {
        return "Index: " + index + ", Size: " + size;
    }

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

    private void fastRemove(int index) {
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            System.arraycopy(elementData, index + 1, elementData, index,
                    numMoved);
        }
        elementData[--size] = null;
    }

    @Override
    public E remove(int index) {
        E e = get(index);
        int numMoved = elementData.length - index - 1;
        if (numMoved > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        }
        elementData[--size] = null;
        return e;
    }

    @Override
    public boolean remove(Object object) {
        if (object == null) {
            for (int index = 0; index < elementData.length; index++) {
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
            }
        } else {
            for (int index = 0; index < elementData.length; index++) {
                if (object.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
            }
        }
        return false;
    }

    @Override
    public int size() {
        return this.size;
    }
}

3 LinkList实现

LinkedList 和 ArrayList 一样，都实现了 List 接口，但其内部的数据结构有本质的不同。LinkedList 是基于链表实现的（通过名字也能区分开来），所以它的插入和删除操作比ArrayList 更加高效。但也是由于其为基于链表的，所以随机访问的效率要比ArrayList差。

3.1 LinkedList数据结构原理

LinkedList底层的数据结构是基于双向循环链表的，且头结点中不存放数据,如下：
LinkList1.jpeg

既然是双向链表，那么必定存在一种数据结构——我们可以称之为节点，节点实例保存业务数据，前一个节点的位置信息和后一个节点位置信息，如下图所示：
LinkList2.png

3.2 数组和链表结构对比

3.3 内存存储区别

3.4 逻辑结构区别

3.5 总结

3.6 手写LinkList代码实现

LinkList6.png

本文由 凛冬王昭君 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Feb 26,2020

← → ↓ ↑