Java顺序表

时间:2022-06-03 星鸦wyk 人气:0

写在前面

关于数据结构，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)	截取指定部分的元素

最后的截取方法是在原数组上进行截取

加载全部内容