1. 线性表
线性表（Linear List）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见线性表：顺序表、链表、栈、队列…
线性表在逻辑上是线性结构，也就是连续的一条直线。但是在物理上不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
2. 顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表的实现
package myDataStructure.ArrayList;
/**
* @Author: Author
* @CreateTime: 2025-03-18
* @Description:
*/
public interface SeqList<T> {
// 新增元素,默认在数组最后新增
void add(T data);
// 在 pos 位置新增元素
void add(int pos, T data);
// 判定是否包含某个元素
boolean contains(T toFind);
// 查找某个元素对应的位置
int indexOf(T toFind);
// 获取 pos 位置的元素
T get(int pos);
// 给 pos 位置的元素设为 value
void set(int pos, T value);
// 删除第一次出现的关键字key
void remove(T toRemove);
// 获取顺序表长度
int size();
// 清空顺序表
void clear();
}
package myDataStructure.ArrayList;
import java.util.Arrays;
/**
* @Author: Author
* @CreateTime: 2025-03-18
* @Description: 支持泛型的动态数组的实现
*/
public class MyArrayList<T> implements SeqList<T>{
private Object[] array; // 内部使用 Object[] 存储数据，因为 Java 的泛型会在运行时擦除类型信息。
private int size;
public MyArrayList(){
array=new Object[10];
}
// 动态扩容
private void checkCapacity(){
if (array.length==size){
array=Arrays.copyOf(array,size*2);
}
}
// 添加操作的边界检查
private void rangeCheckForAdd(int index) {
if (index<0||index>size){
throw new IndexOutOfBoundsException("index超出范围");
}
}
// 读取修改操作的边界检查
private void rangeCheckForGetAndSet(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("index超出范围");
}
}
@Override
public void add(T data) {
checkCapacity();
array[size]=data;
size++;
}
@Override
public void add(int pos, T data) {
checkCapacity();
rangeCheckForAdd(pos);
for(int i=size;i>pos;i--){
array[i]=array[i-1];
}
array[pos]=data;
size++;
}
@Override
public boolean contains(T toFind) {
if (toFind==null){
// 如果 toFind 是null,直接调用 array[i].equals(toFind) 会导致 NullPointerException
for (int i = 0; i < size; i++) {
if (array[i] == null) {
return true;
}
}
}else {
for (int i=0;i<size;i++){
if (array[i].equals(toFind)){
return true;
}
}
}
return false;
}
@Override
public int indexOf(T toFind) {
if (toFind == null) {
for (int i = 0; i < size; i++) {
if (array[i] == null) {
return i;
}
}
} else {
for (int i = 0; i < size; i++) {
if (toFind.equals(array[i])) {
return i;
}
}
}
return -1;
}
@Override
public T get(int pos) {
rangeCheckForGetAndSet(pos);
return (T)array[pos];
}
@Override
public void set(int pos, T value) {
rangeCheckForGetAndSet(pos);
checkCapacity();
array[pos]=value;
}
@Override
public void remove(T toRemove) {
int pos=indexOf(toRemove);
if (pos==-1){
return; // 元素不存在，直接返回
}
for (int i=pos;i<size-1;i++){
array[i]=array[i+1];
}
array[size-1]=null;// 清理最后一个元素
size--;
}
@Override
public int size() {
return size;
}
@Override
public void clear() {
size=0;
}
public String toString(){
StringBuilder sb = new StringBuilder("[");
for (int i = 0; i < size; i++) {
sb.append(array[i]);
if (i < size - 1) {
sb.append(", ");
}
}
sb.append("]");
return sb.toString();
}
}
3. ArrayList
在集合框架中，ArrayList是一个普通的类，实现了List接口，具体框架图如下：
- ArrayList是以泛型方式实现的，使用时必须要先实例化
- ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
- ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
- ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
- 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择CopyOnWriteArrayList
- ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表
4. ArrayList的问题以及思考
##4.1 插入或删除元素的性能问题（时间复杂度 O(N)）
ArrayList 底层是基于数组实现的，插入或删除元素时，所有后续元素需要整体移动，导致时间复杂度为 O(N)。
- 使用链表（
LinkedList）：- 对于频繁插入或删除操作的场景，
LinkedList是更好的选择。 LinkedList是基于双向链表实现的，插入和删除的时间复杂度为 O(1)（只需调整指针），但随机访问的时间复杂度为 O(N)。- 适用场景：需要频繁插入或删除的场景，但随机访问较少。
- 对于频繁插入或删除操作的场景，
- 使用
ArrayDeque：- 如果操作集中在首尾两端，可以使用
ArrayDeque，它支持高效的首尾插入和删除操作。
- 如果操作集中在首尾两端，可以使用
- 优化插入/删除的逻辑：
- 如果需要频繁插入或删除，尽量批量操作，而不是逐个操作。例如，先将需要插入的数据存储在临时集合中，最后一次性合并到目标集合。
4.2 增容的性能消耗问题
ArrayList 增容时需要重新分配新空间，并将旧数组的数据拷贝到新数组中，这会带来性能开销。
预估容量，合理初始化
ArrayList的初始容量：在创建
ArrayList时，尽量根据实际需求指定初始容量，避免频繁增容。例如：ArrayList<Integer> list = new ArrayList<>(1000);这样可以减少扩容操作的发生。
使用
ArrayList.ensureCapacity()方法：如果知道大概需要插入的元素数量，可以在插入数据前调用
ensureCapacity()方法手动扩容，避免多次增容。例如：list.ensureCapacity(1000);
使用其他动态数据结构：
- 如果扩容的性能开销成为瓶颈，可以考虑使用其他动态数据结构（如
LinkedList或ArrayDeque），具体选择取决于场景需求。
- 如果扩容的性能开销成为瓶颈，可以考虑使用其他动态数据结构（如
4.3 空间浪费问题
ArrayList 增容时容量通常增长为原来的 2 倍，会导致未使用的空间浪费。
手动调整容量：
在确定不再需要新增元素时，可以调用
ArrayList.trimToSize()方法，将ArrayList的容量调整为当前元素的实际大小，减少空间浪费。例如：list.trimToSize();
使用其他集合类（如
LinkedList）：- 如果对空间利用率要求较高，可以考虑使用
LinkedList，因为它的空间分配是动态的，不会预留多余的空间。
- 如果对空间利用率要求较高，可以考虑使用
动态调整容量增长策略：
- 如果对
ArrayList的增容策略不满意，可以自定义一个集合类，继承自ArrayList，并重写其扩容逻辑。例如，可以改为按固定大小增长，而不是倍增。
- 如果对