Quartz 4

顺序表

4 min read

https://www.itbaima.cn/zh-CN/document/

Introduction

既然数组无法实现这样的高级表结构，那么我就基于数组，对其进行强化，也就是说，我们存放数据还是使用数组，但是我们可以为其编写一些额外的操作来强化为线性表，像这样底层依然采用顺序存储实现的线性表，我们称为顺序表。

定义一个新的类型：

public class ArrayList<E> {   // 泛型E，因为表中要存的具体数据类型待定  
 
    int capacity = 10;   //当前顺序表的容量 
     
    int size = 0;   //当前已经存放的元素数量  
    
    private Object[] array = new Object[capacity];   //底层存放数据的数组 
     
    public void add(E element, int index){   //插入方法需要支持在指定下标位置插入  
        for (int i = size; i > index; i--)   //从后往前，一个一个搬运元素  
            array[i] = array[i - 1];  
        array[index] = element;   //腾出位置之后，直接插入元素放到对应位置上  
        size++;   //插入完成之后，记得将size自增  
    }  
}

当插入元素时，需要将插入位置给腾出来，也就是将后面的所有元素向后移，同样的，如果要删除元素，那么也需要将所有的元素向前移动，顺序表是紧凑的，不能出现空位。

只不过这样并不完美，因为我们的插入操作并不是在任何位置都支持插入的，我们允许插入的位置只能是 [0, size] 这个范围内

所以说我们需要在插入之前进行判断：

public void add(E element, int index){
    if(index < 0 || index > size)    //插入之前先判断插入位置是否合法
        throw new IndexOutOfBoundsException("插入位置非法，合法的插入位置为：0 ~ "+size);
    for (int i = size; i > index; i--){
	    array[i] = array[i - 1];
    }
    array[index] = element;
    size++;
}

给add方法加入扩容机制

System.arraycopy()

arraycopy

public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
参数类型说明
srcObject源数组
srcPosint源数组的起始位置（索引）
destObject目标数组
destPosint目标数组的起始位置（索引）
lengthint要复制的元素个数
int[] src = {1, 2, 3, 4, 5};
int[] dest = new int[5];
 
System.arraycopy(src, 1, dest, 0, 3); // 从src[1]开始，复制3个元素到dest[0]
 
for (int i : dest) {
		System.out.print(i + " ");
}

结果：2 3 4 0 0

Link to original

 if(capacity == size) {
        int newCapacity = capacity + (capacity >> 1);   //扩容规则就按照原本容量的1.5倍来吧
        Object[] newArray = new Object[newCapacity];    //创建一个新的数组来存放更多的元素
        System.arraycopy(array, 0, newArray, 0, size);   //使用arraycopy快速拷贝原数组内容到新的数组
        array = newArray;   //更换为新的数组
      	capacity = newCapacity;   //容量变成扩容之后的
}

删除元素

public E remove(int index){
    if(index < 0 || index > size - 1)
        throw new IndexOutOfBoundsException("删除位置非法，合法的插入位置为：0 ~ "+(size - 1));
    E e = (E) array[index];
    for (int i = index; i < size -; i++)
        array[i] = array[i + 1];
    size--;
    return e;
}

Graph View