编程洪同学

模式切换

List 集合 ​

List 接口 ​

List 接口是 Collection 的子接口，特点：

  • 元素有序，按插入顺序存储
  • 允许存储重复元素
  • 提供基于索引的访问方式

25030404.png

图 List 接口中提供的所有方法

下面列举了 List 接口中常用的方法：

java
void add(int index, E element);  // 在指定索引插入元素
E get(int index);  // 获取指定索引的元素
E set(int index, E element);  // 修改索引位置的元素
E remove(int index);  // 删除指定索引的元素
int indexOf(Object o);  // 返回元素的索引
List<E> subList(int fromIndex, int toIndex);  // 截取子列表

在下面代码中，使用 List 接口的实现类 ArrayList 调用相应的方法：

java
List<String> list = new ArrayList<>();
list.add("Java");
list.add("Python");
list.add("C++");

System.out.println(list.get(1)); // Python
list.remove("Python");
System.out.println(list); // [Java, C++]

List 接口中常用的实现类对比：

实现类底层数据结构线程安全性适用场景
ArrayList数组非线程安全读多写少，查询性能高
LinkedList双向链表非线程安全频繁插入、删除操作
Vector数组线程安全（已不推荐）需要线程安全的动态数组

ArrayList ​

ArrayList 是 Java中常用的动态数组实现，属于 List 接口的子类。它基于数组（Array）实现，但提供了动态扩容的能力，非常适合存储和操作有序数据集合。

java
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

25030407.png

图 ArrayList 类的继承关系

数据结构 ​

ArrayList 的底层数据结构是一个动态扩展的数组，其属性如下图所示：

25030405.png

图 ArrayList 类中所有的属性
  • DEFAULT_CAPACITY：默认初始容量，默认为 10。
    java
    private static final int DEFAULT_CAPACITY = 10;
  • EMPTY_ELEMENTDATA：空数组，默认为空数组。
    java
    private static final Object[] EMPTY_ELEMENTDATA = {};
  • DEFAULTCAPACITY_EMPTY_ELEMENTDATA：用于默认大小的空实例的共享空数组实例。将其与 EMPTY_ELEMENTDATA 区分开来，以便知道添加第一个元素时要膨胀多少。
    java
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  • elementData：一个 Object 类型的数组，用于存放实际元素。由于 ArrayList 是泛型类，编译时通过泛型擦除机制存储对象。
    java
    transient Object[] elementData;
  • size：一个 int 类型的变量，表示 ArrayList 当前实际存储的元素数量。它总是小于或等于 elementData 数组的长度。
    java
    private int size;

构造方法 ​

ArrayList 类中提供了三个构造方法，如下图所示：

25030406.png

图 ArrayList 类中提供的构造方法
  • ArrayList()：无参构造方法。使用一个默认容量为 0 的空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 来初始化 elementData。
    java
    public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
  • ArrayList(int initialCapacity)：指定初始容量的构造方法。根据传入的初始容量 initialCapacity 创建一个新的数组，用于初始化 elementData。
    java
    public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    }
}
  • ArrayList(Collection<? extends E> c)：基于现有集合创建。将传入的集合 c 转换为数组，用于初始化 elementData。
    java
    public ArrayList(Collection<? extends E> c) {
   elementData = c.toArray();
   if ((size = elementData.length) != 0) {
       if (elementData.getClass() != Object[].class)
           elementData = Arrays.copyOf(elementData, size, Object[].class);
   } else {
       this.elementData = EMPTY_ELEMENTDATA;
   }
}

扩容机制 ​

ArrayList 的容量是动态调整的，当添加元素时，如果当前数组容量不足，将触发扩容机制。默认情况下，ArrayList 的初始容量为 10，每次扩容大小为当前容量的 1.5 倍。扩容的具体实现通过调用 Arrays.copyOf 将旧数组的内容复制到一个更大的新数组中。

扩容的核心代码如下：

  • grow(int minCapacity)：计算新的容量 newCapacity，然后调用 Arrays.copyOf 将旧数组的内容复制到一个更大的新数组中。
java
/**
 * 增加容量以确保它至少可以容纳最小容量参数指定的元素数量。
 */
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容1.5倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

添加元素 ​

ArrayList 提供了多个 add 方法，用于在末尾或指定位置插入元素。添加元素时，如果当前数组容量不足，将触发扩容机制。

  • add(E e)：在末尾添加元素。
    java
    public boolean add(E e) {
    // ensureCapacityInternal(size + 1)：检查当前容量是否足够，如果不足则调用 grow 方法进行扩容。
    ensureCapacityInternal(size + 1); // 确保容量足够
    elementData[size++] = e; // 添加元素
    return true;
}
  • add(int index, E element)：在指定位置插入元素。
    java
    public void add(int index, E element) {
    rangeCheckForAdd(index); // 检查索引是否越界
    ensureCapacityInternal(size + 1); // 确保容量足够
    System.arraycopy(elementData, index, elementData, index + 1, size - index); // 将 index 位置后的元素向后移动一位
    elementData[index] = element; // 插入元素
    size++;
}

删除元素 ​

ArrayList 的删除操作包括按索引删除和按值删除。删除后会触发数组的移动操作，以保持数组的连续性。

按索引删除元素的代码如下：

java
public E remove(int index) {
    rangeCheck(index); // 检查索引范围
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1; // 需要移动的元素数量
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index, numMoved); // 将删除位置之后的元素向前移动一位
    elementData[--size] = null; // 清空最后一个元素，防止内存泄漏
    return oldValue;
}

查找和更新元素 ​

ArrayList 支持通过索引快速访问元素，时间复杂度为 O(1)。查找和更新元素的代码如下：

java
public E get(int index) {
    rangeCheck(index); // 检查索引范围
    return elementData(index);
}

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

public E set(int index, E element) {
    rangeCheck(index); // 检查索引范围
    E oldValue = elementData(index);
    elementData[index] = element; // 更新元素
    return oldValue;
}

总结 ​

特点：

  • 动态扩容：ArrayList 的容量可以动态调整，超出容量时自动扩展。
  • 高效随机访问：基于数组实现，访问元素时间复杂度为 O(1)。
  • 允许空值：可以存储 null 元素。
  • 线程不安全：ArrayList 本身不是线程安全的，多线程场景需要手动同步。

使用建议：

  • 预先指定容量：如果事先能确定需要存储的数据大小，最好在创建 ArrayList 时指定初始容量，以避免多次扩容带来的性能开销。
  • 避免频繁扩容：尽量一次性添加多个元素，避免频繁触发扩容机制。

LinkedList ​

LinkedList 是 Java 集合框架中的一个双向链表实现，属于 java.util 包。它实现了 List 和 Deque 接口，支持作为双端队列和普通列表使用。LinkedList 的底层数据结构和逻辑设计使其在处理频繁插入和删除操作时表现出色。

25030408.png

图 LinkedList 类的继承关系

数据结构 ​

LinkedList 的底层数据结构是一个双向链表。链表中的每个元素称为节点（Node），每个节点包含以下部分：

  • 数据部分：存储节点的数据元素。
  • 引用部分：包含两个引用，一个指向前一个节点（prev），一个指向下一个节点（next）。

这种结构使得 LinkedList 无需像数组那样在内存中是连续的，节点可以根据需要动态分配和释放。LinkedList 的节点定义如下：

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 维护了以下属性来管理链表，这些属性使得 LinkedList 可以快速访问链表的头部和尾部，从而高效地执行添加、删除等操作：

  • size：表示链表中节点的个数。
  • first：指向链表的第一个节点。
  • last：指向链表的最后一个节点。

25030409.png

图 LinkedList 类中所有的属性

添加元素 ​

LinkedList 支持在头部、尾部或任意位置添加元素。添加元素时，LinkedList 会创建一个新的节点，并更新相关节点的引用。

  • add(E e)：在链表尾部添加元素。
    java
    public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null); // 创建新节点
    last = newNode;
    if (l == null) { // 如果链表为空
        first = newNode;
    } else {
        l.next = newNode; // 更新前一个节点的 next 引用
    }
    size++;
    modCount++;
}
  • addFirst(E e)：在链表头部添加元素。
    java
    public void addFirst(E e) {
    linkFirst(e);
}

void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f); // 创建新节点
    first = newNode;
    if (f == null) { // 如果链表为空
        last = newNode;
    } else {
        f.prev = newNode; // 更新后一个节点的 prev 引用
    }
    size++;
    modCount++;
}
  • add(int index, E element)：在指定位置插入元素。
    java
    public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size) { // 如果是添加到末尾
        linkLast(element);
    } else {
        linkBefore(element, node(index)); // 添加到指定位置
    }
}

void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ); // 创建新节点
    succ.prev = newNode;
    if (pred == null) {
        first = newNode;
    } else {
        pred.next = newNode;
    }
    size++;
    modCount++;
}

删除元素 ​

LinkedList 支持按索引删除和按值删除元素。删除元素时，LinkedList 会断开节点的引用链，并释放节点的内存。

  • remove(int index)：按索引删除元素。
    java
    public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}
  • 按值删除元素：LinkedList 没有直接提供按值删除的方法，但可以通过迭代链表，找到匹配的节点后调用 unlink 方法进行删除。

查找元素 ​

LinkedList 的随机访问性能较低，因为访问某个特定位置的节点需要从头开始遍历链表。LinkedList 通过比较索引与链表长度的一半，决定从头节点开始遍历还是从尾节点开始遍历，以提高查找性能。LinkedList 提供了 get 方法来按索引查找元素：

java
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

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;
    }
}

迭代与遍历 ​

LinkedList 支持多种遍历方式，包括普通 for 循环、增强 for 循环和迭代器。由于 LinkedList 是双向链表，它还提供了 ListIterator 接口，支持双向迭代

总结 ​

特点：

  • 动态大小：LinkedList 的大小是动态的，节点根据需要动态分配和释放。
  • 高效插入和删除：在链表的任意位置插入或删除节点的操作时间复杂度为 O(1)，因为这些操作只涉及到节点的引用改动。
  • 低效随机访问：访问特定索引位置的元素需要从头节点开始遍历链表，时间复杂度为 O(n)。
  • 允许空链表：可以创建一个不包含任何节点的空链表。
  • 线程不安全：LinkedList 本身不是线程安全的，多线程环境需要手动同步。

使用建议：

  • 适用于频繁插入和删除操作：LinkedList 在需要频繁插入或删除操作的场景中表现优异。
  • 避免随机访问：LinkedList 的随机访问性能较低，不适合需要频繁随机访问的场景。
  • 注意线程安全：在多线程环境中使用 LinkedList 时，需要注意线程安全问题，可以通过 Collections.synchronizedList 方法对其进行包装。
编程洪同学服务平台是一个广泛收集编程相关内容和资源，旨在满足编程爱好者和专业开发人员的需求的网站。无论您是初学者还是经验丰富的开发者，都可以在这里找到有用的信息和资料，我们将助您提升编程技能和知识。
CopyRight © 2018-2025 doc.bchtx.cn All Rights Reserved.
专业开发
高端定制
售后无忧
站内资源均为本站制作或收集于互联网等平台，如有侵权，请第一时间联系本站，敬请谅解！本站资源仅限于学习与参考，严禁用于各种非法活动，否则后果自行负责，本站概不承担！