数据结构

ArrayList与线性表

线性表

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

顺序表

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

接口的实现 

 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

package MyAList;

/**
 * 定义一个自定义的数组列表接口 IMyArrayList，该接口规定了一系列操作数组列表的方法。
 * 实现此接口的类需要提供这些方法的具体实现，以完成对数组列表的基本操作。
 */
public interface IMyArrayList {
    /**
     * 向数组列表的末尾添加一个整数元素。
     * 
     * @param data 要添加的整数元素
     */
    void add(int data);

    /**
     * 检查数组列表是否为空。
     * 
     * @return 如果数组列表为空返回 true，否则返回 false
     */
    boolean isEmpty();

    /**
     * 为数组列表扩容，当数组列表容量不足时调用此方法。
     */
    void newCapacity();

    /**
     * 检查指定位置是否合法，如果不合法则抛出 inputErrorException 异常。
     * 
     * @param pos 要检查的位置
     * @throws inputErrorException 当指定位置不合法时抛出此异常
     */
    void checkPos(int pos) throws inputErrorException;

    /**
     * 在数组列表的指定位置插入一个整数元素。
     * 
     * @param pos 要插入元素的位置
     * @param data 要插入的整数元素
     */
    void add(int pos, int data);

    /**
     * 检查数组列表中是否包含指定的整数元素。
     * 
     * @param toFind 要查找的整数元素
     * @return 如果包含指定元素返回 true，否则返回 false
     */
    boolean contains(int toFind);

    /**
     * 查找指定整数元素在数组列表中第一次出现的索引位置。
     * 
     * @param toFind 要查找的整数元素
     * @return 如果找到返回元素的索引位置，未找到则返回 -1
     */
    int indexOf(int toFind);

    /**
     * 获取数组列表中指定位置的元素。
     * 
     * @param pos 要获取元素的位置
     * @return 指定位置的整数元素
     */
    int get(int pos);

    /**
     * 将数组列表中指定位置的元素替换为新的值。
     * 
     * @param pos 要替换元素的位置
     * @param value 新的整数值
     */
    void set(int pos, int value);

    /**
     * 从数组列表中移除指定的整数元素。
     * 
     * @param toRemove 要移除的整数元素
     */
    void remove(int toRemove);

    /**
     * 获取数组列表中当前元素的数量。
     * 
     * @return 数组列表中元素的数量
     */
    int size();

    /**
     * 清空数组列表中的所有元素。
     */
    void clear();

    /**
     * 显示数组列表中的所有元素。
     */
    void 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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179

package MyAList;

public class inputErrorException extends RuntimeException{
    inputErrorException(){
        super();
    }
    inputErrorException(String msg){
        super(msg);
    }
}



package MyAList;

import java.util.Arrays;

public class MyArrayList implements IMyArrayList {
    private int[] array;
    private int useSize;

    public MyArrayList() {
        this.array = new int[10];
        this.useSize = 0;
    }

    // 尾插法添加元素
    @Override
    public void add(int data) {
        // 检查是否需要扩容（数组满了就扩容）
        if (useSize == array.length) {
            newCapacity();
        }
        array[useSize] = data;
        useSize++;
    }

    // 判断集合是否为空（元素数量为0则为空）
    @Override
    public boolean isEmpty() {
        return useSize == 0;
    }

    // 扩容方法（扩大为原来的2倍）
    @Override
    public void newCapacity() {
        this.array = Arrays.copyOf(this.array, this.array.length * 2);
    }

    // 检查索引位置合法性
    @Override
    public void checkPos(int pos) throws inputErrorException {
        // 添加操作允许pos等于useSize（尾插），其他操作不允许
        if (pos < 0 || pos > useSize) {
            throw new inputErrorException("pos位置错误,pos的范围为[0," + useSize + "]");
        }
    }

    // 在指定位置插入元素
    @Override
    public void add(int pos, int data) {
        try {
            checkPos(pos);
            // 检查是否需要扩容
            if (useSize == array.length) {
                newCapacity();
            }
            // 元素后移
            for (int i = useSize; i > pos; i--) {
                array[i] = array[i - 1];
            }
            array[pos] = data;
            useSize++;
        } catch (inputErrorException e) {
            e.printStackTrace();
        }
    }

    // 判断是否包含指定元素
    @Override
    public boolean contains(int toFind) {
        for (int i = 0; i < useSize; i++) {
            if (array[i] == toFind) {
                return true;
            }
        }
        return false;
    }

    // 查找元素首次出现的索引
    @Override
    public int indexOf(int toFind) {
        for (int i = 0; i < useSize; i++) {
            if (array[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

    // 获取指定位置的元素
    @Override
    public int get(int pos) {
        try {
            // 获取元素时pos不能等于useSize（最大索引为useSize-1）
            if (pos >= useSize) {
                throw new inputErrorException("get操作: pos位置错误,pos的范围为[0," + (useSize - 1) + "]");
            }
            checkPos(pos);
            return array[pos];
        } catch (inputErrorException e) {
            System.out.println(e.getMessage());
            e.printStackTrace();
        }
        return 0;
    }

    @Override
    public String toString() {
        return "MyArrayList{" +
                "array=" + Arrays.toString(array) +
                '}';
    }

    // 修改指定位置的元素
    @Override
    public void set(int pos, int value) {
        try {
            checkPos(pos);
            // 设置元素时pos不能等于useSize
            if (pos == useSize) {
                throw new inputErrorException("set操作: pos位置错误,pos的范围为[0," + (useSize - 1) + "]");
            }
            array[pos] = value;
        } catch (inputErrorException e) {
            e.printStackTrace();
        }
    }

    // 删除指定位置的元素
    @Override
    public void remove(int pos) {
        try {
            checkPos(pos);
            // 删除元素时pos不能等于useSize
            if (pos == useSize) {
                throw new inputErrorException("remove操作: pos位置错误,pos的范围为[0," + (useSize - 1) + "]");
            }
            // 元素前移
            for (int i = pos; i < useSize - 1; i++) {
                array[i] = array[i + 1];
            }
            useSize--;
        } catch (inputErrorException e) {
            e.printStackTrace();
        }
    }

    // 返回有效元素的数量
    @Override
    public int size() {
        return useSize;
    }

    // 清空集合（保留容量，只重置有效元素数量）
    @Override
    public void clear() {
        useSize = 0;
    }

    // 打印所有有效元素
    @Override
    public void display() {
        for (int i = 0; i < useSize; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println(); // 换行
    }
}

ArrayList简介

在集合框架中，ArrayList是一个普通的类，实现了List接口

【说明】

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

ArrayList使用

ArrayList的构造

方法 解释
ArrayList() 无参构造
ArrayList(Collection<? extends E> c) 利用其他 Collection 构建 ArrayList
ArrayList(int initialCapacity) 指定顺序表初始容量 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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<Integer>已经限定了，list2中只能存储整形元素
// list3构造好之后，与list中的元素一致
ArrayList<Integer> list3 = new ArrayList<>(list2);
// 避免省略类型，否则：任意类型的元素都可以存放，使用时将是一场灾难
List list4 = new ArrayList();
list4.add("111");
list4.add(100);
}

ArrayList常见操作

ArrayList虽然提供的方法比较多，但是常用方法如下所示

方法 解释
boolean add(E e) 尾插 e
void add(int index, E element) 将 e 插入到 index 位置
boolean addAll(Collection<? extends E> 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

ArrayList的遍历

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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. ArrayList最长使用的遍历方式是：for循环+下标 以及 foreach
  2. 迭代器是设计模式的一种，后序容器接触多了再给大家铺垫

ArrayList的扩容机制

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

 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

Object[] elementData; // 存放元素的空间
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 默认空间
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. 检测是否真正需要扩容，如果是调用grow准备扩容
  2. 预估需要库容的大小 初步预估按照1.5倍大小扩容 如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容 真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
  3. 使用copyOf进行扩容
© 2025 一夕夙愿
微信：zxcyuijkl
使用 Hugo 构建
主题 Stack 由 Jimmy 设计