数据结构第一季 Day02 动态数组DIY

一、设计一个（无泛型、无动态扩容的）数组（仿照系统的 ArrayList）

1. 什么是数据结构？常见的三大类结构是什么？

• 数据结构：是计算机存储、组织数据的方式
• 常见的三大类结构：线性结构、树形结构、图形结构

image.png

2. 大部分编程语言都有一个特点，创建的数组默认是支持动态扩容吗？如果要你设计一个动态扩容的数组，你从设计什么开始？

• 默认不支持动态扩容
• 如果要我设计一个动态扩容的数组，我会从动态数组的接口设计开始（从外层调用入手）

package com.lsp;

public class ArrayList {
    /**
     * 数组的数量
     * @return
     */
    public int size() {
        return 0;
    }
    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty() {
        return false;
    }
    /**
     * 是否包含某个元素
     * @param element
     * @return
     */
    public boolean contains(int element) {
        return false;
    }
    /**
     * 添加元素到最后面
     * @param element
     */
    public void add(int element) {
        
    }
    /**
     * 返回 index 位置对应的元素
     * @param index
     * @return
     */
    public int get(int index) {
        return 0;
    }
    /**
     * 设置 index 位置的元素
     * @param index
     * @param element
     * @return
     */
    public int set(int index, int element) {
        return 0;
    }
    /**
     * 往 index 位置添加元素
     * @param index
     * @param element
     */
    public void add(int index, int element) {
        
    }
    /**
     * 删除 index 位置对应的元素
     * @param index
     * @return
     */
    public int remove(int index) {
        return 0;
    }
    
    /**
     * 查看指定元素所在位置
     * @param element
     * @return
     */
    public int indexOf(int element) {
        return 0;
    }
    /**
     * 清除所有元素
     */
    public void clear() {
        
    }
}

3. 设计动态数组时，设计构造方法、size、isEmpty、get 方法时有什么注意事项？

• 构造函数 的 capacity 要有个默认最小值（边界思想）
• get函数 要进行边界判断，采用抛异常的方式最佳

public class ArrayList {
    /**
     * 所有元素
     */
    private int[] elements;
    /**
     * 元素数量
     */
    private int size = 0;
    
    private static final int DEFAULT_CAPACITY = 10;
    
    public ArrayList() {
        this(DEFAULT_CAPACITY);
    }
    
    public ArrayList(int capacity) {
        capacity = capacity < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : capacity;
        elements = new int[capacity];
    }
    
    /**
     * 数组的数量
     * @return
     */
    public int size() {
        return size;
    }
    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }
    /**
     * 返回 index 位置对应的元素
     * @param index
     * @return
     */
    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
        }
        return elements[index];
    }
}

4. 设计动态数组时， set、indexOf、contains、clear 函数要注意什么？

• ① indexOf 找不到返回 -1
• ② contains 可以调用 indexOf 的实现
• ③ clear 函数可以直接 size = 0

/**
     * 设置 index 位置的元素
     * @param index
     * @param element
     * @return
     */
    public int set(int index, int element) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
        }
        int old = elements[index];
        elements[index] = element;
        return old;
    }
    /**
     * 查看指定元素所在位置
     * @param element
     * @return
     */
    public int indexOf(int element) {
        for (int i = 0; i < elements.length; i++) {
            if (element == elements[i]) {
                return i;
            }
        }
        return ELEMENT_NOT_FOUND;
    }
    /**
     * 是否包含某个元素
     * @param element
     * @return
     */
    public boolean contains(int element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }
    /**
     * 清除所有元素
     */
    public void clear() {
        size = 0;
    }

5. add 、toString 方法的实现

    /**
     * 添加元素到最后面
     * @param element
     */
    public void add(int element) {
        elements[size] = element;
        size++;
    }
    @Override
    public String toString() {
        StringBuffer string = new StringBuffer();
        string.append("size=").append(size).append(",[");
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                string.append(",");
            }
            string.append(elements[i]);
        }
        string.append("]");
        return string.toString();
    }

6. remove 、add(index, element) 方法的实现核心是什么？

• 元素移动

/**
     * 删除 index 位置对应的元素
     * @param index
     * @return
     */
    public int remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
        }
        int old = elements[index];
        for (int i = index + 1; i <= size - 1  ; i++) {
            elements[i - 1] = elements[i];
        }
        size--;
        return old;
    }
    /**
     * 往 index 位置添加元素
     * @param index
     * @param element
     */
    public void add(int index, int element) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
        }
        for (int i = size -1; i >= index; i--) {
            elements[i + 1] = elements[i];
        }
        elements[index] = element;
        size++;
    }

7. 通过上面的代码发现，检查 index 的函数重复出现，我们可以考虑如何封装呢？

    public void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }
    public void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            outOfBounds(index);
        }
    }
    public void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }

8. 我们自己编写的数组已经具备一定能力了，现在要进入测试阶段，每次测试通过输出日志来观察，效率比较低，我可以通过断言类的编写，并且测试我们的 ArrayList

public class Assert {
    public static void test(boolean value) {
        try {
            if (!value) {
                throw new Exception("测试未通过");
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

• 编写测试用例

    public static void main(String[] args) {
        ArrayList list = new ArrayList();
        list.add(11);
        list.add(22);
        list.add(33);
        list.add(88);
        list.add(55);
        
        Assert.test(list.size() == 5);
        Assert.test(list.remove(0) == 11);
        Assert.test(list.size() == 4);
        Assert.test(list.set(1, 100) == 33);
        list.add(4, 200);
        Assert.test(list.size() == 5);
        Assert.test(list.get(4) == 200);
        System.out.println("所有测试通过");
    }

二、为动态数组增加自动扩容能力、以及泛型

1. 我们的动态数组还没有扩容能力，我们需要在哪个方法中扩容？如何扩容？

• 在 add(int index, int element) 方法中进行扩容

    public void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        int[] newElements = new int[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
        System.out.println(oldCapacity + "扩容成" + newCapacity);
    }

2. 我们的动态数组目前只支持 int 类型，如何支持任意任意类型呢？

• 使用泛型技术

// 关键代码一
        elements = (E[]) new Object[capacity];
// 关键代码二
        E[] newElements = (E[]) new Object[newCapacity];

3. 我们的动态数组从 int 变成泛型 E，这时候 clear 方法为什么要进行改造？

• 因为泛型 E 代表对象，对象不用了，要及时进行内存释放

    /**
     * 清除所有元素
     */
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

• 主动调用 System.gc() 让 JVM 及时回收垃圾

image.png

4. 我们的动态数组从 int 变成泛型 E，这个时候 remove 方法为什么要进行改造？

• remove 要对最后一个对象进行释放

    /**
     * 删除 index 位置对应的元素
     * 
     * @param index
     * @return
     */
    public E remove(int index) {
        rangeCheck(index);
        E old = elements[index];
        for (int i = index + 1; i <= size - 1; i++) {
            elements[i - 1] = elements[i];
        }
        elements[--size] = null;
        return old;
    }

5. 我们的动态数组从 int 变成泛型 E，同时我们需要支持 NULL 类型，这个时候 indexOf 方法为什么要进行改造？

• 主要是为了改造 equal 方法
• 同时注意避免 空指针异常

    /**
     * 查看指定元素所在位置
     * 
     * @param element
     * @return
     */
    public int indexOf(E element) {
        if (element == null) {
            for (int i = 0; i < elements.length; i++) {
                if (element == elements[i]) return i;
            }
        } else {
            for (int i = 0; i < elements.length; i++) {
                if (element.equals(elements[i])) return i;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

6.完整代码存盘

package com.lsp;

@SuppressWarnings("unchecked")
public class ArrayList<E> {
    /**
     * 所有元素
     */
    private E[] elements;
    /**
     * 元素数量
     */
    private int size = 0;

    private static final int DEFAULT_CAPACITY = 10;
    private static final int ELEMENT_NOT_FOUND = -1;

    public ArrayList() {
        this(DEFAULT_CAPACITY);
    }

    public ArrayList(int capacity) {
        capacity = capacity < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : capacity;
        elements = (E[]) new Object[capacity];
    }

    /**
     * 数组的数量
     * 
     * @return
     */
    public int size() {
        return size;
    }

    /**
     * 是否为空
     * 
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 返回 index 位置对应的元素
     * 
     * @param index
     * @return
     */
    public E get(int index) {
        rangeCheck(index);
        return elements[index];
    }

    /**
     * 设置 index 位置的元素
     * 
     * @param index
     * @param element
     * @return
     */
    public E set(int index, E element) {
        rangeCheck(index);
        E old = elements[index];
        elements[index] = element;
        return old;
    }

    /**
     * 查看指定元素所在位置
     * 
     * @param element
     * @return
     */
    public int indexOf(E element) {
        if (element == null) {
            for (int i = 0; i < elements.length; i++) {
                if (element == elements[i]) return i;
            }
        } else {
            for (int i = 0; i < elements.length; i++) {
                if (element.equals(elements[i])) return i;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    /**
     * 是否包含某个元素
     * 
     * @param element
     * @return
     */
    public boolean contains(E element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    /**
     * 清除所有元素
     */
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    /**
     * 添加元素到最后面
     * 
     * @param element
     */
    public void add(E element) {
        add(size, element);
    }

    /**
     * 删除 index 位置对应的元素
     * 
     * @param index
     * @return
     */
    public E remove(int index) {
        rangeCheck(index);
        E old = elements[index];
        for (int i = index + 1; i <= size - 1; i++) {
            elements[i - 1] = elements[i];
        }
        elements[--size] = null;
        return old;
    }

    /**
     * 往 index 位置添加元素
     * 
     * @param index
     * @param element
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacity(size + 1);
        for (int i = size - 1; i >= index; i--) {
            elements[i + 1] = elements[i];
        }
        elements[index] = element;
        size++;
    }

    public void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
        System.out.println(oldCapacity + "扩容成" + newCapacity);
    }

    @Override
    public String toString() {
        StringBuffer string = new StringBuffer();
        string.append("size=").append(size).append(",[");
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                string.append(",");
            }
            string.append(elements[i]);
        }
        string.append("]");
        return string.toString();
    }

    public void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }

    public void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            outOfBounds(index);
        }
    }

    public void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }
}