[資料結構] 使用 C 語言:實作動態陣列 (Dynamic Array)

【分享本文】
Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email

    動態陣列的抽象資料結構

    動態陣列 (dynamic array) 和鏈結串列 (linked list) 的抽象資料結構大抵上相同:

    A is a dynamic array.
    
    sub IsEmpty(A): bool
    sub PeakFront(A): data
    sub PeakRear(A): data
    sub At(A, index): data
    sub SetAt(A, index, data): void
    sub Push(A, data): void
    sub Shift(A, data): void
    sub Pop(A): data
    sub Unshift(A): data
    sub InsertAt(A, index, data): void
    sub RemoveAt(A, index): data
    

    以下是動態陣列中和狀態相關的行為:

    • IsEmpty(A):確認陣列是否為空
    • Size(A):得知陣列的大小
    • PeakFront(A):檢視陣列頭端的元素
    • PeakRear(A):檢視陣列尾端的元素
    • At(A, index):檢視陣列中任意位置的元素
    • SetAt(A, index, data):設置陣列中任意位置的元素

    在這些公開行為中,除了 SetAt 會改變動態陣列內部的狀態外,其他的行為都只是查詢用,不會改變動態陣列的狀態。

    以下是操作動態陣列的方法:

    • Push(A, data):從陣列尾端放入元素
    • Shift(A, data):從陣列頭端放入元素
    • Pop(A):從陣列尾端取出元素
    • Unshift(A):從陣列頭端取出元素
    • InsertAt(A, index, data):從陣列中任意位置放入元素
    • RemoveAt(A, index):從陣列中任意位置取出元素

    相對來說,這些方法就會改變動態陣列的狀態。

    如果讀者把串列和動態陣列的抽象資料結構拿來比較,會發現陣列和串列的差異不在其外在行為,而在其內部實作。因實作方式的差異會造成兩者在行為上的效率有別。

    宣告動態陣列類別

    以下是動態陣列的類別宣告:

    class Array
        size <- 0
        capacity <- n
        head <- 0
        tail <- 0
        elements <- an array which initial size == capacity
    

    除了存放資料的陣列 elements 本身外,還會有四個屬性。和陣列大小相關的有陣列當下的大小 size 及陣列的最大容量 capacity;和陣列頭尾位置有關的則有 head (頭端) 和 tail (尾端)。

    陣列在擴展容量時,不會只擴展一個元素,這樣比較沒有效率。常見的做法是在增加元素時偵測是否需要擴增最大容量,若需要擴容,則擴增一倍容量。所以需要 sizecapacity 兩個值來記錄陣列的當下大小和最大容量。

    為了增加陣列的效率,我們會採用環狀陣列。故 headtail 不會固定在相同的位置,而會隨著陣列操作移動。這些端點的移動會隱藏在陣列內部,外部不需手動處理這些端點實際的位置。下文會討論環狀陣列的操作過程。

    以下是等效的 C 程式碼:

    typedef struct array_t array_t;
    
    struct array_t {
        size_t size;
        size_t capacity;
        size_t head;
        size_t tail;
        int *elements;
    };
    

    由於 C 語言的陣列不會儲存陣列長度,故我們要在物件中另存陣列長度和容量的資訊。如果讀者使用 Java 等語言練習資料結構的話,就不需要這個動作。

    動態陣列的建構函式

    以下是 C 語言的動態陣列建構函式:

    array_t * array_new(void)
    {
        array_t *arr = malloc(sizeof(array_t));
        if (!arr)
            return arr;
    
        arr->size = 0;
        arr->capacity = 2;
        arr->head = 0;
        arr->tail = 0;
    
        arr->elements = malloc(arr->capacity * sizeof(int));
        if (!(arr->elements)) {
            array_delete(arr);
            arr = NULL;
            return arr;
        }
    
        return arr;
    }
    

    arr->capacity 的起始值只要大於等於 2 即可,一般會設成 16 或 32,在少量元素操作時才不會頻繁搬移元素。此處故意設為 2 是為了測試擴展容量是否出問題。由於我們是用陣列儲存資料,arr->headarr->tail 不是指標,而是索引值。

    上述建構函式會建立空陣列,這算是比較傳統的做法。我們也可以讓陣列使用者預先填值,如下例:

    array_t *arr = array_init(5, 3, 4, 5, 6, 7);
    

    在這個建構函式中,第一個參數代表陣列長度,第二個以後的參數代表實際填入陣列的值。array_init 用到 C 語言的不定參數,範例如下:

    array_t * array_init(size_t size, int value, ...)
    {
        array_t *arr = malloc(sizeof(array_t));
        if (!arr)
            return arr;
    
        // Create a new empty array.
        arr->size = 0;
        arr->capacity = 2;
        arr->head = 0;
        arr->tail = 0;
    
        arr->elements = malloc(arr->capacity * sizeof(int));
        if (!(arr->elements)) {
            array_delete(arr);
            arr = NULL;
            return arr;
        }
    
        // Fill the first element.
        arr->elements[arr->head] = value;
        arr->size++;
    
        // Start `args`, the paramater list.
        va_list args;
        va_start(args, value);
    
        // Fill more elements.
        for (size_t i = 1; i < size; i++) {
            // Expand the array if needed.
            if (i + 1 > arr->capacity) {
                arr->capacity <<= 1;
    
                int *old_arr = arr->elements;
                int *new_arr = malloc(arr->capacity * sizeof(int));
                if (!new_arr) {
                    array_delete(arr);
                    arr = NULL;
                    va_end(args);
                    return arr;
                }
    
                int i = arr->head;
                int j = arr->head;
                size_t s = 0;
                while (s < arr->size) {
                    new_arr[j] = old_arr[i];
    
                    i = (i + 1) % arr->size;
                    j = (j + 1) % arr->capacity;
                    s++;
                }
    
                arr->elements = new_arr;
                free(old_arr);
            }
    
            // Relocate the tail of the array.
            arr->tail = (arr->head + (arr->size - 1) + 1) % arr->capacity;
            // Fill some element.
            arr->elements[arr->tail] = va_arg(args, int);
            arr->size++;
        }
    
        // Free `args`
        va_end(args);
    
        return arr;
    }
    

    使用不定參數時需引入 ,這是標準函式庫的一部分。一般使用方式是以三個巨集相互搭配:

    • va_start:設置參數清單
    • va_arg:取得參數值
    • va_end:結束參數清單

    使用方式請看本範例。

    另外,我們在這裡實作擴充陣列的程式,後文會介紹細節,此處不重覆。

    動態陣列的解構函式

    以下是 C 語言的動態陣列解構函式:

    void array_delete(void *self)
    {
        if (!self)
            return;
    
        free(((array_t *) self)->elements);
        free(self);
    }
    

    先釋放內部的陣列後再釋放物件本身即可。

    檢查陣列是否為空

    以下虛擬碼檢查陣列是否為空:

    sub IsEmpty(A): bool
        return A.size == 0
    

    由於我們的物件中存有陣列大小的資訊,直接檢查陣列大小 A.size 是否為 0 即可。以下是等效的 C 程式:

    bool array_is_empty(const array_t *self)
    {
        assert(self);
    
        return self->size <= 0;
    }
    

    檢視陣列頭端的元素

    以下是檢查陣列頭端元素的虛擬碼:

    sub PeekFront(A): data
        assert not IsEmpty(A)
        
        return A.elements[A.head]
    

    要先排除陣列為空的情形,之後以 A.head 為索引從 A.elements 取索引即可。以下是等效的 C 程式:

    int array_peak_front(const array_t *self)
    {
        assert(!array_is_empty(self));
    
        return self->elements[self->head];
    }
    

    檢視陣列尾端的元素

    以下是檢查陣列尾端元素的虛擬碼:

    sub PeekRear(A): data
        assert not IsEmpty(A)
        
        return A.elements[A.tail]
    

    要先排除陣列為空的情形。接著,以 A.tail 為索引對 A.elements 取值即可。以下是等效的 C 程式:

    int array_peak_rear(const array_t *self)
    {
        assert(!array_is_empty(self));
    
        return self->elements[self->tail];
    }
    

    檢視陣列中任意位置的元素

    以下是檢視陣列中任意位置的元素的虛擬碼:

    sub At(A, index): data
        assert not IsEmpty(A)
        assert 0 <= index < Size(A)
        
        return A.elements[index]
    

    要先確認陣列不為空及索引值 index 合法,之後直接以 indexA.elements 取值即可。以下是等效的 C 程式:

    int array_at(const array_t *self, size_t index)
    {
        assert(self);
        assert(index < array_size(self));
    
        size_t i = (self->head + index) % self->capacity;
        return self->elements[i];
    }
    

    由於型別 size_t 一定大於等於 0,故只需檢查索引值 index 的上限。

    由於我們在內部使用環狀陣列,在使用索引值時要進行相對應的轉換。轉換方式是將索引值 index 重新以 self->head 為基準點平移,之後以 self->capacity 為容量進行環狀移動即可。

    修改陣列中任意位置的元素

    以下是修改陣列中任意位置元素的虛擬碼:

    sub SetAt(A, index, data): void
        assert not IsEmpty(A)
        assert 0 <= index < Size(A)
        
        A.elements[index] <- data
    

    要先確認陣列不為空及索引值 index 合法,之後以索引 index 取得 A.elements 所在的元素,將其值修改為 data。以下是等效的 C 程式碼:

    void array_set_at(array_t *self, size_t index, int value)
    {
        assert(self);
        assert(index < array_size(self));
    
        size_t i = (self->head + index) % self->capacity;
        self->elements[i] = value;
    }
    

    同樣要以前一節所提的方式對索引值做平移後才能使用。

    從陣列尾端插入元素

    以下是從陣列尾端插入元素的虛擬碼:

    sub Push(A, data): void
        Expand(A)
        
        if A.size > 0 then
            A.tail <- (A.tail + 1) % A.capacity
        end if
    
        A.elements[A.tail] <- data
        A.size++
    

    一開始要先偵測是否需要擴展容量,在容量擴展後才進行下一步動作。下文會談到 Expand(A) 部分的實作方式。

    當陣列大小為 0 時,頭端 A.head 和尾端 A.tail 會指向同一個位置;反之,則需移動 A.tail 以免覆寫到其他元素。由於本陣列為環狀陣列,我們要對 A.tail 平移,之後再以 A.tail 為索引修改元素。以下是等效的 C 語言實作:

    bool array_push(array_t *self, int value)
    {
        assert(self);
    
        if (!array_expand(self)) {
            return false;
        }
    
        if (array_size(self) > 0) {
            self->tail = (self->tail + 1) % self->capacity;
        }
    
        self->elements[self->tail] = value;
        self->size++;
    
        return true;
    }
    

    在這段程式碼中,我們先略過 array_expand 函式,也就是 Expand(A) 部分的虛擬碼。這是因為這段程式碼比較長,而且在數個函式中會共用,故我們將其分離出來。這段虛擬碼稍微長一些,我們會講解:

    sub Expand(A): void
        if A.size < A.capacity then
            return
        end if
        
        A.capacity <- A.capacity * 2
        
        old_arr <- A.elements
        new_arr <- A new array which initial size == A.capacity
        
        i <- A.head
        j <- A.head
        s <- 0
        while s < A.size do
            new_arr[j] <- old_arr[i]
            
            i <- (i + 1) % A.size
            j <- (j + 1) % A.capacity
            s <- s + 1
        end while
        
        A.elements <- new_arr
        A.tail <- (A.head + A.size - 1) % A.capacity
        delete old_arr
    

    A.size 小於 A.capacity,表示不需擴展容量,直接結束此函式即可。

    擴展容量的方式是建立新陣列後,將舊陣列上的元素逐一拷貝到新元素上,將 A.elements 指向新陣列,最後釋放掉舊陣列即可。在這裡我們使用環狀陣列的手法來逐一填值,需注意新陣列和舊陣列的大小相異。最後要修正 A.tail 的位置。

    以下是等效的 C 程式碼:

    static bool array_expand(array_t *self)
    {
        if (self->size < self->capacity)
            return true;
    
        self->capacity <<= 1;
        int *old_arr = self->elements;
        int *new_arr = malloc(self->capacity * sizeof(int));
        if (!new_arr)
            return false;
    
        size_t i = self->head;
        size_t j = self->head;
        size_t s = 0;
        while (s < self->size) {
            new_arr[j] = old_arr[i];
    
            i = (i + 1) % self->size;
            j = (j + 1) % self->capacity;
            s++;
        }
    
        self->elements = new_arr;
        self->tail = (self->head + self->size - 1) % self->capacity;
        free(old_arr);
    
        return true;
    }
    

    從陣列頭端插入元素

    以下是從陣列頭端插入元素的虛擬碼:

    sub Unshift(A, data): void
        Expand(A)
        
        if A.size > 0 then
            A.head <- A.head == 0 ? A.capacity - 1 : A.head - 1
        end if
        
        A.elements[A.head] <- data
        A.size += 1
    

    一開始先視需求擴展容量,再進行下一步動作。擴展容量的程式碼我們已經展示過,此處不重覆。

    我們想做的動作是放入元素,但對 A.head 來說,卻是倒退一步,需注意方向。以下是等效的 C 程式:

    bool array_unshift(array_t *self, int value)
    {
        assert(self);
    
        if (!array_expand(self)) {
            return false;
        }
    
        if (array_size(self) > 0) {
            self->head = self->head == 0 ? self->capacity - 1 : self->head - 1;
        }
    
        self->elements[self->head] = value;
        self->size++;
    
        return true;
    }
    

    從陣列尾端移出元素

    以下是從陣列尾端移出元素的虛擬碼:

    sub Pop(A): result
        result <- A.elements[A.tail]
        
        A.tail <- A.tail == 0 ? A.capacity - 1 : A.tail - 1
        
        A.size -= 1
        
        return result
    

    我們在移出元素時,A.tail 的方向是倒退,需注意兩者的方向。

    在本範例程式中,我們沒有縮減陣列的大小,讀者可以自行嘗試實作看看。建議的方式是當陣列大小 (size) 小於陣列容量 (capacity) 的一半時,將陣列容量減少一半;但最小容量不低於 16 或 32,以免因頻繁搬移造成效能下降。

    以下是等效的 C 語言實作:

    int array_pop(array_t *self)
    {
        assert(!array_is_empty(self));
    
        int result = self->elements[self->tail];
    
        self->tail = self->tail == 0 ? self->capacity - 1 : self->tail - 1;
        self->size--;
    
        return result;
    }
    

    從陣列頭端移出元素

    以下是從陣列頭端移出元素的虛擬碼:

    sub Shift(A): result
        result <- A.elements[A.head]
        
        A.head <- (A.head + 1) % A.size
        A.size -= 1
        
        return result
    

    要注意移出元素時,A.head 的方向是前移。同前一節,讀者可自行嘗試縮減陣列。

    以下是等效的 C 程式碼:

    int array_shift(array_t *self)
    {
        assert(!array_is_empty(self));
    
        int result = self->elements[self->head];
    
        self->head = (self->head + 1) % self->capacity;
        self->size--;
    
        return result;
    }
    

    從陣列中任一位置放入元素

    從陣列中任一位置放入元素時,需分幾個情境:

    • 原先陣列為空
    • 從陣列尾端加入新元素
    • 陣列不需擴展
    • 陣列需擴展

    之後還在再依陣列頭端及尾端的相對位置進行不同的處理。本節的虛擬碼較長,請耐心閱讀,可搭配下文說明來看:

    sub InsertAt(A, index, data): void
        assert 0 <= index <= A.size
        
        if index == A.size then
            Push(A, data)
            return
        end if
        
        if A.size == 0 then
            A.elements[A.head] <- data
            A.size += 1
            return
        end if
    
        _index <- (A.head + index) % A.capacity
    
        if A.size + 1 < A.capacity then
            i <- A.tail
            s <- 0
            while s < A.size do
                if A.head <= A.tail or _index <= A.tail then
                    if _index <= i then
                        A.elements[(i+1) % A.capacity] <- A.elements[i]
                    end if
                    
                    if _index == i then
                        A.elements[i] <- data
                        break
                    end if
                else if A.head <= _index then
                    if i <= A.tail or _index <= i then
                        A.elements[(i+1) % A.capacity] <- A.elements[i]
                    end if
        
                    if _index == i then
                        A.elements[i] <- data
                        break
                    end if
                end if
                
                i <- i == 0 ? i.size - 1 : i - 1
                s += 1
            end while
            
            A.size += 1
            
            A.tail <- (A.tail + 1) % A.capacity
        else
            A.capacity <- A.capacity * 2
            old_arr <- A.elements
            new_arr <- a new array which initial size == A.capacity
    
            i <- A.tail
            j <- A.size - 1
            k <- (A.head + index) % A.size
            s <- 0
            while s < A.size do
                if A.head <= A.tail or _index <= A.tail then
                    if _index <= i then
                        new_arr[(j+1) % A.capacity] <- old_arr[i]
                    
                        if i == _index then
                            new_arr[j] <- data
                        end if
                    else
                        new_arr[j] <- old_arr[i]
                    end if
                else if A.head <= _index then
                    if i <= A.tail or _index <= i then
                        new_arr[(j+1) % A.capacity] <- old_arr[i]
                        if i == _index then
                            new_arr[j] <- data
                        end if
                    else
                        new_arr[j] <- old_arr[i]
                    end if
                end if
    
                i <- i == 0 ? A.size - 1 : i - 1
                j <- j == 0 ? A.capacity - 1 : j - 1
                s += 1
            end
            
            A.elements <- new_arr
            delete old_arr
            
            A.head <- 0
            A.size <- (A.size - 1) + 1
        end
        
        A.size += 1
    

    一開始要先確認索引值 index 的合法性。若陣列為零,index 必為零,反之,index 介於零和陣列大小之間。此處的 index 會比索引上限 size - 11,因為我們允許陣列使用者從陣列尾端推入元素。

    若陣列大小為零,能放的位置只有一個,直接將該元素放入即可。

    若要從陣列尾端放入元素,直接重用 array_push 的程式即可,此處不重覆該部分實作。

    由於我們採環狀陣列,要先將 index 平移成 _index 後再使用。由於本節採用邊搬邊插入元素的方式,所以沒有使用先前的 Expand(A) 代碼。這樣可以避免搬移兩次所造成的效能耗損。

    搬移的方式是從尾端逐一走訪元素至頭端,在到達索引值 (含) 前將當下的元素往後搬移一格。在搬移時,要先區分是否需擴展容量,然後再細分為數種情形:

    • 頭端和尾端方向正常
    • 頭端和尾端方向相反
      • 索引值位於尾端左側
      • 索引值位於頭端右側

    總共有六種情境,所以程式碼會比較長。

    當不需擴展容量時,逐一搬移元素直到索引值所在的位置即可;根據索引值和頭、尾端旳相對關係,可再細分為三種。請讀者自行閱讀虛擬碼。

    當有擴展容量時,逐一搬移元素直到索引值所在的位置即可;同樣地,根據索引值和頭、尾端的相對關係,可再細分為三種。我們在搬移的同時,順便歸零頭、尾端所在的位置,這樣反而比較容易確認頭尾端最後的位置。

    以下是等效的 C 程式碼:

    bool array_insert_at(array_t *self, size_t index, int value)
    {
        assert(self);
        assert(index <= array_size(self));
    
        if (index == array_size(self))
            return array_push(self, value);
    
        size_t _index = (self->head + index) % self->capacity;
    
        if (array_size(self) == 0) {
            self->elements[_index] = value;
            self->size++;
            return true;
        }
    
        if (self->size < self->capacity) {
            size_t i = self->tail;
            size_t s = 0;
            size_t temp;
            while (s < array_size(self)) {
                if (self->head <= self->tail || _index <= self->tail) {
                    if (_index <= i) {
                        temp = (i + 1) % self->capacity;
                        self->elements[temp] = self->elements[i];
                    }
    
                    if (_index == i) {
                        self->elements[i] = value;
                        break; 
                    }
                }
                else if (self->head <= _index) {
                    if (i <= self->tail || i >= _index) {
                        temp = (i + 1) % self->capacity;
                        self->elements[temp] = self->elements[i]; 
                    }
                        
                    if (i == _index) {
                        self->elements[i] = value;
                        break;
                    }
                }
    
                i = i == 0 ? self->capacity - 1 : i - 1;
                s++;
            }
    
            self->tail = (self->tail + 1) % self->capacity;
        }
        else {
            self->capacity <<= 1;
            int *old_arr = self->elements;
            int *new_arr = malloc(self->capacity * sizeof(int));
            if (!new_arr)
                return false;
    
            size_t i = self->tail;
            size_t j = self->size - 1;
            size_t s = 0;
            size_t temp;
            while (s < array_size(self)) {
                if (self->head <= self->tail || _index <= self->tail) {
                    if (_index <= i) {
                        temp = (j + 1) % self->capacity;
                        new_arr[temp] = old_arr[i];
    
                        if (i == _index) {
                            new_arr[j] = value;
                        }
                    }
                    else {
                        new_arr[j] = old_arr[i];
                    }
                }
                else if (self->head <= _index) {
                    if (i <= self->tail || _index <= i) {
                        temp = (j + 1) % self->capacity;
                        new_arr[temp] = old_arr[i];
    
                        if (i == _index) {
                            new_arr[j] = value;
                        }
                    }
                    else {
                        new_arr[j] = old_arr[i];
                    }
                }
    
                i = i == 0 ? self->size - 1 : i - 1;
                j = j == 0 ? self->capacity - 1 : j - 1;
                s++;
            }
    
            self->elements = new_arr;
            free(old_arr);
        
            self->head = 0;
            self->tail = (self->size - 1) + 1;
        }
    
        self->size++;
    
        return true;
    }
    

    從陣列中任意位置取出元素

    以下是從陣列中移出元素的虛擬碼:

    sub RemoveAt(A, index): result
        assert not IsEmpty(A)
        assert 0 <= index < A.size
        
        _index <- (A.head + index) % A.capacity
        result <- A.elements[_index]
        
        if A.size == 1 then
            A.tail <- A.tail == 0 ? A.size - 1 : A.tail - 1
            A.size -= 1
            return result
        end if
        
        i <- A.head
        s <- 0
        while s < A.size do
            if A.head <= A.tail then
                if _index <= i then
                    A.elements[(i+1) % A.capacity] <- A.elements[i]
                end if
            else
                if _index <= A.tail then
                    if _index <= 1 and i <= A.tail then
                        A.elements[(i+1) % A.capacity] <- A.elements[i]
                    end if
                else
                    if i <= A.tail or _index <= i then
                        A.elements[(i+1) % A.capacity] <- A.elements[i]
                    end if
                end if
            end if
    
            i <- (i + 1) % A.capacity
            s += 1
        end while
        
        A.tail <- A.tail == 0 ? A.capacity - 1 : A.tail - 1
        A.size -= 1
        
        return result
    

    搬移時,從頭端逐一走訪元素至尾端,在索引值所在點開始逐一將後一個元素的值覆寫到當下的位置。要依據索引值和頭、尾端相對位置分為三種情境。請讀者自行閱讀虛擬碼,以了解搬移的細節。

    以下是等效的 C 程式碼:

    int array_remove_at(array_t *self, size_t index)
    {
        assert(!array_is_empty(self));
        assert(index < array_size(self));
    
        size_t _index = (self->head + index) % self->capacity;
        int result = self->elements[_index];
    
        if (array_size(self) == 1) {
            self->tail = self->tail == 0 ? self->size - 1 : self->tail - 1;
            self->size--;
            return result;
        }
    
        size_t i = self->head;
        size_t s = 0;
        size_t temp;
        while (s < array_size(self)) {
            if (self->head <= self->tail) {
                if (_index <= i) {
                    temp = (i + 1) % self->capacity;
                    self->elements[i] = self->elements[temp];
                }
            }
            else {
                if (_index <= self->tail) {
                    if (_index <= i && i <= self->tail) {
                        temp = (i + 1) % self->capacity;
                        self->elements[i] = self->elements[temp];
                    }
                }
                else {
                    if (i <= self->tail || _index <= i) {
                        temp = (i + 1) % self->capacity;
                        self->elements[i] = self->elements[temp];
                    }
                }
            }
    
            i = (i + 1) % self->capacity;
            s++;
        }
    
        self->tail = self->tail == 0 ? self->capacity - 1 : self->tail - 1;
        self->size--;
    
        return result;
    }
    

    演算法上的效率

    動態陣列中和狀態相關的行為的效率:

    • IsEmpty(A)O(1)
    • Size(A)O(1)
    • PeakFront(A)O(1)
    • PeakRear(A)O(1)
    • At(A, index)O(1)
    • SetAt(A, index, data)O(1)

    以下是操作動態陣列的方法:

    • Push(A, data):amortized O(1)
    • Shift(A, data):amortized O(1)
    • Pop(A)O(1)
    • Unshift(A)O(1)
    • InsertAt(A, index, data)O(n)
    • RemoveAt(A, index)O(n)

    動態陣列比起鏈結串列的優點,在於隨機存取的效率較好 (O(1)O(n)),若元素搬動不頻繁,使用動態陣列會比鏈結串列佳。

    【分享本文】
    Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email
    【追蹤新文章】
    Facebook Twitter Plurk