【數(shù)據(jù)結(jié)構(gòu)與算法】 01 - 動(dòng)態(tài)數(shù)組

1. 什么是數(shù)據(jù)結(jié)構(gòu) ？

  1. 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)組織數(shù)據(jù)的方式。

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

  1. 數(shù)組、鏈表、棧、隊(duì)列、哈希表。

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

  1. 二叉樹、AVL樹、紅黑樹、B樹、堆、Trie、哈夫曼樹、并查集。

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

  1. 鄰接矩陣、鄰接表。

2. 線性表

  1. 線性表是有n個(gè)相同類型元素的有限序列。（n >= 0）。
線性表

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

2.1 常見的線性表

  1. 數(shù)組。

  2. 鏈表。

  3. 棧。

  4. 隊(duì)列。

  5. 哈希表(散列表)。

2.2 數(shù)組

  1. 數(shù)組是一種順序存儲(chǔ)的線性表，所有元素的 內(nèi)存地址都是連續(xù)的 。
數(shù)組

  1. 在很多編程語言中，數(shù)組都有一個(gè)致命的缺點(diǎn)：無法動(dòng)態(tài)的修改容量。

  2. 在實(shí)際開發(fā)中，我們希望數(shù)組容量是可以動(dòng)態(tài)改變的。

2.3 動(dòng)態(tài)數(shù)組

動(dòng)態(tài)數(shù)組的簡(jiǎn)單實(shí)現(xiàn) （int類型）
  1. 定義一個(gè)ArrayList 類。
  1. 定義成員和靜態(tài)變量 ：
    /**
     * 數(shù)組的尺寸
     */
    private int size = 0;

    /**
     * 數(shù)組實(shí)例
     */
    private int[] elements;

    /**
     * 定義一個(gè)默認(rèn)的數(shù)組容量 為 10
     */
    private static final int DEFAULT_CAPACITY = 10;
    /**
     * 元素未找到 返回 -1
     */
    private static final int ELEMENT_NOT_FOUNT = -1;
  1. 定義有參構(gòu)造和無參構(gòu)造用于初始化數(shù)組：
    /**
     * 無參構(gòu)造，通過this(param) 調(diào)用有參構(gòu)造
     */
    public ArrayList() {
        // this() 調(diào)用自身有參構(gòu)造函數(shù)
        this(DEFAULT_CAPACITY);
    }

    /**
     * 定義有參構(gòu)造方便進(jìn)行初始化
     *
     * @param capacity
     */
    public ArrayList(int capacity) {
         // 如果傳遞的容量 小于默認(rèn)的容量將使用默認(rèn)容量 否則使用傳遞的數(shù)組容量
        capacity = capacity < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : capacity;
        elements = new int[capacity];
    }
  1. size() 方法 返回?cái)?shù)組的長(zhǎng)度：
   /**
     * 返回?cái)?shù)組中元素的個(gè)數(shù)
     *
     * @return
     */
    public int size() {
        return size;
    }
  1. isEmpty() 判斷當(dāng)前數(shù)組是否為空：
   /**
     * 數(shù)組是否為空
     *
     * @return
     */
    public boolean isEmpty() {
        // 判斷size 是不是等于 0 即可 如果size == 0 表示 數(shù)組是空的
        return size == 0;
    }
  1. contains(int element) 判斷數(shù)組中是否包含某個(gè)元素：
  public boolean contains(T element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }
  1. void add(int element) 向數(shù)組中添加指定的元素:
 public void add(int element) {
        // size是動(dòng)態(tài)變化的 初始值是 0 添加第一個(gè)元素 在添加完成一個(gè)元素最后將 size + 1 操作
        // elements[size++] = element;
        // 直接調(diào)用在指定位置添加元素的方法
        add(size, element);
    }
  1. int get(int index) 返回指定index處的元素:
 public int get(int index) {
        // 首先判斷一下傳遞進(jìn)來的索引值是否合法
        rangeCheck(index);
        return elements[index];
    }
  1. int set(int index, int element) 設(shè)置index位置的元素為某值,并返回之前的值:
public int set(int index, int element) {
        // 首先判斷一下傳遞進(jìn)來的索引值是否合法
        rangeCheck(index);
        int old = elements[index];
        elements[index] = element;
        return old;
    }
  1. void add(int index, int element) 向指定位置添加元素 ：
簡(jiǎn)單圖解
public void add(int index, int element) {
        // 這里index的范圍是允許等于size的因?yàn)椴迦氲臅r(shí)候可能是在最后一個(gè)位置插入一個(gè)元素
        rangeCheckForAd(index);
        for (int i = size - 1; i >= index; i--) {
            elements[i + 1] = elements[i];
        }
        // 將空出的位置填入值
        elements[index] = element;
        // size 加一
        size++;
    }
  1. int remove(int index) 刪除index位置的元素 并返回刪除的值: 由于數(shù)組的內(nèi)存地址是連續(xù)的，無法直接挖掉某個(gè)元素，所以必須將數(shù)組進(jìn)行移動(dòng)，刪除元素。
簡(jiǎn)單圖解

圖中需要將 index = 3 位置的元素 55 刪除 ，需要移動(dòng)的范圍是 [4,6],未移動(dòng)之前的數(shù)組 size = 7 , index = 3. 得出需要移動(dòng)的通項(xiàng) [index + 1 , size - 1]

public int remove(int index) {
        rangeCheck(index);
        // 記錄一下即將需要?jiǎng)h除的值
        int old = elements[index];

        // 循環(huán)的范圍就是需要移動(dòng)的元素的范圍 ， 因?yàn)樾枰苿?dòng)這么多個(gè)元素 從 [index + 1,size -1]
        for (int i = index + 1; i <= size - 1; i++) {
            elements[i - 1] = elements[i];
        }
        // 長(zhǎng)度減一
        size--;
        return old;
    }
  1. int indexOf(int element) 查找元素在數(shù)組中的位置:
public int indexOf(int element) {
        for (int i = 0; i < size; i++) {
            if (elements[i] == element) {
                return i;
            }
        }
        return ELEMENT_NOT_FOUNT;
    }
  1. void clear() 清除數(shù)組中所有元素:
public void clear() {
        size = 0;
    }
  1. 重寫默認(rèn)的 toString() 方法 ：
 @Override
    public String toString() {
        // 字符串拼接使用StringBuilder 提高效率
        StringBuilder str = new StringBuilder();

        // 拼接格式 size = 3 [88,33,99]
        str.append("size = ").append(size).append(" [ ");

        for (int i = 0; i < size; i++) {
            // 和 i != size -1 對(duì)比優(yōu)先選擇 i != 0, 因?yàn)?size - 1 需要進(jìn)行一次運(yùn)算
            if (i != 0) {
                str.append(", ");
            }
            str.append(elements[i]);
        }

        str.append("]");
        return str.toString();
    }

15 . 檢查 index 的范圍：

  /**
     * 檢查index的范圍
     *
     * @param index
     */
    private void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            // index 是傳遞的索引 >= size 表示該索引已經(jīng)越界
            ouOfBound(index);
        }
    }

    /**
     * 統(tǒng)一拋出異常
     *
     * @param index
     */
    private void ouOfBound(int index) {
        throw new IndexOutOfBoundsException("index:" + index + "size:" + size);
    }
  1. 檢查 index的范圍-添加元素時(shí)是允許 size == index :
  /**
     * 判斷添加元素時(shí)的index 的范圍
     *
     * @param index
     */
    private void rangeCheckForAdd(int index) {
        // 添加的時(shí)候可能是添加到了最后一個(gè)元素 所以是允許 index 等于 size的
        if (index < 0 || index > size) {
            // index 是傳遞的索引 >= size 表示該索引已經(jīng)越界
            ouOfBound(index);
        }
    }

2.4 細(xì)節(jié)優(yōu)化

使用泛型改寫動(dòng)態(tài)數(shù)組
@SuppressWarnings("all")
public class ArrayList<T> {

    /**
     * 記錄的是數(shù)組的尺寸
     */
    private int size = 0;

    /**
     * 定義一個(gè)數(shù)組
     */
    private T[] elements;

    /**
     * 數(shù)組默認(rèn)容量
     */
    private final static int DEFAULT_CAPACITY = 10;

    /**
     * 元素未找到的時(shí)候返回 -1
     */
    private final static int ELEMENT_NOT_FOUND = -1;


    /**
     * 無參構(gòu)造調(diào)用有參構(gòu)造
     */
    public ArrayList() {
        this(DEFAULT_CAPACITY);
    }

    /**
     * @param capacicy
     */
    public ArrayList(int capacicy) {
        // 判斷當(dāng)前傳遞的數(shù)組容量和默認(rèn)的數(shù)組容量 如果傳遞容量小于默認(rèn)的容量就使用默認(rèn)的數(shù)組容量
        capacicy = capacicy < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : capacicy;
        // 如果是 int 分配的是連續(xù)的四十個(gè)字節(jié)
        // 對(duì)象數(shù)組中存儲(chǔ)的是對(duì)象的地址值 因?yàn)椴煌瑢?duì)象大占用的內(nèi)存空間可能是不一樣的
        // 對(duì)象不再不引用的時(shí)候就會(huì)被釋放
        elements = (T[]) new Object[capacicy];
    }

    /**
     * 返回?cái)?shù)組的尺寸
     *
     * @return
     */
    public int size() {
        return size;
    }

    /**
     * 判斷數(shù)組是否為空
     *
     * @return
     */
    public boolean isEmpty() {
        // 如果size 等于 0 表示數(shù)組為空
        return size == 0;
    }

    /**
     * 判斷數(shù)組中是否存在某個(gè)元素
     *
     * @param element
     * @return
     */
     public boolean contains(T element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
     }

    /**
     * 向數(shù)組末尾添加一個(gè)元素
     *
     * @param element
     */
    public void add(T element) {
        add(size, element);
    }

    /**
     * 向數(shù)組中指定位置添加某個(gè)元素
     *
     * @param index
     * @param element
     */
    public void add(int index, T element) {
        // 檢查index的范圍
        rangeCheckForAdd(index);

        // 判斷當(dāng)前的容量進(jìn)行擴(kuò)容操作看看后面一個(gè)位置
        ensureCapacity(size + 1);

        // 這里的移動(dòng)必須是從后往前移
        for (int i = size - 1; i >= index; i--) {
            elements[i + 1] = elements[i];
        }
        elements[index] = element;
        size++;
    }

    /**
     * 根據(jù) index 獲取元素
     *
     * @param index
     * @return
     */
    public T get(int index) {
        rangeCheck(index);
        return elements[index];
    }

    /**
     * 將 index 位置的元素設(shè)置為  element 并將原來的元素返回
     *
     * @param index
     * @param element
     * @return
     */
    public T set(int index, T element) {
        rangeCheckForAdd(index);
        // 將舊元素事先保存起來
        T oldElement = elements[index];
        elements[index] = element;
        return oldElement;
    }

    /**
     * 移除 index 處的元素 并返回被移除的元素
     *
     * @param index
     * @return
     */
    public T remove(int index) {
        rangeCheck(index);
        // 記錄需要?jiǎng)h除的元素
        T oldElement = elements[index];
        for (int i = index + 1; i <= size - 1; i++) {
            elements[i - 1] = elements[i];
        }
        size--;
        // 最后一個(gè)位置的元素 清空
        elements[size] = null;
        return oldElement;
    }

    /**
     * 返回某個(gè)元素在數(shù)組中的位置
     *
     * @param element
     * @return
     */
    public int indexOf(T element) {
        for (int i = 0; i < size; i++) {
            if (elements.equals(elements)) {
                return i;
            }
        }
        return ELEMENT_NOT_FOUND;
    }


    /**
     * 清空數(shù)組
     * <p>
     * 現(xiàn)在泛型的形式 size = 0 已經(jīng)不能這樣寫了
     * <p>
     * 不引用的對(duì)象就會(huì)被銷毀
     */
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null; // 將 數(shù)組中 實(shí)例 與 每個(gè)對(duì)象斷開
        }
        // elements = null; // 直接釋放數(shù)組不可行 ，下次需要再 new 一個(gè)數(shù)組
        size = 0;
    }

    /**
     * 判斷index的范圍
     *
     * @param index
     */
    private void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            outOfBound(index);
        }
    }

    private void outOfBound(int index) {
        throw new IndexOutOfBoundsException(" index : " + index + " size : " + size);
    }


    /**
     * 適用于添加方法
     *
     * @param index
     */
    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            outOfBound(index);
        }
    }

    /**
     * 保證數(shù)組的容量
     *
     * @param capacity
     */
    private void ensureCapacity(int capacity) {
        // 獲取當(dāng)前數(shù)組元素最大的容量
        int oldCapacity = elements.length;
        if (oldCapacity > capacity) {
            return;
        }
        // 否則將進(jìn)行擴(kuò)容 擴(kuò)容為原來的 1.5倍 (oldCapacity >> 1) => (oldCapacity  / 2)
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 使用新的容量創(chuàng)建一個(gè)新的數(shù)組
        T[] newElements = (T[]) new Object[newCapacity];
        // 將原數(shù)組中的元素移動(dòng)到新的數(shù)組中
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        // 將原來的數(shù)組實(shí)例指向新的數(shù)組實(shí)例
        elements = newElements;
        System.out.println(oldCapacity + "擴(kuò)容為:" + newCapacity);
    }

    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        str.append("size = ").append(size).append(" [");
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                str.append(", ");
            }
            str.append(elements[i]);
        }
        str.append("] ");
        return str.toString();
    }
}
創(chuàng)建數(shù)組時(shí)使用所有類的父類 Object 創(chuàng)建對(duì)象數(shù)組
 elements = (T[]) new Object[capacicy];
clear() 方法細(xì)節(jié)
對(duì)象數(shù)組
  1. 對(duì) clear() 方法進(jìn)行優(yōu)化 。因?yàn)楫?dāng)前數(shù)組中存儲(chǔ)的是對(duì)象，在釋放數(shù)組的資源的時(shí)候需要進(jìn)行如下的處理，防止資源的浪費(fèi)：
public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null; // 將 數(shù)組中 實(shí)例 與 每個(gè)對(duì)象斷開
        }
        // elements = null; // 直接釋放數(shù)組不可行 ，下次需要再 new 一個(gè)數(shù)組
        size = 0;
    }
remove()方法細(xì)節(jié)
  1. 在移除某個(gè)元素時(shí)，需要將元素從后往前移動(dòng)，最后會(huì)保留最后一個(gè) size - 1的位置存著一個(gè)之前的對(duì)象，此時(shí)需要將其進(jìn)行釋放:
public T remove(int index) {
        rangeCheck(index);
        // 記錄需要?jiǎng)h除的元素
        T oldElement = elements[index];
        for (int i = index + 1; i <= size - 1; i++) {
            elements[i - 1] = elements[i];
        }
        size--;
        // 最后一個(gè)位置的元素 清空
        elements[size] = null;
        return oldElement;
    }
數(shù)組動(dòng)態(tài)擴(kuò)容細(xì)節(jié)
  1. 當(dāng)在添加元素的時(shí)候需要對(duì)數(shù)組進(jìn)行動(dòng)態(tài)的擴(kuò)容操作：

首先傳遞的參數(shù)為，我們即將添加元素的位置。將此位置作為標(biāo)準(zhǔn) 和 數(shù)組當(dāng)前的容量進(jìn)行比較。
如果當(dāng)前的數(shù)組容量 數(shù)組.length 是大于該位置所需容量的，將直接返回，否則將進(jìn)行擴(kuò)容操作。
擴(kuò)容是將數(shù)組擴(kuò)容為原來的 1.5 倍。之后創(chuàng)建一個(gè)新的數(shù)組對(duì)象，將原數(shù)組中的元素復(fù)制到新數(shù)組中。
將原數(shù)組的引用指向新的數(shù)組對(duì)象。

   /**
     * 保證數(shù)組的容量
     *
     * @param capacity
     */
    private void ensureCapacity(int capacity) {
        // 獲取當(dāng)前數(shù)組元素最大的容量
        int oldCapacity = elements.length;
        if (oldCapacity > capacity) {
            return;
        }
        // 否則將進(jìn)行擴(kuò)容 擴(kuò)容為原來的 1.5倍 (oldCapacity >> 1) => (oldCapacity  / 2)
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 使用新的容量創(chuàng)建一個(gè)新的數(shù)組
        T[] newElements = (T[]) new Object[newCapacity];
        // 將原數(shù)組中的元素移動(dòng)到新的數(shù)組中
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        // 將原來的數(shù)組實(shí)例指向新的數(shù)組實(shí)例
        elements = newElements;
        System.out.println(oldCapacity + "擴(kuò)容為:" + newCapacity);
    }
如何判斷某個(gè)對(duì)象是否被回收
  1. 重寫實(shí)體類中的 finalize方法，該方法在對(duì)象被回收之前會(huì)執(zhí)行。
@Override
    protected void finalize() throws Throwable {
        super.finalize();
        System.out.println("對(duì)象被回收");
    }
  1. 但是對(duì)象不再被引用是JVM不會(huì)馬上進(jìn)行回收，如果需要進(jìn)行立即回收可以使用如下代碼 :
  // 提醒 JVM的垃圾回收機(jī)制 回收垃圾
  System.gc();
重寫equals() 方法指定比較規(guī)則
  1. equals() 方法 默認(rèn)比較的是對(duì)象的地址值。
/**
     * 重寫 equals方法 指定比較規(guī)則
     * @param obj
     * @return
     */
    @Override
    public boolean equals(Object obj) {
        Person person = (Person) obj;
        return this.name == person.name && this.age == person.age;
    }
空值處理
  1. 在可以使用泛型的動(dòng)態(tài)數(shù)組中可能會(huì)出現(xiàn)包含空值的情況，其實(shí)其中的 indexOf() 方法就需要進(jìn)行處理。
   /**
     * 返回某個(gè)元素在數(shù)組中的位置，如果在數(shù)組中是允許存儲(chǔ)空值的在判斷的時(shí)候就需要注意對(duì)空值的處理
     *
     * @param element
     * @return
     */
    public int indexOf(T element) {
        if (element == null) {
            for (int i = 0; i < size; i++) {
                if (elements[i] == null) {
                    return i;
                }
            }
        } else {
            // 需要將 element 寫在前面 elements[i] 可能會(huì)出現(xiàn)空值 null 如果不進(jìn)行處理的話可能就會(huì)出現(xiàn)空指針異常
            for (int i = 0; i < size; i++) {
                if (element.equals(elements[i])) {
                    return i;
                }
            }
        }
        return ELEMENT_NOT_FOUND;
    }
優(yōu)化 remove()方法中的循環(huán)條件
  1. 優(yōu)化前 ：
public T remove(int index) {
        rangeCheck(index);
        // 記錄需要?jiǎng)h除的元素
        T oldElement = elements[index];
        for (int i = index + 1; i <= size - 1; i++) {
            elements[i] = elements[i - 1];
        }
        size--;
        // 最后一個(gè)位置的元素 清空
        elements[size] = null;
        return oldElement;
    }
  1. 優(yōu)化后：
   public T remove(int index) {
        rangeCheck(index);
        // 記錄需要?jiǎng)h除的元素
        T oldElement = elements[index];
        // 原來的循環(huán)條件 : int i = index + 1; i <= size - 1; i++
        for (int i = index; i < size; i++) {
            elements[i] = elements[i - 1];
        }
        size--;
        // 最后一個(gè)位置的元素 清空
        elements[size] = null;
        return oldElement;
    }
優(yōu)化 add() 方法中的循環(huán)條件
  1. 優(yōu)化前：
 public void add(int index, T element) {
        // 檢查index的范圍
        rangeCheckForAdd(index);

        // 判斷當(dāng)前的容量進(jìn)行擴(kuò)容操作看看后面一個(gè)位置
        ensureCapacity(size + 1);

        // 這里的移動(dòng)必須是從后往前移  
        for (int i = size - 1; i >= index; i--) {
            elements[i] = elements[i - 1];
        }
        elements[index] = element;
        size++;
    }
  1. 優(yōu)化后：
 public void add(int index, T element) {
        // 檢查index的范圍
        rangeCheckForAdd(index);

        // 判斷當(dāng)前的容量進(jìn)行擴(kuò)容操作看看后面一個(gè)位置
        ensureCapacity(size + 1);

        // 這里的移動(dòng)必須是從后往前移  原來的循環(huán)條件 int i = size - 1; i >= index; i--
        // 原來的循環(huán)條件 int i = size - 1; i >= index; i--
        for (int i = size; i > index; i--) {
            elements[i] = elements[i - 1];
        }
        elements[index] = element;
        size++;
    }
優(yōu)化Person對(duì)象中的equals()方法
  1. 對(duì)equals() 方法中添加對(duì)類型的檢查，判斷是否屬于當(dāng)前類型或其子類等。
@Override
    public boolean equals(Object obj) {
        // 為了嚴(yán)謹(jǐn)起見 需要進(jìn)行以下修改
        if (obj == null) {
            return false;
        }
        // 判斷其是否屬于Person類型 ，如果是則將其進(jìn)行強(qiáng)制類型轉(zhuǎn)換這樣才不會(huì)報(bào)錯(cuò)
        if (obj instanceof Person) {
            Person person = (Person) obj;
            return this.name == person.name && this.age == person.age;
        }
        return false;
    }
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容