一.ArrayList 的特性

1. 访问效率高

基于数组实现，支持随机访问（通过索引 get(int index)），时间复杂度为 O(1)；
这是 ArrayList 对比 LinkedList 最核心的优势（LinkedList 随机访问是 O(n)）。

2. 增删效率（分场景）

尾部增删（add (E e)/remove (size-1)）：效率高，时间复杂度 O(1)（无扩容时）；
中间 / 头部增删（add (int index, E e)/remove (int index)）：需要移动后续元素，时间复杂度 O(n)，效率低；
原因：数组元素在内存中是连续存储的，中间插入 / 删除会导致后续元素整体移位。

3. 线程不安全

ArrayList 是非线程安全的集合，多线程环境下同时读写会导致数据错乱（如 ConcurrentModificationException）；
解决方案：

使用 Collections.synchronizedList(new ArrayList<>()) 包装成线程安全版本；
用 CopyOnWriteArrayList（并发包下，写操作时复制数组，读写分离，适合读多写少场景）。

4. 空值与重复元素

允许存储 null 值（可以通过 add(null) 添加）；
允许存储重复元素（如 add(“a”); add(“a”) 是合法的）。

5. Cloneable 与浅拷贝

1.ArrayList 实现了 Cloneable 接口，调用 clone() 方法会返回一个新的 ArrayList 实例，但同样是浅拷贝：
2.新 ArrayList 的数组是新对象，但数组中的元素（引用类型）仅复制引用地址；

示例：如果 ArrayList 中存自定义类对象，修改原对象会影响克隆后的 ArrayList 元素。

二.链表

链表的概念和结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

一.链表的种类

链表的种类有8种，其中的主要分类可以是；

1.带头和不带头

带头节点的实现

classNode{intdata;Nodenext;publicNode(intdata){this.data=data;this.next=null;}}classLinkedList{Nodehead;// 头结点（不存储实际数据）publicLinkedList(){head=newNode(-1);// 初始化头结点}// 添加节点publicvoidadd(intdata){NodenewNode=newNode(data);Nodecurrent=head;while(current.next!=null){current=current.next;}current.next=newNode;}// 删除节点publicvoiddelete(intdata){Nodecurrent=head;while(current.next!=null){if(current.next.data==data){current.next=current.next.next;return;}current=current.next;}}}

不带头的链表实现

classNode{intdata;Nodenext;publicNode(intdata){this.data=data;this.next=null;}}classLinkedList{Nodehead;// 直接指向第一个有效节点publicLinkedList(){head=null;// 初始化为空}// 添加节点publicvoidadd(intdata){NodenewNode=newNode(data);if(head==null){head=newNode;}else{Nodecurrent=head;while(current.next!=null){current=current.next;}current.next=newNode;}}// 删除节点publicvoiddelete(intdata){if(head==null)return;if(head.data==data){head=head.next;return;}Nodecurrent=head;while(current.next!=null){if(current.next.data==data){current.next=current.next.next;return;}current=current.next;}}}

关键区别

初始化：带头结点的链表初始化时创建一个虚拟头节点，不带头结点的链表直接初始化为null。
插入/删除操作：带头结点的链表无需单独处理头节点为空的情况，不带头结点的链表需要额外判断头节点是否为空。
代码复杂度：不带头结点的链表在操作头节点时需要更多边界条件判断，带头结点的链表逻辑更统一。

2.单向和双向

// 单向链表节点classSinglyNode{intdata;SinglyNodenext;}// 双向链表节点classDoublyNode{intdata;DoublyNodenext;DoublyNodeprev;}

复杂度对比

3.循环和非循环

循环的代码实现片段

classNode{intdata;Nodenext;Node(intdata){this.data=data;}}非循环的代码实现片段// 创建循环链表Nodehead=newNode(1);head.next=newNode(2);head.next.next=head;// 尾节点指向头节点

Nodehead=newNode(1);head.next=newNode(2);// 尾节点默认next为null

循环链表的尾节点指向头节点，形成一个闭环结构。这种设计允许从任意节点出发遍历整个链表，适用于需要循环访问的场景。

非循环链表的尾节点指向null，表示链表结束。遍历时需从头节点开始，到达尾节点时终止，结构简单且直观。

二.链表中的重要方法