四川省造价工程信息网_泰安人力资源招聘_公司宣传网站制作_浏览器下载

ArrayList 详细介绍

内部实现

ArrayList 是基于动态数组的数据结构。它允许随机访问元素，并且在内存中是连续存储的。当 ArrayList 的容量不足时，它会创建一个更大的数组，并将现有元素复制到新数组中，这可能会导致性能开销。内部使用的是 Object[] 数组来存储元素。

性能特点

• 随机访问：O(1)，因为可以直接通过索引访问。
• 插入和删除（末尾）：平均情况下 O(1)；最坏情况下 O(n)，如果需要扩容的话。
• 插入和删除（中间或开头）：O(n)，因为需要移动元素以保持数组的连续性。

使用场景

• 当你需要频繁地进行随机访问或者在列表末尾添加/移除元素时，ArrayList 是一个很好的选择。
• 如果你预计列表的大小不会频繁变化，那么 ArrayList 也可以是一个合适的选择，因为它提供了较快的读取速度。

import java.util.ArrayList;public class ArrayListExample {public static void main(String[] args) {// 创建一个ArrayList实例，默认初始容量为10ArrayList<String> list = new ArrayList<>();// 添加元素到ArrayList// add() 方法在列表末尾添加元素，时间复杂度为 O(1)list.add("Apple");list.add("Banana");list.add("Orange");// 打印列表，toString() 方法返回列表内容的字符串表示System.out.println("Initial List: " + list);// 随机访问元素，get() 方法根据索引获取元素，时间复杂度为 O(1)String element = list.get(1); // 获取索引为1的元素System.out.println("Element at index 1: " + element);// 在末尾添加元素，add() 方法在列表末尾添加元素，时间复杂度为 O(1)list.add("Grapes");System.out.println("After adding Grapes: " + list);// 删除元素，remove() 方法根据索引删除元素，时间复杂度为 O(n)list.remove(2); // 删除索引为2的元素System.out.println("After removing index 2: " + list);// 设置元素值，set() 方法替换指定位置的元素，时间复杂度为 O(1)list.set(1, "Mango"); // 将索引为1的元素设置为 "Mango"System.out.println("After setting index 1 to Mango: " + list);// 检查是否包含某个元素，contains() 方法遍历列表查找元素，时间复杂度为 O(n)boolean containsApple = list.contains("Apple");System.out.println("Contains Apple: " + containsApple);// 获取列表大小，size() 方法返回列表中元素的数量，时间复杂度为 O(1)int size = list.size();System.out.println("List size: " + size);}
}

LinkedList 详细介绍

内部实现

LinkedList 是基于双向链表的数据结构。每个节点不仅包含元素本身，还包含指向前后节点的引用。这种结构使得在链表两端进行插入和删除操作非常高效。内部使用了 Node<E> 类来表示链表中的节点。

性能特点

• 随机访问：O(n)，因为必须遍历链表到达指定位置。
• 插入和删除（两端）：O(1)，不需要移动其他元素。
• 插入和删除（中间）：O(n)，首先需要找到目标位置。

使用场景

• 当你需要频繁地在列表的任意位置进行插入或删除操作时，LinkedList 提供了更好的性能。
• 如果你需要一个队列或双端队列的数据结构，LinkedList 实现了 Deque 接口，可以高效地支持这些数据结构所需的头部和尾部操作。

import java.util.LinkedList;public class LinkedListExample {public static void main(String[] args) {// 创建一个LinkedList实例LinkedList<String> list = new LinkedList<>();// 添加元素到LinkedList// add() 方法在列表末尾添加元素，时间复杂度为 O(1)list.add("Apple");list.add("Banana");list.add("Orange");// 打印列表，toString() 方法返回列表内容的字符串表示System.out.println("Initial List: " + list);// 使用迭代器遍历元素，iterator() 方法返回一个用于遍历列表的迭代器for (String fruit : list) {System.out.println(fruit);}// 在头部插入元素，addFirst() 方法在列表头部添加元素，时间复杂度为 O(1)list.addFirst("Strawberry");System.out.println("After adding to head: " + list);// 在尾部添加元素，addLast() 方法在列表尾部添加元素，时间复杂度为 O(1)list.addLast("Grapes");System.out.println("After adding to tail: " + list);// 删除第一个和最后一个元素，removeFirst() 和 removeLast() 方法分别删除头尾元素，时间复杂度为 O(1)list.removeFirst();list.removeLast();System.out.println("After removing first and last: " + list);// 获取第一个和最后一个元素，getFirst() 和 getLast() 方法分别获取头尾元素，时间复杂度为 O(1)String first = list.getFirst();String last = list.getLast();System.out.println("First Element: " + first);System.out.println("Last Element: " + last);// 插入元素到指定位置，add(int index, E element) 方法在指定位置插入元素，时间复杂度为 O(n)list.add(1, "Peach");System.out.println("After inserting Peach at index 1: " + list);// 删除指定位置的元素，remove(int index) 方法删除指定位置的元素，时间复杂度为 O(n)list.remove(1);System.out.println("After removing element at index 1: " + list);}
}

线程安全性与同步

默认情况下，ArrayList 和 LinkedList 都不是线程安全的。如果在多线程环境中使用它们，你需要确保适当的同步。可以使用 Collections.synchronizedList() 方法来包装列表，以获得线程安全的版本。但是需要注意，即使列表被同步了，迭代器仍然不是线程安全的。

import java.util.Collections;
import java.util.List;
import java.util.ArrayList;public class SynchronizedListExample {public static void main(String[] args) {// 创建一个ArrayList实例，并用 Collections.synchronizedList 包装以获得线程安全的版本List<String> syncList = Collections.synchronizedList(new ArrayList<>());// 或者对于 LinkedList// List<String> syncList = Collections.synchronizedList(new LinkedList<>());// 对于同步列表的操作...synchronized (syncList) {syncList.add("Thread-safe Element");}// 注意：即使列表是线程安全的，迭代器也不是线程安全的。// 必须在外层加锁来保证迭代期间的安全性。synchronized (syncList) {for (String item : syncList) {// 迭代操作...}}}
}

迭代器失效

当在迭代过程中修改了 ArrayList 或 LinkedList，除了通过迭代器自身的 remove 或 add 方法外，都会抛出 ConcurrentModificationException。这是为了防止并发修改带来的不一致性问题。

import java.util.Iterator;
import java.util.ArrayList;public class IteratorExample {public static void main(String[] args) {ArrayList<String> list = new ArrayList<>();list.add("Apple");list.add("Banana");// 获取迭代器Iterator<String> it = list.iterator();while (it.hasNext()) {String fruit = it.next();if ("Banana".equals(fruit)) {// 正确的方式：通过迭代器移除元素，避免 ConcurrentModificationExceptionit.remove();}// 错误的方式：直接通过list.remove()会导致ConcurrentModificationException// list.remove(fruit);}// 打印最终列表System.out.println("Final List after iteration removal: " + list);}
}