正文

Java集合框架原理深度剖析：从源码看ArrayList、LinkedList等核心类实现

/0 浏览量
0702

在Java编程中，集合框架（Collection Framework）是一个非常核心的组成部分，它提供了一套操作集合对象的统一接口和实现。这个框架中包含了许多接口和类，其中ArrayList、LinkedList等类是最常用的集合实现。本文将深入剖析Java集合框架的原理，并从源码层面解析ArrayList和LinkedList等核心类的实现。

1. 集合框架概述

Java集合框架提供了一套丰富的接口和实现，用于存储和操作对象集合。它主要分为以下几类：

  • List：有序集合，可以重复元素，包含ArrayList、LinkedList等实现。
  • Set：无序集合，不允许重复元素，包含HashSet、TreeSet等实现。
  • Queue：用于实现队列算法的集合，包括PriorityQueue等实现。
  • Map：键值对集合，包含HashMap、TreeMap等实现。

2. ArrayList原理分析

ArrayList是Java中常用的动态数组实现，具有以下特点：

  • 基于数组实现，元素存储在连续的内存空间中。
  • 线性查找时间复杂度为O(1)，插入和删除操作的时间复杂度为O(n)。
  • 允许存储任何类型的对象。

以下是ArrayList的核心类源码分析：

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable {
    private static final long serialVersionUID = 8683452581122892189L;
    private static final int DEFAULT_CAPACITY = 10;
    transient Object[] elementData;
    private int size;

    public ArrayList() {
        this.elementData = new Object[DEFAULT_CAPACITY];
    }

    public ArrayList(int initialCapacity) {
        if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        this.elementData = new Object[initialCapacity];
    }

    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size);
        } else {
            this.elementData = new Object[10];
        }
    }

    // ... (其他方法)
}

2.1 构造函数

  • 无参构造函数：创建一个初始容量为10的ArrayList实例。
  • 带参构造函数：根据指定容量创建ArrayList实例。
  • 集合构造函数：将指定集合转换为ArrayList实例。

2.2 线性查找

线性查找通过遍历数组实现，时间复杂度为O(n)。

public E get(int index) {
    Objects.checkIndex(index, size);
    return (E) elementData[index];
}

2.3 插入和删除操作

插入和删除操作涉及到数组的复制和扩容。当添加元素时，如果数组已满，则创建一个容量更大的新数组，并将旧数组中的元素复制到新数组中。删除操作与插入类似。

3. LinkedList原理分析

LinkedList是基于链表实现的集合，具有以下特点：

  • 元素存储在节点中，节点包含数据域和指针域。
  • 查找、插入和删除操作的时间复杂度为O(n)。
  • 空间复杂度为O(1)，因为不需要连续的内存空间。

以下是LinkedList的核心类源码分析：

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, Serializable {
    private static final long serialVersionUID = -2851682305566765464L;
    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;

    public LinkedList() {}

    public LinkedList(Collection<? extends E> c) {
        this(c.toArray());
        if (c.getClass() == getClass()) {
            @SuppressWarnings("unchecked")
            LinkedList<E> cast = (LinkedList<E>) c;
            first = cast.first;
            last = cast.last;
            size = cast.size;
        }
    }

    public LinkedList(E[] array) {
        this.size = array.length;
        if (size > 0) {
            first = new Node<>(null, array[0], null);
            last = first;
            for (int i = 1; i < size; i++) {
                last = last.next = new Node<>(last, array[i], null);
            }
        }
    }

    // ... (其他方法)
}

static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

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

3.1 构造函数

  • 无参构造函数：创建一个空LinkedList实例。
  • 集合构造函数：将指定集合转换为LinkedList实例。
  • 数组构造函数：将指定数组转换为LinkedList实例。

3.2 链表查找

链表查找需要遍历节点，时间复杂度为O(n)。

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 & ~-1; i > index; i--)
            x = x.prev;
        return x;
    }
}

3.3 插入和删除操作

插入和删除操作主要涉及到节点之间的指针调整。插入操作需要找到正确的插入位置，并将新节点插入到链表中。删除操作需要找到待删除节点，并将其前一个节点的next指针指向待删除节点的下一个节点。

4. 总结

本文从源码层面深入剖析了Java集合框架的核心类实现，包括ArrayList和LinkedList。通过分析这两个类的源码，我们可以了解到它们各自的优缺点，以及在实际应用中如何根据需求选择合适的集合实现。了解集合框架的原理对于提高编程能力具有重要意义。

-- 展开阅读全文 --