【数据结构与算法】Java描述：第一节：ArrayList顺序表

这篇文章我们自己实现一个顺序表， 从而更好的认识它。

一、顺序表的本质

顺序表的本质其实就是一个数组，但是在插入，查找与删除上，有些复杂，顺序表通过对方法进行封装，方便了使用。

---

---

二、自己的顺序表 2.1 我们先来定义一个接口，用来规范好方法

在接口中定义好 增删改查 的方法，在顺序表类中继承好这个接口

---

2.2 定义好顺序表需要的变量

分别是需要操作的数组，在顺序表中有效的数据，顺序表的大小

---

---

三、实现各种方法

不全部介绍，演示几个比较严谨的方法

增加方法：

判满，扩容，判断插入位置是否合法

---

删除一个数据的方法：

---

其余较简单方法不演示了，都是利用数组和usedsize写的

import java.util.ArrayList; import java.util.Arrays; public class MyArraylist implements Ilist{ public int[] array; public int usedSize; //顺序表中有意义的位数 public final int capacity = 10 ; //固定顺序表的大小 public MyArraylist() { this.array = new int[capacity]; } //判断数组是否满了 public boolean isFull(){ return this.usedSize == capacity; } //数组满了要扩容,复制原来的数组，把长度扩大二倍 private void grow(){ this.array = Arrays.copyOf(this.array, this.array.length*2); } //检查插入位置是否合法 public void checkPos(int pos) throws PosIllegal{ if(pos<0 || pos>usedSize){ throw new PosIllegal("插入位置不合法"); } } //判断数组是否为空 public void checkEmpty(){ if(isEmpty()){ throw new ArrayEmptyException("顺序表为空！"); } } public boolean isEmpty(){ return usedSize == 0; } @Override public void add(int data) { if (isFull()){ this.grow(); } this.array[this.usedSize] = data; usedSize++; } @Override public void add(int pos,int data) { try { //位置判断是否合法 checkPos(pos); //判断数组是否满了 if (isFull()){ this.grow(); } //挪动元素 for (int i = this.usedSize-1; i >=pos ; i--) { this.array[i+1] = this.array[i]; } this.array[pos] = data; usedSize++; }catch (PosIllegal e){ System.out.println("插入位置有问题。。。"); e.printStackTrace(); } } //查找数组是否包含toFind @Override public boolean contains(int toFind) { for (int i = 0; i <usedSize ; i++) { if(array[i]==toFind){ return true; } } return false; } //返回要找数据的下标 @Override public int indexOf(int toFind) { for (int i = 0; i <usedSize ; i++) { if(array[i]==toFind){ return i; } } return -1; } public void checkPos2(int pos) throws PosIllegal{ if(pos<0 || pos>=usedSize){ throw new PosIllegal("插入位置不合法"); } } @Override //获取指定位置的数值 public int get(int pos) { try{ checkEmpty(); checkPos2(pos); return array[pos]; }catch (PosIllegal e){ e.printStackTrace(); }catch (ArrayEmptyException e) { e.printStackTrace(); } return -1; } @Override //更新某位置 public void set(int pos,int value) { try{ checkEmpty(); checkPos2(pos); array[pos]=value; }catch (PosIllegal e){ e.printStackTrace(); }catch (ArrayEmptyException e) { e.printStackTrace(); } } @Override //移除某个数据（不确定位置） public void remove(int toRemove) { try{ checkEmpty(); int pos = indexOf(toRemove); if(pos==-1){ return; } for (int i = pos; pos< usedSize-1 ; i++) { //减1是为了最后一位不用变 array[i]=array[i+1]; usedSize--; } }catch (ArrayEmptyException e) { e.printStackTrace(); } } @Override public int size() { return this.usedSize; } @Override //清空顺序表的方法 public void clear() { for (int i = 0; i <usedSize ; i++) { usedSize = 0; } } @Override //打印顺序表的方法 public void display() { for (int i = 0; i <this.usedSize ; i++) { System.out.print(this.array[i]+" "); } } }

接口代码：

public interface Ilist { // 在 pos 位置新增元素 void add(int data); 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(); // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的 void display(); }