面试题：自定义实现符合Collection接口规范的类

import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class CustomCollection<T> implements Collection<T> {
    private static final int DEFAULT_CAPACITY = 16;
    private T[] elements;
    private int size;

    public CustomCollection() {
        elements = (T[]) new Object[DEFAULT_CAPACITY];
        size = 0;
    }

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

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(Object o) {
        for (int i = 0; i < size; i++) {
            if (elements[i].equals(o)) {
                return true;
            }
        }
        return false;
    }

    @Override
    public Iterator<T> iterator() {
        return new CustomIterator();
    }

    @Override
    public Object[] toArray() {
        Object[] array = new Object[size];
        System.arraycopy(elements, 0, array, 0, size);
        return array;
    }

    @Override
    public <T1> T1[] toArray(T1[] a) {
        if (a.length < size) {
            return (T1[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
        }
        System.arraycopy(elements, 0, a, 0, size);
        if (a.length > size) {
            a[size] = null;
        }
        return a;
    }

    @Override
    public boolean add(T e) {
        ensureCapacity(size + 1);
        elements[size++] = e;
        return true;
    }

    @Override
    public boolean remove(Object o) {
        for (int i = 0; i < size; i++) {
            if (elements[i].equals(o)) {
                System.arraycopy(elements, i + 1, elements, i, size - i - 1);
                elements[--size] = null;
                return true;
            }
        }
        return false;
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        for (Object o : c) {
            if (!contains(o)) {
                return false;
            }
        }
        return true;
    }

    @Override
    public boolean addAll(Collection<? extends T> c) {
        boolean modified = false;
        for (T e : c) {
            modified |= add(e);
        }
        return modified;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        boolean modified = false;
        for (Object o : c) {
            modified |= remove(o);
        }
        return modified;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        boolean modified = false;
        for (int i = 0; i < size; i++) {
            if (!c.contains(elements[i])) {
                System.arraycopy(elements, i + 1, elements, i, size - i - 1);
                elements[--size] = null;
                i--;
                modified = true;
            }
        }
        return modified;
    }

    @Override
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    private void ensureCapacity(int minCapacity) {
        if (minCapacity > elements.length) {
            int newCapacity = elements.length * 2;
            if (newCapacity < minCapacity) {
                newCapacity = minCapacity;
            }
            T[] newElements = (T[]) new Object[newCapacity];
            System.arraycopy(elements, 0, newElements, 0, size);
            elements = newElements;
        }
    }

    private class CustomIterator implements Iterator<T> {
        private int cursor;

        @Override
        public boolean hasNext() {
            return cursor < size;
        }

        @Override
        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            return elements[cursor++];
        }
    }
}

存储结构设计

数组：采用动态数组来存储元素。初始容量设为16，当元素个数超过数组容量时，将数组容量翻倍，以减少频繁的内存分配和拷贝。这样既避免了固定大小数组的空间浪费，又保证了添加操作的高效性，平均时间复杂度接近O(1)。

方法实现优化思路

添加元素（add方法）：先检查容量是否足够，不足则扩容，然后将元素添加到数组末尾。扩容操作采用翻倍策略，减少内存重新分配的频率。
删除元素（remove方法）：通过线性查找找到要删除的元素，然后将其后的元素向前移动一位，覆盖要删除的元素，最后将数组末尾置为null，并减小size。时间复杂度为O(n)，在删除元素较少时效率尚可。
遍历（iterator方法）：实现一个内部迭代器类，使用一个游标cursor来跟踪当前位置，保证了遍历的一致性和安全性，时间复杂度为O(n)。
其他方法：如contains、containsAll、addAll等方法，基于数组遍历实现，在数据量较大时可考虑优化为更高效的查找算法（如哈希表等），当前实现为基本的线性查找。

星途面试题库

面试题：自定义实现符合Collection接口规范的类

知识考点

面试题答案

存储结构设计

方法实现优化思路