一、什么是數(shù)據(jù)結(jié)構(gòu)

(1) 概念

?? 數(shù)據(jù)結(jié)構(gòu)是計算機(jī)存儲、組織數(shù)據(jù)的方式

(2) 分類

?? 線性結(jié)構(gòu)

• 線性表（數(shù)組、鏈表、棧、隊列、哈希表）

?? 樹形結(jié)構(gòu)

• 二叉樹
• AVL 樹
• 紅黑樹
• B 樹
• 堆
• Trie
• 哈夫曼樹
• 并查集

?? 圖形結(jié)構(gòu)

• 鄰接矩陣
• 鄰接表

二、線性表

?? 線性表是具有 n 個相同類型元素的有限序列（n >= 0）

• a1 是首節(jié)點(diǎn)（首元素）， an 是尾結(jié)點(diǎn)（尾元素）
• a1 是 a2 的前驅(qū)
• a2 是 a1 的后繼

常見的線性表有：
??? 數(shù)組
??? 鏈表
??? 棧
??? 隊列
??? 哈希表（散列表）

三、數(shù)組（Array）

(1) 數(shù)組的底層結(jié)構(gòu)

?? 數(shù)組是一種順序存儲的線性表，全部元素的內(nèi)存地址是連續(xù)的

// 【new】向堆空間申請一段存儲空間
int[] array = new int[]{11, 22, 33};

(2) 數(shù)組缺點(diǎn)

• ??數(shù)組有個致命的缺點(diǎn)：無法動態(tài)修改容量
• ??數(shù)組創(chuàng)建完畢后，能夠存儲的數(shù)據(jù)就固定了
• ??數(shù)組操縱元素的方式不夠面向?qū)ο?/li>

?? 自己實現(xiàn)動態(tài)數(shù)組，彌補(bǔ)數(shù)組的缺點(diǎn)

四、動態(tài)數(shù)組（Dynamic Array）接口設(shè)計

public interface List<E> {
    /**
     * 元素的數(shù)量
     */
    int size();

    /**
     * 是否為空
     */
    boolean isEmpty();

    /**
     * 是否包含某個元素
     */
    boolean contains(E element);

    /**
     * 添加元素到最后面
     */
    void add(E element);

    /**
     * 返回 index 位置對應(yīng)的元素
     */
    E get(int index);

    /**
     * 設(shè)置 index 位置的元素
     */
    E set(int index, E element);

    /**
     * 往 index 位置添加元素
     */
    void add(int index, E element);

    /**
     * 刪除 index 位置對應(yīng)的元素
     */
    E remove(int index);

    /**
     * 返回元素的下標(biāo)
     */
    int indexOf(E element);

    /**
     * 清空數(shù)組
     */
    void clear();
}

五、動態(tài)數(shù)組的設(shè)計和基本代碼實現(xiàn)

(1) 成員變量

Java 中的成員變量會自動初始化，比如：
?? int 類型自動初始化為 0
?? 對象類型自動初始化為 null

?? size 記錄動態(tài)數(shù)組中元素的個數(shù)
?? elements 用于實際存儲數(shù)據(jù)
?? 動態(tài)數(shù)組的底層是數(shù)組

(2) 代碼

/**
 * 只支持存儲 int 類型數(shù)據(jù)的動態(tài)數(shù)組
 */
public class ArrayListInt {
    private int size;
    private int[] elements;

    public static final int DEFAULT_CAPACITY = 10;
    public static final int ELEMENT_NOT_FOUND = -1;

    public ArrayListInt() {
        this(DEFAULT_CAPACITY);
    }

    public ArrayListInt(int capacity) {
        capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
        elements = new int[capacity];
    }

    public int size() {
        return size;
    }

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

    /**
     * 獲取 index 索引處的元素
     */
    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("size: " + size + ", " + "index: " + index);
        }

        return elements[index];
    }

    /**
     * 設(shè)置 index 位置的元素
     *
     * @param index   下標(biāo)
     * @param element 要設(shè)置的元素
     * @return 原來的元素?
     */
    public int set(int index, int element) {
        // 獲取 index 位置的元素
        int old = get(index);
        elements[index] = element;

        return old;
    }

    /**
     * 返回元素的索引
     */
    public int indexOf(int element) {
        // 如果數(shù)組為空, 直接找不到
        if (isEmpty()) return ELEMENT_NOT_FOUND;

        for (int i = 0; i < size; i++) {
            if (element == elements[i]) return i;
        }
        return ELEMENT_NOT_FOUND;
    }

    /**
     * 檢查數(shù)組中是否包含 element 元素
     */
    public boolean contains(int element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    /**
     * 清除全部元素
     * 只要【size = 0】就無法獲取到數(shù)組中的任何元素了
     */
    public void clear() {
        size = 0;
    }

}

① get ()

?? 該方法的作用：獲取 index 索引處的元素
?? 數(shù)組可通過索引獲取到元素
?? 要做參數(shù)（index）校驗

② indexOf ()

?? 返回某個元素的索引
?? 遍歷每個下標(biāo)的元素，拿數(shù)組中的每個元素和參數(shù)元素進(jìn)行比較

③ clear ()

?? 清除全部元素（清空數(shù)組）
?? 在當(dāng)前的代碼中，只要【size = 0】就無法獲取到數(shù)組中的任何元素了（就可以理解為清空了數(shù)組）

六、add 方法和擴(kuò)容

?? add(int element)：往數(shù)組的尾部添加元素 element
?? add(int index, int element)：往數(shù)組的 index 索引位置添加元素 element

(1) add (int element)

??? 每次往尾部添加元素的時候，是往數(shù)組的索引為 size 位置添加元素

public class ArrayListInt {

    /**
     * 往數(shù)組尾部添加元素
     */
    public void add(int element) {
        // TODO 擴(kuò)容檢測
        elements[size++] = element;
    }

}

(2) 打印動態(tài)數(shù)組中的元素

☆寫法1：

public class ArrayListInt {

    /**
     * 遍歷打印數(shù)組中的元素
     */
    public String printElements() {
        StringBuilder sb = new StringBuilder();
        sb.append("{size=").append(size).append(", [");

        for (int i = 0; i < size; i++) {
            sb.append(elements[i]);
            if (i != size - 1) {
                sb.append(", ");
            }
        }

        sb.append("]}");

        return sb.toString();
    }

}

?? 遍歷獲取數(shù)組中的各個元素，然后進(jìn)行拼接
?? Java 中大量字符串拼接用 StringBuilder 最好

☆寫法2：

public class ArrayListInt {
 
    /**
     * 遍歷打印數(shù)組中的元素
     */
    public String printElements() {
        StringBuilder sb = new StringBuilder();
        sb.append("{size=").append(size).append(", [");

        for (int i = 0; i < size; i++) {
            // 不是第 0 個元素就先拼接【, 】
            if (i != 0) {
                sb.append(", ");
            }

            sb.append(elements[i]);
        }

        sb.append("]}");

        return sb.toString();
    }

}

?? 不是第 0 個元素就先拼接【, 】
?? 相比寫法1每次循環(huán)少了一次減法運(yùn)算

(3) add (int index, int element)

☆ 往 index 位置插入元素 element
?? 把 index 位置到 size - 1 位置【[index, size-1]】的元素往后挪動【空出 index 位置的元素】
?? 把 element 元素賦值到 index 索引位置
?? 從 索引為 size - 1 處開始挪動

public class ArrayListInt {

    /**
     * 在 index 位置插入元素 element
     */
    public void add(int index, int element) {
        // 當(dāng) index 等于 size 的時候, 是往數(shù)組的尾部添加元素
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("size: " + size + ", " + "index: " + index);
        }

        // TODO 擴(kuò)容檢測

        // 挪動元素（從最后一個元素開始挪動）
        for (int i = size - 1; i >= index; i--) {
            elements[i + 1] = elements[i];
        }

        // 把元素 element 賦值到 index 索引位置
        elements[index] = element;
        size++; // 數(shù)組元素加1
    }

}

(4) 數(shù)組越界異常的封裝

public class ArrayListInt {

    public void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("index: " + index + " size: " + size);
    }

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

    public void rangeCheck4Add(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }

}

?? outOfBounds(int index)：封裝拋異常的方法
?? rangeCheck(int index)：索引 index 不能小于 0 或 大于等于 size，否則都會數(shù)組越界
?? rangeCheck4Add(int index)：添加元素的時候 index 是可以等于 size 的（此時是往數(shù)組的最后添加元素）

(5) MyJunit（接口測試）

??使用異常知識進(jìn)行接口測試：當(dāng)測試不通過的時候，會拋異常
??測試通過的時候，打印 Success!

public class MyJunit {

    public static void test(boolean boolean_) {
        try {
            if (!boolean_) throw new Exception("測試不通過");
            System.out.println("\nSuccess!");
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

}

(6) 擴(kuò)容【 ensureCapacity() 】

??① 申請全新的數(shù)組空間（容量適宜）
??② 把就數(shù)據(jù)的數(shù)據(jù)復(fù)制到全新的數(shù)組中
?? 添加的時候才會考慮擴(kuò)容操作

    /**
     * 擴(kuò)容檢測
     *
     * @param capacity 數(shù)組容量至少是 capacity
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        // 如果所需容量足夠, 則不擴(kuò)容
        if (oldCapacity >= capacity) return;

        // 申請全新的數(shù)組空間（新容量是舊容量的 1.5 倍）
        capacity = oldCapacity + (oldCapacity >> 1);
        int[] newElements = new int[capacity];

        // 把舊數(shù)組中的數(shù)據(jù)復(fù)制到新數(shù)組中
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }

        // elements 指針指向新數(shù)組
        elements = newElements;

        System.out.println(oldCapacity + "擴(kuò)容為" + capacity);
    }

七、remove (int index)

?? 作用：刪除 index 索引處的元素，返回之前 index 索引處的元素

?? 思路：① 用后面的元素把要 刪除的索引 index 位置的元素覆蓋掉
?? ② 數(shù)組 size 減 1
?? ③ 如何覆蓋? 遍歷

public class ArrayListInt {

    /**
     * 刪除 index 位置的元素
     *
     * @param index 下標(biāo)
     * @return 原來的元素
     */
    public int remove(int index) {
        // 取出 index 索引處原來的元素
        int old = get(index);

        // 覆蓋掉 index 索引處的元素
        for (int i = index; i < size; i++) {
            elements[i] = elements[i + 1];
        }

        // 最后一個元素不被訪問到的關(guān)鍵代碼
        size--;

        return old;
    }

}

八、僅能存儲 int 類型的動態(tài)數(shù)組 ArrayListInt 完整代碼

/**
 * 只支持存儲 int 類型數(shù)據(jù)的動態(tài)數(shù)組
 */
@SuppressWarnings("all")
public class ArrayListInt {
    private int size;
    private int[] elements;

    public static final int DEFAULT_CAPACITY = 10;
    public static final int ELEMENT_NOT_FOUND = -1;

    public ArrayListInt() {
        this(DEFAULT_CAPACITY);
    }

    public ArrayListInt(int capacity) {
        capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
        elements = new int[capacity];
    }

    public int size() {
        return size;
    }

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

    /**
     * 獲取 index 索引處的元素
     */
    public int get(int index) {
        rangeCheck(index);

        return elements[index];
    }

    /**
     * 設(shè)置 index 位置的元素
     *
     * @param index   下標(biāo)
     * @param element 要設(shè)置的元素
     * @return 原來的元素?
     */
    public int set(int index, int element) {
        // 獲取 index 位置的元素
        int old = get(index);
        elements[index] = element;

        return old;
    }

    /**
     * 返回元素的索引
     */
    public int indexOf(int element) {  
        for (int i = 0; i < size; i++) {
            if (element == elements[i]) return i;
        }
        return ELEMENT_NOT_FOUND;
    }

    /**
     * 檢查數(shù)組中是否包含 element 元素
     */
    public boolean contains(int element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    /**
     * 清除全部元素
     * 只要【size = 0】就無法獲取到數(shù)組中的任何元素了
     */
    public void clear() {
        size = 0;
    }

    /**
     * 往數(shù)組尾部添加元素
     */
    public void add(int element) {
        add(size, element);
    }


    /**
     * 在 index 位置插入元素 element
     */
    public void add(int index, int element) {
        rangeCheck4Add(index);

        // 擴(kuò)容檢測, 保證容量至少是【size+1】
        ensureCapacity(size + 1);

        // 挪動元素（從最后一個元素開始挪動）
        for (int i = size - 1; i >= index; i--) {
            elements[i + 1] = elements[i];
        }

        // 把元素 element 賦值到 index 索引位置
        elements[index] = element;
        size++; // 數(shù)組元素加1
    }

    /**
     * 擴(kuò)容檢測
     *
     * @param capacity 數(shù)組容量至少是 capacity
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        // 如果所需容量足夠, 則不擴(kuò)容
        if (oldCapacity >= capacity) return;

        // 申請全新的數(shù)組空間（新容量是舊容量的 1.5 倍）
        capacity = oldCapacity + (oldCapacity >> 1);
        int[] newElements = new int[capacity];

        // 把舊數(shù)組中的數(shù)據(jù)復(fù)制到新數(shù)組中
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }

        // elements 指針指向新數(shù)組
        elements = newElements;

        System.out.println(oldCapacity + "擴(kuò)容為" + capacity);
    }

    /**
     * 刪除 index 位置的元素
     *
     * @param index 下標(biāo)
     * @return 原來的元素
     */
    public int remove(int index) {
        // 取出 index 索引處原來的元素
        int old = get(index);

        // 覆蓋掉 index 索引處的元素
        for (int i = index; i < size - 1; i++) {
            elements[i] = elements[i + 1];
        }

        // 最后一個元素不被訪問到的關(guān)鍵代碼
        size--;

        return old;
    }

    public void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("index: " + index + " size: " + size);
    }

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

    public void rangeCheck4Add(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }

    /**
     * 遍歷打印數(shù)組中的元素
     */
    public String printElements() {
        StringBuilder sb = new StringBuilder();
        sb.append("{size=").append(size).append(", [");

        for (int i = 0; i < size; i++) {
            // 不是第 0 個元素就拼接【, 】
            if (i != 0) {
                sb.append(", ");
            }

            sb.append(elements[i]);
        }

        sb.append("]}");

        return sb.toString();
    }

}

九、泛型（讓動態(tài)數(shù)組中能存放各種類型的數(shù)據(jù)）

?? 可使用 Java 中的泛型讓動態(tài)數(shù)據(jù)更加通用（在動態(tài)數(shù)組中能存放任何數(shù)據(jù)類型的數(shù)據(jù)）

(1) clear () 【對象數(shù)組】

?? 當(dāng)動態(tài)數(shù)組中可以存儲任何類型的時候，對于 clear() 方法，僅僅把 size 設(shè)置為 0 是不夠的
?? 把 size 設(shè)置為 0 后，雖然使用動態(tài)數(shù)組的人無法獲取到任何數(shù)據(jù)，但這些數(shù)據(jù)仍然存活在內(nèi)存中【這些數(shù)據(jù)依然存在，只是你無法使用它而已】
?? 最佳的方式是：把 size 設(shè)置為 0，并把這些內(nèi)存都回收掉（置為 null）

    /**
     * 清除全部元素
     */
    public void clear() {
        // 銷毀堆空間的對象數(shù)據(jù)
        for (int i = 0; i < elements.length; i++) {
            elements[i] = null;
        }
        
        size = 0;
    }

(2) 對象的比較不用 【==】

?? 兩個 對象用 == 運(yùn)算符進(jìn)行比較的時候，比較的是兩個對象的內(nèi)存地址
?? 若不想比較兩個對象的內(nèi)存地址，需要用 equals() 方法

    public int indexOf(E element) {
        if (element == null) return ELEMENT_NOT_FOUND;

        // 如果數(shù)組為空, 直接找不到
        if (isEmpty()) return ELEMENT_NOT_FOUND;

        for (int i = 0; i < size; i++) {
            if (element.equals(elements[i])) return i;
        }
        return ELEMENT_NOT_FOUND;
    }

(3) remove (int index) 清空最后一個元素

    /**
     * 刪除 index 位置的元素
     *
     * @param index 下標(biāo)
     * @return 原來的元素
     */
    public E remove(int index) {
        // 取出 index 索引處原來的元素
        E old = get(index);

        // 覆蓋掉 index 索引處的元素
        for (int i = index + 1; i < size; i++) {
            elements[i - 1] = elements[i];
        }

        // 把最后一個元素置空
        elements[--size] = null;

        return old;
    }

(4) null 值處理

動態(tài)數(shù)組中應(yīng)該要能夠存放 null 值

    /**
     * 返回元素的索引
     */
    public int indexOf(E element) {
        if (null == element) {
            for (int i = 0; i < size; i++) {
                if (elements[i] == null) return i;
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (element.equals(elements[i])) return i;
            }
        }

        return ELEMENT_NOT_FOUND;
    }

(5) ArrayList 完整代碼

/**
 * 泛型讓動態(tài)數(shù)組中能存放任何數(shù)據(jù)類型的數(shù)據(jù)
 */
@SuppressWarnings("all")
public class ArrayList<E> {
    private int size;
    private E[] elements;

    public static final int DEFAULT_CAPACITY = 10;
    public static final int ELEMENT_NOT_FOUND = -1;

    public ArrayList() {
        this(DEFAULT_CAPACITY);
    }

    public ArrayList(int capacity) {
        capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;

        elements = (E[]) new Object[capacity];
    }

    public int size() {
        return size;
    }

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

    /**
     * 獲取 index 索引處的元素
     */
    public E get(int index) {
        rangeCheck(index);

        return elements[index];
    }

    /**
     * 設(shè)置 index 位置的元素
     *
     * @param index   下標(biāo)
     * @param element 要設(shè)置的元素
     * @return 原來的元素?
     */
    public E set(int index, E element) {
        // 獲取 index 位置的元素
        E old = get(index);
        elements[index] = element;

        return old;
    }

    /**
     * 返回元素的索引
     */
    public int indexOf(E element) {
        if (null == element) {
            for (int i = 0; i < size; i++) {
                if (elements[i] == null) return i;
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (element.equals(elements[i])) return i;
            }
        }

        return ELEMENT_NOT_FOUND;
    }

    /**
     * 檢查數(shù)組中是否包含 element 元素
     */
    public boolean contains(E element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    /**
     * 清除全部元素
     */
    public void clear() {
        // 銷毀堆空間的對象數(shù)據(jù)
        for (int i = 0; i < elements.length; i++) {
            elements[i] = null;
        }

        size = 0;
    }

    /**
     * 往數(shù)組尾部添加元素
     */
    public void add(E element) {
        add(size, element);
    }

    /**
     * 在 index 位置插入元素 element
     */
    public void add(int index, E element) {
        rangeCheck4Add(index);

        // 擴(kuò)容檢測, 保證容量至少是【size + 1】
        ensureCapacity(size + 1);

        // 挪動元素（從最后一個元素開始挪動）
        for (int i = size - 1; i >= index; i--) {
            elements[i + 1] = elements[i];
        }

        // 把元素 element 賦值到 index 索引位置
        elements[index] = element;
        size++; // 數(shù)組元素加1
    }


    /**
     * 擴(kuò)容檢測
     *
     * @param capacity 數(shù)組容量至少是 capacity
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        // 如果所需容量足夠, 則不擴(kuò)容
        if (oldCapacity >= capacity) return;

        // 申請全新的數(shù)組空間（新容量是舊容量的 1.5 倍）
        capacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[capacity];

        // 把舊數(shù)組中的數(shù)據(jù)復(fù)制到新數(shù)組中
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }

        // elements 指針指向新數(shù)組
        elements = newElements;

        System.out.println(oldCapacity + "擴(kuò)容為" + capacity);
    }

    /**
     * 刪除 index 位置的元素
     *
     * @param index 下標(biāo)
     * @return 原來的元素
     */
    public E remove(int index) {
        // 取出 index 索引處原來的元素
        E old = get(index);

        // 覆蓋掉 index 索引處的元素
        for (int i = index + 1; i < size; i++) {
            elements[i - 1] = elements[i];
        }

        // 把最后一個元素置空
        elements[--size] = null;

        return old;
    }

    public void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("index: " + index + " size: " + size);
    }

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

    public void rangeCheck4Add(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }

    /**
     * 遍歷打印數(shù)組中的元素
     */
    public String printElements() {
        StringBuilder sb = new StringBuilder();
        sb.append("{size=").append(size).append(", [");

        for (int i = 0; i < size; i++) {
            // 不是第 0 個元素就拼接【, 】
            if (i != 0) {
                sb.append(", ");
            }

            sb.append(elements[i]);
        }

        sb.append("]}");

        return sb.toString();
    }

}

JDK 中內(nèi)置了動態(tài)數(shù)組類：java.util.ArrayList

如有錯誤和疑問，歡迎和我交流文章來源地址http://www.zghlxwxcb.cn/news/detail-499815.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】1、學(xué)習(xí)動態(tài)數(shù)組數(shù)據(jù)結(jié)構(gòu)（基本模擬實現(xiàn) Java 的 ArrayList 實現(xiàn)增刪改查）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！