【数据结构】顺序表-阿里云开发者社区

1.模拟实现顺序表

顺序表顾名思义按顺序存放的就是顺序表。顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改。

那我接下来我们就自己模仿一个顺序表，来实现数据的增删查改：

在.png

1.1 顺序的结构

在写顺序表的时候需要把成员属性和成员方法写在类中，所以在写之前需要把创建一个顺序表的类：

public class MyArrayList {
}

接下来我们要将写的成员属性和成员方法都写在这个 MyArrayList 类当中

1.2 顺序表的成员属性

arr：一个顺序表最主要的就是存放数据，有了数据才可以进行一些成员方法的操作，顺序表之所以叫做顺序表因为它是按顺序进行存储数据的，数组也是按顺序进行存储的，那我们就可以定义一个数组类型的成员变量用来存储数据

number：有些方法的操作需要在最后一个数据后面一个位置进行操作比如尾插、尾删都需要知道最后一个数据后面一个下标，那么我们就可以定义一个 int 类型成员变量来记录数据的个数，因为数组从0下标开始，那我定义的记录数据个数的成员变量肯定就是对应在最后一个数据后面的一个位置下标

volume：我们存储数据的时候肯定需要开辟空间，开辟多大的空间我们就可以定义一个静态整型的成员变量在固定每次开辟空间的大小

sum：当数据个数等于数据容量的时候就需要增加容量，那么我们就可以定义一个整型的成员变量来存储当前数组的容量大小，方便后面判断是否需要增加容量

private int[] arr;//存放数据数组
private int number;//数据个数
private static final int volume = 10;//容量
private int sum = volume;//数组容量

1.3 顺序表的构造方法

我们在学习 JavaSE 的时候有学习到构造方法，构造方法在实例化一个对象的时候会自动执行且只会在这个对象中只执行一次，当我们实例化一个顺序表的时候就需要给它开辟空间，那我们就可以利用构造方法来给它开辟空间，在实例化对象的时候直接给它开辟一个 volume 大小的空间，后序空间不够的时候在用成员方法进行扩容，所以上述成员变量记录数组容量的我们定义时直接给它赋值为了 volume

//构造方法第一次初始化数组容量
public MyArrayList() {
    this.arr = new int[volume];
}

1.4 顺序表的成员方法

1.4.1 扩容

number 是记录数据的个数，sum 是记录数组大小，如果number >= sum 说明数组已经存不下数据了，那么就需要给数组进行增加容量，然后将 sum 设置为当前数组扩容的空间大小

//扩容
public void JudgeNull() {
    if (number >= sum) {
        arr = Arrays.copyOf(arr,volume * 2);
    }
    sum *= 2;
}

1.4.2 打印顺序表

打印顺序表只需要将数组遍历到 number-1，因为数组下标从0开始，数组中只存放了 number 个数据

// 打印顺序表
public void display() {
    for (int i = 0; i < number; i++) {
        System.out.print(arr[i]+" ");
    }
    System.out.println();
}

1.4.3 尾插

在数组中最后一个元素后面一个位置进行新增，首先在新增对象之前判断是否需要增容，然后在将 data 数据存储在数组中最后一个元素后面一个位置，然后number++

// 新增元素,默认在数组最后新增
public void add(int data) {
    JudgeNull();
    arr[number] = data;
    number++;
}

1.4.4 在指定位置插入

在指定位置进行插入对象，首先在新增对象之前判断是否需要增容，然后在判断位置是否合法，如果位置小于数据的个数且合法那么就将pos位置及后面位置整体向后移动，然后将data放在pos位置，然后number++，如果pos等于数据个数那么就等于尾插，否则就位置不合法

// 在 pos 位置新增元素
public void add(int pos, int data) throws AddException{
    JudgeNull();
    if (pos < number && pos >= 0) {
        for (int i = number; i >= pos ; i--) {
            arr[i] = arr[i - 1];
        }
        arr[pos] = data;
        number++;
    } else if (pos == number) {
        add(data);
    } else {
        throw new AddException("插入位置不合法");
    }
}

1.4.5 判断数组中是否有这个元素

将数组遍历到 number-1 位置，如果里面有 toFind 这个元素就返回 true，如果遍历完还没有就直接返回 false

// 判定是否包含某个元素
public boolean contains(int toFind) {
    for (int i = 0; i < number; i++) {
        if (arr[i] == toFind) {
            return true;
        }
    }
    return false;
}

1.4.6 返回指定元素的下标

将数组遍历到 number-1 位置，如果里面有 toFind 这个元素就返回当前位置下标 i，如果遍历完还没有就直接返回 -1

// 查找某个元素对应的位置
public int indexOf(int toFind) {
    for (int i = 0; i < number; i++) {
        if (arr[i] == toFind) {
            return i;
        }
    }
    return -1;
}

1.4.7 获取指定位置存储的元素

首先判断这个位置是否已经存储了元素，如果指定位置小于数据个数，且位置 >=0 就返回当前位置的元素，否则返回 -1

// 获取 pos 位置的元素
public int get(int pos) {
    if (pos < number && pos >= 0) {
        return arr[pos];
    } else {
        return -1;
    }
}

1.4.8 给指定位置元素设置为指定值

判断位置是否合法，如果位置小于数据的个数且合法那么就将pos位置设置为 value 值，如果pos等于数据个数那么就等于尾插，否则就位置不合法

// 给 pos 位置的元素设为 value
public void set(int pos, int value)throws AddException {
    if (pos < number && pos >= 0) {
        arr[pos] = value;
    } else if (pos == number) {
        add(value);
    } else {
        throw new AddException("设置的位置不合法");
    }
}

1.4.9 删除第一次出现的指定元素

首先将数组遍历到 number-1 位置，在遍历过程中如果找到指定元素就将这个位置后面所以的元素前移一位，就删掉了这个元素然后number--，否则里面就没有这个元素就不需要删除

//删除第一次出现的关键字key
public void remove(int toRemove) {
    for (int i = 0; i < number; i++) {
        if (arr[i] == toRemove){
            for (int j = i; j < number; j++) {
                arr[j] = arr[j+1];
            }
            number--;
            return;
        }
    }
}

1.4.10 获取顺序表中存储数据的个数

number成员变量就是用来存储当前数组中元素个数的，直接返回number即可

// 获取顺序表中存储的元素个数
public int size() {
    return number;
}

1.4.11 清空顺序表

将数组遍历到 number - 1位置，在遍历过程中将每个位置中的元素都设置为 0，遍历完后将number 设置为 0

// 清空顺序表
public void clear() {
    for (int i = 0; i < number; i++) {
        arr[i] = 0;
    }
    number = 0;
}

2.浅谈Java中ArrayList类

我们按住 ctrl 键点击 ArrayList 即可来到 ArrayList 类中

2.1 ArrayList类的定义

ArrayList是一个泛型类，它继承了AbstractList 这个抽象泛型类

ArrayList实现了 List 泛型接口

ArrayList实现了RandomAccess接口表明ArrayList支持随机访问

ArrayList实现了Cloneable接口，表明ArrayList是可以clone的

ArrayList实现了Serializable接口，表明ArrayList是支持序列化的

为.png

ArrayList 和 Vector 不同，ArrayList 不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector 或者 CopyOnWriteArrayList

ArrayList 底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

2.1 ArrayList的成员属性

我.png

elementData：用来保存ArrayList数据的数组，这个数组会不断改变，前面没有 final 修饰表示地址值会发生变化

2.2 ArrayList的构造方法

2.2.1 无参构造方法

使用无参构造方法将 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 这个空数组赋值给 elementData 这个数组，无参构造方法不会开辟空间。而是在第一次使用 add 方法的时候开辟 DEFAULT_CAPACITY 大小的空间

却.png

2.2.2 有参构造方法

1.指定顺序表的初始容量

前.png

2.利用其他 Collection 构建 ArrayList

请.png

2.3 ArrayList的方法

方法	解释
boolean add(E e)	尾插 e
void add(int index, E element)	将 e 插入到 index 位置
boolean addAll(Collection c)	尾插 c 中的元素

E remove(int index)	删除 index 位置元素
boolean remove(Object o)	删除遇到的第一个 o
E get(int index)	获取下标 index 位置元素

E set(int index, E element)	将下标 index 位置元素设置为 element
void clear()	清空
boolean contains(Object o)	判断 o 是否在线性表中

int indexOf(Object o)	返回第一个 o 所在下标
int lastIndexOf(Object o)	返回最后一个 o 的下标
List subList(int fromIndex, int toIndex)	截取部分 list

如果有人想看这些方法的实现过程可以去IDEA中查看

2.3 ArrayList的遍历

public static void main(String[] args) {
    ArrayList<Integer> arrayList = new ArrayList<>();
    arrayList.add(1);
    arrayList.add(2);
    arrayList.add(3);
    arrayList.add(4);
    arrayList.add(5);
    arrayList.add(6);
    arrayList.add(7);
}

如何将上面的 arrayList 对象进行遍历呢？

2.3.1 for循环+下标法

for (int i = 0; i < arrayList.size(); i++) {
    System.out.println(arrayList.get(i));
}

2.3.2 foreach法

for (int x:arrayList) {
    System.out.println(x);
}

2.3.3 迭代器法

Iterator<Integer> it = arrayList.listIterator();
while(it.hasNext()){
    System.out.println(it.next());
}

【数据结构】顺序表