Java中如何满足头尾高效增删+随机访问的List需求？

针对你需要的「实现List接口、头尾增删最优性能、任意索引get高效」的场景，现有JDK原生集合无法完全满足，可通过以下几种方式解决：

一、自定义循环数组式List实现 #

基于ArrayDeque的循环数组思路，实现List接口，维护起始偏移量来实现头尾O(1)操作，同时保证get操作直接通过数组下标访问，时间复杂度O(1)。

核心思路：

• 用数组存储元素，维护start偏移量标记第一个元素的位置
• 头尾增删时，通过取模计算目标位置，无需移动大量元素
• get操作通过(start + index) % 数组容量直接定位元素位置
• 扩容时重新复制元素到新数组，保证后续操作的效率

简单实现示例：

import java.util.AbstractList;
import java.util.NoSuchElementException;

public class CircularArrayList<E> extends AbstractList<E> {
    private Object[] elements;
    private int start;
    private int size;
    private static final int DEFAULT_CAPACITY = 16;

    public CircularArrayList() {
        elements = new Object[DEFAULT_CAPACITY];
    }

    @Override
    public E get(int index) {
        checkIndexValidity(index);
        return (E) elements[(start + index) % elements.length];
    }

    public void addFirst(E element) {
        ensureCapacity(size + 1);
        start = (start - 1 + elements.length) % elements.length;
        elements[start] = element;
        size++;
    }

    public void addLast(E element) {
        ensureCapacity(size + 1);
        elements[(start + size) % elements.length] = element;
        size++;
    }

    @Override
    public void add(int index, E element) {
        if (index == 0) {
            addFirst(element);
            return;
        }
        if (index == size) {
            addLast(element);
            return;
        }
        // 中间插入需移动元素，时间复杂度O(n)，兼容List接口规范
        ensureCapacity(size + 1);
        if (index < size / 2) {
            start = (start - 1 + elements.length) % elements.length;
            for (int i = 0; i < index; i++) {
                elements[(start + i) % elements.length] = elements[(start + i + 1) % elements.length];
            }
        } else {
            for (int i = size; i > index; i--) {
                elements[(start + i) % elements.length] = elements[(start + i - 1) % elements.length];
            }
        }
        elements[(start + index) % elements.length] = element;
        size++;
    }

    public E removeFirst() {
        checkNotEmpty();
        E removed = (E) elements[start];
        elements[start] = null; // 辅助GC
        start = (start + 1) % elements.length;
        size--;
        return removed;
    }

    public E removeLast() {
        checkNotEmpty();
        int lastIdx = (start + size - 1) % elements.length;
        E removed = (E) elements[lastIdx];
        elements[lastIdx] = null;
        size--;
        return removed;
    }

    @Override
    public E remove(int index) {
        if (index == 0) {
            return removeFirst();
        }
        if (index == size - 1) {
            return removeLast();
        }
        // 中间删除需移动元素，时间复杂度O(n)，兼容List接口规范
        E removed = get(index);
        if (index < size / 2) {
            for (int i = index; i > 0; i--) {
                elements[(start + i) % elements.length] = elements[(start + i - 1) % elements.length];
            }
            start = (start + 1) % elements.length;
        } else {
            for (int i = index; i < size - 1; i++) {
                elements[(start + i) % elements.length] = elements[(start + i + 1) % elements.length];
            }
        }
        size--;
        return removed;
    }

    private void ensureCapacity(int minCapacity) {
        if (minCapacity > elements.length) {
            int newCapacity = Math.max(minCapacity, elements.length * 2);
            Object[] newElements = new Object[newCapacity];
            for (int i = 0; i < size; i++) {
                newElements[i] = elements[(start + i) % elements.length];
            }
            elements = newElements;
            start = 0;
        }
    }

    private void checkIndexValidity(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }

    private void checkNotEmpty() {
        if (size == 0) {
            throw new NoSuchElementException();
        }
    }

    @Override
    public int size() {
        return size;
    }
}

这个实现的优势：

• 头尾增删操作均摊时间复杂度O(1)，仅扩容时会触发O(n)的复制操作，日常操作无性能损耗
• get操作时间复杂度O(1)，直接访问数组元素
• 完全实现List接口，可无缝替换现有List使用

二、基于业务场景权衡选择原生集合 #

如果你的业务场景存在明显的操作频率倾斜，可直接选择JDK原生集合：

• 若get操作频率极低，可接受get的O(n)时间复杂度，直接使用LinkedList，它的头尾增删是原生O(1)实现，稳定可靠
• 若头尾增删操作频率极低，可接受头尾操作的O(n)时间复杂度，使用ArrayList即可，它的get操作是原生O(1)，实现成熟且无需额外开发

三、使用第三方库的现成实现 #

如果不想自定义开发，可使用Apache Commons Collections中的CircularArrayList，它基于循环数组实现List接口，天然支持头尾O(1)增删和O(1)的get操作，只需引入对应库依赖即可使用。

内容的提问来源于stack exchange，提问作者maplemaple