数据结构-顺序表
目录
实现顺序表
基本骨架
各个方法的实现
判断数组是否满
在数组最后新增元素
在pos位置插入元素
判断是否包含某个元素
查找某个元素对应的位置
获取/改变pos位置的元素
删除第一次出现的元素
获取顺序表的长度
清空顺序表
打印顺序表
注意事项
使用顺序表
认识构造方法
无参构造
利用其他Collection构建ArrayList
指定顺序表初始容量
ArrayList常见操作
ArrayList的遍历
顺序表的优缺点
顺序表其实就是一个数组，数组本身又是连续的一块内存，操作数组，在数组上进行增删查改。
实现顺序表
基本骨架
创建一个arraylist的包->创建一个类MyArrayList、异常类（位置不合法）、测试类->定义一个接口（含要实现的方法）
package arraylist;interface IList {// 新增元素,默认在数组最后新增void add(int data);// 在 pos 位置新增元素void add(int pos, int data);// 判定是否包含某个元素boolean contains(int toFind);// 查找某个元素对应的位置int indexOf(int toFind);// 获取 pos 位置的元素int get(int pos);// 给 pos 位置的元素设为 valuevoid set(int pos, int value);//删除第一次出现的关键字keyvoid remove(int toRemove);// 获取顺序表长度int size();// 清空顺序表void clear();// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的void display();//判断数组是否满Boolean isFull();
}
package arraylist;public class MyArrayList implements IList{public int[] elem;//定义一个elem数组int usedSize;//记录数组中所存的个数public MyArrayList() {this.elem = new int[10];}@Overridepublic void add(int data) {}@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() {}@Overridepublic Boolean isFull() {return null;}
}
package arraylist;//异常类的处理 更多内容请看专栏JavaSE语法
public class PosNotLegalException extends RuntimeException {public PosNotLegalException() {}public PosNotLegalException(String msg) {super(msg);}
}
package arraylist;public class Test {public static void main(String[] args) {//实现之后 有两种方法来使用此顺序表MyArrayList myArrayList = new MyArrayList();IList iList = new MyArrayList();}
}
各个方法的实现
判断数组是否满
@Override
public Boolean isFull() {return usedSize == elem.length;
}在数组最后新增元素
1、先要判断数组是否满了
2、如果满了进行扩容
3、没满则elem[usedSize]=data;
@Override
public void add(int data) {if (isFull()) {this.elem = Arrays.copyOf(elem, 2 * elem.length);} else this.elem[usedSize] = data;this.usedSize++;}在pos位置插入元素
1、先判断pos位置是否合法
2、再判断数组元素是否已满
3、找到pos位置，再移动元素（从最后一个元素向前遍历）elem[i]=elem[i-1];i>=pos+1;
4、插入元素elem[pos]=data;
@Override
public void add(int pos, int data) {try {checkPosOfAdd(pos);} catch (PosNotLegalException e) {e.printStackTrace();}if (isFull()) {this.elem = Arrays.copyOf(elem, 2 * elem.length);}for (int i = this.usedSize - 1; i >= pos; i--) {this.elem[i] = this.elem[i - 1];}this.elem[pos] = data;this.usedSize++;
}//该方法用来判断插入元素的pos位置是否合法
private void checkPosOfAdd(int pos) throws PosNotLegalException {if (pos < 0 || pos > usedSize)throw new PosNotLegalException("pos位置不合法");
}判断是否包含某个元素
@Override
public boolean contains(int toFind) {for (int i = 0; i < usedSize; i++) {if (this.elem[i] == toFind)return true;}return false;
}查找某个元素对应的位置
1、遍历找到这个元素并返回对应的位置
2、找不到返回-1
@Override
public int indexOf(int toFind) {for (int i = 0; i < usedSize; i++) {if (this.elem[i] == toFind)return i;}return -1;
}获取/改变pos位置的元素
先判断pos位置是否合法
@Override
public int get(int pos) {try {checkPosGetAndSet(pos);} catch (PosNotLegalException e) {e.printStackTrace();}return this.elem[pos];
}@Override
public void set(int pos, int value) {try {checkPosGetAndSet(pos);} catch (PosNotLegalException e) {e.printStackTrace();}this.elem[pos] = value;
}private void checkPosGetAndSet(int pos) throws PosNotLegalException {if (pos < 0 || pos >= usedSize)throw new PosNotLegalException("get/set pos位置不合法");
}删除第一次出现的元素
1、先找到这个元素所在的位置
2、再从这个位置开始往后进行遍历elem[i]=elem[i+1];i<usedSize-1;
@Override
public void remove(int toRemove) {int pos = indexOf(toRemove);if (pos == -1) {System.out.println("没有找到要删除的元素!");return;}for (int i = pos; i < usedSize - 1; i++) {this.elem[i] = this.elem[i + 1];}usedSize--;
}获取顺序表的长度
@Override
public int size() {return this.usedSize;
}清空顺序表
引用类型和基本数据类型不一样，引用类型会引用一个对象，如果只是将usedSize置为0，里面的对象还在引用着之前的对象—"内存泄漏"（本来不需要的对象还有元素在引用）。
@Override
public void clear() {
// for (int i = 0; i < usedSize; i++) {
// elem[i]=null;
// }this.usedSize = 0;
}打印顺序表
@Override
public void display() {for (int i = 0; i < this.usedSize; i++) {System.out.print(this.elem[i] + " ");}System.out.println();
}
注意事项
使用usedSize来记录当前有效数据个数，在增加了元素或删除了元素时要随时对usedSize++/--。
使用顺序表
以后在使用顺序表的时候，不可能再重头搭建一个顺序表。在Java当中已经实现了一个顺序表，我们只需来使用这个集合类。
此时仍然有两种方法来使用
public static void main(String[] args) {ArrayList<Integer> arrayList = new ArrayList<>();List<Integer> list = new ArrayList<>(); }通过list访问的方法比通过arrayList访问的方法少，因为前者只能访问接口中特有的方法，而后者为对象可以访问arrayList自己的方法。
认识构造方法
无参构造
只是一个数组引用
数组的长度为0
当调用一个不带参数的构造方法的时候，并没有给数组分配大小，数组的长度为0。那为什么可以add元素？
当调用不带参数的构造方法进行add时，第一次add会分配大小为10的内存。扩容机制为1.5倍扩容。
利用其他Collection构建ArrayList
1、ArrayList是实现了Collection接口的
2、参数的类型是当前arrayList2指定的泛型类型本身
指定顺序表初始容量
初始化指定数组大小
ArrayList常见操作
ArrayList的遍历
public class Test1 {public static void main(String[] args) {ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(10);arrayList.add(3);arrayList.add(9);arrayList.add(7);arrayList.add(23);for (int i = 0; i < arrayList.size(); i++) {System.out.print(arrayList.get(i) + " ");}System.out.println();System.out.println("================");for (Integer x : arrayList) {System.out.print(x + " ");}System.out.println();System.out.println("================");Iterator<Integer> it = arrayList.iterator();while (it.hasNext()) {System.out.print(it.next() + " ");}System.out.println();System.out.println("================");ListIterator<Integer> it1 = arrayList.listIterator();while (it1.hasNext()) {System.out.print(it1.next() + " ");}System.out.println();System.out.println("================");//从指定位置开始打印（倒着打印）ListIterator<Integer> it2 = arrayList.listIterator(arrayList.size());while (it2.hasPrevious()) {System.out.print(it2.previous() + " ");}System.out.println();System.out.println("================");}
}
顺序表的优缺点
优点：在给定下标的情况下，访问速度比较快-O(1)。适用于经常进行下标查找或更新的操作。
缺点：
- 对于ArrayList来说不方便插入和删除因为要移动数组元素，最坏情况下，0下标插入，得移动所有元素，删除0下标也得移动所有元素。
- 扩容可能会浪费空间。假设现在100个长度放满了，还有一个元素没放，假设此时扩容，多了50个，但是实际只需要一个。