关于arraylist:数据结构和算法-ArrayList

1. 什么是线性表

对于线性表的概念以及 LinkedList 和ArrayList的区别能够参考上篇文章。

Segment Fault

Bugkit

上面咱们间接看看如何用 Java 实现ArrayList

2. java 实现

其中的抽象类 AbstractList 和接口 List 也是本人定义的，如须要看残缺代码，能够到文末的 Github 查看残缺代码。

/**
 * @param <E> Type of element
 * @author bugkit
 * @since 2021.10.27
 */
public class ArrayList<E> extends AbstractList<E> implements List<E> {

    // 存储元素的数组
    private E[] data;
    // 元素的默认容量，最多只能装 8 个
    private int capacity = 8;

    // 创立容量为 8 的数组
    public ArrayList() {data = (E[]) new Object[capacity];
    }
    // 创立容量为传入参数大小的数组
    public ArrayList(int capacity) {
        this.capacity = capacity;
        data = (E[]) new Object[capacity];
    }

    // 获取在 data 数组中的第 i 个元素
    @Override
    public E get(int i) {if (i >= size) {throw new IndexOutOfBoundsException("Index" + i + "is out of range" + size);
        }
        return data[i];
    }

    // 移除在 data 数组中的第 i 个元素
    @Override
    public E remove(int i) {if (i >= size) {throw new IndexOutOfBoundsException("Index" + i + "is out of range" + size);
        }
        E e = data[i];
        System.arraycopy(data, i + 1, data, i, size - i);
        size--;
        return e;
    }
    
    // 在 data 数组的第 i 个地位插入新的元素，如果 i 大于以后元素的个数则会报错数组越界
    @Override
    public boolean add(E e, int i) {if (i > size) {throw new IndexOutOfBoundsException("Index" + i + "is out of range" + size);
        }
        if (size == capacity - 1) {resize();
        }
        if (size + 1 - i >= 0) 
            System.arraycopy(data, i, data, i + 1, size + 1 - i);
        data[i] = e;
        size++;
        return true;
    }

    // 增加元素到开端
    @Override
    public boolean add(E e) {return add(e, size);
    }

    // 移除特定元素，如果元素存在则移除该元素并返回 true，否则返回 false
    @Override
    public boolean remove(E e) {for (int i = 0; i < size; i++) {if (data[i].equals(e)) {remove(i);
                return true;
            }
        }
        return false;
    }

    // 判断 ArrayList 是否存在元素 e
    @Override
    public boolean contains(E e) {for (int i = 0; i < size; i++) {if (data[i].equals(e)) {return true;}
        }
        return false;
    }

    @Override
    public String toString() {StringBuilder sb = new StringBuilder();
        sb.append("ArrayList {");
        for (int i = 0; i < size; i++) {sb.append(data[i]).append(",");
        }
        sb.replace(sb.length() - 1, sb.length(),"").append("}");
        return sb.toString();}
    // 扩容，当 add 元素后，size == capacity，则会将 ArrayList 扩容为原来的两倍，// 并将原来的元素按程序拷贝到新的 data 数组
    private void resize() {
        capacity = capacity * 2;
        E[] newData = (E[]) new Object[capacity];
        System.arraycopy(data, 0, newData, 0, size);
        data = newData;
    }
}