一、顺序表的理解
顺序表是用一段
物理地址连续
的存储单元词义存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改。
顺序表可以分为静态顺序表和动态顺序表：
-
静态顺序表使用一块已经确定开辟的定长空间来存储数组元素。
-
动态顺序表可以根据数组元素个数来动态的开辟内存。
注意数组下标是从0开始
二、顺序表的代码实现
首先我们要先构建一个顺序表并初始化顺序表。
public class MyArrayList {
public int[] elem;
public int usedSize;
public void MyArrayList(){
this.elem= new int[10];
}
}我在其中定义了一个构造方法，用来以后存放数组元素。
1. 打印顺序表
我们通过已知的数组元素，使用for循环即可打印数组元素。
public void display(){
for (int i = 0; i < usedSize; i++) {
System.out.println(this.elem[i]+" ");
}
System.out.println();
}
2. 在顺序表中添加元素
在顺序表中添加元素分为两种情况：
-
在数组的末尾插入元素
这种情况比较简单，我们只需要在数组的最后一个元素后面插入新元素就可以了
-
在数组的中间或者开头插入元素
无论是在数组元素的中间插入元素还是在数组元素的开头插入元素，我们都需要将插入元素之后的元素整体向后移动，空出来的空间来存放新的数据元素。
public void add(int pos, int data) {
if(pos < 0 || pos > usedSize){ //判断插入下标位置是否合法
System.out.println("位置不合法");
return;
}
if(isFull()){ //判断数组元素是否已满，如果已满则需要进行数组扩容
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
for (int i = this.usedSize - 1; i >= pos; i--) {
elem[i+1] = elem[i]; //将所有插入元素之后的数组元素向后移动
}
this.elem[pos] = data;
this.usedSize++;
}
3. 判定是否包含某个元素
判定是否包含特定元素的时候我们只需遍历数组，寻找对应值相等的数组元素并返回是否寻找成功即可。
public boolean isFull(){
return this.usedSize == this.elem.length;//判断数组的长度
}
// 判定是否包含某个元素
public boolean contains(int toFind) {
for (int i = 0; i < usedSize; i++) { //遍历数组
if(elem[i] == toFind);
return true;
}
return false;
}
4.查找某个元素对应的位置
在上一步的基础上，返回数组下标即可。
public int search(int toFind) {
for (int i = 0; i < usedSize; i++) {
if(elem[i] == toFind){
return i;
}
}
return -1;
}
5. 获取 pos 位置的元素
判断pos位置我们需要注意一个关键点：pos下标位置是否合法
public int getPos(int pos) {
if(pos < 0 || pos > usedSize){
System.out.println("位置不合法");
return -1;
}
return this.elem[pos];
}
6. 给 pos 位置的元素设为 value
依然要判断位置是否合法
public void setPos(int pos, int value) {
if(pos < 0 || pos > usedSize){
System.out.println("位置不合法");
}
this.elem[pos] = value;
}
7. 删除第一次出现的关键字key
在删除顺序表中的元素也分为两种情况：
-
在顺序表的表尾删除元素
这种情况比较简单，我们直接删除表尾元素即可
-
在顺序表中间删除元素
在顺序表的中间或者头部删除元素时，要注意将删除元素后面的元素全部向前移动一格。
public void remove(int toRemove) {
int index = this.search(toRemove);
if(index < 0 || index > usedSize){
System.out.println("没找到要删除的元素");
}
for (int i = index; i < this.usedSize; i++) {
this.elem[i] = this.elem[i+1];
}
this.usedSize--;
}
8. 获取顺序表长度
public int size() {
return this.usedSize;
}
9. 清空顺序表
清空顺序表只要将长度置空即可。
public void clear() {
this.usedSize = 0;
}
三、顺序表的优点和缺点
顺序表的优点是可以对给定的数据元素进行随机存取，时间复杂度为O(1)。
缺点是1. 顺序表中间/头部的插入删除，时间复杂度为O(N) 2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。