01.数组

1. 泛型的思想

实现了一个可以存放任意类型的数组，这个数组可以伸缩，当添加一个元素超过了这个数组的容量，那么这个数组会自动扩容，当数组中的个数小于容量的四分之一的时候，数组容量会收缩到原来容量的一半，而且，对于扩容和锁容，我也对相关的算法进行的优化，让扩容与添加数据缩容与删除数据绑定到一起执行。

datastructure.array.Array

public class datastructure.array.Array<E>{
    // 泛型不能存放基本的数据类型
    private E[] data;
    private int size;

    // 有参数构造函数
    public datastructure.array.Array(int capacity){
        // 泛型数组，由于历史遗留原因，必须绕一个圈
        data = (E[])new Object[capacity];
        size = 0;
    }

    // 无参构造函数
    public datastructure.array.Array(){
        this(10);
    }

    // 获取数组中个元素个数
    public int getSize(){
        return this.size;
    }

    // 获取数组的容量
    public int getCapacity(){
        return this.data.length;
    }

    // 返回数组是否为空
    public boolean isEmpty(){
        return  this.size == 0;
    }

    // 在第index个位置插入一个新的元素e
    public void add(int index, E e){

        if(index < 0 || index > size){
            throw new IllegalArgumentException("AddLast failed. require index>=0 and <=?");
        }

        // 扩容数组,如果
        if(size == data.length){
            E[] newData = (E[])new Object[data.length * 2];
            for(int i = 0; i < index;i++){
                newData[i] = data[i];
            }
            newData[index] = e;
            for(int i = index ; i < size;i++){
                newData[i+1] = data[i];
            }
            data = newData;
        } else {
            for(int i = size - 1; i >= index; i--)
                data[i + 1] = data[i];
            data[index] = e;
        }
        size ++;

    }

    // 向所有元素后面添加一个新元素
    public void addLast(E e){
        this.add(size, e);
    }

    // 向所有元素前面添加一个新元素
    public void addFirst(E e){
        this.add(0, e);
    }

    // 获取index索引位置的元素
    public E get(int index) {
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Get failed, Index is illegal.");
        return data[index];
    }

    // 修改index索引位置的元素
    public void set(int index, E e) {
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Set failed, Index is illegal");
        data[index] = e;
    }

    // 查找数组中是否含有元素e,
    public boolean contains(E e){
        for(int i=0;i < size;i++){
            // 两个对象之间值的比较用equals
            if(data[i].equals(e))
                return true;
        }
        return false;
    }

    // 查找数组中是否含有元素e元素的索引,如果查到，返回查询到的第一个索引值，否则返回-1
    public int find(E e){
        for(int i=0;i < size;i++){
            if(data[i].equals(e))
                return i;
        }
        return -1;
    }

    // 删除指定位置的元素，防止复杂度的震荡，
    // 懒缩容。
    public E remove(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed, Index is illegal");
        E ret = data[index];
        if(size-1 == data.length / 4 && data.length / 2 != 0){
            // 懒惰缩容，防止复杂度震荡，当数组的size小于capacity的四分之一才开始缩容
            E[] newData = (E[])new Object[data.length / 2];
            for(int i = 0; i < index; i++){
                newData[i] = data[i];
            }
            for(int i = index; i < size - 1;i++){
                newData[i] = data[i+1];
            }
            data = newData;
        } else {
            for(int i = index; i < size-1;i ++)
                data[i] = data[i+1];
        }

        size --;
//        data[size] = null; // 回收内存，可选
//        // loitering objects != memory leak
        return ret;
    }

    // 删除的快捷方法
    public E removeFirst(){
        return remove(0);
    }
    public E removeLast(){
        return remove(size -1);
    }
    // 删除指定的元素e
    public void removeElement(E e){
        int index = find(e);
        if(index != -1){
            remove(index);
        }
    }
    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
//        res.append(String.format("datastructure.array.Array: size = %d , capacity = %d\n", size, data.length));
        res.append(String.format("datastructure.array.Array: size = %d , capacity = %d\n", size, data.length));
        res.append('[');
        for(int i = 0; i < size; i++) {
            res.append(data[i]);
            if(i != size - 1)
                res.append(", ");
        }
        res.append(']');
        return res.toString();
    }

    private void resize(int newCapacity){
        E[] newData = (E[])new Object[newCapacity];
        for(int i = 0; i < size; i++){
            newData[i] = data[i];
        }
        data = newData;
    }
}

datastructure.stack.Student

public class datastructure.stack.Student {

    private String name;
    private int score;

    public datastructure.stack.Student(String studentName, int studentScore){
        name = studentName;
        score = studentScore;
    }

    @Override
    public String toString(){
        return String.format("datastructure.stack.Student(name: %s, score:%d", name, score);
    }

    public static void main(String[] args){

        datastructure.array.Array<datastructure.stack.Student> arr = new datastructure.array.Array<>();
        arr.addLast(new datastructure.stack.Student("Alex", 99));
        arr.addLast(new datastructure.stack.Student("Egon", 100));
        arr.addLast(new datastructure.stack.Student("Peiqi", 98));
        System.out.println(arr);
    }
}

datastructure.datastructure.linkedList.bannerySearchTree.Main

public class datastructure.datastructure.linkedList.bannerySearchTree.Main {

    public static void main(String[] args) {

        datastructure.array.Array<Object> arr = new datastructure.array.Array<>(3);
        Integer Int = 100;
        Double Dou = 12.54;
        String Str = "哈哈大圣";
        datastructure.stack.Student LingTing = new datastructure.stack.Student("lingting", 100);

        arr.addLast(Int);
        arr.addLast(Dou);
        arr.addLast(Str);
        arr.addLast(LingTing);
        System.out.println(arr);
        arr.remove(1);
        arr.remove(1);
        System.out.println(arr);
        arr.remove(1);
        System.out.println(arr);
    }
}