顺序表详解——遍历、增添、查找、删除、修改、清除

1.线性表与顺序表

线性表是指具有相同性质的元素组成的有限序列，由N个成员组成一个整体的数据结构，常见的线性表由：顺序表、链表、栈、队列、还有字符串.

线性表在逻辑上，是连续的，在物理结构上，不一定是连续的，他们开辟的物理空间之间不是彼此相连的，相互存在间隙。线性表储存是通常以数组和链式结构储存。

顺序表属于线性表，他开辟的物理空间是连续的，其底层逻辑就是数组，但是顺序表的逻辑实现是通过类来完成
相对于对普通的数组进行操作，顺序表显得更高级

• 可以扩容。顺序表在数组的基础上，当顺序表容量满了，可以自动实现扩大容量的功能，一般都是按原来比例的二倍进行扩容。

注意： Java提供的顺序表在开辟的阶段，如果未给出指定的容量capacity默认为零，其源码为:

    public ArrayList() {
      this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  }    

   //而DEFAULTCAPACITY_EMPTY_ELEMENTDATA起始大小为零，当第一次add的时候，系统给出的默认大小为十。
1
2
3
4
5

• 知晓有效元素的个数。数组给定容量后，只能查看总容量，也就是给定的大小，不能知晓有效元素的个数。就是当给定大小的数组为十个int类型的大小时，而数组里有效的数字只有一个int类型的元素。数组是无法判断这个大小只有一个int类型的大小。而顺序表中的有效元素size可以判断顺序表中的有效数字有多少。

所以可以把数组的功能当作顺序表功能的子集。

注意事项： 顺序表中的容量（capacity）和元素个数（size）的区别
顺序表的容量相当于数组的指定大小，元素个数size相当于该指定大小的空间中有效利用的空间中元素的个数

2.打印顺序表

//遍历顺序表，并打印
    public void display(){
        //usedSize==0
        for (int i = 0; i < this.usedSize; i++) {
            System.out.println(this.elem[i]+" ");
        }
        System.out.println();
    }
1
2
3
4
5
6
7
8

3.新增元素

在新增元素时，要考虑到顺序表是否已经满了，如果满了，则需要扩大容量

    public boolean isFull(){
        if(this.usedSize==this.elem.length){
            return true;
        }
        return false;
    }
1
2
3
4
5
6

尾插

    //新增元素，默认在数组最后新增
    public void add(int data){
        //1.判断是否满了，如果满了，则扩容
        if(isFull()){
            //扩容
            this.elem= Arrays.copyOf(this.elem,2*this.elem.length);
        }
        //2.如果没满
        this.elem[this.usedSize]=data;
        this.usedSize++;
    }
1
2
3
4
5
6
7
8
9
10
11

任意位置pos插入元素

在指定位置插入元素，判断是否满了的同时，还要判断指定位置的合法性，当位置合法时，从插入的位置开始，该位置和后面的位置元素向后挪一个单位，给足空隙让插入的元素放进去。

    private boolean checkPosInAdd(int pos){
        //判断位置的合法性, 不能跳跃插入元素，插入的位置前面必须要有元素
        if(pos<0||pos>this.usedSize){
            System.out.println("pos位置不合法");
            return false;
        }
        return true;//合法
    }

    //在pos位置新增元素
    public void add(int pos,int data){
        if(!checkPosInAdd(pos)){
            throw new MyArrayListIndexOutOfException("添加方法中的pos位置不合理");
        }
        if(isFull()) {
            this.elem=Arrays.copyOf(this.elem,2*this.elem.length);
        }

        //挪数据
        for (int i = this.usedSize-1; i >= pos ; i--) {
            this.elem[i+1]=this.elem[i];
        }
        //挪完数据
        this.elem[pos]=data;
        this.usedSize++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

4.判定是否包含某个元素

    //判定是否包含某个元素
    public boolean contains(int toFind){
        for (int i = 0; i < this.usedSize; i++) {   //遍历整个顺序表，找指定的元素toFind
            if(this.elem[i]==toFind)
                return true;
        }
        return false;
    }
1
2
3
4
5
6
7
8

5.找到某个元素对应的位置

跟在顺序表中，查找指定元素一样，遍历整个顺序表，如果找到对应元素，直需要返回对应的下标即可，如果没找到指定元素，则返回-1，表示查找失败。

    //找到某个元素对应的位置
    public int indexOf(int toFind){
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i]==toFind)
                return i;
        }
     return -1;
    }
1
2
3
4
5
6
7
8

6.获取pos位置的元素

首先判断下标的合法性，在合法的基础上，给定指定下标，返回该下标下，对应的元素

    private boolean checkPosInGet(int pos){
        //判断位置的合法性
        if(pos<0||pos>this.usedSize){
            System.out.println("pos位置不合法");
            return false;
        }
        return true;//合法
    }
    //获取pos位置的元素
    public int get(int pos){
        //检验获取位置pos的合法性
        if(!checkPosInGet(pos)){
            throw new MyArrayListIndexOutOfException("获取pos下标时，位置不合法");
        }
        return this.elem[pos];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

7.pos位置的元素进行更新(修改)

修改元素，不仅要判断给定的pos位置是否合法，还要判断是否为空，如果为空，可以进行自定义报错，在合法且顺序表不为空的情况下，用所给的value元素代替pos位置下标的元素

    //给pos位置的元素更新
    public void set(int pos,int value){
        if(!checkPosInGet(pos)){
            throw new MyArrayListIndexOutOfException("更新pos下标的元素，位置不合法");
        }
        if(isEmpty()){
            throw new MyArrayListEmptyException("顺序表为空");
        }

        this.elem[pos]=value;
    }
1
2
3
4
5
6
7
8
9
10
11

8.删除第一次出现的关键字key

删除某个元素的功能，其原理就是通过后面元素将前面元素进行覆盖，覆盖到最后的位置，直到最后两个元素相等，在此基础上，在usedsize–，就可以实现删除操作，虽然最后还是有一个位置的元素未被覆盖，但是当下次需要利用时，再将其覆盖就好了

    //删除第一次出现的关键字key
    public void remove(int toRemove){
        if(isEmpty()==true){
            throw new MyArrayListEmptyException("顺序表为空");
        }
            if(contains(toRemove)){
                for(int j=indexOf(toRemove);j

    //获取顺序表长度，返回usedsize
    public int size(){
        return this.usedSize;
    }
1
2
3
4

    //清空顺序表
    public void clear(){
//        如果为引用类型 必须全部置空，同时也要置为零  
//        for (int i = 0; i < usedSize; i++) {
//            this.elem[i]=null;
//        }
        this.usedSize=0;
        System.out.println("已完全清除");
    }
1
2
3
4
5
6
7
8
9