美文网首页数据结构与算法
数据结构第一季 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

    一、设计一个（无泛型、无动态扩容的）数组（仿照系统的 ArrayList） 1. 什么是数据结构？常见的三大类结构...

  • 100天iOS数据结构与算法实战 Day02 - 栈

    100天iOS数据结构与算法实战 Day02 - 栈 100天iOS数据结构与算法实战 Day02 - 栈

  • ArrayList和LinkList的区别

    ArrayList：是Array的数据结构，Array是动态数组，是对List接口的实现，他是数组队列，相当于动态...

  • 8.LinkedList

    ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。LinkedList不支...

  • 2020-07-16

    1、看完谷粒商城31 2、恋上数据结构之动态数组

  • 浅谈动态数组&数据结构（object-C）

    什么是数据结构？ 接下来我们手写一个动态数组 首先动态数组的接口设计如下： 实现代码如下： #import ...

  • Redis源码

    一、Redis数据结构： SDS SDS（动态字符串）包含字符数组buf[]，字符数组现有长度len，字符数组分配...

  • 数据结构与算法二（动态数组）

    目录一、什么是数据结构？二、线性表2.1 数组（Array）2.2 动态数组(Dynamic Array)接口设计...

  • ArrayList and LinkedList

    ArrayList and LinkedList ArrayList是实现了基于动态数组的数据结构，LinkedL...

  • ARTS-第二周

    Algorithm 从基础开始手写动态数组 git代码地址 数组定义：数组（Array）是一种线性表数据结构。它用...

网友评论

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

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

    延伸阅读

    深度阅读

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

    栏目导航

    热点阅读

    数据结构与算法

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

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

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

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

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

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