美文网首页
数据结构 - 动态数组学习笔记

数据结构 - 动态数组学习笔记

作者: 我阿郑 | 来源:发表于2021-12-16 21:23 被阅读0次

数据结构和算法动态可视化网站

学习李明杰老师的恋上数据结构笔记

一、 数组

数组是一种顺序存储的线性表，所有元素的内存地址都是连续的。

int[] array = new int[]{11, 22, 33}

在很多编程语言中，数组有个致命的缺点， 无法动态修改容量。实际开发中我们希望数组的容量是动态变化的。

二、动态数组（Dynamic Array）接口设计

  • 创建ArrayList类
public class ArrayList<E> {
    private int size; // 管理数组中元素的个数
    private E[] elements; // 管理存取的数据

    // 元素的数量
    int size(); 
    // 是否为空
    boolean isEmpty();
    // 是否包含某个元素
    boolean contains(E element); 
    // 添加元素到最后面
    void add(E element);
   // 往index位置添加元素
    void add(int index, E element);  
    // 返回index位置对应的元素
    E get(int index); 
    // 设置index位置的元素
    E set(int index, E element); 
    // 删除index位置对应的元素 
    E remove(int index); 
    // 查看元素的位置
    int indexOf(E element); 
    // 清除所有元素
    void clear(); 
}

在Java中，成员变量会自动初始化，比如：

  • int 类型自动初始化为 0
  • 对象类型自动初始化为 null

三、动态数组的设计和实现

1、构造方法

如果构建的数组空间小于默认空间，则会以默认空间构建数组。

public class ArrayList<E> {
    private int size;
    private E[] elements;
    // 设置elements数组默认的初始化空间
    private static final int CAPACITY_DEFAULT = 10;
    
    public ArrayList(int capacity) {
        capacity = capacity < CAPACITY_DEFAULT ? CAPACITY_DEFAULT : capacity;
        elements = (E[]) new Object[capacity];
    }
    
    // 便利构造器
    public ArrayList() {
        this(CAPACITY_DEFAULT);
    }
}

2、添加元素

数组添加元素分为两种情况：

  • Case1 ：在最后一个元素的后面添加新元素
    • 这个新元素需要添加到的索引等于当前数组元素的个数 加1（即 size + 1）
  • Case2: 将元素插入到某个位置（非最后面）。
/**
 * 添加元素到尾部
 * @param element
 */
public void add(E element) {
    add(size, element);
}

/**
 * 在index位置插入一个元素
 * @param index
 * @param element
 */
public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacity(size + 1);
    for (int i = size; i > index; i--) {
        elements[i] = elements[i - 1];
    }
    elements[index] = element;
    size++;
}
// 检测数组越界
private void rangeCheckForAdd(int index) {
    if (index < 0 || index > size) {
        outOfBounds(index);
    }
}
private void outOfBounds(int index) {
    throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}

如果是Case2的情况，需要依次变动插入位置后面的元素
⚠️ 注意，需要从最后一个元素开始变动

比如有一个原数组 {11, 22, 33,55}, 向index=2的位置插入元素44

image.png

（即：把55赋值到index为4的位置，把33赋值到index为3的位置，最后把44赋值到index为2的位置）

image.png

3、数组扩容

由于数组elements最大的容量只有10，所以当数组存满元素时，就需要对数组进行扩容。

因为数组是无法动态扩容的，所以需要创建一个新的数组，这个数组的容量要比之前数组的容量大。接着，将原数组中的元素存放到新数组中，这样就实现了数组的扩容。

image.png 
private void ensureCapacity() {
    // 获取数组当前容量
    int oldCapacity = elements.length;
    // 如果 当前存储的元素个数 < 当前数组容量, 直接返回
    if (size < oldCapacity) return;
    // 新数组的容量为原数组容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 创建新数组
    E[] newElements = (E[]) new Object[newCapacity];
    // 原数组中的元素存储到新数组中
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[i];
    }
    // 引用新数组
    elements = newElements;
}

实现add函数，需要在添加新元素之前，判断数组越界和扩容。

public void add(int index, E element) {
        //判断越界    
        rangeCheckForAdd(index);
        //判断扩容            
        ensureCapacity(size + 1);
        
        for (int i = size; i > index; i--) {
                elements[i] = elements[i - 1];
        }
        elements[index] = element;
        size++;
}

4、删除元素

删除元素，实际上就是去掉指定位置的元素，并将后面的元素向前移动（其实是向前赋值）。

如下图，当删除索引为2的元素时，只需要将后面的元素向前移动，然后在去掉最后一个元素，size减1即可

image.png 
/**
 * 删除index位置的元素
 * @param index
 * @return
 */
public E remove(int index) {
  // 删除元素时传入的索引不能越界
    rangeCheck(index);
    
    E old = elements[index];
    for (int i = index + 1; i < size; i++) {
        elements[i - 1] = elements[i];
    }
    elements[--size] = null;
    return old;
}

5、数组缩容

当数组中的元素删除后，数组剩余的空间可能会很大，这样就会造成内存的浪费，当数组中元素删除后，我们需要对数组进行缩容。

实现方法类似于扩容，当数组中容量小于某个值时，创建新的数组，然后将原有数组中的元素存入新数组即可。


public void trim() {
    // 获取当前数组的容量
    int capacity = elements.length;
    // 当size大于等于容量的一半, 或则容量已经小于默认容量(10)时, 直接返回
    if (size >= capacity >> 1 || capacity < CAPACITY_DEFAULT) return;
    // 计算新的容量 = 原有容量的一半
    int newCapacity = capacity >> 1;
    // 创建新数组
    E[] newElements = (E[]) new Object[newCapacity];
    // 将原数组元素存入新数组
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[i];
    }
    // 引用新数组
    elements = newElements;
}

最终, remove方法实现如下：

public E remove(int index) {
    // 判断索引是否越界
    rangeCheck(index);
    // 取出需要删除的元素
    E old = elements[index];
    // 通过循环, 将index后面的所有元素向前移动一位
    for (int i = index + 1; i < size; i++) {
        elements[i - 1] = elements[i];
    }
    // 删除最后一个元素
    elements[--size] = null;
    // 判断数组是否需要缩容
    trim();
    // 将删除的元素返回
    return old;
}

6、清空数组

清空数组时，需要将所有的元素置为null，只有这样才能真正的释放对象，然后size置为0。

public void clear() {
    // 清空存储的数据
    for (int i = 0; i < size; i++) {
        elements[i] = null;
    }
    // 将size置为0
    size = 0;
}

7、修改元素

修改元素时，只需要将原有位置的元素替换掉即可，同样需要注意一下索引是否越界。

public E set(int index, E element) {
    // 判断索引是否越界
    rangeCheck(index);
    // 取出被替换元素
    E oldElement = elements[index];
    // 替换元素
    elements[index] = element;
    // 返回被替换元素
    return oldElement;
}

8、查询元素

查询元素，只需要将指定索引的元素返回，注意索引是否越界即可

public E get(int index) {
    rangeCheck(index);
    return elements[index];
}

9、 查看元素位置

可以通过循环, 查找元素在数组中的位置。

注意：假如数组中可以存储null，而null是不能调用equals方法的，所以需要对传入的元素进行判断，如果查找的元素是null，需要单独处理。

当元素存在时返回索引，否则返回变量ELEMENT_ON_FOUND的值。

private static final int ELEMENT_NOT_FOUND = -1;
public int indexOf(E element) {
    // null的处理
    if (element == null) {
        for (int i = 0; i < size; i++) {
            if (elements[i] == null) return i;
        }
    } else {
        for (int i = 0; i < size; i++) {
            if (element.equals(elements[i])) return i;
        }
    }
    return ELEMENT_NOT_FOUND;
}

是否包含某元素： 只需通过判断索引是否等于ELEMENT_ON_FOUND即可

public boolean contains(E element) {
    // 查看元素的索引是否为ELEMENT_ON_FOUND即可
    return indexOf(element) != ELEMENT_ON_FOUND;
}

10、动态数组打印

可以重写toString方法, 来打印ArrayList中的元素

public String toString() {
    StringBuilder string = new StringBuilder();
    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();
}
  • 重写toString 方法
  • 在toString方法中将元素拼接成字符串
  • 字符串拼接建议使用 StringBuilder

到此为止，我们成功的实现了动态数组。

11、 测试一下

ArrayList<Integer> list1  = new ArrayList<>();
list1.add(99);
list1.add(88);
list1.add(77);
list1.add(66);
list1.add(55);

list1.set(3, 80);

if ((int)list1.get(3) != 80) {
    throw new IllegalAccessError("测试不通过");
}

Asserts.test((int)list1.get(3) == 80);

// Asserts断言类
package com.alangeit;
public class Asserts {
    public static void test(boolean value) {
        try {
            if (!value) throw new Exception("测试未通过");
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

动态数组的复杂度

image.png

ArrayList能否进一步优化？

image.png

  • 在ArrayList中，如果要删除索引0位置的元素，则需要将索引0之后的元素全部往前移一位。

  • 如果要在索引0位置添加元素，也需要将索引0及之后的元素全部往后移一位。

    image.png

  • 在ArrayList中增加一个记录首元素位置的属性。

  • 删除索引0位置的元素，我们只需要将first属性改为1。

  • 在索引0位置添加元素，则只需要将first属性改为0。

    image.png

  • 如果继续往前插入元素，则将插入的元素存放在索引8这个位置，并将first改为8。

  • 当要获取索引8下一个元素时，对索引取模，则拿到索引0位置的元素。

    image.png

  • 如果插入元素，则可选择挪动前半段数据或后半段数据。

  • 在索引2处插入元素99，可以选择将元素22，33左移，然后插入99即可。

  • 扩容和缩容同样可以优化。

以下是完整源码

java版本

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

    private static final int DEFAULT_CAPACITY = 10; // 初始容量
    private static final int ELEMENT_NOT_FOUND = -1;
    
    public ArrayList(int capacity) { // 容量小于10一律扩充为10
        capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
        elements = (E[])new Object[capacity];
    }
    public ArrayList(){
        this(DEFAULT_CAPACITY);
    }
    /**
     * 元素的数量
     * @return
     */
    public int size(){
        return size;
    }
    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }
    /**
     * 是否包含某个元素
     * @param element
     * @return
     */
    public boolean contains(E element){
        return indexOf(element) != ELEMENT_NOT_FOUND; // 找的到该元素则返回True
    }
    /**
     * 在index位置插入一个元素
     * @param index
     * @param element
     */
    public void add(int index, E element){ 
        rangeCheckForAdd(index); // 检查下标越界
        ensureCapacity(size + 1); // 确保容量够大
        
        // 0 1 2 3 4 5 6 7 8 9  (index)
        // 1 2 3 4 5 6 x x x x  (原数组)
        // 在index=2处，插入9，元素全部后移
        // 1 2 9 3 4 5 6 x x x  (add后数组)
        // 先从后往前开始, 将每个元素往后移一位, 然后再赋值
        for (int i = size - 1; i > index; i--) {
            elements[i + 1] = elements[i];
        }
        elements[index] = element; // 复制
        size++;
    }
    /**
     * 添加元素到最后面
     */
    public void add(E element){
        add(size, element);
    }
    /**
     * 设置index位置的元素
     * @param index
     * @param element
     * @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;
    }
    /**
     * 删除index位置的元素
     * @param index
     * @return
     */
    public E remove(int index){
        rangeCheck(index);
        // 0 1 2 3 4 5  (index)
        // 1 2 3 4 5 6  (原数组)
        // 删除index为2的元素，元素前移
        // 1 2 4 5 6    (remove后的数组)
        // 从前往后开始移, 用后面的元素覆盖前面的元素
        E old = elements[index];
        for (int i = index; i < size - 1; i++) {
            elements[i] = elements[i + 1];
        }
        elements[--size] = null; // 删除元素后, 将最后一位设置为null
        return old;
    }
    /**
     * 查看元素的索引
     * @param element
     * @return
     */
    public int indexOf(E element){
        /*
        // 不对 null 进行处理也可以，但是健壮性不够
        for (int i = 0; i < size; i++) {
            if(elements[i].equals(element)) return i;
        }
         */
        if(element == null){ // 对 null 进行处理
            for (int i = 0; i < size; i++) {
                if(elements[i] == null) return i;
            }
        }else{
            for (int i = 0; i < size; i++) {
                if(elements[i].equals(element)) return i;
            }
        }
        return ELEMENT_NOT_FOUND;
    }
    /**
     * 清除所有元素
     */
    public void clear(){
        // 使用泛型数组后要注意内存管理(将元素置null)
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }
    /**
     * 扩容操作
     */
    private void ensureCapacity(int capacity){
        int oldCapacity = elements.length;
        if(oldCapacity >= capacity) return;
        // 新容量为旧容量的1.5倍
        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("size="+oldCapacity+", 扩容到了"+newCapacity);
    }
    /****************封装好的功能函数**************************/
    // 下标越界抛出的异常
    private void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }
    // 检查下标越界(不可访问或删除size位置)
    private void rangeCheck(int index){
        if(index < 0 || index >= size){
            outOfBounds(index);
        }
    }
    // 检查add()的下标越界(可以在size位置添加元素)
    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }
    /****************封装好的功能函数***************************/
    @Override
    public String toString() {
        // 打印形式为: size=5, [99, 88, 77, 66, 55]
        StringBuilder string = new StringBuilder();
        string.append("size=").append(size).append(", [");
        for (int i = 0; i < size; i++) {
            if(0 != i) string.append(", ");
            string.append(elements[i]);
        }
        string.append("]");
        return string.toString();
    }
}

//  测试一下
public static void main(String[] args) {
    ArrayList<Person> list = new ArrayList<>();
    
    list.add(new Person(10, "jack"));
    list.add(new Person(20, "rose"));
    list.add(null);
    list.add(null);
    
    System.out.println("add()添加元素: " + list);
    
    System.out.println("get()获取元素: " + list.get(0));
    
    list.set(0, new Person(99, "ghost"));
    System.out.println("set()设置元素值: " + list);
    
    list.remove(0);
    System.out.println("remove()删除元素: " + list);
    
    list.clear();
    System.out.println("clear()清空数组: " + list);
}

相关文章

  • 数据结构 - 动态数组学习笔记

    数据结构和算法动态可视化网站[https://visualgo.net/zh] 学习李明杰老师的恋上数据结构[%5...

  • 链表

    数据结构之链表 前面我们学习了三种线性结构的数据结构，动态数组，栈和队列，但是这三种数据结构其实说到底都是数组，即...

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

    前言：本文是用来记录自己学习数据结构与算法的笔记，写的不对的地方欢迎指正。 数组定义 数组是一种线性表数据结构。它...

  • ArrayList和LinkList的区别

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

  • 8.LinkedList

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

  • 数据结构之数组

    数据结构之数组 这个系列是在学习慕课网玩转数据结构课程的学习笔记，用JAVA语言来重新系统的整理一下数据结构的知识...

  • 数据结构（二）：栈和队列

    本系列为数据结构学习笔记，如有错误请指正~ 数据结构（一）：数组和链表 一、理论知识 栈和队列都是线性数据结构，属...

  • 数据结构（三）：散列表

    本系列为数据结构学习笔记，如有错误请指正~数据结构（一）：数组和链表数据结构（二）：栈和队列 一、基本概念 散列表...

  • 01.数据结构之数组篇

    文章为极客时间《数据结构与算法之美》的学习笔记。 什么是数组？ 数组是一种线性表数据结构。它用一组连续的内存空间，...

  • JDK8中ArrayList源码分析

    ArrayList是一个动态数组,可灵活的增删元素,更改数组 1.前言 前面几章学习了数据结构和算法的基础知识,对...

网友评论

      本文标题：数据结构 - 动态数组学习笔记

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

      延伸阅读

      深度阅读

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

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|数据结构 - 动态数组学习笔记|投稿指南|网站地图|RSS订阅|排版工具|手机版

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

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

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

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

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