ArrayList

ArrayList：順序表

我們可以將順序表的底層理解成為一個陣列（可以擴容的陣列），但是相比于陣列多出一個記錄有效資料的計數器size，如：

順序表和陣列的區別：

上面說，順序表的底層可以理解為一個陣列，但是相比于陣列，更加的高級，
順序表可以自己擴容；
順序表嚴格區分陣列容量和元素的個數，
所以陣列其實就是一種不完備的順序表，

順序表中的注意點：

我們需要區分順序表中的兩個概念：容量（capacity）和元素個數（size），
容量可以理解為陣列的大小（長度），元素個數是size中記錄的有效元素個數，
順序表中，資料的存盤是需要連續的，不可以元素和元素之間存在“空隙”，當進行插入、洗掉等操作時，操作完成后，也要保證順序表的連續，

ArrayList的常用方法

在Java中，內置了ArrayList的許多方法，我們常用的一些方法（增刪改查），如下：

    //尾插
    boolean add(Integer e);
    //指定位置插入
    void add(int index, Integer e);
    //洗掉指定位置
    Integer remove(int index);
    //洗掉指定元素
    boolean remove(Integer e);
    //獲取元素
    Integer get(int index);
    //set
    Integer set(int index, Integer e);
    //判斷是否包含
    boolean contains(Integer e);
    //從前到后首次遇到
    int indexOf(Integer e);
    //從后到前首次遇到
    int lastIndexOf(Integer e);
    //請空順序表
    void clear();
    //獲取元素個數
    int size();
    //判斷size==0？
    boolean isEmpty();

模擬實作ArrayList的常用方法

當我們需要模擬實作ArrayList的時候，我們需要先創建一個陣列，和計數器size，
我們需要考慮到陣列連續性的問題，以及操作中判斷陣列是否滿了，需要2倍擴容的題，以及下標合法性校驗…

1、定義介面，列出需要實作的方法：

package ArrayList;
public interface MyList {
    //尾插
    boolean add(Integer e);
    //指定位置插入
    void add(int index, Integer e);
    //洗掉指定位置
    Integer remove(int index);
    //洗掉指定元素
    boolean remove(Integer e);
    //獲取元素
    Integer get(int index);
    //set
    Integer set(int index, Integer e);
    //判斷是否包含
    boolean contains(Integer e);
    //從前到后首次遇到
    int indexOf(Integer e);
    //從后到前首次遇到
    int lastIndexOf(Integer e);
    //請空順序表
    void clear();
    //獲取元素個數
    int size();
    //判斷size==0？
    boolean isEmpty();
}

2、具體實作：

package ArrayList;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 模擬實作自己的ArrayList
 */
public class MyArrayList implements MyList {
    private Integer[] array;
    private int size;

    public MyArrayList() {
        array = new Integer[10];
        size = 0;
    }

    //判斷是否滿了
    private void isFull() {
        if (size < array.length) {
            return;
        }
        Integer[] arr = new Integer[array.length * 2];
        //注意： 沒有Integer型別的copyOf方法，
        //arr = Arrays.copyOf(array, array.length);
        for (int i=0;i<array.length;i++){
            arr[i]=array[i];
        }
        this.array = arr;
    }


    @Override
    public boolean add(Integer e) {
        isFull();
        array[size] = e;
        size++;
        return true;
    }

    @Override
    public void add(int index, Integer e) {
        isFull();
        if (index < 0 || index > size()) {
            // 下標不合法
            throw new ArrayIndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        for (int from = size() - 1; from >= index; from--) {
            array[from + 1] = array[from];
        }
        array[index] = e;
        size++;
    }

    @Override
    public Integer remove(int index) {
        if (index < 0 || index >= size()) {
            // 下標不合法
            throw new ArrayIndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        Integer e = array[index];
        for (int from = index + 1; from < size; from++) {
            array[from - 1] = array[from];
        }
        array[size - 1] = null;
        size--;
        return e;
    }

    @Override
    public boolean remove(Integer e) {

        int i = indexOf(e);
        if (i < 0) {
            return false;
        }
        remove(i);
        return true;
    }

    @Override
    public Integer get(int index) {
        if (index < 0 || index >= size()) {
            // 下標不合法
            throw new ArrayIndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        return array[index];
    }

    @Override
    public Integer set(int index, Integer e) {
        if (index < 0 || index >= size()) {
            // 下標不合法
            throw new ArrayIndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        Integer old = array[index];
        array[index] = e;
        return old;
    }

    @Override
    public boolean contains(Integer e) {
        return indexOf(e) >= 0;
    }

    @Override
    public int indexOf(Integer e) {
        for (int i = 0; i < size(); i++) {
            if (array[i].equals(e)) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public int lastIndexOf(Integer e) {
        for (int i = size() - 1; i >= 0; i--) {
            if (array[i].equals(e)) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public void clear() {
        Arrays.fill(array, null);
        size = 0;
    }

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

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

    @Override
    public String toString() {

        Integer[] toShow = Arrays.copyOf(array, size);
        return Arrays.toString(toShow);
    }
}

3、測驗

package ArrayList;

public class MyArrayListDemo {
    public static void main(String[] args) {
        MyList list = new MyArrayList();
        System.out.println(list);   // []
        list.add(1);
        list.add(2);
        list.add(3);
        System.out.println(list);   // [1, 2, 3]
        list.add(0, 100);
        list.add(0, 200);
        list.add(0, 300);
        System.out.println(list);   // [300, 200, 100, 1, 2, 3]

        Integer remove = list.remove(2);
        System.out.println(list);   // [300, 200, 1, 2, 3]
        System.out.println(remove); // 100

        boolean r = list.remove((Integer)1);    // 通過型別轉換，確認呼叫的是 remove(Integer) 而不是 remove(int)
        System.out.println(r);      // true
        System.out.println(list);   // [300, 200, 2, 3]

        System.out.println(list.size());
        System.out.println(list.isEmpty());
        list.clear();
        System.out.println(list.size());
        System.out.println(list.isEmpty());
    }
}

4、結果：

總結：我發現資料結構的邏輯性很強，需要慢慢的思考，結合圖形，加深理解！！！