目录
一、用数组实现顺序表
一、用数组实现顺序表
我们提到过,顺序表是基于数组的封装,这次我们以int为例,用数组去实现一个顺序表。
public class MyArrayList { private int[] arr; public MyArrayList(int capacity){//指定初始容量 arr = new int[capacity];//这个顺序表依然是空的,还得使用add往里面添加有效元素 }}
既然存在有效与无效,那我们该如何区分呢?我们可以定义一个size变量。
private int size;//规定前size个元素为有效元素
下面就是进行写出方法,比如增、删、查、改等。
//获取元素个数 public int size(){ return size; } //新增元素,尾插 public void add(int val){ } //任意位置新增元素 public void add(int index,int val){ } //根据下标获取元素 public void get(int index){ } //根据下标设置元素 public void set(int index,int val){ } //根据数组的值删除元素 public void delete(int val){ } //根据下标删除元素 public int remove(int index,int val){ } //判断元素是否存在 public boolean contains(int val){ } //查找元素所在位置 public int indexOf(int index){ } //删除所有元素 public void clear(){ } //打印操作,把ArrayList转成字符串 @Override public String toString() { }
这里是一些主要的方法,如果我们想实现其他方法,也可以再新增。我们对方法进行了命名之后,下面就是进行实现。我们先来看新增元素的实现。我们需要把新增的元素放到最后的位置,下标为size。如果说size比arr.length的值要小,那么我们正常添加就可以,可如果我们size的值比arr.length要小,我们要先进行扩容。我们可以再写一个resize方法来扩容。
//新增元素,尾插 public void add(int val){ if(size == arr.length){ resize(); } arr[size] = val; size++; } private void resize(){//这个方法只有程序员才能调用 //创建一个更长的数组,长度扩大到原来的1.5倍 //这样就能保证我们每添加一个元素,长度够用 int[] newArr = new int[(int)(arr.length * 1.5)]; for (int i = 0; i < size; i++) { //原来数组的元素复制到新数组中 newArr[i] = arr[i]; //新数组代替旧数组,旧的数组会被垃圾回收给释放掉 arr = newArr; } }
我们还要实现toString方法,方便我们后期打印这个顺序表。
@Override public String toString() { // 打印的格式形如: [1, 2, 3, 4] StringBuilder stringBuilder = new StringBuilder(); stringBuilder.append("["); for (int i = 0; i < size; i++) { stringBuilder.append(arr[i]); if (i < size - 1) { stringBuilder.append(", "); } } stringBuilder.append("]"); return stringBuilder.toString(); }
下面我们来进行一下测试,
public static void test(){ MyArrayList list = new MyArrayList(6); list.add(1); list.add(2); list.add(3); list.add(4); System.out.println(list.size); System.out.println(list); } public static void main(String[] args) { test(); }
下面是调试结果
运行结果
下面我们进行对新增元素的实现,当我们插入一个新元素时,这个新元素之后的所有元素都要后移一个位置。那么此时我们的时间复杂度就是。
public void add(int index, int val) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("Index out of bounds"); } // 如果数组已经满了, 继续添加元素, 也是要先扩容 if (size == arr.length) { resize(); } // 搬运元素的操作. 从后往前, 依次把每个元素都往后搬运一个位置. // 如果元素本身的下标是 i, 就把这个元素赋值到 i+1 的位置上. // index 位置的元素也需要往后搬运一下, i >= index for (int i = size - 1; i >= index; i--) { arr[i + 1] = arr[i]; } // 此时就相当于把 index 位置已经腾出来了. 把新元素放到 index 位置上就好了. arr[index] = val; // 不要忘记更新 size size++; }
有的老铁可能觉得这个方法有点麻烦,如果说我们直接插入的新元素,这个位置的旧元素直接后移到我们顺序表中的最后一个位置行不行,并且此时的时间复杂度就是。其实呢,对于我们的顺序表和链表这样的结构来说,它们都是“有序的”,如果我们把原有的顺序改变了,就不是原来的结构了。
//根据下标获取元素public int get(int index){ if(index<0 || index>arr.length){ throw new IndexOutOfBoundsException("下标越界"+index); } return arr[index]; }
数组通过[]访问下标,时间复杂度是。Java的数组呢,本质是来源于C/C++,C/C++中数组访问下标时间复杂度同样也是。我们知道数组是一块连续存放的内存空间,通过过数组首元素和下标快速算出来对应元素的地址,根据这个地址来访问这个内存空间。内存的硬件设备具备一个特性,随机访问能力。
对于删除元素,也是要保证顺序表在有序的前提下,对于尾删的情况,直接进行size--就可以了,不必进行搬运。 但如果说,我们删除中间的某一个元素,当index==size时,尾插是可以的,但index>size的时候,就会出现异常。
if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("下标越界: " + index); }
//根据下标删除元素 public int remove(int index,int val){ if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("下标越界: " + index); } //要删除的元素先保存起来,就不怕后期搬运的时候被覆盖 int result = arr[index]; if (index == size-1){ //尾删 size--; return result; } //一定要注意边界值,可以代入具体数字进行验证 for (int i = index; i < size-1; i++) { arr[i] = arr[i+1];//进行向后搬运 } }
仔细分析上面的代码时就会发现,当index为尾删的时候,for循环是进不去的,接下来进行的就是size--的操作。
public static void test2(){ MyArrayList list = new MyArrayList(10); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); list.add(6); list.add(7); list.remove(0); System.out.println(list); list.remove(2); System.out.println(list); list.remove(4); System.out.println(list); list.remove(100); System.out.println(list); }
对于delete方法,我们需要先找到这个值所在的位置,找到之后,调用remove方法执行。
for (int i = 0; i < size; i++) { if(arr[i] == val){ //找到了 break; } }
这个for循环结束的条件有两个,i==size或者是arr[i]==val时,但由于我们这个i是for循环里面的局部变量,我们可以把i改成index,并作用再for循环之外。
//根据数组的值删除元素 public void delete(int val){ int index = 0; for (; index < size; index++) { if(arr[index] == val){ //找到了 break; } } for (int i = index; i < size-1; i++) { arr[i] = arr[i+1];//进行向后搬运 } }
对于contains方法和IndexOf两个方法的代码逻辑非常相似,也比较简单,就不作过多讲解。
//判断元素是否存在 public boolean contains(int val){ for (int i = 0; i < size; i++) { if (arr[i] == val) { return true; } } return false; } //查找元素所在位置 public int indexOf(int val){ for (int i = 0; i < size; i++) { if (arr[i] == val) { return i; } } return -1; }