ArraysList 与顺序表 ——模拟实现

---

1.顺序表的创建

顺序表是一个数组，顺序表有许多功能，元素的增加、删除、查找、修改等。

在类里面使用这种方法创建它即可；

usedSize默认值为0（统计顺序表里面元素个数）。

public Array( ) { }为无参数的构造方法，实例化对象时自动实例化arr。

2. 顺序表的增加元素

增加元素有两种：

一、末尾插入

• 首先判定增加元素，数组会不会越界，如果越界那么就进行扩容操做
  增加元素顺序表默认在最后一个元素后面插入
  每增加一个元素usedSize++;
  
  ​​​​​​
  

二、任意位置插入

 

 思路： 找到最后一个元素的下标，将要插入位置的下标及后面元素的下标这一段一同向后移动一段，空出要插入下标的位置，最后将要插入的元素放到里面。

 2.顺序表的删除

 如：

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

 思路：删除元素及删除，所以顺序表中不能没有元素，否则无法进行后续操作。

将数组进行遍历，找到这个这个目标元素下标，将目标元素后面元素赋值给目标元素，然后依此类推，将最后一个元素赋值给其前面元素。

usedSize--; 

 

这时会有同学问：

     删除后的数组的最后一个元素还是原本的数组的最后一个元素啊？

答：

   usedSize-- 数组边界已经减小，打印出来的元素不会包括后者最后一个元素。

3、顺序表的修改

 

将pow下标修改成 val.

pow不可超远最后一个元素的下标。

4、顺序表的查询

 分为两种： 情况一：查找下标是什么元素

                     情况二：查找元素在什么下标

情况一：

 

情况二：

 

5.总体代码如下： 

import java.util.Arrays;

// 线性表
// 线性表的创建
 class Array{
   // 线性表的创建
    public int [] arr;
    public int usedSize;
    public Array(){
        arr = new int[4];
    }
    public void add(int val){
        if(isFull()){
            arr = Arrays.copyOf(arr,arr.length*2);
        }
     arr[usedSize] = val;
     usedSize++;
    }
    public boolean isFull(){
        return usedSize == arr.length;
    }
    public void add(int sst,int val){

        int s = usedSize;
        while (s>=sst){
            if(isFull()){
                arr = Arrays.copyOf(arr,arr.length*2);
            }
            arr[s+1] = arr[s];
            s--;

        }
        arr[s+1] = val;
        usedSize++;

    }

    public void display(){
        for (int i = 0; i < usedSize; i++) {
            System.out.print(arr[i]+" ");
        }
    }
    //删除第一次出现的关键字key
    public void remove(int toRemove) {
        if(isEmpty()){
            return;
        }
        for (int i = 0; i < usedSize; i++) {
            if(arr[i] == toRemove){
                int a = i;
                while (a < usedSize) {
                    arr[a] = arr[a + 1];
                    a++;
                }
                break;
            }
        }
        usedSize--;
        System.out.println();
    }
    public boolean isEmpty(){
       return usedSize == 0;
    }

    public void set(int pow , int val){
        if(pow > usedSize){
            return;
        }
        arr[pow] = val;
    }
    public int get (int pow ){
        return arr[pow];
    }

    public int indexOf(int val){
        for (int i = 0; i < usedSize; i++) {
            if(arr[i] == val){
                return i;
            }
        }
        return -1;
    }
    public boolean contains(int toFind){
        for (int i = 0; i < usedSize; i++) {
            if(arr[i] == toFind){
                return true;
            }
        }
        return false;
    }
    public void clear(){
        usedSize=0;
    }


}

public class TextDemo {
    public static void main(String[] args) {

        
    }
}

 其中包括contains方法、清楚方法、内容简单，代码一看就明白。

6、ArraysList的方法