twolf技术站

Appearance

动态数组 ​

一、定义 ​

动态数组线性表是一种基于动态数组实现的线性表，它结合了数组的随机访问特性和动态扩展的灵活性。在动态数组线性表中，元素是按照顺序排列的，可以根据下标进行快速访问，同时也支持动态地插入和删除元素，使得线性表的大小可以根据需要进行动态调整。

二、特点 ​

动态数组线性表具有以下特点：

  1. 底层采用动态数组：动态数组线性表的底层数据结构是动态数组，它具有数组的随机访问特性，可以通过下标来快速访问元素。
  2. 大小可变：动态数组线性表的大小可以根据需要进行动态调整，可以动态地插入和删除元素，以适应数据的变化。
  3. 自动扩展和收缩：当线性表中的元素数量达到动态数组的容量上限时，会自动扩展数组的大小；当元素数量减少到一定程度时，会自动收缩数组的大小，以节省内存空间。

三、实现方式 ​

动态数组线性表通常采用动态数组来实现，动态数组具有以下特点：

  1. 连续存储：动态数组的元素在内存中是连续存储的，可以通过下标来访问元素，具有数组的随机访问特性。
  2. 动态扩展：当动态数组中的元素数量超过容量上限时，会动态地扩展数组的大小，通常是将数组的大小增加一定的比例（如倍增）。
  3. 动态收缩：当动态数组中的元素数量减少到一定程度时，会动态地收缩数组的大小，通常是将数组的大小缩小一定的比例（如减半）。

四、应用场景 ​

动态数组线性表广泛应用于各种场景，特别是需要灵活管理和操作数据的场合，例如：

  1. 动态数据集合：动态数组线性表适用于存储和操作动态的数据集合，如动态数组实现的列表、集合等数据结构。
  2. 缓冲区管理：动态数组线性表常用于实现缓冲区管理，可以动态地添加和删除缓冲区中的数据。
  3. 动态数组容器：在编程语言和标准库中，动态数组线性表通常作为动态数组容器的基础，提供灵活的数据存储和操作功能。

五、实现 ​

5.1 接口定义 ​

/**
 * @Description list接口
 * @Author lcy
 * @Date 2020/9/7 10:27
 */
public interface IList<E> {

    /**
     * 找不到数据返回值
     */
    static final int ELEMENT_NOT_FOUND = -1;

    /**
     * 根据下标添加对象
     * @param index   下标
     * @param element 对象
     * @author lcy
     * @date 2020/9/3 20:55
     **/
    void add(int index,E element);

    /**
     * 根据下标设置对象
     * @param index   下标
     * @param element 对象
     * @author lcy
     * @date 2020/9/3 20:55
     **/
    void set(int index,E element);

    /**
     * 获取对象
     * @param index 下标
     * @return E
     * @author lcy
     * @date 2020/9/3 20:56
     **/
    E get(int index);

    /**
     * 清除数组数据
     * @author lcy
     * @date 2020/9/3 20:56
     **/
    void clear();

    /**
     * 查询对象所在节点下标
     * @param element 对象
     * @return int
     * @author lcy
     * @date 2020/9/3 21:00
     **/
    int indexOf(E element);

    /**
     * 根据下标删除对象
     * @param index 下标
     * @author lcy
     * @date 2020/9/3 21:01
     **/
    E remove(int index);

}

5.2 抽象链表 ​

/**
 * @Description 抽象链表类
 * @Author lcy
 * @Date 2020/9/7 10:49
 */
public abstract class AbstractLinear<E> implements IList<E> {

    /**
     * 线性表长度
     */
    protected int size = 0;

    /**
     * 返回数组长度
     */
    public int size(){
        return size;
    }

    /**
     * 添加对象
     * @param element 对象
     * @author lcy
     * @date 2020/9/3 20:55
     **/
    public void add(E element){
        add(size,element);
    }

    /**
     * 判断是否为空
     * @return boolean
     * @author lcy
     * @date 2020/9/3 20:58
     **/
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 判断对象在不在数组中
     * @param element 对象
     * @return boolean
     * @author lcy
     * @date 2020/9/3 21:08
     **/
    public boolean contains(E element){
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    /**
     * 校验下标范围
     * @param index 下标
     * @author lcy
     * @date 2020/9/4 14:18
     **/
    protected void rangeCheck(int index){
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
    }

    /**
     * 校验添加的下标范围
     * @param index 下标
     * @author lcy
     * @date 2020/9/4 14:18
     **/
    protected void rangeCheckAdd(int index){
        //添加时候的校验，如果小于0或者大于size，抛出异常
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
    }
}

5.3 动态数组（复制数组） ​

/**
 * @Description 动态数组
 * @Author lcy
 * @Date 2020/9/3 19:55
 */
public class DynamicArray<E> extends AbstractLinear<E> {

    /**
     * 数组变量
     */
    private Object[] elements;

    /**
     * 默认初始长度
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 无参构造
     */
    public DynamicArray(){
        this(DEFAULT_CAPACITY);
    }

    /**
     * 有长度的构造方法
     */
    public DynamicArray(int initialCapacity){
        //如果长度小于0，抛出异常
        if (initialCapacity < 0) {
            throw new RuntimeException();
        } else {
            //大于0 设置初始长度
            elements = new Object[initialCapacity];
        }
    }

    /**
     * 根据下标添加对象
     * @param index   下标
     * @param element 对象
     * @author lcy
     * @date 2020/9/3 20:55
     **/
    @Override
    public void add(int index,E element){
        //校验下标是否大于数组边界
        rangeCheckAdd(index);
        //校验是否需要扩容
        ensureCapacity();
        //数据移位
        System.arraycopy(elements,index,elements,index + 1,size - index);
        //设置下标数组的值
        elements[index] = element;
        size++;
    }

    /**
     * 根据下标设置对象
     * @param index   下标
     * @param element 对象
     * @author lcy
     * @date 2020/9/3 20:55
     **/
    @Override
    public void set(int index,E element){
        //检查下标是否在[0,size)的范围
        rangeCheck(index);
        //设置值
        elements[index] = element;
    }

    /**
     * 获取对象
     * @param index 下标
     * @return E
     * @author lcy
     * @date 2020/9/3 20:56
     **/
    @Override
    public E get(int index){
        //检查下标是否在[0,size)的范围
        rangeCheck(index);
        //获取对象，转换成泛型对应的对象
        return (E)elements[index];
    }

    /**
     * 清除数组数据
     * @author lcy
     * @date 2020/9/3 20:56
     **/
    @Override
    public void clear(){
        //清除数组数据，将值设为null。不需要重新构造数组
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    /**
     * 查询对象所在节点下标
     * @param element 对象
     * @return int
     * @author lcy
     * @date 2020/9/3 21:00
     **/
    @Override
    public int indexOf(E element){
        //如果传入的是null，为了防止空指针，用==号，否则用equals
        if (element == null) {
            for (int i = 0; i < size; i++) {
                if (null == elements[i]) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                //element一定不为null，用它来进行eq
                if (element.equals(elements[i])) {
                    return i;
                }
            }
        }

        return ELEMENT_NOT_FOUND;
    }

    /**
     * 根据下标删除对象
     * @param index 下标
     * @author lcy
     * @date 2020/9/3 21:01
     **/
    @Override
    public E remove(int index){
        //检查下标是否在[0,size)的范围
        rangeCheck(index);
        Object element = elements[index];
        for (int i = 0; i < size; i++) {
            if (i == index) {
                //数组移位
                System.arraycopy(elements,i + 1,elements,i,size - 1 - i);
                elements[--size] = null;
            }
        }
        //判断是否缩容
        trim();
        return (E)element;
    }

    /**
     * 返回数组
     * @return E[]
     * @author lcy
     * @date 2020/9/4 9:08
     **/
    public E[] toArray(){
        return (E[])Arrays.copyOf(elements,size);
    }

    /**
     * 保证数组的容量
     * @author lcy
     * @date 2020/9/4 14:49
     **/
    public void ensureCapacity(){
        //如果数组的长度小于size的长，对数组扩容
        if (elements.length < size) {
            //新容量为旧容量的1.5倍  element.length右移1位 即除以2
            //<<:  左移运算符，num << 1,相当于num乘以2^1 ，num << 2,相当于num乘以2^2 = 4
            //>>:  右移运算符，num >> 1,相当于num除以2^1
            //>>>: 无符号右移，忽略符号位，空位都以0补齐
            int addSize = elements.length >> 1;
            elements = Arrays.copyOf(elements,addSize + elements.length);
        }
    }

    /**
     * 判断是否需要缩容
     * @author lcy
     * @date 2020/9/8 20:56
     **/
    private void trim(){
        //长度的十分之一大于size，缩容一半
        if (elements.length >> 2 >= size && elements.length >= DEFAULT_CAPACITY) {
            elements = Arrays.copyOf(elements,elements.length >> 1);
        }
    }

    public static void main(String[] args){
        DynamicArray<Object> array = new DynamicArray<>();
        System.out.println(array.isEmpty());
        System.out.println(array.size);
        String a = "sss";
        array.add(a);
        array.add("2");
        array.add(1);
        System.out.println(Arrays.toString(array.toArray()));
        array.add(1,"32");
        System.out.println(Arrays.toString(array.toArray()));
        System.out.println("根据下标获取对象：" + array.get(1));
        System.out.println(array.isEmpty());
        System.out.println("根据对象获取下标：" + array.indexOf(a));
        array.remove(0);
        System.out.println(Arrays.toString(array.toArray()));
        System.out.println(array.contains("4"));
        array.set(0,"22");
        array.add(0,"aa");
        System.out.println(Arrays.toString(array.toArray()));
        System.out.println(array.size);
        array.clear();
        System.out.println("------------------------------------------");
        ArrayList<Object> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(1);
        System.out.println(arrayList.size());
        System.out.println(Arrays.toString(arrayList.toArray()));
        arrayList.remove(1);
        System.out.println(arrayList.size());
        System.out.println(Arrays.toString(arrayList.toArray()));
        arrayList.clear();
        System.out.println(arrayList.size());
        System.out.println(Arrays.toString(arrayList.toArray()));
    }

}

5.4 动态数组（优化） ​

这里通过移动数组下标，利用可用空间，而不需要每次都进行复制数组进行扩容

/**
 * @Description 动态数组--优化
 * @Author lcy
 * @Date 2020/9/3 19:55
 */
public class DynamicArrayList<E> extends AbstractLinear<E> {

    /**
     * 数组变量
     */
    private Object[] elements;

    /**
     * 初始下标
     */
    private int firstIndex = 0;

    /**
     * 默认初始长度
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 无参构造
     */
    public DynamicArrayList(){
        this(DEFAULT_CAPACITY);
    }

    /**
     * 有长度的构造方法
     */
    public DynamicArrayList(int initialCapacity){
        //如果长度小于0，抛出异常
        if (initialCapacity < 0) {
            throw new RuntimeException();
        } else {
            //大于0 设置初始长度
            elements = new Object[initialCapacity];
        }
    }

    /**
     * 根据下标添加对象
     * @param index   下标
     * @param element 对象
     * @author lcy
     * @date 2020/9/3 20:55
     **/
    @Override
    public void add(int index,E element){
        //校验下标是否大于数组边界
        rangeCheckAdd(index);
        //校验是否需要扩容
        ensureCapacity();
        //需要插入数据的下标
        int elementIndex = Math.floorMod(firstIndex + index,elements.length);
        if (index == size) {
            elements[elementIndex] = element;
        } else if (index == 0) {
            //取模运算，重新获取下标
            firstIndex = Math.floorMod(firstIndex - 1,elements.length);
            elements[firstIndex] = element;
        } else {

            if (index > size >> 1) {
                //通过模移位
                for (int i = firstIndex + size - 1; i >= firstIndex + index; i--) {
                    int prevIndex = Math.floorMod(i,elements.length);
                    int tmpIndex = Math.floorMod(i + 1,elements.length);
                    elements[tmpIndex] = elements[prevIndex];

                }
            } else {
                for (int i = firstIndex; i < firstIndex + index; i++) {
                    int prevIndex = Math.floorMod(i - 1,elements.length);
                    int tmpIndex = Math.floorMod(i,elements.length);
                    elements[prevIndex] = elements[tmpIndex];
                }
                firstIndex = Math.floorMod(firstIndex - 1,elements.length);
                elementIndex = Math.floorMod(firstIndex + index,elements.length);
            }
            elements[elementIndex] = element;
        }
        size++;
    }

    /**
     * 根据下标设置对象
     * @param index   下标
     * @param element 对象
     * @author lcy
     * @date 2020/9/3 20:55
     **/
    @Override
    public void set(int index,E element){
        //检查下标是否在[0,size)的范围
        rangeCheck(index);
        //设置值
        elements[Math.floorMod(firstIndex + index,elements.length)] = element;
    }

    /**
     * 获取对象
     * @param index 下标
     * @return E
     * @author lcy
     * @date 2020/9/3 20:56
     **/
    @Override
    public E get(int index){
        //检查下标是否在[0,size)的范围
        rangeCheck(index);
        //获取对象，转换成泛型对应的对象
        return (E)elements[Math.floorMod(firstIndex + index,elements.length)];
    }

    /**
     * 清除数组数据
     * @author lcy
     * @date 2020/9/3 20:56
     **/
    @Override
    public void clear(){
        //清除数组数据，将值设为null。不需要重新构造数组
        for (int i = 0; i < size; i++) {
            int index = Math.floorMod(firstIndex + i,elements.length);
            elements[index] = null;
        }
        size = 0;
    }

    /**
     * 查询对象所在节点下标
     * @param element 对象
     * @return int
     * @author lcy
     * @date 2020/9/3 21:00
     **/
    @Override
    public int indexOf(E element){
        //如果传入的是null，为了防止空指针，用==号，否则用equals
        if (element == null) {
            for (int i = 0; i < size; i++) {
                int index = Math.floorMod(firstIndex + i,elements.length);
                if (null == elements[index]) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                int index = Math.floorMod(firstIndex + i,elements.length);
                //element一定不为null，用它来进行eq
                if (element.equals(elements[index])) {
                    return i;
                }
            }
        }

        return ELEMENT_NOT_FOUND;
    }

    /**
     * 根据下标删除对象
     * @param index 下标
     * @author lcy
     * @date 2020/9/3 21:01
     **/
    @Override
    public E remove(int index){
        //检查下标是否在[0,size)的范围
        rangeCheck(index);
        Object element =  elements[Math.floorMod(firstIndex + size,elements.length)];
        if (index > size >> 1) {
            //通过模移位
            for (int i = firstIndex + index; i < firstIndex + size + index; i++) {
                int prevIndex = Math.floorMod(i,elements.length);
                int tmpIndex = Math.floorMod(i + 1,elements.length);
                elements[tmpIndex] = elements[prevIndex];
            }
            elements[Math.floorMod(firstIndex + size,elements.length)] = null;
        } else {
            for (int i = firstIndex + index; i > firstIndex + index; i--) {
                int prevIndex = Math.floorMod(i - 1,elements.length);
                int tmpIndex = Math.floorMod(i,elements.length);
                elements[tmpIndex] = elements[prevIndex];
            }
            elements[firstIndex] = null;
            firstIndex = Math.floorMod(firstIndex + 1,elements.length);

        }
        size--;
        //判断是否缩容
        //trim();

        return (E)element;
    }

    /**
     * 返回数组
     * @return E[]
     * @author lcy
     * @date 2020/9/4 9:08
     **/
    public E[] toArray(){
        return (E[])Arrays.copyOf(elements,size);
    }



    /**
     * 保证数组的容量
     * @author lcy
     * @date 2020/9/4 14:49
     **/
    public void ensureCapacity(){
        //如果数组的长度小于size的长，对数组扩容
        if (elements.length <= size) {
            //新容量为旧容量的1.5倍  element.length右移1位 即除以2
            //<<:  左移运算符，num << 1,相当于num乘以2^1 ，num << 2,相当于num乘以2^2 = 4
            //>>:  右移运算符，num >> 1,相当于num除以2^1
            //>>>: 无符号右移，忽略符号位，空位都以0补齐
            //判断需要尾部移动还是头部移动
            boolean endMove = size - firstIndex < elements.length >> 1;
            int addSize = elements.length >> 1;
            elements = Arrays.copyOf(elements,elements.length + addSize);

            //如果是尾部移动
            if (endMove) {
                //移动步数
                int move = elements.length - firstIndex;
                for (int i = 0; i < move; i++) {
                    //数据移动
                    elements[elements.length - 1 - i] = elements[firstIndex + i];
                    //清空原有下标数据
                    elements[firstIndex] = null;
                }
                //重新定义头结点下标
                firstIndex = elements.length - move - 1;
            } else {
                int move = firstIndex;
                for (int i = 0; i < move; i++) {
                    //数据移动
                    elements[size - 1 - move] = elements[i];
                    //清空原有下标数据
                    elements[i] = null;
                }
            }

            //System.arraycopy(elements,firstIndex,elements,0,size - firstIndex);
            ////如果头结点不在0
            //if (firstIndex != 0) {
            //    //如果头结点大于长度的一半，往后移
            //    if (firstIndex > size >> 1) {
            //        System.arraycopy(elements,firstIndex,elements,elements.length - size + firstIndex,size - firstIndex);
            //        for (int i = firstIndex; i < size - firstIndex; i++) {
            //            //清空原有的元素
            //            elements[i] = null;
            //        }
            //        firstIndex = elements.length - size + firstIndex;
            //    } else {
            //        //如果头结点小于长度的一半，头结点前面的数据拼接在尾部
            //        System.arraycopy(elements,0,elements,size - firstIndex,firstIndex);
            //        for (int i = 0; i < firstIndex; i++) {
            //            elements[i] = null;
            //        }
            //    }
            //}
        }
    }

    /**
     * 判断是否需要缩容
     * @author lcy
     * @date 2020/9/8 20:56
     **/
    private void trim(){
        //长度的十分之一大于size，缩容一半
        if (elements.length >> 2 >= size && elements.length >= DEFAULT_CAPACITY) {
            elements = Arrays.copyOf(elements,elements.length >> 1);
        }
    }

    @Override public String toString(){

        StringBuilder stringBuilder = new StringBuilder("array{");
        for (int i = firstIndex; i < firstIndex + size; i++) {
            int index = Math.floorMod(i,elements.length);
            stringBuilder.append("[").append(elements[index]).append("],");
        }
        if (size > 0) {
            stringBuilder.setLength(stringBuilder.length() - 1);
        }
        stringBuilder.append("}");

        return stringBuilder.toString();
    }

    public static void main(String[] args){

        DynamicArrayList<Object> array = new DynamicArrayList<>();
        String a = "sss";
        for (int i = 0; i < 10; i++) {
            array.add(i,i);
        }
        System.out.println(array);
        System.out.println(array.size);
        array.add(a);
        System.out.println(array);
        array.add(1,"32");
        System.out.println(array);
        //array.add(2,"33");
        //System.out.println(array);
        System.out.println("根据下标获取对象：" + array.get(1));
        System.out.println(array.isEmpty());
        System.out.println("根据对象获取下标：" + array.indexOf(a));
        array.remove(0);
        System.out.println(array);
        System.out.println(array.contains("4"));
        array.set(0,"22");
        array.add(0,"aa");
        System.out.println(array);
        System.out.println(array.size);
        array.clear();
        System.out.println(array);
        System.out.println("------------------------------------------");
    }

}

六、总结 ​

动态数组线性表是一种基于动态数组实现的线性表，它结合了数组的随机访问特性和动态扩展的灵活性。动态数组线性表支持动态调整大小、快速访问和灵活插入删除等操作，适用于各种需要动态管理和操作数据的场景。对于动态数组线性表的深入理解和熟练运用，有助于提高程序的效率和性能。

粤ICP备2024174490号-1 Copyright © 2024-present twolf