当前位置：首页 > news >正文

【数据结构_4】顺序表

news 2025/4/16 7:21:22

一、ArrayList功能的实现（书接上文）：

1.实现arraylist的根据下标进行删除操作

    //4.实现根据下标进行删除的操作public String remove(int index){//1.首先我们要对index的值进行判断if(index<0 ||index>=size){//应该是抛出异常throw new IndexOutOfBoundsException("Index:"+index+"Size"+size)}//提前把删除的元素保存一份，否则后面搬运的时候就会覆盖String elem = data[index];//2.进行删除操作for (int i = index; i < size-1; i++) {data[i]=data[i+1];}size--;return elem;}

2.根据元素的值来删除元素

    //5.根据元素的值来删除元素public static boolean remove(String elem){//1.首先我们需要遍历数组来查找元素是否存在int RemovePos =0;for (; RemovePos < size; RemovePos++) {if(data[RemovePos].equals(elem)){break;};}//2.出来之后有两种情况，一种是RemovePos==size，另一种是找到了元素elemif(RemovePos == size){return false;}else{//3.要进行根据下标来删除元素的操作for (int i = RemovePos; i < size-1; i++) {data[i]=data[i+1];}size--;return true;}}

3.set和get操作

    //6.实现get和set功能public  String get(int index){//还要对下标进行合法性判断if(index<=0 ||index >=size){throw new IndexOutOfBoundsException("Index:"+index+"Size:"+size);}return data[index];}public void set(int index,String elem){if(index<=0 ||index >=size){throw new IndexOutOfBoundsException("Index:"+index+"Size:"+size);}data[index]=elem;}

*注意，这里的抛出异常不可以不写。虽然就算不写最后也会抛出异常，但是这个地方在考察大家对于不合法的Index的判断，是一个面试的考点，所以一定要写。一定要有这个意识！

5.clear清空操作

    public static void clear(){size=0;}

*逻辑删除将有效长度标记为0

6.contains包含操作

    public static boolean contains(String elem){for (int i = 0; i < size; i++) {if(data[i].equals(elem)){return true;}}return false;}

7.根据元素返回下标

    //9.根据元素的值返回下标public static int  indexOf(String elem){for (int i = 0; i < size; i++) {if(data[i].equals(elem)){return i;}}return -1;}

8.从后往前遍历

    //10.从后往前遍历public static int lastIndexOf(String elem){for (int i = size-1; i >=0 ; i--) {if(data[i].equals(elem)){return i;}}return -1;}

9.实现subList操作

    public ArrayList<String> subList(int fromIndex, int toIndex){//1.首先要判断参数的合法性if( fromIndex < 0 || fromIndex >= size || toIndex < fromIndex){throw new IndexOutOfBoundsException("fromIndex: "+fromIndex +"toIndex" +toIndex);}//2.先创建一个顺序表ArrayList<String> arrayList = new ArrayList<>(toIndex-fromIndex);//3.将对应区间上的值分到顺序表上for (int i = fromIndex; i <toIndex ; i++) {String elem = this.get(i);arrayList.add(elem);}return arrayList;}

至此，ArrayList的大多数操作功能都已经被成功实现，下面是一个总结版本：

package arrayList;import javax.management.openmbean.OpenDataException;
import java.util.ArrayList;
import java.util.Arrays;public class MyArrayList {private static String[] data = null;//表示有效元素的个数private static int  size =0;//创建一个构造方法 似地默认的初始容量为10public MyArrayList(){data = new String[10];}//如果初始容量给的小于10，那我们要把他扩容到10public MyArrayList(int capacity){if(capacity<=10){capacity=10;}data = new String[capacity];}@Overridepublic String toString() {//把有效字符转化为字符串，并把他们拼接到一起StringBuilder stringBuilder = new StringBuilder();stringBuilder.append("[");for (int i = 0; i < size; i++) {stringBuilder.append(data[i]);if(i!=size-1) {stringBuilder.append(",");}}stringBuilder.append("]");return stringBuilder.toString();//最后还要通过toString方法把StringBuilder转化为字符串类型}//1.实现尾插操作public void add(String elem){data[size] = elem;//这里本来就有10的容量了，只不过数组里没有任何东西，所以可以这样存放，也不会触发数组越界的问题size++;//实现扩容方法if(size > data.length){resize();}}//2.实现扩容操作public void resize(){//思路：首先我们要创建一个更大的数组newDataString[] newData = new String[data.length + data.length>>1];//然后将旧数组的值一个个赋值到新数组for (int i = 0; i < data.length ; i++) {newData[i]= data[i];}//然后将data的地址赋给newDatanewData = data;}//3.实现中间插入元素的操作public void add(int index,String elem){//1.首先要考虑index的值是否合法if(index <0 || index >size){//这里要考虑边界情况//当index = 0的时候相当于”头插“//当index = size 的时候相当于”尾插“//如果满足if条件，那我们就要抛出越界的异常throw new IndexOutOfBoundsException("Index: "+ index +"Size "+size);}//2.现在我们先把Index直至size的元素全部向后挪1位//*这里要注意，应该是从后往前移动，否则后面的值都被覆盖掉了for (int i = size-1; i >=index ; i--) {data[i+1]= data[i];}//3.最后把elem放到index这个位置就可以了data[index] = elem;//不要忘记size还要++size++;}//4.实现根据下标进行删除的操作//*这里要把他改成静态方法，使得全局都可以调用！！public static String remove(int index){//1.首先我们要对index的值进行判断if(index<0 ||index>=size){//应该是抛出异常throw new IndexOutOfBoundsException("Index:"+index+"Size"+size);}//提前把删除的元素保存一份，否则后面搬运的时候就会覆盖String elem = data[index];//2.进行删除操作for (int i = index; i < size-1; i++) {data[i]=data[i+1];}size--;return elem;}//5.根据元素的值来删除元素public static boolean remove(String elem){//1.首先我们需要遍历数组来查找元素是否存在int RemovePos =0;for (; RemovePos < size; RemovePos++) {if(data[RemovePos].equals(elem)){break;};}//2.出来之后有两种情况，一种是RemovePos==size，另一种是找到了元素elemif(RemovePos == size){return false;}else{remove(RemovePos);return true;}}//6.实现get和set功能public  String get(int index){//还要对下标进行合法性判断if(index<=0 ||index >=size){throw new IndexOutOfBoundsException("Index:"+index+"Size:"+size);}return data[index];}public void set(int index,String elem){if(index<=0 ||index >=size){throw new IndexOutOfBoundsException("Index:"+index+"Size:"+size);}data[index]=elem;}//7.clear清空操作public static void clear(){size=0;}//8.contains包含操作public static boolean contains(String elem){return indexOf(elem)!=-1;}//9.根据元素的值返回下标public static int  indexOf(String elem){for (int i = 0; i < size; i++) {if(data[i].equals(elem)){return i;}}return -1;}//10.从后往前遍历public static int lastIndexOf(String elem){for (int i = size-1; i >=0 ; i--) {if(data[i].equals(elem)){return i;}}return -1;}//11.实现subList操作public ArrayList<String> subList(int fromIndex, int toIndex){//1.首先要判断参数的合法性if( fromIndex < 0 || fromIndex >= size || toIndex < fromIndex){throw new IndexOutOfBoundsException("fromIndex: "+fromIndex +"toIndex" +toIndex);}//2.先创建一个顺序表ArrayList<String> arrayList = new ArrayList<>(toIndex-fromIndex);//3.将对应区间上的值分到顺序表上for (int i = fromIndex; i <toIndex ; i++) {String elem = this.get(i);arrayList.add(elem);}return arrayList;}public static void main(String[] args) {}}