【数据结构与算法】ArrayList与顺序表

✨个人主页：bit me
✨当前专栏：数据结构
✨每日一语：上海就是商海，北京就是背景，誓言就是失言，彩礼就是财力，理想就是离乡，而平民就要拼命

 

💦一.线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

顺序表：

链表：

 

💞二.顺序表

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

顺序表底层是一个数组，为什么不直接操作数组就好了，还需要单独写个类？

例如我们在数组中放置一部分元素

问在这个数组里面，有几个有效数据？

肯定有人会说3个，在Java里数组没有元素默认为0，判断的时候遇到0就停止，然后总数就是元素个数，那如果这三个元素中加了一个0呢？我们又该如何去判断呢？

这里正确的做法是用计数器，先创建一个对象，我们定义一个usedSize来记录有效的数据个数，然后添加一些方法，最后进行增删查改（CURD）。

💕2.1 接口的实现

在数组中是否可以隔着空的数组位插入元素？答案是不可以，在数据结构当中，每次储存元素的时候，一定要有一个前驱信息的，可以在两个元素中间插入

例如我们写的顺序表的相关操作：
我们还需要对他们进行完善和改进
步骤：

1. 定义一个类：

public class MyArraylist {
    public int[] elem;
    public int usedSize;//0
    private static final int DEFAULT_SIZE = 4;//定义数组长度的

    public MyArraylist(){
        this.elem = new int[DEFAULT_SIZE];
    }
    ...
    ...
}
1
2
3
4
5
6
7
8
9
10
11

成员变量包含数组，数组里的元素个数，数组长度(可以使用final修饰让数据不被改变)

2. 顺序表的打印：

 public void display() {
    //usedSize = 0
    for (int i = 0; i < this.usedSize; i++) {
        System.out.print(this.elem[i]+" ");
    }
    System.out.println();
}
1
2
3
4
5
6
7

用循环把每个元素都遍历一次，中间用空格分开

3. 新增元素：

// 新增元素,默认在数组最后新增
public void add(int data) {
    //1.判断是否是满的，如果满的，那么进行扩容
    if(isFull()){
        //扩容2倍
        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

默认在数组最后新增

①需要判断数组是否是满的，满的就需要扩容，
②不满的话就进行元素插入，判断数组满不满状态的函数实现

isFull判断函数实现：

//判断当前数组是不是满的  true:满   false：空
public boolean isFull(){
    if(this.usedSize == this.elem.length){
        return true;
    }
    return false;
    //在这里可以直接优化为一行代码
    //return this.usedSize == this.elem.length;
}
1
2
3
4
5
6
7
8
9

4. 在pos位置新增元素：

// 在 pos 位置新增元素
public void add(int pos, int data) {
    //1.判断pos位置合法性
    if(!checkPosInAdd(pos)){
        throw new MyArraylistIndexOutofException("添加方法的Pos不合理！");
    }

    //2.判断是否是满的，如果满的，那么进行扩容
    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

①先判断pos位置合法性，既不能是负数，又必须要有前驱信息的支持
②判断组数元素是否满了，继续调用isFull()函数
③我们插入数据的时候，需要先把插入元素后面的元素都往后挪一位，挪数据实现
从数组的最后一个元素开始往后挪，一次挪到当pos位置空出，没有元素的时候即可
④挪完数据之后，我们把pos位置赋值为data，并且把数组大小扩容一位，方便再进行新增元素

判断pos位置合法性函数checkPosInAdd实现：

private boolean checkPosInAdd(int pos){
    //1.判断pos位置合法性
    if(pos < 0 || pos > this.usedSize){
        System.out.println("pos位置不合法");
        return false;
    }
    return true;//合法
}
1
2
3
4
5
6
7
8

5. 判定是否包含了某个元素

public boolean contains(int toFind) {
    for (int i = 0; i < this.usedSize; i++) {
        if(this.elem[i] == toFind){
            return true;
        }
    }
    return false;
}
1
2
3
4
5
6
7
8

6. 查找某个元素对应的位置

// 查找某个元素对应的位置
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
9

7. 获取pos下标的元素

// 获取 pos 位置的元素
public int get(int pos) {
    if(!checkPosInGet(pos)){
        throw new MyArraylistIndexOutofException("获取pos下标时，位置不合法！");
    }
    //判断是否为空(可有可无)
    if(isEmpty()){
        throw new MyArrayListEmptyException("获取元素的时候，顺序表为空！");
    }
    return this.elem[pos];
}
1
2
3
4
5
6
7
8
9
10
11

①先判断pos位置合法性
②判断数组是否为空（可有可无）

判断pos位置合法性函数checkPosInGet实现：

private boolean checkPosInGet(int pos){
    //1.判断pos位置合法性
    if(pos < 0 || pos >= this.usedSize){
        System.out.println("pos位置不合法");
        return false;
    }
    return true;//合法
}
1
2
3
4
5
6
7
8

判断数组是否为空isEmpty函数实现：

private boolean isEmpty(){
    return this.usedSize == 0;
}
1
2
3

8. 给pos位置的元素替换成value

①先要进行合法性判断再替换

// 给 pos 位置的元素设为 value
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
12

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

//删除第一次出现的关键字key
//判断条件：1.顺序表不为空   2.顺序表当中有我们要删除的元素  3.找到它的下标  4.把i+1的值赋给i，i还要小于usedSize-1
public void remove(int key) {
    if(isEmpty()){
        throw new MyArrayListEmptyException("顺序表为空，不能删除！");
    }
    int index = indexOf(key);
    if(index == -1){
        System.out.println("不存在你要找的数据！");
        return;
    }
    for (int i = index; i < this.usedSize-1; i++) {
        this.elem[i] = this.elem[i+1];
    }
    //删除完成
    this.usedSize--;
    this.elem[usedSize] = 0;//此处不能置为null是因为elem是int类型 如果是引用类型则置为null
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

①顺序表不为空
②顺序表当中有我们要删除的元素
③找到它的下标
④把i+1的值赋给i，i还要小于usedSize-1
（只要涉及到删除数据，如果是引用数据类型，那么就要把elem[i] = null;否则就会发生内存泄漏）

10. 获取顺序表长度

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

11. 清空顺序表

// 清空顺序表
public void clear() {
    //因为是基本类型，所以置为0即可
    this.usedSize = 0;
    /*当它是引用类型时
    for (int i = 0; i < this.usedSize; i++) {
        this.elem[i] = null;
    }
    this.usedSize = 0;
    */
}
1
2
3
4
5
6
7
8
9
10
11

①基本类型置为0即可，若是引用类型则循环打印置为null，再置为0

注意：
此处可以把elem置为null可以吗？可以，但是很暴力，数组直接被回收了，顺序表只执行了一次就没了，再次使用的时候还需开辟新的数组，相当于我们每次使用的时候还需new一次，很麻烦也没必要

在这里面添加，获取pos下标不合法的时候我们也可以写我们需要的异常类来更好的实现我们需要的异常，实现异常的抛出是我们赋值命名的异常名：

public class MyArrayListEmptyException extends RuntimeException{
    public MyArrayListEmptyException(){

    }

    public MyArrayListEmptyException(String message){
        super(message);
    }
}
1
2
3
4
5
6
7
8
9

public class MyArraylistIndexOutofException extends RuntimeException{
    public MyArraylistIndexOutofException(){

    }

    public MyArraylistIndexOutofException(String message){
        super(message);
    }
}

1
2
3
4
5
6
7
8
9
10

在主函数里对顺序表的操作：

public static void main(String[] args) {
    MyArraylist myArraylist = new MyArraylist();
    myArraylist.add(0,1);//给0下标赋值为1
    myArraylist.add(1,2);
    myArraylist.add(2,3);
    myArraylist.add(3,4);
    myArraylist.add(4,5);
    myArraylist.display();//输出顺序表
    myArraylist.set(4,199);//把下角标为4的元素替换成199
    myArraylist.display();

    System.out.println("=============");
    myArraylist.clear();//清空顺序表
    myArraylist.display();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

 

⚡️三. ArrayList简介

在集合框架中，ArrayList是一个普通的类，实现了List接口，具体框架图如下：

1. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
2. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
3. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
4. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList
5. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

 

🎶四. ArrayList使用

🎵4.1 ArrayList的构造

方法一ArrayList()不带参数的构造方法的使用：

ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);//往数组最后的一个位置存元素
arrayList.add(2);
arrayList.add(3);
arrayList.add(4);
System.out.println(arrayList);//用字符串的形式打印出来所有的元素
System.out.println(arrayList.size());//获取当前有效数据的个数
System.out.println(arrayList.get(1));//获取指定下标的元素
1
2
3
4
5
6
7
8

方法二的使用：

ArrayList<Integer> arrayList2 = new ArrayList<>(arrayList);
arrayList2.add(99);
arrayList2.add(199);
System.out.println(arrayList2);
1
2
3
4

arrayList2承接了arrayList1的数据（使用其他的集合 来构造当前的List，底层源码实现是数组的拷贝）

方法三的使用：

ArrayList<Integer> arrayList3 = new ArrayList<>(15);
1

指定初始化数组容量大小

在源码的实现里：
①：第一次add的时候，我们底层的数组才变成了10，如果只是调用了不带参数的构造方法，默认还是0
②：grow函数就是扩容函数，扩容的方式是1.5倍的扩容

例如整体的举例使用：

public static void main(String[] args) {
	// ArrayList创建，推荐写法
	// 构造一个空的列表
	List<Integer> list1 = new ArrayList<>();
	// 构造一个具有10个容量的列表
	List<Integer> list2 = new ArrayList<>(10);
	list2.add(1);
	list2.add(2);
	list2.add(3);
	// list2.add("hello"); // 编译失败，List已经限定了，list2中只能存储整形元素
	// list3构造好之后，与list中的元素一致
	ArrayList<Integer> list3 = new ArrayList<>(list2);
	// 避免省略类型，否则：任意类型的元素都可以存放，使用时将是一场灾难
	List list4 = new ArrayList();
	list4.add("111");
	list4.add(100);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

🎵4.2 ArrayList常见操作

在这里面我们不解释过多的方法，许多都是和原来的方法一样，直接套用换参数就可以

①第二个add方法：

ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(0,1);
arrayList.add(1,2);
arrayList.add(2,99);
System.out.println(arrayList);
1
2
3
4
5

需要注意的是：在我们实现元素插入赋值的时候，不能隔着空的元素插入，否则就报错了，而且结果打印的顺序也是随机的

②第三个addAll方法：

ArrayList<Integer> arrayList2 = new ArrayList<>();
arrayList2.addAll(arrayList);
arrayList2.add(19);

System.out.println(arrayList2);
1
2
3
4
5

arrayList2把arrayList的元素都拿过来了，在最后添加一个元素19

③第四个remove方法：

arrayList.remove(0);//删除下标的元素
System.out.println(arrayList);
int index = arrayList.lastIndexOf(new Integer(99));//直接删除选定的元素
System.out.println(arrayList);
1
2
3
4

这里面又分为按照下标来删除和按照元素来删除，如上代码演示

④第十一个lastIndexOf方法：

int index = arrayList.lastIndexOf(new Integer(99));
System.out.println(index);
1
2

查找元素下标

⑤最后一个subList方法

ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(0,1);
arrayList.add(1,2);
arrayList.add(2,99);
arrayList.add(3,199);
arrayList.add(4,299);
System.out.println(arrayList);

List<Integer> list = arrayList.subList(1,3);//区间左闭右开
System.out.println(list);
1
2
3
4
5
6
7
8
9
10

相当于字符串的截取，区间左闭右开
这里面我们如果把list里面的数值改变了，是否会影响原来的arraylist数组呢？

System.out.println("===================");
list.set(0,999999999);
System.out.println(list);
System.out.println("原来的list" + arrayList);
1
2
3
4

当我们改变list里的元素时，arraylist里的元素也被改变了
在这里也可以说明截取函数，是在本身函数上进行截取的

🎵4.3 ArrayList的遍历

ArrayList 可以使用三方方式遍历：for循环+下标、foreach、使用迭代器

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
// 使用下标+for遍历
for (int i = 0; i < list.size(); i++) {
    System.out.print(list.get(i) + " ");
}
System.out.println();
// 借助foreach遍历
for (Integer x : list) {
    System.out.print(x + " ");
}
System.out.println();
//使用迭代器
Iterator<Integer> it = list.listIterator();
while(it.hasNext()){
    System.out.print(it.next() + " ");
}
System.out.println();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

🎵4.4 ArrayList的扩容机制（源码实现）

ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容：以下是ArrayList源码中扩容方式

Object[] elementData; // 存放元素的空间
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 默认空间为0
private static final int DEFAULT_CAPACITY = 10; // 默认容量大小
public boolean add(E e) {
	ensureCapacityInternal(size + 1); // Increments modCount!!
	elementData[size++] = e;
	return true;
}
private void ensureCapacityInternal(int minCapacity) {
	ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
	if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
	return Math.max(DEFAULT_CAPACITY, minCapacity);
	}
	return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
	modCount++;
	// overflow-conscious code
	if (minCapacity - elementData.length > 0)
	grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
	// 获取旧空间大小
	int oldCapacity = elementData.length;
	// 预计按照1.5倍方式扩容
	int newCapacity = oldCapacity + (oldCapacity >> 1);
	// 如果用户需要扩容大小 超过 原空间1.5倍，按照用户所需大小扩容
	if (newCapacity - minCapacity < 0)
	newCapacity = minCapacity;
	// 如果需要扩容大小超过MAX_ARRAY_SIZE，重新计算容量大小
	if (newCapacity - MAX_ARRAY_SIZE > 0)
	newCapacity = hugeCapacity(minCapacity);
	// 调用copyOf扩容
	elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
	// 如果minCapacity小于0，抛出OutOfMemoryError异常
	if (minCapacity < 0)
	throw new OutOfMemoryError();
	return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

总结：

1. 检测是否真正需要扩容，如果是调用grow准备扩容
2. 预估需要库容的大小
   ①初步预估按照1.5倍大小扩容
   ②如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
   ③真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
3. 使用copyOf进行扩容

 

💤五. 顺序表的一般用途及优缺点：

1. 用途及优点：一般来说，顺序表使用在频繁查找数据，给定下标，可以快速查找O(1)，会使用它，如果你的数据需要频繁的进行插入或者删除，那么就不适合使用顺序表

2. 缺点：
   ① 顺序表中间/头部的插入删除，时间复杂度为O(N)
   ②增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
   ③增容一般是呈1.5倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到150，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了45个数据空间。