美文网首页数据结构与算法
数据结构第一季 Day02 动态数组DIY

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

作者: 望穿秋水小作坊 | 来源:发表于2021-02-28 21:49 被阅读0次

    一、设计一个（无泛型、无动态扩容的）数组（仿照系统的 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);
    }
}

    相关文章

      网友评论

        本文标题：数据结构第一季 Day02 动态数组DIY

        本文链接：https://www.haomeiwen.com/subject/dwgwfltx.html

        延伸阅读

        深度阅读

        • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

        栏目导航

        热点阅读

        数据结构与算法

        关于我们|服务条款|联系我们|数据结构第一季 Day02 动态数组DIY|投稿指南|网站地图|RSS订阅|排版工具|手机版

        提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

        Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

        备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

        本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

        所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！