Java_ArrayList与顺序表复习笔记

ArrayList 与顺序表复习笔记

1. 学习目标

掌握线性表、顺序表、ArrayList 的基本概念、常见操作、遍历方式、扩容机制，以及 ArrayList 在实际案例中的使用。

2. 线性表

2.1 概念

线性表是由n个具有相同特性的数据元素组成的有限序列。

常见线性表包括：

• 顺序表
• 链表
• 栈
• 队列

2.2 逻辑结构与物理结构

线性表在逻辑上是线性结构，即元素之间呈现一条连续的线性关系。

但线性表在物理存储上不一定连续，常见的物理存储方式有两种：

1. 数组存储：物理地址连续。
2. 链式存储：物理地址不一定连续，通过引用或指针连接元素。

3. 顺序表

3.1 概念

顺序表是使用一段物理地址连续的存储单元，依次存储数据元素的线性结构。

一般情况下，顺序表底层使用数组实现，并在数组上完成增、删、查、改等操作。

3.2 顺序表的核心特点

1. 底层空间连续。
2. 支持通过下标随机访问。
3. 插入和删除可能需要搬移元素。
4. 容量不够时需要扩容。

3.3 顺序表基本结构

publicclassSeqList{privateint[]array;privateintsize;// 默认构造方法SeqList(){}// 将顺序表的底层容量设置为 initcapacitySeqList(intinitcapacity){}}

其中：

• array：底层数组，用于存储元素。
• size：当前顺序表中的有效元素个数。

3.4 顺序表常见接口

// 新增元素，默认在数组最后新增publicvoidadd(intdata){}// 在 pos 位置新增元素publicvoidadd(intpos,intdata){}// 判断是否包含某个元素publicbooleancontains(inttoFind){returntrue;}// 查找某个元素对应的位置publicintindexOf(inttoFind){return-1;}// 获取 pos 位置的元素publicintget(intpos){return-1;}// 将 pos 位置的元素设置为 valuepublicvoidset(intpos,intvalue){}// 删除第一次出现的关键字 keypublicvoidremove(inttoRemove){}// 获取顺序表长度publicintsize(){return0;}// 清空顺序表publicvoidclear(){}// 打印顺序表，通常用于测试publicvoiddisplay(){}

3.5 顺序表插入与删除的代价

插入元素

在指定位置插入元素时，需要将该位置及其后面的元素整体向后移动一位。

时间复杂度：O(N)

删除元素

删除指定位置元素时，需要将该位置后面的元素整体向前移动一位。

时间复杂度：O(N)

4. ArrayList 简介

4.1 ArrayList 的本质

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

它的底层是一段连续空间，支持动态扩容，本质上是一个动态类型的顺序表。

4.2 ArrayList 的主要特点

1. 使用泛型实现，使用前通常需要实例化并指定元素类型。
2. 实现了RandomAccess接口，支持随机访问。
3. 实现了Cloneable接口，支持克隆。
4. 实现了Serializable接口，支持序列化。
5. 底层使用数组存储元素。
6. 支持自动扩容。
7. 不是线程安全的。

4.3 线程安全问题

ArrayList适合在单线程环境中使用。

多线程环境中可以考虑：

• Vector
• CopyOnWriteArrayList

5. ArrayList 的构造方法

5.1 推荐写法

List<Integer>list1=newArrayList<>();

推荐使用接口接收实现类对象，便于后续替换实现。

5.2 指定初始容量

List<Integer>list2=newArrayList<>(10);

当可以预估元素数量时，可以指定初始容量，减少扩容次数。

5.3 使用已有集合构造

ArrayList<Integer>list3=newArrayList<>(list2);

构造完成后，list3中的元素与list2中的元素一致。

5.4 避免使用原生类型

不推荐这样写：

Listlist4=newArrayList();list4.add("111");list4.add(100);

原因：省略泛型后，集合中可以存放任意类型元素，后续使用时容易出现类型转换问题。

推荐这样写：

List<Integer>list=newArrayList<>();

6. ArrayList 常见操作

6.1 添加元素

List<String>list=newArrayList<>();list.add("JavaSE");list.add("JavaWeb");list.add("JavaEE");

add(E e)默认将元素添加到末尾。

6.2 获取元素个数

System.out.println(list.size());

size()返回集合中有效元素个数。

6.3 获取指定位置元素

System.out.println(list.get(1));

注意：下标范围必须是[0, size)，否则会抛出下标越界异常。

6.4 修改指定位置元素

list.set(1,"JavaWEB");

set会覆盖指定下标位置上的原元素。

6.5 指定位置插入元素

list.add(1,"Java数据结构");

插入后，原来index位置及其后面的元素会统一向后移动。

6.6 删除指定元素

list.remove("JVM");

删除第一次出现的指定元素，删除成功后，其后面的元素会统一向前移动。

6.7 删除指定下标元素

list.remove(list.size()-1);

注意：下标不能超过有效元素范围，否则会抛出下标越界异常。

6.8 判断元素是否存在

if(list.contains("测试课程")){list.add("测试课程");}

contains返回true表示集合中存在指定元素，否则返回false。

6.9 查找元素位置

list.add("JavaSE");System.out.println(list.indexOf("JavaSE"));System.out.println(list.lastIndexOf("JavaSE"));

• indexOf：从前往后查找，返回第一次出现的位置。
• lastIndexOf：从后往前查找，返回最后一次出现的位置。

6.10 截取子列表

List<String>ret=list.subList(0,4);

subList(0, 4)表示截取[0, 4)范围内的元素。

注意：subList返回的子列表与原列表存在关联，修改时要特别小心。

6.11 清空集合

list.clear();System.out.println(list.size());

clear()会清空所有有效元素。

7. ArrayList 的遍历方式

ArrayList常见遍历方式有三种：

1. for循环 + 下标
2. foreach
3. 迭代器

7.1 for 循环 + 下标

for(inti=0;i<list.size();i++){System.out.print(list.get(i)+" ");}

特点：

• 适合需要使用下标的场景。
• ArrayList支持随机访问，因此这种方式很常用。

7.2 foreach 遍历

for(Integerinteger:list){System.out.print(integer+" ");}

特点：

• 写法简洁。
• 适合只读取元素、不关心下标的场景。

7.3 迭代器遍历

Iterator<Integer>it=list.listIterator();while(it.hasNext()){System.out.print(it.next()+" ");}

迭代器是一种设计模式，在 Java 集合框架中被广泛使用。

8. ArrayList 扩容机制

8.1 为什么需要扩容

ArrayList底层使用数组存储元素，数组长度固定。

当元素数量超过当前数组容量时，需要申请更大的新数组，并将旧数组中的元素复制过去。

8.2 默认容量

当使用无参构造创建ArrayList时，底层最初是一个空数组。

第一次添加元素时，默认容量会扩展为10。

privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};privatestaticfinalintDEFAULT_CAPACITY=10;

8.3 添加元素时的扩容流程

publicbooleanadd(Ee){ensureCapacityInternal(size+1);elementData[size++]=e;returntrue;}

添加元素时，核心流程如下：

1. 判断当前容量是否足够。
2. 如果容量足够，直接插入元素。
3. 如果容量不够，调用扩容逻辑。
4. 扩容完成后，将元素放入数组末尾。
5. size加一。

8.4 计算容量

privatestaticintcalculateCapacity(Object[]elementData,intminCapacity){if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){returnMath.max(DEFAULT_CAPACITY,minCapacity);}returnminCapacity;}

如果底层数组还是默认空数组，第一次扩容时容量取DEFAULT_CAPACITY和minCapacity中较大的值。

8.5 触发扩容

privatevoidensureExplicitCapacity(intminCapacity){modCount++;if(minCapacity-elementData.length>0){grow(minCapacity);}}

当minCapacity大于当前数组长度时，调用grow进行扩容。

8.6 扩容大小

intoldCapacity=elementData.length;intnewCapacity=oldCapacity+(oldCapacity>>1);

扩容时，新容量通常是旧容量的1.5倍。

其中：

oldCapacity>>1

表示旧容量除以2。

所以：

newCapacity=oldCapacity+oldCapacity/2;

8.7 特殊情况

如果用户实际需要的容量超过预估的1.5倍容量，则按照实际需要的容量扩容。

if(newCapacity-minCapacity<0){newCapacity=minCapacity;}

如果需要扩容的大小超过最大数组限制，则重新计算容量。

privatestaticfinalintMAX_ARRAY_SIZE=Integer.MAX_VALUE-8;

8.8 真正扩容

elementData=Arrays.copyOf(elementData,newCapacity);

Arrays.copyOf会申请新空间，并将旧数组中的元素复制到新数组中。

8.9 扩容流程总结

1. 插入元素前检查容量是否足够。
2. 容量不够时进入扩容流程。
3. 默认按照旧容量的1.5倍扩容。
4. 如果1.5倍仍然不够，则按实际需求容量扩容。
5. 扩容前检查是否超过最大数组限制。
6. 使用Arrays.copyOf完成新数组申请和数据复制。

9. ArrayList 的问题与思考

9.1 任意位置插入、删除效率低

ArrayList底层使用连续空间。

在任意位置插入或删除元素时，需要整体搬移后续元素。

时间复杂度：O(N)

9.2 扩容有额外开销

扩容过程需要：

1. 申请新空间。
2. 拷贝旧数据。
3. 释放旧空间。

因此，频繁扩容会带来时间和空间上的额外消耗。

9.3 可能造成空间浪费

扩容通常会申请比当前实际需求更大的空间。

例如容量扩到较大后，如果后续只插入少量数据，剩余空间就会被浪费。

9.4 改进方向

针对这些问题，可以考虑使用其他数据结构：

1. 链表：适合频繁插入、删除的场景。
2. LinkedList：Java 集合框架中的链式线性表实现。
3. 合理设置初始容量：减少扩容次数。
4. 根据业务选择数据结构：频繁随机访问优先考虑ArrayList，频繁插入删除可以考虑链表。

10. 重点速记

1. 线性表是具有相同特性的数据元素组成的有限序列。
2. 顺序表底层使用连续空间，一般用数组实现。
3. ArrayList本质是动态顺序表。
4. ArrayList支持随机访问，查询指定下标元素效率高。
5. ArrayList任意位置插入、删除效率较低，时间复杂度为O(N)。
6. ArrayList无参构造时，第一次添加元素会扩容到默认容量10。
7. ArrayList扩容通常按1.5倍增长。
8. ArrayList不是线程安全的。
9. 使用泛型可以限制集合中存储的元素类型，避免类型混乱。
10. subList(fromIndex, toIndex)截取范围是左闭右开区间[fromIndex, toIndex)。

11. 易错点整理

11.1 下标越界

get、set、remove(index)都要求下标合法。

合法范围通常是：

0 <= index < size

插入时add(index, element)的合法范围通常是：

0 <= index <= size

11.2 remove 的重载问题

ArrayList中remove有两个常见重载：

remove(intindex)remove(Objecto)

对于List<Integer>，删除整数元素时容易混淆：

List<Integer>list=newArrayList<>();list.add(1);list.add(2);list.add(3);list.remove(1);// 删除下标为 1 的元素list.remove(Integer.valueOf(1));// 删除元素 1

11.3 subList 不是完全独立的新 ArrayList

subList返回的是原列表的一部分视图，与原列表有关联。

修改原列表或子列表时，要注意可能互相影响。

11.4 泛型不能省略

不推荐使用：

Listlist=newArrayList();

推荐使用：

List<String>list=newArrayList<>();

12. 面试与考试常问问题

12.1 ArrayList 底层是什么？

底层是数组。

12.2 ArrayList 为什么支持随机访问？

因为底层数组空间连续，可以通过下标直接计算元素位置。

12.3 ArrayList 插入和删除为什么慢？

因为在中间位置插入或删除元素时，需要搬移后续元素。

12.4 ArrayList 默认容量是多少？

第一次添加元素时，默认容量为10。

12.5 ArrayList 如何扩容？

容量不足时，通常扩容为旧容量的1.5倍，并通过Arrays.copyOf拷贝数据。

12.6 ArrayList 是否线程安全？

不是线程安全的。

多线程场景可以考虑Vector或CopyOnWriteArrayList。

12.7 ArrayList 和顺序表有什么关系？

ArrayList可以看作 Java 中动态顺序表的一种实现。