动态数组的实现

2023-12-23 10:40:08

定义

1. 在计算机科学中,数组是由一组元素(值或变量)组成的数据结构,每个元素有至少一个索引或键来标识。

2. 因为数组内的元素是连续存储的,所以数组中元素的地址,可以通过其索引计算出来。

3. 知道了数组的数据其实地址BaseAddress,就可以由公式BaseAddress+ i * size 计算出索引i元素的地址。

?* i 即索引,在java,C等语言都是从0开始。

* size 是每个元素占用字节,例如int 占4,double 占8.

性能

空间占用

java中数据结构为:

* 8字节markword

* 4字节class指针(压缩class指针的情况)

* 4 字节数组大小(决定了数组最大容量 2 ^ 32)?

* 数组元素 + 对齐字节(java中所有对象都是8字节1的整数倍 ^12? , 不足的要用对齐字节补足)

动态数组

package com.ma.test;

import java.util.Arrays;
import java.util.Iterator;
import java.util.function.Consumer;
import java.util.stream.IntStream;

/**
 * @author Mtz
 * @version 1.0
 * @2023/12/2119:51
 * @function
 * @comment
 */
public class DynamicArray implements Iterable<Integer> {

    private int size = 0; // 逻辑大小
    private int capacity = 8; // 容量
    private int[] array = new int[capacity];

    public void addLast(int element) {
        add(size, element);
    }

    public void add(int index, int element) {

        checkAndGrow();

        if (index >= 0 && index < size) {
            // 向后挪动,空出待插入位置
            System.arraycopy(array, index, array
                    , index + 1, size - index);
        }
        array[index] = element;
        size++;
    }

    private void checkAndGrow() {

        if (size == 0) {
            array = new int[capacity];
            // 容量检查
        } else if (size == capacity) {
            // 进行扩容
            capacity += capacity >> 1;

            int[] newArray = new int[capacity];
            System.arraycopy(array, 0, newArray, 0, size);
            array = newArray;
        }
    }


    public int get(int index) {
        return array[index];
    }

    public void foreach(Consumer<Integer> consumer) {
        {
            for (int i = 0; i < size; i++) {
                consumer.accept(array[i]);
            }
        }
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int i = 0;

            @Override
            public boolean hasNext() {
                return i < size; // 有没有下一个元素
            }

            @Override
            public Integer next() {  // 并移动到下一个元素
                return array[i++];
            }
        };
    }

    public IntStream stream() {
        return IntStream.of(Arrays.copyOfRange(array, 0, size));
    }


    public int remove(int index) {
        int removed = array[index];

        if (index < size - 1) {
            System.arraycopy(array, index + 1, array,
                    index, size - index - 1);
        }
        size--;
        return removed;
    }
}

测试

package com.ma.test;

/**
 * @author Mtz
 * @version 1.0
 * @2023/12/229:05
 * @function
 * @comment
 */
public class Test {
    public static void main(String[] args) {
        DynamicArray dynamicArray = new DynamicArray();
        dynamicArray.addLast(1);
        dynamicArray.addLast(2);
        dynamicArray.addLast(3);
        dynamicArray.addLast(4);

        dynamicArray.foreach((element)->{
            System.out.println(element);
        });

        for (Integer element : dynamicArray){
            System.out.println(element);
        }

        dynamicArray.stream().forEach(element->{
            System.out.println(element);
        });
    }
}

文章来源:https://blog.csdn.net/weixin_67573348/article/details/135134437
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。