HBC BLOG

主题

Java集合框架：ArrayList、LinkedList与Set集合完全指南 ​

目录 ​

一、核心知识点 ​

1. ArrayList底层源码分析 ​

1.1 构造方法 ​

无参构造

java
ArrayList<String> list = new ArrayList<>();
  • 构造一个初始容量为10的空列表
  • 重要：不是一new就创建长度为10的数组，而是第一次add时才创建
  • 如果超出容量，自动扩容1.5倍

有参构造

java
ArrayList<String> list = new ArrayList<>(15);
  • 直接指定数组长度，避免频繁扩容

1.2 源码解析 ​

无参构造创建对象

java
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

第一次add时创建长度为10的数组

java
public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity,
                oldCapacity >> 1);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

1.3 重要注意事项 ​

删除元素时的陷阱

java
ArrayList<Integer> list = new ArrayList<>();
list.add(2);

// 错误：会调用根据索引删除的remove方法
// list.remove(2);

// 正确：需要装箱
list.remove(Integer.valueOf(2));

ArrayList使用场景

2. LinkedList集合 ​

2.1 基本特点 ​

特性说明
元素有序是
有索引否
元素可重复是
线程安全否
数据结构双向链表

2.2 特有方法 ​

LinkedList提供了大量直接操作首尾元素的方法：

java
// 添加元素
public void addFirst(E e)    // 插入到开头
public void addLast(E e)     // 添加到结尾

// 获取元素
public E getFirst()          // 获取第一个元素
public E getLast()           // 获取最后一个元素

// 删除元素
public E removeFirst()       // 移除并返回第一个元素
public E removeLast()        // 移除并返回最后一个元素

// 栈操作
public E pop()               // 弹出栈顶元素
public void push(E e)        // 推入栈顶

2.3 使用示例 ​

java
LinkedList<String> list = new LinkedList<>();
list.add("开心超人");
list.add("哆啦A梦");
list.add("柯南");
list.add("加菲猫");

list.addFirst("小猫");
list.addLast("小狗");

System.out.println(list.getFirst());    // 小猫
System.out.println(list.getLast());     // 小狗

list.removeFirst();
list.removeLast();

栈操作示例（先进后出）

java
LinkedList<String> stack = new LinkedList<>();
stack.push("开心超人");
stack.push("哆啦A梦");
stack.push("柯南");
stack.push("加菲猫");

System.out.println(stack.pop());  // 加菲猫
System.out.println(stack.pop());  // 柯南
System.out.println(stack.pop());  // 哆啦A梦
System.out.println(stack.pop());  // 开心超人

2.4 底层结构 ​

Node节点对象

java
private static class Node<E> {
    E item;           // 节点上的元素
    Node<E> next;     // 记录下一个节点地址
    Node<E> prev;     // 记录上一个节点地址

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

LinkedList节点结构

2.5 get方法优化 ​

LinkedList的get方法采用二分思想优化查询：

java
Node<E> node(int index) {
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
  • 如果index < size/2，从前往后遍历
  • 如果index >= size/2，从后往前遍历

3. Collections集合工具类 ​

3.1 特点 ​

  • 构造方法私有
  • 方法均为静态
  • 使用类名直接调用

3.2 常用方法 ​

方法说明
static <T> boolean addAll(Collection<? super T> c, T... elements)批量添加元素
static void shuffle(List<?> list)打乱集合顺序
static <T> void sort(List<T> list)按默认规则排序（ASCII码值）
static <T> void sort(List<T> list, Comparator<? super T> c)按指定规则排序

3.3 使用示例 ​

批量添加和打乱

java
ArrayList<String> list = new ArrayList<>();
Collections.addAll(list, "小猫", "小狗", "小猪", "小牛", "小羊");
Collections.shuffle(list);

默认排序

java
ArrayList<String> list = new ArrayList<>();
list.add("b.疑是地上霜");
list.add("a.床前明月光");
list.add("c.举头望明月");
list.add("d.低头思故乡");
Collections.sort(list);

3.4 自定义排序 ​

使用Comparator

java
ArrayList<Person> list = new ArrayList<>();
list.add(new Person("张三", 18));
list.add(new Person("李四", 16));
list.add(new Person("王五", 20));

// 升序：o1-o2
// 降序：o2-o1
Collections.sort(list, (o1, o2) -> o1.getAge() - o2.getAge());

使用Comparable

java
@Data
public class Student implements Comparable<Student> {
    private String name;
    private Integer score;

    @Override
    public int compareTo(Student o) {
        return this.getScore() - o.getScore();  // 升序
    }
}

// 使用
ArrayList<Student> list = new ArrayList<>();
list.add(new Student("张三", 100));
list.add(new Student("李四", 90));
list.add(new Student("王五", 95));
Collections.sort(list);

3.5 Arrays.asList注意事项 ​

java
List<String> list = Arrays.asList("小猫", "小狗", "小猪");
// 注意：不要修改集合长度，底层是数组，被final定死
// list.add("小马");  // 会抛出异常

4. 泛型 ​

4.1 为什么使用泛型 ​

从使用层面：统一类型，防止类型转换异常

从定义层面：定义时不确定类型，使用时再规定，代码更灵活

不使用泛型的问题

java
ArrayList list = new ArrayList();
list.add("abc");
list.add(1);
list.add(true);

for (Object o : list) {
    String s = (String) o;  // 运行时抛出ClassCastException
    System.out.println(s.length());
}

泛型类型转换异常

4.2 泛型的定义 ​

含有泛型的类

java
public class MyArrayList<E> {
    private Object[] arr = new Object[10];
    private int size = 0;

    public void add(E e) {
        arr[size] = e;
        size++;
    }

    public E get(int index) {
        return (E) arr[index];
    }
}

// 使用
MyArrayList<String> list = new MyArrayList<>();
list.add("abc");
String element = list.get(0);

含有泛型的方法

java
public class MyCollections {
    public static <E> void addAll(ArrayList<E> list, E... elements) {
        for (E e : elements) {
            list.add(e);
        }
    }
}

// 使用
ArrayList<String> list = new ArrayList<>();
MyCollections.addAll(list, "小猫", "小狗", "小猪");

含有泛型的接口

java
public interface MyList<E> {
    void add(E e);
}

// 实现方式1：实现时确定类型
public class MyScanner implements MyIterator<String> {
    @Override
    public String next() {
        return "键盘录入字符串";
    }
}

// 实现方式2：创建对象时确定类型
public class MyArrayList<E> implements MyList<E> {
    public void add(E e) {
        // 实现
    }
}

4.3 泛型的高级使用 ​

泛型通配符 ?

java
public void method(ArrayList<?> list) {
    for (Object o : list) {
        System.out.println(o);
    }
}

// 可以接收任意类型的ArrayList
method(new ArrayList<String>());
method(new ArrayList<Integer>());

泛型上限

java
// ?只能接收Number及其子类
public static void get1(Collection<? extends Number> collection) {
    // ...
}

get1(new ArrayList<Integer>());  // ✓
get1(new ArrayList<Number>());   // ✓
// get1(new ArrayList<String>()); // ✗

泛型下限

java
// ?只能接收Number及其父类
public static void get2(Collection<? super Number> collection) {
    // ...
}

get2(new ArrayList<Number>());   // ✓
get2(new ArrayList<Object>());   // ✓
// get2(new ArrayList<Integer>()); // ✗

5. 红黑树 ​

5.1 为什么需要红黑树 ​

提高查询效率

红黑树结构

5.2 红黑树规则 ​

  1. 每一个节点或是红色的，或者是黑色的
  2. 根节点必须是黑色
  3. 如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，每个叶节点(Nil)是黑色的
  4. 如果某一个节点是红色，那么它的子节点必须是黑色（不能出现两个红色节点相连的情况）
  5. 对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点

红黑树示例

可视化工具：https://www.cs.usfca.edu/~galles/visualization/RedBlack

6. Set集合 ​

6.1 Set接口特点 ​

  • 是一个接口
  • 实现类：HashSet、LinkedHashSet、TreeSet
  • Set集合中的功能没有对Collection接口中的功能进行扩充
  • 所有的set集合底层都是依靠map集合实现的

Set集合继承体系

6.2 HashSet ​

特点

  • 元素无序
  • 无索引
  • 元素不可重复
  • 线程不安全

数据结构

  • JDK 8之前：哈希表 = 数组 + 链表
  • JDK 8开始：哈希表 = 数组 + 链表 + 红黑树

使用示例

java
HashSet<String> set = new HashSet<>();
set.add("小猫");
set.add("小狗");
set.add("小猪");
set.add("小牛");

for (String s : set) {
    System.out.println(s);
}

6.3 LinkedHashSet ​

特点

  • 元素有序
  • 无索引
  • 元素不可重复
  • 线程不安全

数据结构

  • 哈希表 + 双向链表

使用示例

java
LinkedHashSet<String> set = new LinkedHashSet<>();
set.add("小猫");
set.add("小狗");
set.add("小猪");
set.add("小牛");

for (String s : set) {
    System.out.println(s);  // 按添加顺序输出
}

二、重点难点 ​

1. ArrayList扩容机制 ⭐⭐⭐ ​

核心要点

  • 无参构造：第一次add时才创建长度为10的数组
  • 扩容时机：当元素个数超过当前容量
  • 扩容大小：新容量 = 旧容量 * 1.5倍
  • 扩容方式：创建新数组，复制元素

面试重点

java
// 扩容核心代码
int newCapacity = oldCapacity + (oldCapacity >> 1);  // 相当于1.5倍

2. LinkedList双向链表结构 ⭐⭐⭐ ​

核心要点

  • 每个节点包含三个部分：prev、item、next
  • 查询优化：二分查找，从中间分开
  • 插入删除效率高，查询效率低

3. 泛型擦除 ⭐⭐⭐ ​

核心要点

  • 泛型只在编译期有效
  • 运行期会进行类型擦除
  • 泛型本质上就是Object类型

4. HashSet如何保证元素唯一 ⭐⭐⭐ ​

核心要点

  • 先比较hashCode
  • 如果hashCode相同，再比较equals
  • 两者都相同才认为是重复元素

三、常见面试题 ​

1. ArrayList和LinkedList的区别？⭐⭐⭐ ​

答案

对比项ArrayListLinkedList
数据结构动态数组双向链表
查询效率高（有索引）低（需要遍历）
增删效率低（需要移动元素）高（只需修改指针）
内存占用连续内存分散内存
适用场景查询多，增删少增删多，查询少

2. ArrayList的扩容机制？⭐⭐⭐ ​

答案

  1. 无参构造创建ArrayList时，初始化为空数组
  2. 第一次add时，创建长度为10的数组
  3. 当元素个数超过当前容量时，自动扩容
  4. 扩容大小为原容量的1.5倍
  5. 使用Arrays.copyOf复制元素到新数组

3. 如何在遍历ArrayList时删除元素？⭐⭐ ​

答案

错误方式

java
for (int i = 0; i < list.size(); i++) {
    if (list.get(i).equals("删除元素")) {
        list.remove(i);  // 会漏删
    }
}

正确方式1：倒序遍历

java
for (int i = list.size() - 1; i >= 0; i--) {
    if (list.get(i).equals("删除元素")) {
        list.remove(i);
    }
}

正确方式2：使用迭代器

java
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    if (iterator.next().equals("删除元素")) {
        iterator.remove();
    }
}

4. Comparable和Comparator的区别？⭐⭐⭐ ​

答案

对比项ComparableComparator
所属包java.langjava.util
方法compareTo(T o)compare(T o1, T o2)
使用方式类实现接口单独创建比较器
排序规则this - oo1 - o2
适用场景自然排序定制排序

示例对比

java
// Comparable
public class Student implements Comparable<Student> {
    private int score;
    
    @Override
    public int compareTo(Student o) {
        return this.score - o.score;  // 升序
    }
}

// Comparator
Collections.sort(list, (o1, o2) -> o1.getScore() - o2.getScore());

5. HashSet如何保证元素唯一性？⭐⭐⭐ ​

答案

  1. 添加元素时，先计算元素的hashCode值
  2. 如果hashCode值不存在，直接添加
  3. 如果hashCode值存在，调用equals方法比较
  4. 如果equals返回true，认为是重复元素，不添加
  5. 如果equals返回false，添加到链表中

重要结论

  • 必须同时重写hashCode和equals方法
  • 相同对象必须返回相同的hashCode
  • equals返回true的两个对象，hashCode必须相同

6. HashSet和LinkedHashSet的区别？⭐⭐ ​

答案

对比项HashSetLinkedHashSet
元素顺序无序有序（插入顺序）
数据结构哈希表哈希表 + 双向链表
性能稍快稍慢（维护链表）
适用场景不需要顺序需要保持插入顺序

7. 什么是泛型擦除？⭐⭐⭐ ​

答案

  • 泛型只在编译期有效，用于类型检查
  • 运行期会将泛型擦除，替换为Object或上限类型
  • 编译器会在必要的地方插入类型转换代码

示例

java
List<String> list = new ArrayList<>();
list.add("abc");

// 编译后
List list = new ArrayList();
list.add("abc");
String s = (String) list.get(0);  // 编译器插入的类型转换

8. 泛型通配符?、? extends T、? super T的区别？⭐⭐⭐ ​

答案

通配符含义适用场景
?任意类型不关心具体类型
? extends TT及其子类读取数据（生产者）
? super TT及其父类写入数据（消费者）

PECS原则

  • Producer Extends, Consumer Super
  • 频繁往外读取内容，适合用上界Extends
  • 经常往里插入内容，适合用下界Super

四、实用代码片段 ​

1. ArrayList常用操作 ​

java
// 创建并初始化
ArrayList<String> list = new ArrayList<>();
Collections.addAll(list, "元素1", "元素2", "元素3");

// 遍历方式1：普通for
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

// 遍历方式2：增强for
for (String s : list) {
    System.out.println(s);
}

// 遍历方式3：迭代器
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

// 遍历方式4：forEach + lambda
list.forEach(System.out::println);

2. LinkedList作为栈和队列 ​

java
// 作为栈使用（先进后出）
LinkedList<String> stack = new LinkedList<>();
stack.push("元素1");
stack.push("元素2");
System.out.println(stack.pop());  // 元素2

// 作为队列使用（先进先出）
LinkedList<String> queue = new LinkedList<>();
queue.addLast("元素1");
queue.addLast("元素2");
System.out.println(queue.removeFirst());  // 元素1

3. 集合排序 ​

java
// 方式1：实现Comparable
public class Person implements Comparable<Person> {
    private int age;
    
    @Override
    public int compareTo(Person o) {
        return this.age - o.age;
    }
}

// 方式2：使用Comparator
Collections.sort(list, Comparator.comparingInt(Person::getAge));

// 方式3：多条件排序
Collections.sort(list, (o1, o2) -> {
    int result = o1.getAge() - o2.getAge();
    return result != 0 ? result : o1.getName().compareTo(o2.getName());
});

4. HashSet去重 ​

java
// 自定义对象去重
public class Person {
    private String name;
    private int age;
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Person person = (Person) obj;
        return age == person.age && Objects.equals(name, person.name);
    }
}

HashSet<Person> set = new HashSet<>();
set.add(new Person("张三", 18));
set.add(new Person("张三", 18));  // 不会重复添加

5. 泛型方法 ​

java
// 泛型方法示例
public class Utils {
    // 交换数组中两个元素
    public static <T> void swap(T[] arr, int i, int j) {
        T temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    // 打印集合
    public static <E> void print(Collection<E> collection) {
        for (E e : collection) {
            System.out.println(e);
        }
    }
}

五、经典练习题 ​

练习1：ArrayList基本操作 ⭐ ​

题目：创建一个ArrayList，存储5个学生对象，按照年龄升序排序并输出。

参考答案

java
public class Student {
    private String name;
    private int age;
    
    // 构造方法、getter、setter、toString省略
}

public class Test {
    public static void main(String[] args) {
        ArrayList<Student> list = new ArrayList<>();
        list.add(new Student("张三", 18));
        list.add(new Student("李四", 16));
        list.add(new Student("王五", 20));
        list.add(new Student("赵六", 17));
        list.add(new Student("钱七", 19));
        
        Collections.sort(list, Comparator.comparingInt(Student::getAge));
        
        for (Student student : list) {
            System.out.println(student);
        }
    }
}

练习2：LinkedList栈实现 ⭐⭐ ​

题目：使用LinkedList实现一个简单的栈，包含push、pop、peek方法。

参考答案

java
public class MyStack<E> {
    private LinkedList<E> list = new LinkedList<>();
    
    public void push(E e) {
        list.addFirst(e);
    }
    
    public E pop() {
        return list.removeFirst();
    }
    
    public E peek() {
        return list.getFirst();
    }
    
    public boolean isEmpty() {
        return list.isEmpty();
    }
    
    public int size() {
        return list.size();
    }
}

练习3：HashSet去重 ⭐⭐ ​

题目：创建一个HashSet存储学生对象，要求姓名和年龄相同的学生视为同一个学生。

参考答案

java
public class Student {
    private String name;
    private int age;
    
    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Student student = (Student) obj;
        return age == student.age && Objects.equals(name, student.name);
    }
    
    @Override
    public String toString() {
        return "Student{name='" + name + "', age=" + age + "}";
    }
}

public class Test {
    public static void main(String[] args) {
        HashSet<Student> set = new HashSet<>();
        set.add(new Student("张三", 18));
        set.add(new Student("李四", 16));
        set.add(new Student("张三", 18));  // 不会添加
        
        System.out.println(set.size());  // 2
    }
}

练习4：泛型方法 ⭐⭐ ​

题目：编写一个泛型方法，可以接收任意类型的数组，并反转数组元素。

参考答案

java
public class ArrayUtils {
    public static <T> void reverse(T[] arr) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left < right) {
            T temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
    
    public static void main(String[] args) {
        Integer[] arr = {1, 2, 3, 4, 5};
        reverse(arr);
        System.out.println(Arrays.toString(arr));  // [5, 4, 3, 2, 1]
        
        String[] strArr = {"a", "b", "c", "d"};
        reverse(strArr);
        System.out.println(Arrays.toString(strArr));  // [d, c, b, a]
    }
}

练习5：集合综合应用 ⭐⭐⭐ ​

题目：从键盘录入5个学生的姓名和成绩，存储到ArrayList中，按照成绩降序排序，输出前三名学生。

参考答案

java
public class Student implements Comparable<Student> {
    private String name;
    private int score;
    
    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }
    
    @Override
    public int compareTo(Student o) {
        return o.score - this.score;  // 降序
    }
    
    @Override
    public String toString() {
        return name + ": " + score + "分";
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayList<Student> list = new ArrayList<>();
        
        for (int i = 0; i < 5; i++) {
            System.out.print("请输入第" + (i + 1) + "个学生的姓名：");
            String name = scanner.next();
            System.out.print("请输入第" + (i + 1) + "个学生的成绩：");
            int score = scanner.nextInt();
            list.add(new Student(name, score));
        }
        
        Collections.sort(list);
        
        System.out.println("前三名学生：");
        for (int i = 0; i < 3 && i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }
}

六、学习建议 ​

1. 学习路线 ​

ArrayList基础 → ArrayList源码 → LinkedList → Collections工具类
    ↓
泛型基础 → 泛型高级特性 → 泛型通配符
    ↓
红黑树（了解） → HashSet → LinkedHashSet → TreeSet（后续学习）

2. 重点掌握 ​

必须掌握

  • ArrayList的扩容机制
  • LinkedList的双向链表结构
  • Collections工具类的常用方法
  • 泛型的基本使用
  • HashSet如何保证元素唯一

理解即可

  • 红黑树的基本规则
  • 泛型擦除原理
  • 泛型上下限

3. 常见错误 ​

错误1：ArrayList删除元素时索引问题

java
// 错误
for (int i = 0; i < list.size(); i++) {
    list.remove(i);  // 会漏删
}

// 正确
for (int i = list.size() - 1; i >= 0; i--) {
    list.remove(i);
}

错误2：HashSet存储自定义对象未重写hashCode和equals

java
// 必须同时重写hashCode和equals方法
@Override
public int hashCode() {
    return Objects.hash(name, age);
}

@Override
public boolean equals(Object obj) {
    // 实现逻辑
}

错误3：泛型使用基本类型

java
// 错误
ArrayList<int> list = new ArrayList<>();

// 正确
ArrayList<Integer> list = new ArrayList<>();

4. 面试准备 ​

高频考点

  1. ArrayList扩容机制
  2. ArrayList vs LinkedList
  3. HashSet如何保证元素唯一
  4. Comparable vs Comparator
  5. 泛型擦除
  6. 泛型通配符

代码手写

  1. 手写ArrayList核心方法
  2. 手写LinkedList节点类
  3. 手写自定义排序
  4. 手写HashSet去重逻辑

5. 实践建议 ​

  1. 多看源码：理解ArrayList和LinkedList的实现原理
  2. 多写代码：完成所有练习题，加深理解
  3. 多画图：画出链表结构、红黑树结构
  4. 多对比：对比不同集合的特点和使用场景
  5. 多总结：整理笔记，形成知识体系

附录：知识点速查表 ​

ArrayList vs LinkedList ​

操作ArrayListLinkedList
随机访问O(1)O(n)
头部插入O(n)O(1)
尾部插入O(1)O(1)
中间插入O(n)O(n)
删除O(n)O(1)

Set集合对比 ​

集合元素顺序线程安全数据结构
HashSet无序不安全哈希表
LinkedHashSet有序不安全哈希表+链表
TreeSet排序不安全红黑树

泛型通配符 ​

通配符说明示例
?任意类型ArrayList<?>
? extends TT及其子类ArrayList<? extends Number>
? super TT及其父类ArrayList<? super Integer>