首页 > 编程学习 > 数据结构-ArrayList解析和实现代码

数据结构-ArrayList解析和实现代码

发布时间:2022/11/27 10:43:54

arrayList结构的实现是数组结构,数组没有扩容机制,arrayList的扩容机制采用的是复制数组,了解你会发现ArrayList虽然实现比较简单,但是设计还是很巧妙的。咱们先来简单实现下..

咱们看下定义的全局变量

1.默认初始化空间为10,也就是默认数组空间大小

2.定义个空元素

3.顶一个数组存储元素

4.数组长度

5.构造方法默认给个空元素

    // 默认初始化空间
    private static final int DEFAULT_CAPACITY = 10;
    // 空元素
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELMENTDATA = {};
    // ArrayList元素数组缓冲区
    transient Object[] elementData;
    // List 集合元素数量
    private int size;

    public ArrayList() {
        // 默认给个空的元素,当开始添加元素的时候在初始化长度
        this.elementData = DEFAULTCAPACITY_EMPTY_ELMENTDATA;
    }

1.添加元素

添加就是将数据存储到上边定义的elementData数组里,需要按数组下标一个个的排好存储,但是如果超出了默认的数组长度10怎么办?需要新开辟空间,把原数组原封不动的放回原有的位置,接下来看下代码。

第一次添加元素时

  1.1 size为0,minCapacity得到的就是1,因为数据都是空,所以minCapacity设置了默认值10

   1.2 10-0 肯定大于0,创建数组空间,那么当数组存储10条时这个minCapacity就是11,11-10大于0,需要扩容了还是运用了一个操作,这块设计的就很好

   1.3 当需要扩容时找到旧数组的长度,然后用旧数组的长度+旧数组长度除以2,也就是除了第一次扩容是10,第二次就是15。

    1.4 新要开辟的数字小于之前的minCapacity,newCapacity - minCapacity,那就把minCapacity赋值给newCapacity,在第一次存储数据就是这样,newCapacity=0,minCapacity=10,就需要赋值

    1.5 通过Arrays.copyof(数组,长度); 开辟空间,扩容也是如此

    1.6 然后存储数据,返回成功

第二次添加元素时

minCapacity=2,判断扩容2-10是小于0的,不扩容,直接存储返回数据

// 添加
    public boolean add(E e) {
        int minCapacity = size + 1;
        if (elementData == DEFAULTCAPACITY_EMPTY_ELMENTDATA) {
            minCapacity = DEFAULT_CAPACITY;
        }
        // 判断是否数组容量不足
        if (minCapacity - elementData.length > 0) {
            int oldCapacity = elementData.length;
            // 加原来数组长度+将原来数组长度除2
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            // 扩展数据比原最小容量小就直接赋值minCapacity
            if (newCapacity - minCapacity < 0) {
                newCapacity = minCapacity;
            }
            // 进行复制原数组操作
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
        // 存储数据
        elementData[size++] = e;
        return true;
    }

2.获取元素

获取元素非常简单,根据下标获取元素即可

    // 根据索引查询
    public E get(int index) {
        return (E) elementData[index];
    }

3.删除元素

删除元素需要考虑移动元素的情况,假如1-2-3-4,删除2以后数组就是134,3的下标就是1,而不是以前的2。

根据System.arraycopy进行解决移动数据问题,假如现有1-2-3-5-8数据,删除了3也就是小标2的数据,那么原数组的拷贝需要从index+1开始,也就是不拷贝3的元素,拷贝到目标元素还是elementData,从index位置也就是3的位置开始拷贝,拷贝几个数据呢,需要拷贝size-index-1,也就是说5-2-1=2,拷贝两个就是5和8到elementData,这样数组最后就剩1-2-5-8,其实就是挤出去的,是不是设计很巧妙,拷贝完后将长度减1,并把数组最后一个元素置为空


    public E remove(int index) {
        E e = get(index);
        // 总共拷贝多条数据
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            // 把elementData元素进行拷贝,从index+1(就是当前要删除的下一个元素开始)
            // 拷贝到elementData元素,从index下标为止,赋值后所有的数据
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        }
        elementData[--size] = null;
        return e;
    }

4.更新

更新则和获取一样,通过下标元素找到值直接赋当前值

    // 更新
    public boolean set(int index, E e) {
        elementData[index] = e;
        return true;
    }

全部代码

package linkedList;

import java.util.Arrays;
import java.util.List;

/**
 * @Author df
 * @Date 2022/11/20 15:16
 * @Version 1.0
 */
public class ArrayList<E> {
    // 默认初始化空间
    private static final int DEFAULT_CAPACITY = 10;
    // 空元素
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELMENTDATA = {};
    // ArrayList元素数组缓冲区
    transient Object[] elementData;
    // List 集合元素数量
    private int size;

    public ArrayList() {
        // 默认给个空的元素,当开始添加元素的时候在初始化长度
        this.elementData = DEFAULTCAPACITY_EMPTY_ELMENTDATA;
    }

    // 添加
    public boolean add(E e) {
        int minCapacity = size + 1;
        if (elementData == DEFAULTCAPACITY_EMPTY_ELMENTDATA) {
            minCapacity = DEFAULT_CAPACITY;
        }
        // 判断是否数组容量不足
        if (minCapacity - elementData.length > 0) {
            int oldCapacity = elementData.length;
            // 加原来数组长度+将原来数组长度除2
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            // 扩展数据比原最小容量小就直接赋值minCapacity
            if (newCapacity - minCapacity < 0) {
                newCapacity = minCapacity;
            }
            // 进行复制原数组操作
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
        // 存储数据
        elementData[size++] = e;
        return true;
    }

    // 根据索引查询
    public E get(int index) {
        return (E) elementData[index];
    }

    public E remove(int index) {
        E e = get(index);
        // 总共拷贝多条数据
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            // 把elementData元素进行拷贝,从index+1(就是当前要删除的下一个元素开始)
            // 拷贝到elementData元素,从index下标为止,赋值后所有的数据
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        }
        elementData[--size] = null;
        return e;
    }

    // 更新
    public boolean set(int index, E e) {
        elementData[index] = e;
        return true;
    }

    public void print() {
        for (Object o : elementData) {
            System.out.print("-" + o);
        }
        System.out.println("");
    }

    public static void main(String[] args) {
        List list = new java.util.ArrayList();
        list.add("1111");

        System.out.println("插入元素----");
        ArrayList arrayList = new ArrayList();
        arrayList.add("1");
        arrayList.add("2");
        arrayList.add("3");
        arrayList.add("5");
        arrayList.add("8");
        arrayList.print();

        System.out.println("获取元素----");
        System.out.println(arrayList.get(2));
        System.out.println("删除元素----");
        arrayList.remove(2);
        arrayList.print();
        System.out.println("更新元素----");
        arrayList.set(2, "3");
        arrayList.print();

    }
}

执行结果 

 

Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式