快捷導(dǎo)航

Java動(dòng)態(tài)數(shù)組的實(shí)現(xiàn)過程

更新時(shí)間：2026年01月08日 14:26:50 作者：當(dāng)年明月思古今

本文介紹了如何實(shí)現(xiàn)一個(gè)簡(jiǎn)單的動(dòng)態(tài)數(shù)組,包括基礎(chǔ)結(jié)構(gòu)設(shè)計(jì)、核心功能實(shí)現(xiàn)、性能分析、實(shí)現(xiàn)特點(diǎn)以及改進(jìn)建議,通過這個(gè)實(shí)現(xiàn),我們能夠更好地理解動(dòng)態(tài)數(shù)組的工作原理和核心操作

1. 基礎(chǔ)結(jié)構(gòu)設(shè)計(jì)

首先，讓我們看看類的基本結(jié)構(gòu)：

public class MyList {
    private int[] arr;        // 底層數(shù)組
    private int capacity = 10; // 數(shù)組容量
    private int size = 0;     // 當(dāng)前元素個(gè)數(shù)
    private int extendRatio = 2; // 擴(kuò)容倍數(shù)
}

這個(gè)實(shí)現(xiàn)包含了四個(gè)關(guān)鍵的成員變量：

arr: 存儲(chǔ)實(shí)際數(shù)據(jù)的底層數(shù)組
capacity: 數(shù)組的容量
size: 當(dāng)前實(shí)際存儲(chǔ)的元素?cái)?shù)量
extendRatio: 擴(kuò)容時(shí)的倍數(shù)

2. 核心功能實(shí)現(xiàn)

2.1 基本操作

獲取元素個(gè)數(shù)和容量

public int size() {
    return size;
}

public int capacity() {
    return capacity;
}

獲取和設(shè)置元素

public int get(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }
    return arr[index];
}

public void set(int index, int num) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }
    arr[index] = num;
}

2.2 添加元素

public void add(int item) {
    if (size == capacity) {
        extendCapacity();
    }
    arr[size] = item;
    size++;
}

2.3 插入元素

public void insert(int index, int item) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }
    if (size == capacity) {
        extendCapacity();
    }
    // 將index后的元素都向后移動(dòng)一位
    for (int i = size - 1; i >= index; i--) {
        arr[i + 1] = arr[i];
    }
    arr[index] = item;
    size++;
}

2.4 刪除元素

public int remove(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }
    int num = arr[index];
    // 將index后的元素都向前移動(dòng)一位
    for (int i = index; i < size - 1; i++) {
        arr[i] = arr[i + 1];
    }
    size--;
    return num;
}

2.5 擴(kuò)容機(jī)制

private void extendCapacity() {
	// 新建一個(gè)長(zhǎng)度為原數(shù)組 extendRatio 倍的新數(shù)組，并將原數(shù)組復(fù)制到新數(shù)組
    arr = Arrays.copyOf(arr, extendRatio);
    // 更新列表容量
    capacity = arr.length;
}

3. 性能分析

時(shí)間復(fù)雜度

訪問元素 (get/set): O(1)
在末尾添加元素 (add): 平均O(1)
插入元素 (insert): O(n)
刪除元素 (remove): O(n)

空間復(fù)雜度

初始空間復(fù)雜度: O(1)
擴(kuò)容后的空間復(fù)雜度: O(n)

4. 實(shí)現(xiàn)特點(diǎn)

動(dòng)態(tài)擴(kuò)容：當(dāng)數(shù)組空間不足時(shí)，會(huì)自動(dòng)擴(kuò)容為原來的2倍。
邊界檢查：所有的操作都會(huì)進(jìn)行嚴(yán)格的邊界檢查，防止數(shù)組越界。
數(shù)據(jù)搬移：在插入和刪除操作時(shí)，需要移動(dòng)元素，這是數(shù)組實(shí)現(xiàn)的一個(gè)缺點(diǎn)。

5. 改進(jìn)建議

考慮添加收縮機(jī)制，當(dāng)數(shù)組使用率過低時(shí)減少容量
可以支持泛型，使其能夠存儲(chǔ)任意類型的數(shù)據(jù)
優(yōu)化擴(kuò)容機(jī)制，使用更靈活的擴(kuò)容策略
添加迭代器支持，提供更方便的遍歷方式

總結(jié)

這個(gè)簡(jiǎn)單的動(dòng)態(tài)數(shù)組實(shí)現(xiàn)展示了數(shù)據(jù)結(jié)構(gòu)中最基本的一些概念：動(dòng)態(tài)擴(kuò)容、邊界檢查、元素操作等。通過理解這些基礎(chǔ)實(shí)現(xiàn)，我們可以更好地理解Java中ArrayList等集合類的工作原理。

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: