17-手写List框架

凛冬王昭君 2020年02月26日 320次浏览

1 集合框架介绍

集合框架简图

  • 所有集合类都位于java.util包下。Java的集合类主要由两个接口派生而出:Collection和Map,Collection和Map是Java集合框架的根接口,这两个接口又包含了一些子接口或实现类。
  • 集合接口:6个接口(短虚线表示),表示不同集合类型,是集合框架的基础。
  • 抽象类:5个抽象类(长虚线表示),对集合接口的部分实现。可扩展为自定义集合类。
  • 实现类:8个实现类(实线表示),对接口的具体实现。
  • Collection 接口是一组允许重复的对象。
  • Set 接口继承 Collection,集合元素不重复。
  • List 接口继承 Collection,允许重复,维护元素插入顺序。
  • Map接口是键-值对象,与Collection接口没有什么关系。
  • Set、List和Map可以看做集合的三大类:
  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 添加元素后大于当前数组的长度,则进行扩容,将数组的长度增加原来数组的一半。

  • add方法
    image.png
  • 判断实际存放的容量是否大于elementData
    image.png
  • 判断是否需要扩容
    image.png
  • 扩容实现
    image.png

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 数组和链表结构对比

  • 数组是将元素在内存中连续存放,由于每个元素占用内存相同,可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素,需要移动大量元素,在内存中空出一个元素的空间,然后将要增加的元素放在其中。同样的道理,如果想删除一个元素,同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据,很少插入和删除元素,就应该用数组。
    array.jpeg
  • 链表中的元素在内存中不是顺序存储的,而是通过存在元素中的指针联系到一起,每个结点包括两个部分:一个是存储 数据元素 的 数据域,另一个是存储下一个结点地址的 指针。如果要访问链表中一个元素,需要从第一个元素开始,一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了,只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表。
    LinkList3.jpeg

3.3 内存存储区别

  • 数组从栈中分配空间, 对于程序员方便快速,但自由度小。
  • 链表从堆中分配空间, 自由度大但申请管理比较麻烦。

3.4 逻辑结构区别

  • 数组必须事先定义固定的长度(元素个数),不能适应数据动态地增减的情况。当数据增加时,可能超出原先定义的元素个数;当数据减少时,造成内存浪费。 
  • 链表动态地进行存储分配,可以适应数据动态地增减的情况,且可以方便地插入、删除数据项。(数组中插入、删除数据项时,需要移动其它数据项) 

3.5 总结

  • 存取方式上,数组可以顺序存取或者随机存取,而链表只能顺序存取; 
  • 存储位置上,数组逻辑上相邻的元素在物理存储位置上也相邻,而链表不一定; 
  • 存储空间上,链表由于带有指针域,存储密度不如数组大; 
  • 按序号查找时,数组可以随机访问,时间复杂度为O(1),而链表不支持随机访问,平均需要O(n); 
  • 按值查找时,若数组无序,数组和链表时间复杂度均为O(1),但是当数组有序时,可以采用折半查找将时间复杂度降为O(logn); 
  • 插入和删除时,数组平均需要移动n/2个元素,而链表只需修改指针即可; 
  • 空间分配方面: 数组在静态存储分配情形下,存储元素数量受限制,动态存储分配情形下,虽然存储空间可以扩充,但需要移动大量元素,导致操作效率降低,而且如果内存中没有更大块连续存储空间将导致分配失败; 链表存储的节点空间只在需要的时候申请分配,只要内存中有空间就可以分配,操作比较灵活高效;

3.6 手写LinkList代码实现

LinkList6.png