Java数据结构顺序表的详细讲解
作者:星鸦wyk 时间:2023-11-20 23:01:35
写在前面
关于数据结构,Java官方其实已经帮我们写好并封装起来了,在真正需要使用的时候直接调用即可,但为了更好的理解数据结构,我会按照源码的思路写一个简化后的数据结构,默认接收的数据为int
1.线性表
线性表是多个具有相同特性的数据元素的序列,线性表在逻辑上是一条连续的直线,但在实际存储上却不一定
顺序表则是线性表的一种,是用一段物理地址连续的存储单元依次存储数据元素的线性结构,通常是使用数组来实现
2.顺序表的实现
新建一个类叫做ArrList,顺序表的底层是数组,所以类里面也要有数组,其次还需要一个计数器来判断数组目前使用的空间是多少,那么顺序表的框架就完成了
public class ArrList {
public int[] arr;
public int count;
public ArrList() {
this.arr = new int[5]; //初始给5个大小空间
}
}
接下来就是顺序表的增删改查等操作了
2.1增加数据
增加数据有两个方法:末尾增加数据和任意位置增加数据
2.1.1尾部增加数据
在这之前需要进行的一项工作是判断顺序表的空间是否已满,如果空间已满的话需要进行扩容,判断顺序表空间是否已满的依据是计数器的值和数组的长度是否相等
public boolean isFull() {
return this.count==this.arr.length;
}
public void tailAdd(int data) {
//首先判断顺序表是否已满
if(isFull()) {
//顺序表已满,需要扩容,这里是扩大为原来的两倍
this.arr= Arrays.copyOf(this.arr,2*this.arr.length);
}
//程序走到这,不管有没有扩容,此时顺序表都是未满,直接添加数据
this.arr[this.count]=data;
this.count++;
}
2.1.2任意位置增加数据
任意位置添加数据的话首先要判断输入的值是否是合法的,有一点要注意:如果输入的值和计数器的值是相等的,那么此时就是在顺序表末尾添加数据,这个数是合法的
public void add(int index,int data) {
//首先需要判断index的值是否合法,不合法直接抛出异常
if(index<0||index>this.count) {
throw new ArrayIndexOutOfBoundsException("位置非法");
}
if(isFull()) {
//顺序表已满,需要扩容
this.arr= Arrays.copyOf(this.arr,2*this.arr.length);
}
if(index==this.count) {
this.arr[this.count]=data;
this.count++;
} else {
//中间位置添加数据需要先把从此处开始到末尾的数据都往后移动一位,从后往前移
for (int i = this.count-1; i >=index ; i--) {
this.arr[i+1]=this.arr[i];
}
this.arr[index]=data;
this.count++;
}
}
2.2查找数据
输入一个值,遍历顺序表进行查找,有则返回下标,没有返回-1
public int find (int data) {
for (int i = 0; i < this.count; i++) {
if(this.arr[i]==data) {
return i;
}
}
return -1;
}
之所以返回值是int而不是boolean是因为后面的删除和修改数据的方法会使用到此方法
2.3删除数据
找到要删除的值的下标,从此处开始用后面的值对前面的值进行覆盖,最后将尾部的值改为0
public void delData(int data) {
int i=find(data);
if(i!=-1) {
for (int j = i; j <this.count-1 ; j++) {
this.arr[j]=this.arr[j+1];
}
this.count--;
this.arr[this.count]=0;
}
}
2.4修改数据
修改指定位置的值,依旧首先要判断位置是否合法
public void setIndex (int index,int data) {
if(index<0||index>=this.count) {
throw new ArrayIndexOutOfBoundsException("位置非法");
}
this.arr[index]=data;
}
最后是销毁顺序表,不需要吧数组进行销毁,否则下次使用的时候还需要再实例化一个对象,只需要让计数器为0即可
public void clear () {
this.count=0;
}
3.ArrayList
Java中的顺序表叫做ArrayList,这是一个泛型类,这个类继承了多个其它类以及接口,其中包括List接口,List提供了很多抽象方法,ArrayList实现此接口对这些方法进行重写
3.1ArrayList的实例化
ArrayList有三种构造方法
ArrayList() | 无参构造 |
ArrayList(Collection<? extends E> c) | 利用其他 Collection 构建 ArrayList |
ArrayList(int initialCapacity) | 指定顺序表初始容量 |
要说明的是:调用无参数构造方法,默认数组的大小为0,之后在调用里面的方法(比如add方法)的时候会有专门的扩容的方法将其扩容为10,之后如果数组满了的话扩容为之前的1.5倍(源码里面套的方法太多就不展示了)
3.2ArrayList常用的方法
boolean add(E e) | 尾插 |
void add(int index, E element) | 将元素插入到 index 位置 |
boolean addAll(Collection<? extends E> c) | 尾插 c 中的元素 |
E remove(int index) | 删除 index 位置元素 |
boolean remove(Object o) | 删除遇到的第一个指定的值 |
E get(int index) | 获取下标 index 位置元素 |
E set(int index, E element) | 修改下标 index 位置的元素 |
void clear() | 销毁顺序表 |
boolean contains(Object o) | 判断指定元素是否在表中 |
int indexOf(Object o) | 返回第一个指定元素所在下标 |
int lastIndexOf(Object o) | 返回最后一个指定元素的下标 |
List<E> subList(int fromIndex, int toIndex) | 截取指定部分的元素 |
最后的截取方法是在原数组上进行截取
来源:https://blog.csdn.net/qq_52989768/article/details/124574731
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
谈谈HttpClient使用详解
SpringCloud @FeignClient参数的用法解析
C#控制台带参数程序源码编写实例讲解
c#根据文件大小显示文件复制进度条实例
![](https://img.aspxhome.com/file/2023/5/116575_0s.png)
JAVA字符串占位符使用方法实例
Android绘制机器人小实例
![](https://img.aspxhome.com/file/2023/8/138798_0s.jpg)
当用户退出点击浏览器后退仍可回到原来页面的解决方案
Android对话框AlertDialog详解
![](https://img.aspxhome.com/file/2023/3/82423_0s.jpg)
Java接口中尽量避免使用数组
![](https://img.aspxhome.com/file/2023/0/69930_0s.png)
整理Java编程中常用的基本描述符与运算符
Java判断主机是否能ping通代码实例
![](https://img.aspxhome.com/file/2023/8/90958_0s.png)
C#实现读取DataSet数据并显示在ListView控件中的方法
关于java 图形验证码的解决方法
C#机器入门学习之判断日报是否合格详解
![](https://img.aspxhome.com/file/2023/7/119477_0s.png)
详解Mybatis Generator的具体使用教程
![](https://img.aspxhome.com/file/2023/1/130901_0s.jpg)
经典实例讲解C#递归算法
![](https://img.aspxhome.com/file/2023/2/94552_0s.gif)
Android实现彩信附件的添加与删除功能
详解flutter中常用的container layout实例
![](https://img.aspxhome.com/file/2023/6/113306_0s.png)
WPF使用DrawingContext实现二维绘图
C语言 超详细总结讲解二叉树的概念与使用
![](https://img.aspxhome.com/file/2023/2/120782_0s.webp)