面试官:如何自己设计一个ArrayList？

ArrayList集合是面试常问之一,作为校招生应该不仅要知道它的使用方法以及底层数据结构,而且希望我们通过查看ArrayList的源码自己能够设计出与jdk中ArrayList功能类似的ArrayList(迷你版)。

public class ArrayList {
    
    private int size;

    
    private E[] elements;

    private static final int DEFAULT_CAPACITY = 10;

    private static final int ELEMENT_NOT_FOUND = -1;

    public ArrayList(int initialCapacity){
        if (initialCapacity < 0){
            throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
        }
        initialCapacity = Math.max(initialCapacity, DEFAULT_CAPACITY);
        elements = (E[]) new Object[initialCapacity];
    }

    public ArrayList(){
        this(DEFAULT_CAPACITY);
    }

    
    private void ensureCapacity(int capacity){
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) {
            return;
        }
        //扩容容量为旧数组的的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++){
            newElements[i] = elements[i];
        }
        elements = newElements;
        System.out.println(oldCapacity+"扩容为："+newCapacity);
    }
    
    public int size(){
        return size;
    }

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

    
    public boolean contains(E element){
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    
    public void add(E element){
       
        add(size, element);
    }

    
    public E get(int index){
        rangeCheck(index);
        return elements[index];
    }

    
    public E set(int index, E element){
        rangeCheck(index);
        E old = elements[index];
        elements[index] = element;
        return old;
    }

    private void outOfBounds(int index){
        throw new IndexOutOfBoundsException("Index:" + index+ ",Size:" +size);
    }

    private void rangeCheck(int index){
        if (index < 0 || index >= size){
            outOfBounds(index);
        }
    }

    private void rangeCheckForAdd(int index){
        if (index < 0 || index > size){
            outOfBounds(index);
        }
    }

    
    public void add(int index, E element){
        rangeCheckForAdd(index);
        ensureCapacity(size + 1);

        for (int i = size -1; i >= index; i--){
            elements[i+1] = elements[i];
        }
        elements[index] = element;
        size++;

    }

    
    public E remove(int index){

        if (isEmpty()){
            throw new RuntimeException("集合中的数据元素为空,删除元素失败！");
        }
        rangeCheck(index);
        for(int i = index; i < size - 1; i++){
            elements[i] = elements[i+1];
        }
        size--;
        elements[size] = null;
        return elements[index];
    }

    
    public int indexOf(E element){
        if (element == null){
            for (int i = 0; i < size; i++){
                if(element == (elements[i])){
                    return i;
                }
            }
        }else{
            for (int i = 0; i < size; i++){
                if(element.equals(elements[i])){
                    return i;
                }
            }
        }

        return ELEMENT_NOT_FOUND;
    }

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

    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("size=").append(size).append(", [");
        for (int i = 0; i < size; i++){

            if (i != 0){
                string.append(", ");
            }
            string.append(elements[i]);
        }
        string.append("]");
        return string.toString();
    }
}

测试：

public class ArrayListTest {
    public static void main(String[] args) {

        //创建ArrayList对象往集合中添加元素
        ArrayList list = new ArrayList<>();
        for (int i = 0; i < 30; i++){
            list.add(i);
        }
            list.set(2, 80);
            list.set(3, 90);
            list.set(4, 100);
            list.set(5, 101);
            System.out.println("数组是否为空：" + list.isEmpty());
            System.out.println("删除的元素为：" + list.remove(12));
            System.out.println("索引的元素为：" + list.indexOf(4));
            list.add(list.size(), 90);
            System.out.println(list.get(4));
            System.out.println(list);

//        ArrayList arrayList = new ArrayList<>();
//        arrayList.add(new ArrayListPerson(11,"罗斯"));
//        arrayList.add(new ArrayListPerson(12,"杰克"));
//        arrayList.add(new ArrayListPerson(13,"科比"));
//        arrayList.add(new ArrayListPerson(14,"詹姆斯"));
//        arrayList.add(null);
//
//        System.out.println(arrayList.size());
//
        arrayList.clear();
        System.gc();
//        System.out.println(arrayList);
    }
}

运行结果:

自己设计一个类型,往集合中存储

public class ArrayListPerson {
    private int id;
    private String name;

    public ArrayListPerson(){

    }

    public ArrayListPerson(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "ArrayListPerson{" +
                "id=" + id +
                ", name='" + name + ''' +
                '}';
    }

    @Override
    protected void finalize() throws Throwable {
        super.finalize();
        System.out.println("person finalize!");
    }

    @Override
    public boolean equals(Object o) {
        if (o == null) {
            return false;
        }
        if (o instanceof ArrayListPerson){
            ArrayListPerson arrayListPerson = (ArrayListPerson) o;
            return this.id == arrayListPerson.id;
        }
        return false;

    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }
}

运行测试注释掉的代码结果：

如有不当之处,欢迎在评论区留言共同探讨,共同进步。感谢你的观看！