01_动态数组

01_动态数组

1、什么是数据结构?

  • 数据结构是计算机存储、组织数据的方式

    01_动态数组线性结构:线性表(数组、链表、栈、队列、哈希表)

    01_动态数组树形结构:二叉树、AVL树、红黑树、B树、堆、Trie哈夫曼树、并查集

    01_动态数组图形结构:邻接矩阵、邻接表

  • 在实际应用中,根据使用场景来选择最合适的数据结构

2、线性表

  • 线性表是具有n个相同类型元素的有限序列(n>=0)

    01_动态数组

    • a1是首节点(首元素),an是尾结点(尾元素)
    • a1是a2的前驱,a2是a1的后继
  • 常见的线性表有

    • 数组
    • 链表
    • 队列
    • 哈希表(散列表)

3、数组

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

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

01_动态数组

  • 在很多编程语言中,数组都有个致命的缺点(无法动态修改容量)
  • 实际开发中,我们更希望数组的容量是可以动态改变的

3.1、动态数组(Dynamic Array)接口设计

◼ int size(); // 元素的数量

◼ boolean isEmpty(); // 是否为空

◼ boolean contains(E element); // 是否包含某个元素

◼ void add(E element); // 添加元素到最后面

◼ E get(int index); // 返回index位置对应的元素

◼ E set(int index, E element); // 设置index位置的元素

◼ void add(int index, E element); // 往index位置添加元素

◼ E remove(int index); // 删除index位置对应的元素

◼ int indexOf(E element); // 查看元素的位置

◼ void clear(); // 清除所有元素

3.2、动态数组的设计

01_动态数组

  • 在Java中,成员变量会自动初始化,比如
    • int类型自动初始化为0
    • 对象类型自动初始化为null

3.2.1、添加元素——add(E element)

01_动态数组当size等于0时

01_动态数组当size等于5时

elements[size] = elementl
size++;

3.2.2、打印数组

  • 重写toString方法
  • 在toString方法中将元素拼接成字符串
  • 字符串拼接建议使用StringBuilder

3.2.3、删除元素——remove(int index)

size等于7

index等于3

01_动态数组

我们要删除的元素是数组下标为3的元素,即删除44

我们要做的事情就是将后边的数挨个向前移,从index+1处开始

①我们要将55向前移,覆盖44

01_动态数组得到的样式如下:

01_动态数组

然后我们要将后一位向前移:

01_动态数组

得到如下:

01_动态数组

然后将最后一位向前移:

01_动态数组

最后得到如下:

01_动态数组

最后我们需要做的就是维护size大小,进行size--操作

3.2.4、添加元素——add(int index,E element)

size等于5

index等于2

需要注意的是,我们进行添加元素时,顺序应该是从数组最后面的元素开始,一位一位向后挪动,因为如果我们是从index+1的位置开始挪动的话,前一位元素会将后面位置的值进行覆盖,就会出现线面错误覆盖顺序的图示:

01_动态数组

下面是错误的覆盖顺序

01_动态数组

3.2.5、如何扩容

01_动态数组

3.2.6、泛型

  • 使用泛型技术可以让动态数组更加通用,可以存放任何数据类型
public class ArrayList<E>{
	private int size;
	private E elements;
}

elements = (E[]) Object[capacity];
ArrayList<Integer> list = new ArrayList<>();

3.2.7、对象数组

Object[] objects = new Object[7];

01_动态数组

3.2.8、内存管理细节

public void clear(){
	for(int i = 0; i < size; i++){
		elements[i] = null;
	}
	
	size = 0;
}
public E remove(int index){
        rangeCheck(index);

        E old = elements[index];

        for(int i = index + 1; i <= size - 1; i++){
            elements[i-1] = elements[i];
        }

        elements[--size] = null;

        return old;
}

3.2.9、null的处理

  • 一个内部设计方面的问题
  • 是否可以存储null数据?
public int indexOf(E element){
        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;
}

最后是代码:

package nuc.edu;

import java.util.Arrays;

/**
 * @author 薛东
 * @date 2021/3/5 16:43
 */
public class ArrayList<E> {
    /**
     * 数组的大小
     */
    private int size;

    /**
     * 所有元素
     */
    private E[] elements;

    public static final int DEFAULT_CAPACITY = 10;
    public static final int ELEMENT_NOT_FOUND = -1;

    public ArrayList(int capacity){
        capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
        elements = (E[])new Object[capacity];
    }

    public ArrayList(){
        this(DEFAULT_CAPACITY);
    }

    /**
     * 清除所有元素
     */
    public void clear(){
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
    }

    /**
     * 元素的数量
     * @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;
    }

    /**
     * 添加元素到尾部
     * @param element
     */
    public void add(E element){
        add(size,element);
    }

    /**
     * 获取index位置的元素
     * @param index
     * @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
     * @param element
     */
    public void add(int index, E element){
        rangeCheckForAdd(index);
        ensureCapacity(size + 1);

        for(int i = size - 1; i >= index; i--){
            elements[i + 1] = elements[i];
        }
        elements[index] = element;
        size++;
    }

    /**
     * 删除index位置的元素
     * @param index
     * @return
     */
    public E remove(int index){
        rangeCheck(index);

        E old = elements[index];

        for(int i = index + 1; i <= size - 1; i++){
            elements[i-1] = elements[i];
        }

        size--;
        elements[size] = null;

        return old;
    }

    /**
     * 查看元素的索引
     * @param element
     * @return
     */
    public int indexOf(E element){
        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;
    }

    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(oldCapacity + "扩容为:" + newCapacity);
    }

    private void outOfBounds(int index){
        throw new IndexOutOfBoundsException("index:" + index + ",size:" + size);
    }

    private void rangeCheck(int index){
        if(index < 0 || index >= size){
            outOfBounds(index);
        }
    }

    private void rangeCheckForAdd(int index){
        if(index < 0 || index > size){
            outOfBounds(index);
        }
    }

    @Override
    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();
    }
}
上一篇:【Debug】 你所知道的Elements - DOM---第五天


下一篇:linux内核--自旋锁的理解