Java List——针对实习面试

Java List

Java List的三种主要实现是什么？它们各自的特点是什么？

Java中List接口的三种主要实现分别是ArrayList、LinkedList和Vector。它们各自的特点如下：

1. ArrayList

• 基于动态数组：ArrayList内部使用数组来存储元素，这使得随机访问元素非常快速（时间复杂度为O(1)）。
• 非同步：ArrayList不是线程安全的，因此在多线程环境中需要外部同步措施。
• 快速失败迭代器：ArrayList的迭代器在迭代过程中，如果检测到集合结构被修改，会立即抛出ConcurrentModificationException。
• 适合随机访问：如果你需要频繁地读取列表中的元素并且不需要经常插入或删除元素，那么ArrayList是最佳选择。

2. LinkedList

• 基于双向链表：LinkedList内部使用链表来存储元素，每个元素都包含对前一个和后一个元素的引用。
• 非同步：和ArrayList一样，LinkedList也不是线程安全的。
• 适合插入和删除操作：由于链表的结构，LinkedList在插入和删除元素时（特别是在列表的开头或中间）不需要移动其他元素，因此操作速度快（时间复杂度为O(1)）。
• 不支持快速随机访问：与ArrayList不同，LinkedList不支持快速随机访问，访问特定索引的元素需要从头开始遍历链表。

3. Vector

• 基于动态数组：Vector和ArrayList类似，也是基于数组实现的，但它提供了线程安全的操作。
• 同步：Vector的所有方法都是同步的，这意味着它是线程安全的，但这也导致了性能上的开销。
• 快速失败迭代器：与ArrayList类似，Vector的迭代器在检测到并发修改时也会抛出ConcurrentModificationException。
• 已过时：由于性能问题，Vector类已被官方标记为过时（deprecated），建议使用Collections.synchronizedList包装ArrayList来获得更好的性能。

在选择List的实现时，你应该根据你的具体需求来决定。如果你需要频繁地访问列表中的元素，并且不需要经常插入或删除元素，那么ArrayList是一个好的选择。如果你需要在列表中频繁地插入或删除元素，尤其是在列表的开头或中间，那么LinkedList可能更合适。如果你需要一个线程安全的列表，并且不关心性能，那么Vector可以满足你的需求，但通常推荐使用Collections.synchronizedList来包装ArrayList。

Java List和Array（数组）的区别？

Java中List接口和数组（Array）在功能和使用上有一些关键的区别。以下是List和数组的主要区别：

1. 类型和大小

• 数组：在Java中，数组是固定大小的，一旦声明，其长度不能改变。数组可以存储基本数据类型和对象。
• List：List是一个接口，其大小可以动态增长和缩减。List可以存储对象，但不支持基本数据类型。

2. 实现

• 数组：数组是Java的一种基本数据结构，用于存储固定大小的同类型元素。
• List：List是一个接口，有多个实现类，如ArrayList、LinkedList等，这些实现类提供了不同的存储和访问方式。

3. 性能

• 数组：对于基本数据类型数组，访问和赋值操作通常比List快，因为数组是连续内存存储。
• List：对于对象，List（特别是ArrayList）提供了更多的灵活性和功能，如动态扩容、添加、删除元素等，但可能在性能上不如数组。

4. 功能

• 数组：数组提供基本的元素访问，但不支持List提供的一些高级操作，如addAll()、removeAll()、iterator()等。
• List：List接口提供了丰富的操作方法，如add()、remove()、contains()、iterator()等，以及Collections类提供的静态方法，如sort()、binarySearch()等。

5. 泛型

• 数组：数组在声明时就需要指定其类型，且这个类型在数组的生命周期内不能改变。
• List：List可以使用泛型来指定存储的元素类型，这使得List更加灵活和安全。

6. 多维数组

• 数组：可以创建多维数组，如int[][]。
• List：虽然List本身不支持多维，但可以通过创建List的List来实现类似多维数组的功能。

7. 序列化

• 数组：数组可以很容易地序列化和反序列化。
• List：List的序列化和反序列化需要额外的处理，如使用ArrayList的writeObject()和readObject()方法。

8. 初始值

• 数组：数组的元素在创建时可以有默认值，例如，整数数组的元素默认为0。
• List：List的元素在创建时默认值为null。

9. 线程安全

• 数组：数组不是线程安全的。
• List：List的实现类，如Vector，是线程安全的，但通常推荐使用Collections.synchronizedList来包装非线程安全的List。

10. 可变性

• 数组：数组一旦创建，其大小和内容都不可变（除非重新创建一个新的数组）。
• List：List的大小和内容都是可变的，可以通过添加、删除元素来改变。

在面试中，理解这些区别可以帮助你根据具体需求选择使用数组还是List，并能够解释为什么在某些情况下一个比另一个更合适。

Java List和Set有什么区别？

Java中的List和Set是集合框架中的两个接口，它们有以下主要区别：

1. 元素唯一性

• List：允许重复元素，即同一个列表中可以包含多个相同的对象。
• Set：不允许重复元素，如果尝试添加重复的元素，它将被忽略或替换。

2. 元素顺序

• List：通常是有序的，即元素的顺序是按照它们被添加的顺序保存的。
• Set：通常是无序的，即不保证元素的顺序。

3. 实现类

• List：常见的实现类有ArrayList、LinkedList和Vector。
• Set：常见的实现类有HashSet、LinkedHashSet和TreeSet。

4. 性能

• List：对于添加、删除和查找操作，性能可能因实现而异。例如，ArrayList在随机访问时非常高效，但在中间或开始处插入和删除元素时可能需要移动元素，效率较低。LinkedList在插入和删除操作时效率较高，但在随机访问时效率较低。
• Set：对于添加、删除和查找操作，性能也取决于实现。例如，HashSet提供了非常快的平均时间复杂度，特别是对于添加和删除操作，但在迭代时可能不如TreeSet快。TreeSet保持元素有序，因此插入和查找操作通常较慢。

5. 迭代器

• List：返回的迭代器是快速失败的，即如果在迭代过程中修改了列表（除了通过迭代器自己的remove方法），将抛出ConcurrentModificationException。
• Set：返回的迭代器也是快速失败的。

6. 应用场景

• List：当你需要保持元素顺序，或者需要频繁访问列表中的元素时，使用List。
• Set：当你需要确保元素唯一性，或者不关心元素的顺序时，使用Set。

7. 方法

• List：提供了一些特有的方法，如get(int index)、set(int index, E element)、add(int index, E element)和remove(int index)。
• Set：没有提供额外的索引相关的方法，因为它不支持有序性。

8. 线程安全

• List：Vector是线程安全的，但通常推荐使用Collections.synchronizedList来包装非线程安全的List。
• Set：Collections.synchronizedSet可以用来包装非线程安全的Set，如HashSet。

在面试中，理解List和Set的区别对于选择合适的集合类型非常重要。面试官可能会询问你如何在它们之间做出选择，或者如何使用它们的特性来解决特定的问题。

ArrayList和Vector有什么区别？

ArrayList和Vector都是Java集合框架中用于存储动态数组的类，但它们之间存在一些关键区别：

1. 线程安全性

• ArrayList：不是线程安全的，因此在多线程环境中需要外部同步措施来保证线程安全。
• Vector：是线程安全的，内部方法都是同步的，不需要额外的同步措施。

2. 性能

• ArrayList：由于不是线程安全的，通常比Vector有更好的性能，尤其是在单线程环境中。
• Vector：由于所有操作都是同步的，所以性能通常比ArrayList差，尤其是在多线程环境中。

3. 扩容机制

• ArrayList：在内部使用数组来存储元素，当元素数量超过当前数组容量时，会进行数组扩容，通常是创建一个新的更大的数组，并将旧数组的元素复制到新数组中。
• Vector：同样使用数组来存储元素，但扩容机制与ArrayList不同。Vector的扩容因子默认为2，即每次扩容都会将容量增加到原来的两倍，这可能导致比ArrayList更大的内存占用。

4. 已被弃用

• ArrayList：是推荐使用的集合类，因为它是非线程安全的，所以在单线程环境中性能更好。
• Vector：由于性能问题，已经被官方标记为过时（deprecated），不推荐使用。如果需要线程安全的集合，建议使用Collections.synchronizedList来包装ArrayList。

5. 继承结构

• ArrayList和Vector都实现了List接口，但Vector继承自AbstractList，而ArrayList继承自AbstractList的子类AbstractSequentialList。

6. 默认容量

• ArrayList：默认初始容量为10（可以通过构造函数设置初始容量）。
• Vector：默认初始容量也为10（也可以通过构造函数设置）。

7. 迭代器

• ArrayList和Vector：它们的迭代器都是快速失败的，即如果在迭代过程中修改了集合（除了通过迭代器自己的remove或add方法），将抛出ConcurrentModificationException。

在面试中，你可能会被问到如何选择使用ArrayList或Vector，或者如何在ArrayList和Vector之间进行转换。理解这些区别可以帮助你根据具体需求选择最合适的集合类型。

什么是LinkedList？它与ArryList有什么区别？

LinkedList 是 Java 集合框架中的一个类，它实现了 List 接口。LinkedList 是基于双向链表实现的，每个元素都包含了对前一个和后一个元素的引用。以下是 LinkedList 的一些关键特性以及与 ArrayList 的主要区别：

LinkedList 的特性：

1. 基于链表实现：LinkedList 的内部使用链表结构来存储元素，每个元素都包含对前一个和后一个元素的引用。
2. 非同步：LinkedList 不是线程安全的，因此在多线程环境中需要外部同步措施。
3. 快速插入和删除：由于链表的结构，LinkedList 在插入和删除元素时（特别是在列表的开头或中间）不需要移动其他元素，因此操作速度快（时间复杂度为 O(1)）。
4. 不支持快速随机访问：与 ArrayList 不同，LinkedList 不支持快速随机访问，访问特定索引的元素需要从头开始遍历链表。
5. 可以当作队列或栈使用：LinkedList 实现了 Deque 接口，因此它可以被用作队列或栈。

ArrayList 的特性：

1. 基于动态数组实现：ArrayList 内部使用数组来存储元素，这使得随机访问元素非常快速（时间复杂度为 O(1)）。
2. 非同步：ArrayList 不是线程安全的，因此在多线程环境中需要外部同步措施。
3. 快速随机访问：由于数组的结构，ArrayList 支持快速的随机访问。
4. 插入和删除操作可能较慢：在 ArrayList 中插入和删除元素可能需要移动其他元素，特别是在列表的中间位置，这可能导致较慢的操作（时间复杂度为 O(n)）。

主要区别：

1. 内部数据结构：ArrayList 使用动态数组，而 LinkedList 使用双向链表。
2. 随机访问性能：ArrayList 支持快速的随机访问，而 LinkedList 不支持。
3. 插入和删除性能：LinkedList 在插入和删除操作上通常比 ArrayList 快，特别是在列表的开头或中间。
4. 内存占用：LinkedList 的每个元素都需要额外的内存来存储前后元素的引用，因此可能比 ArrayList 占用更多内存。
5. 功能实现：LinkedList 实现了 Deque 接口，提供了队列、栈等数据结构的操作，而 ArrayList 没有实现这些接口。
6. 迭代器性能：LinkedList 的迭代器在列表中间插入或删除元素时，不需要像 ArrayList 那样移动后续元素，因此在某些操作中可能更快。

在面试中，你可能会被问到如何选择使用 ArrayList 或 LinkedList，这取决于你的具体需求，例如是否需要频繁的随机访问，或者是否需要频繁的插入和删除操作。

什么是ArrayList扩容机制？

ArrayList 是 Java 集合框架中的一部分，它实现了一个可以动态增长和缩减的索引序列。ArrayList 内部使用数组来存储元素，当列表的当前容量不足以容纳更多元素时，ArrayList 需要扩容以确保可以添加新元素。ArrayList 的扩容机制如下：

初始容量

• 当创建一个 ArrayList 实例时，它有一个初始容量（默认通常是10，但也可以指定其他值）。这个容量是指内部数组的初始大小。

扩容过程

1. 添加元素：当使用 add() 方法添加元素时，ArrayList 会检查内部数组是否还有空间容纳新元素。
2. 检查容量：如果数组已满，ArrayList 会创建一个新的、容量更大的数组。
3. 扩容策略：新数组的容量通常是旧数组容量的1.5倍（或者通过构造函数指定的增长因子），但这不是固定的，具体实现可能会有所不同。
4. 元素复制：ArrayList 会将旧数组中的所有元素复制到新数组中。
5. 引用更新：一旦所有元素都被复制，旧数组会被丢弃，内部引用指向新数组。

影响性能

• 性能开销：扩容操作涉及到创建新数组和复制旧数组中的元素，这可能会带来显著的性能开销，尤其是在数组较大时。
• 频繁操作：如果 ArrayList 需要频繁扩容（例如，在循环中添加大量元素），这可能会导致性能问题。为了避免这种情况，一种常见的做法是在添加大量元素之前预先设置一个足够大的容量。

示例代码
以下是一个简单的示例，展示了 ArrayList 扩容的过程：

import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        System.out.println("Initial capacity: " + list.size());

        // 添加元素直到需要扩容
        for (int i = 0; i < 15; i++) {
            list.add("Element " + i);
        }

        System.out.println("New capacity after resizing: " + list.size());
    }
}

在这个例子中，当添加第11个元素时，ArrayList 将扩容到至少容纳15个元素的容量。

在面试中，了解 ArrayList 的扩容机制对于编写高效的代码非常重要，特别是在处理大量数据时。面试官可能会询问你如何在添加元素时优化 ArrayList 的性能，或者如何预测和避免频繁的扩容操作。