数据结构--动态数组

2023-01-11

字数统计: 1.2k字 | 阅读时长≈ 5分

数据结构分类：

按逻辑结构分
- 线性结构
  - 数组
  - 链表
  - 栈
  - 队列
  - 串
- 非线性结构
  - 树
  - 图或网
  - 集合
按存储结构(物理结构)分
- 顺序存储
- 链式存储
- 索引存储
- 散列存储（hash存储）

数组优点：

随机存取，随机访问数据，查询效率高，O(1)
存储密度高，每个结点只存储数据元素（相对于链表）

数组缺点：

创建时需固定数组长度，易造成空间浪费或不足，不足后期扩容效率低；
除尾部外其他位置频繁的插入和删除数据，效率低。

动态数组：

/**
* 动态数组
* @author zzr
* @create 2023-08-01-21:53
*/
public class DynamicArray implements Iterable<Integer>{
    private int[] array={};//静态数组
    private int size=0;//元素个数
    private int capacity=10;//容量

    //扩容
    public void grow(){
        if (size==0){//懒加载
            array=new int[capacity];
        }
        if (size==capacity){
            capacity+=capacity>>1;//容量1.5倍
            int[] newArray=new int[capacity];
            System.arraycopy(array,0,newArray,0,size);
            array=newArray;
        }
    }

    //在末尾添加
    public void add(int element){
        add(size,element);
    }

    //在任意位置添加
    public void add(int index,int element){
        grow();
        if (index>=0&&index<=size) {
            if (index >= 0 && index < size) {
                System.arraycopy(array, index, array, index + 1, size - index);
            }
            array[index] = element;
            size++;
        }else {
            throw new RuntimeException("输入的插入位置不合法！");
        }
    }

    //获取索引位置的值
    public int get(int index){
        if (index>=0&&index<size) {
            return array[index];
        }else {
            throw new RuntimeException("输入的索引不合法！");
        }
    }

    //末尾删除元素
    public int remove(){
        return remove(size-1);
    }

    //删除元素
    public int remove(int index){
        if (index>=0&&index<size) {
            int remove=array[index];
            System.arraycopy(array,index+1,array,index,size-index-1);
            size--;
            return remove;
        }else {
            throw new RuntimeException("输入的索引不合法！");
        }
    }

    //遍历
    //函数式接口
    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));//把数组转为流
    }

}

Java 动态数组：

ArrayList

继承关系：
- Iterator 接口：主要用于遍历输出
  - Collection接口
    - List接口：存储有序的、可重复的数据
      - ArrayList 类
特点：作为List接口的主要实现类；线程不安全的，效率高；底层使用Object[] elementData存储，可加入null

底层源码分析：

1） jdk 7情况下: ArrayList list = new ArrayList();

底层创建了长度是10的Object[]数组elementData，如果添加导致elementData数组容量不够，则扩容。默认情况下，扩容为原来的容量的1.5倍，同时需要将原有数组中的数据复制到新的数组中。

结论：建议开发中使用带参的构造器：ArrayList list = new ArrayList(int capacity)

2） jdk 8中ArrayList的变化: ArrayList list = new ArrayList();

底层Object[] elementData初始化为{}.并没创建长度为10的数组，第一次调用add()时，底层才创建了长度10的数组，并将数据添加到elementData中，后续的添加和扩容操作与jdk 7 无异。

3）小结：jdk7中的ArrayList的对象的创建类似于单例的饿汉式，而jdk8中的ArrayList的对象的创建类似于单例的懒汉式，延迟了数组的创建，节省内存。

常用方法：

（1）boolean isEmpty()：如果列表不包含元素，则返回true。

（2）int size()：返回此列表中的元素个数。

（3）add(E e) ：向列表的尾部添加指定的元素。

（4）void add(int index, E element)：在列表的指定位置插入指定元素。

（5）boolean contains(Object o)：如果列表包含指定的元素，则返回true。

（6）E get(int index)：返回列表中指定位置的元素。

（7）E set(int index, E element)：用指定元素替换列表中指定位置的元素。

（8）int indexOf(Object o)：返回此列表中第一次出现的指定元素的索引。如果此列表不包含该元素，则返回-1。

（9）int lastIndexOf(Object o)：返回此列表中最后出现的指定元素的索引。如果列表不包含此元素，则返回-1。

（10）void clear()：从列表中移除所有元素。

（11）E remove(int index)：移除列表中指定位置的元素。

（12）boolean remove(Object o)：从此列表中移除第一次出现的指定元素（如果存在）。
vector

继承关系：
- Iterator 接口
  - Collection接口
    - List接口
      - Vetcor 类
特点：作为List接口的古老实现类；线程安全的，效率低；底层使用Object[] elementData存储

底层源码分析：jdk7和jdk8中通过Vector()构造器创建对象时，底层都创建了长度为10的数组。在扩容方面，默认扩容为原来的数组长度的2倍。

本文作者： zzr
本文链接： http://zzruei.github.io/2023/01feb95590.html
版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！