java数据结构集合复习之ArrayList与顺序表

前言: 这是我最一年学习java的一部分的回顾总结

1.List

1.1什么是List?

在框架集合中,List是一个接口,继承自Collection。

Collection也是一个接口，该接口中规范了后序容器中常用的一些方法，具体如下所示

站在数据结构的角度来看，List就是一个线性表，即n个具有相同类型元素的有限序列，在该序列上可以执行增删改查以及变量等操作。

1.2 List的使用

List是个接口，并不能直接用来实例化
如果要使用，必须去实例化List的实现类

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ListExample {
    public static void main(String[] args) {
        // 使用 ArrayList 实现类
        List<String> arrayList = new ArrayList<>();
        arrayList.add("Apple");
        arrayList.add("Banana");
        arrayList.add("Orange");

        System.out.println("ArrayList: " + arrayList);

        // 使用 LinkedList 实现类
        List<String> linkedList = new LinkedList<>();
        linkedList.add("Mango");
        linkedList.add("Kiwi");
        linkedList.add("Grape");

        System.out.println("LinkedList: " + linkedList);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

List 不能直接实例化是因为接口本身只是一种规范或契约，它定义了一组方法的签名，但并没有提供这些方法的具体实现。
接口的主要目的是为了实现多态性和代码的解耦。通过定义接口，不同的类可以实现相同的接口，从而以统一的方式进行处理。 打个比方，想象 List
接口是一个菜谱，它只规定了要有哪些菜（方法），但没有告诉你具体怎么做这些菜（方法的实现）。只有具体的厨师（实现类），比如 ArrayList
或者 LinkedList ，才能按照这个菜谱做出实际的菜肴（实现方法）。

ArrayList与顺序表

2.1 线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

2.2 顺序表

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

下面是手动实现一个顺序表的实现

package com;

import java.util.Arrays;

public class SeqList {
    private int[] array;
    //记录当前顺序表当中 有多少个有效的数据
    private int size;
    private static final int INIT_CAPACITY = 5;
    // 默认构造方法 将顺序表的底层容量设置为INIT_CAPACITY
    public SeqList(){
        this.array = new int[INIT_CAPACITY];
    }
    //判断当前顺序表是否满了 注意在进行新增操作是都要考虑数组是否需要判断满表
    public boolean isFull(){
        //返回当前表中的元素个数与当前表的长度作比较若相等是ture,反之false
        return size == array.length;
    }
    //给数组扩容 注意在进行新增操作是都要考虑数组是否需要扩容
    private void resize(){
        array = Arrays.copyOf(array,2*array.length);
    }
    // 新增元素,默认在数组最后新增
    public void add(int data){

        if (isFull()){
            resize();
        }
        this.array[size] = data;
        //将当前指针位置＋1,每次新增操作都需要
        size++;
    }
    // 在 pos 位置新增元素
    public void add(int pos,int data){
        //判断pos位置合不合法
        if (pos<0 || pos>this.size){
            throw new PosOutBoundsException("add 元素的时候，pos位置不合法！");
        }
        if(isFull()){
            resize();
        }
        for (int i = size-1; i >= pos; i--) {
            array[i+1] = array[i];
        }
        array[pos] = data;
        size++;
    }
    // 判定是否包含某个元素
    public boolean contains(int toFind) {
        for (int i = 0; i <this.size; i++) {
            if(array[i] == toFind){
                return true;
            }
        }
        return false;
    }
    // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        for (int i = 0; i < this.size; i++) {
            if (array[i] == toFind){
                return i;
            }
        }
        return -1;
    }
    // 获取 pos 位置的元素
    public int get(int pos) {
        if (pos<0 || pos>this.size){
            throw new PosOutBoundsException("pos位置不合法！");
            
        }
        return array[pos];

    }
    // 给 pos 位置的元素设为 value
    public void set(int pos, int value) {
        if (pos<0 || pos>this.size){
            throw new PosOutBoundsException("pos位置不合法！");
        }
        this.array[pos] = value;

    }
    //删除第一次出现的关键字key
    public void remove(int toRemove) {
        if (isEmpty()){
            return;
        }
        int index = indexOf(toRemove);
        if (index == -1){
            System.out.println("没有你要删除的数据");
        }
        for (int i = index; i < this.size-1; i++) {
            this.array[i] = this.array[i+1];
        }
        size--;
    }
    // 获取顺序表长度
    public int size() {
        return size;
    }
    // 清空顺序表
    public void clear() {
       size=0;
    }
    // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
    public void display() {
        for (int i = 0; i < this.size; i++) {
            System.out.println(this.array[i]+ " ");
        }
    }
    public boolean isEmpty(){
        return this.size == 0;
    }
    public static void main(String[] args) {
        SeqList seqList = new SeqList();
        seqList.add(1);
        seqList.add(2);
        seqList.add(3);
        seqList.add(4);
        seqList.add(1,10000);
        seqList.display();
    }
}
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

2.3 ArrayList的遍历

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

public static void main(String[] args) {
        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 integer : list) {
            System.out.print(integer + " ");
        }
        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
23

注意:

1. ArrayList最常使用的遍历方式是：for循环+下标 以及 foreach
2. 迭代器是设计模式的一种

2.4ArrayList的扩容机制

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

private static final int DEFAULT_CAPACITY = 10;// 默认容量大小
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};// 默认空间
transient Object[] elementData; 存放元素的空间

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
45
46
47
48
49

总结:

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

2.5 ArrayList的小练习

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
杨辉三角
解法:

 public List<List<Integer>> generate(int numRows) {
         List<List<Integer>> allList = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> list = new ArrayList<>();
            list.add(1);
            for (int j = 1; j < i; j++) {
               list.add(allList.get(i-1).get(j-1)+allList.get(i-1).get(j));
            }
            if(i != 0){
                list.add(1);
            }
            allList.add(list);
        }
        return allList;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.6ArrayList的问题及思考

问题:

1. ArrayList底层使用连续的空间，任意位置插入或删除元素时，需要将该位置后序元素整体往前或者往后搬移，故时间复杂度为O(N)
2. 增容需要申请新空间,拷贝数据释放旧空间,会有不小的消耗
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考:
如何解决以上问题呢？

1. 对于频繁的插入或删除元素 我们可以适合的数据结构,例如LinkedList。LinkedList底层使用链表实现，在链表中间进行插入和删除操作的时间复杂度为 O(1)，但它在随机访问元素时的性能相对较差。

2. 针对增容带来消耗的问题：
   如能预先估计集合可能需要存储的元素数量，在创建ArrayList时指定合适的初始容量，可以减少扩容的次数。或者采用内存池技术：创建一个内存池来管理内存分配和释放。当需要扩容时，从内存池中获取预先分配好的合适大小的内存块，而不是每次都进行新的内存申请和释放操作。

3. 关于增容导致的空间浪费问题：
   一种解决思路是使用自定义的动态数组实现，根据实际元素数量更精确地控制扩容策略，而非简单地按照固定倍数扩容。例如，可以根据当前元素数量和一个预设的负载因子来决定是否扩容以及扩容的幅度。但这种方式需要自己实现动态数组的相关逻辑，增加了编程的复杂性