JAVA数据结构与算法_基础篇：常用集合概述

Java集合框架作为数据处理的核心工具，为开发者提供了丰富的数据结构和算法实现。本文将深入剖析常用集合类的特性与应用场景。

12、数据结构与算法 - 基础：常用集合简述

一、Java 集合框架全景图

作为JDK 1.2引入的核心组件，Java集合框架（JCF）通过统一接口层级整合了各类数据容器。该体系以两大根接口为核心：

                        Iterable
                           |
                    ┌──────┴──────┐
               Collection        Map
               /    |          /    
            List  Queue  Set   HashMap  SortedMap
            /      |           /         |
     ArrayList  Deque  HashSet  ...  ConcurrentHashMap
     LinkedList  |     /    
     Vector    ArrayDeque  LinkedHashSet
      |                   TreeSet
     Stack

Collection接口包含三个重要子类型：

1. List：支持索引访问的有序集合
2. Set：确保元素唯一性的容器
3. Queue/Deque：实现先进先出或双端操作

需特别注意的是，Map接口独立于Collection体系，专门处理键值对映射关系。

二、List 家族：有序可重复的线性列表

2.1 核心实现类对比

特性	ArrayList	LinkedList	Vector	Stack
底层数据结构	动态数组（Object[]）	双向链表	动态数组	继承 Vector
随机访问（get）	O(1)	O(N)（需遍历）	O(1)	O(1)
头/尾插入	O(N) / 均摊 O(1)	O(1) / O(1)	O(N) / 均摊 O(1)	O(N) / 均摊 O(1)
中间插入/删除	O(N)（移动元素）	O(1)（修改指针，但查找 O(N)）	O(N)	O(N)
内存占用	仅数据 + 少量预留	数据 + 两个指针（prev/next）	同 ArrayList	同 Vector
线程安全			（synchronized）
扩容策略	1.5 倍（oldCapacity + oldCapacity >> 1）	按需分配节点	2 倍（可指定增量）	同 Vector
适用场景	随机访问多、尾部增删多	频繁头尾操作、无随机访问需求	旧代码遗留，极少新用	需要 LIFO 栈结构

2.2 ArrayList 的动态扩容机制

/** 模拟ArrayList扩容逻辑 */
public class ArrayListSimulator {
    private Object[] elements;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;
    
    public ArrayListSimulator() {
        elements = new Object[DEFAULT_CAPACITY];
    }
    
    private void ensureCapacity(int minCapacity) {
        if (minCapacity > elements.length) {
            int newCapacity = elements.length + (elements.length >> 1);
            elements = Arrays.copyOf(elements, newCapacity);
        }
    }
}

十、总结

Java集合框架通过List、Set、Map和Queue四大体系，完美解决了各类数据处理需求。掌握各集合类的底层实现与适用场景，是开发高效Java应用的重要基础。