ArrayList顺序表简单实现

一、创建MyArrayList框架 

1.1 MyArrayList 类中实现 arr 数组

import java.util.Arrays;public class MyArrayList {private int[] arr;private int usesize;private static final int P = 10;public MyArrayList() {arr = new int[P];}

在 MyArrayList 类内创建 arr 数组，usesize 是 arr 数组内元素个数，定义常量 P 为10，并通过构造器将 arr 数组的初始内存赋值为10

1.2 实现 IList 接口

public interface IList {// 在数组末尾新增元素public void add(int data);// 判断数组是否已满boolean isFull();// 在 pos 位置新增元素public void add(int pos, int data);// 判定是否包含某个元素public boolean contains(int toFind);// 查找某个元素对应的位置public int indexOf(int toFind);// 获取 pos 位置的元素public int get(int pos);// 给 pos 位置的元素设为 valuepublic void set(int pos, int value);//删除第一次出现的关键字keypublic void remove(int toRemove); // 获取顺序表长度public int size() ;// 清空顺序表public void clear();// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的public void display() ;
}

该接口内有各种抽象类方法， MyArrayList 类 implements IList 接口后需要重写接口内的所有抽象类方法

1.3  MyArrayList 类 implements IList 接口

import java.util.Arrays;public class MyArrayList implements IList{private int[] arr;private int usesize;private static final int P = 10;public MyArrayList() {arr = new int[P];}@Overridepublic void add(int data) {}@Overridepublic boolean isFull() {return false;}@Overridepublic void add(int pos, int data) {}@Overridepublic boolean contains(int toFind) {return false;}@Overridepublic int indexOf(int toFind) {return 0;}@Overridepublic int get(int pos) {return 0;}@Overridepublic void set(int pos, int value) {}@Overridepublic void remove(int toRemove) {}@Overridepublic int size() {return 0;}@Overridepublic void clear() {}@Overridepublic void display() {}
}

 

二、重写各种方法

// 在数组末尾新增元素
public void add(int data);
// 判断数组是否已满
boolean isFull();
// 在 pos 位置新增元素
public void add(int pos, int data);
// 判定是否包含某个元素
public boolean contains(int toFind);
// 查找某个元素对应的位置
public int indexOf(int toFind);
// 获取 pos 位置的元素
public int get(int pos);
// 给 pos 位置的元素设为 value
public void set(int pos, int value);
//删除第一次出现的关键字key
public void remove(int toRemove);
// 获取顺序表长度
public int size() ;
// 清空顺序表
public void clear();
// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
public void display() ;

2.1 重写两种 add 方法

在数组末尾新增元素

2.1.1 第一种：

@Override
public void add(int data) {if(isFull()) {        // 在添加元素前使用 isFull 方法需判断数组是否存满grow();           // 如果已满，使用 grow 方法扩大数组}arr[usesize] = data;usesize++;}

2.1.1.1  isFull 方法

判断数组是否已满

@Override
public boolean isFull() {    // 判满，返回 usesize 与 数组长度 的比较结果return usesize == this.arr.length;  
}

2.1.1.2  grow 方法

private void grow() {      // 使用 Arrays.copyOf 方法将数组的长度扩大为原来的两倍arr = Arrays.copyOf(arr, 2 * arr.length);  
}

 

 2.1.2 第二种：

在 pos 位置新增元素

@Override
public void add(int pos, int data) {try{                    // 使用 try...catch() 处理异常 check2(pos);        // 使用 check2 方法判断 pos 位置是否合法，并抛出异常if(isFull()) {      // 在添加元素前使用 isFull 方法需判断数组是否存满grow();         // 如果已满，使用 grow 方法扩大数组    }for (int i = usesize - 1; i >= pos ; i--) {arr[i + 1] = arr[i];}arr[pos] = data;usesize++;} catch (PosException e) {        // 捕捉异常，打印异常信息System.out.println("插入位置有误");e.printStackTrace();}}

2.1.2.1 check2 方法： 

private void check2(int pos) throws PosException{if(pos < 0 || pos > usesize ) {      // check 方法中的 pos 不允许 = usesize    throw new PosException("输入位置有误"); // 如果 pos不合法，抛出PosException}
}

2.1.2.2 PosException 类：

public class PosException extends RuntimeException{  // 自定义 PosException 异常public PosException() {super();}public PosException(String message) {super(message);}
}

 2.2 重写 contains 方法

判定是否包含某个元素

遍历 arr 数组，如果数组有与toFind相同的元素则返回 true ，否则返回 false

@Override
public boolean contains(int toFind) {for (int i = 0; i < usesize; i++) {   // 遍历数组if(toFind == arr[i]) {            // 判断数组中是否有与 toFind 相同的元素   return true;                  // 如果有，返回true}}return false;                         // 遍历完数组后，没有与 toFind 相同的元素
}                                         // 返回 false                       

2.3 重写 indexOf 方法

查找某个元素对应的位置

遍历数组，如果数组中存在与 toFind 相同的元素则返回数组下标，否则返回 -1

@Override
public int indexOf(int toFind) {for (int i = 0; i < usesize; i++) { // 遍历数组if(toFind == arr[i]) {          // 判断数组中是否有与 toFind 相同的元素     return i;                   // 如果有，返回该元素下标}}return -1;                        // 遍历完数组后，没有与 toFind 相同的元素      
}                                     // 返回 -1          

2.4 重写 get 方法

获取 pos 位置的元素 

@Override
public int get(int pos) {try{                  // 使用 try...catch() 处理异常       empty();          // 判断数组是否为空，为空则抛出异常EmptyExceptioncheck(pos);       // 使用 check 方法判断 pos 位置是否合法，并抛出异常 return arr[pos];  // 返回 pos 位置的元素      } catch (PosException e) {      // 捕捉异常，打印异常信息e.printStackTrace();} catch (EmptyException e) {    // 捕捉异常，打印异常信息    e.printStackTrace();}return -1;
}

 2.4.1 empty 方法

private void empty() throws EmptyException{   // 判断 usesize 是否为零，为零抛出异常if(usesize == 0) {                           EmptyException              throw new EmptyException("数组为空");    }

2.4.2  check 方法

private void check(int pos) throws PosException{ if(pos < 0 || pos >= usesize ) {       // check 方法中的 pos 允许 = usesize    throw new PosException("输入位置有误");// 如果 pos不合法，抛出PosException}
}

2.4.3  EmptyException 类

public class EmptyException extends RuntimeException{ // 自定义 EmptyException 异常public EmptyException() {super();}public EmptyException(String message) {super(message);}
}

 

2.5 重写 set 方法

给 pos 位置的元素设为 value 

@Override
public void set(int pos, int value) {try{empty();          // 判断数组是否为空，为空则抛出异常EmptyExceptioncheck(pos);       // 使用 check 方法判断 pos 位置是否合法，并抛出异常 arr[pos] = value; // 将 pos 位置的值赋值为 value} catch (PosException e) {     // 捕捉异常，打印异常信息e.printStackTrace();} catch (EmptyException e) {   // 捕捉异常，打印异常信息     e.printStackTrace();}
}

2.6 重写 remove 方法

删除第一次出现的关键字key

@Override
public void remove(int toRemove) {try{empty();      // 判断数组是否为空，为空则抛出异常EmptyException   int p = indexOf(toRemove);  // 使用 indexOf 方法获取要删除元素的下标位置if(p == -1) {         // 返回 -1 则数组中没有要删除的元素并结束return;}for (int j = p; j < usesize - 1; j++) {  // 从要删除元素下标开始遍历数组arr[j] = arr[j + 1];     // 将数组中后一个元素赋值给前一个元素usesize--;  // usesize 减一}} catch (EmptyException e) {  // 捕捉异常，打印异常信息e.printStackTrace();}
}

 2.7 重写 size 方法

获取顺序表长度

@Override
public int size() {return usesize;  // 返回 usesize
}

2.8 重写 clear 方法

清空顺序表 

@Override
public void clear() {usesize = 0;  // 将 usesize 赋值为零
}

2.9 重写 display 方法

打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的

@Override
public void display() {for (int i = 0; i < usesize; i++) {  // 遍历数组并打印数组信息System.out.print(arr[i] + " ");  }
}

三、总结 

顺序表是通过一段连续的存储单元来存储数据元素的，这种存储方式使得元素在物理位置上是相邻的，从而可以通过下标直接访问任意位置的元素。这种特性使得顺序表在访问元素时具有非常高的效率。顺序表的基本操作包括插入、删除、查找和修改等，通过不断练习和实践，我逐渐掌握了这些操作的实现技巧。顺序表的性能与其存储方式和操作实现密切相关。

我深入了解了顺序表的时间复杂度和空间复杂度分析方法。这有助于我在实际编程中根据需求选择合适的数据结构和算法，以达到最优的性能。学习顺序表不仅是为了理解其基本概念和特性，更重要的是将其应用于实际编程中。

我尝试使用顺序表解决了一些实际问题，如实现一个简单的通讯录管理系统、统计一个文本文件中不同单词的出现次数等。这些实践经历让我更加深入地理解了顺序表的实际应用和价值。