List接口及其在代码题中的使用

---

一、List是什么？

List是Java集合框架中的有序集合接口（位于java.util包），允许存储重复元素和null值。核心实现类：

1. ArrayList：基于动态数组，随机访问快
2. LinkedList：基于双向链表，插入删除快
3. Vector（过时）：线程安全的动态数组

二、解决什么问题

1. 动态扩容：自动调整容量（如ArrayList默认初始容量10，扩容1.5倍）
2. 有序存储：元素按插入顺序排列（索引从0开始）
3. 快速访问：通过索引直接定位元素（ArrayList的get(i)时间复杂度O(1)）
4. 灵活操作：支持增删改查、排序、遍历等

三、核心方法

方法	说明	时间复杂度
add(E e)	尾部添加元素	ArrayList: O(1) 均摊, LinkedList: O(1)
get(int index)	获取索引处元素	ArrayList: O(1), LinkedList: O(n)
remove(int index)	删除索引处元素	ArrayList: O(n), LinkedList: O(n)
size()	返回元素数量	O(1)
sort(Comparator c)	排序（JDK8+）	O(n log n)

四、代码题常用场景

1. 数据存储：存储题目输入（如整数序列、字符串）
2. 动态数组：需要频繁按索引访问时用ArrayList
3. 栈/队列：LinkedList可用作栈（addLast/removeLast）或队列（addLast/removeFirst）
4. 去重操作：结合Set去重（new ArrayList<>(new HashSet<>(list))）
5. 排序：list.sort(Comparator.naturalOrder())（JDK8+）
6. 二维结构：List<List<Integer>>表示矩阵或树结构

五、Java示例

// 1. 基础操作
List<Integer> nums = new ArrayList<>();
nums.add(3);  // [3]
nums.add(1, 5);  // [3,5] (在索引1插入)
int first = nums.get(0);  // 3

// 2. 排序（JDK8+）
nums.sort((a, b) -> b - a);  // 降序排序

// 3. 遍历（JDK8+ lambda）
nums.forEach(num -> System.out.print(num + " "));

// 4. 链表实现队列
Deque<Integer> queue = new LinkedList<>();
queue.offer(1);  // 入队
queue.poll();     // 出队

六、ArrayList vs LinkedList

场景	ArrayList	LinkedList
频繁随机访问	✅ (O(1))	❌ (O(n))
头部插入/删除	❌ (O(n))	✅ (O(1))
内存占用	较小（仅存储数据）	较大（额外存储前后指针）
遍历速度	快（缓存友好）	慢（内存不连续）

七、注意事项

1. 线程安全：ArrayList/LinkedList非线程安全，多线程用Collections.synchronizedList()或CopyOnWriteArrayList
2. 初始化容量：预估数据量时指定初始容量（new ArrayList<>(1000)）避免多次扩容
3. 装箱开销：优先用IntStream等原始类型集合（JDK8+）
4. 遍历删除：必须用迭代器避免ConcurrentModificationException

   Iterator<Integer> it = list.iterator();
   while(it.hasNext()) {
       if(it.next() % 2 == 0) it.remove();  // 安全删除偶数
   }

八、总结

在代码题中：

1. 80%场景用ArrayList：随机访问频繁（如动态规划、数组操作）
2. 链表特性用LinkedList：需快速头尾操作（如LRU缓存、BFS队列）
3. JDK8+特性提升效率：
   • 排序：list.sort(Comparator.reverseOrder())
   • 过滤：list.removeIf(num -> num < 0)
   • 转换：List<String> strList = list.stream().map(Object::toString).toList()

📌 关键技巧：遇到"滑动窗口"用ArrayList+双指针；"频繁插入删除"用LinkedList；"排序/去重"结合Stream API（JDK8+）。