Modul 0 [Dynamic Array] - lab-kcks/Modul-STRUKDAT GitHub Wiki

Dynamic Array

Pengertian

Sebuah dynamic array memungkinkan sebuah array bertindak secara dinamis (ukuran array berubah-ubah) berdasarkan banyaknya data yang diinputkan dan pada saat yang sama memiliki akses acak ke elemen yang disimpan.

Cara Kerja

Pengimplementasian dynamic array biasanya menggunakan static array dengan ukuran awal tertentu.

Contohnya, ukuran awal array adalah 4 dan sudah diisi sebanyak 4 elemen. Ketika hendak mengisi elemen ke-5 dengan nilai 6, maka ukuran array akan bertambah dua kali lipat dari ukuran awal kemudian menyalin data yang ada di array awal ke array yang baru lalu memasukkan elemen ke-5.

dynamic array
  • Logical Size merupakan area array yang dapat diakses.
  • Capacity merupakan ukuran array yang sebenarnya. Area diluar logical size seharusnya tidak dapat diakses.

Static Arrray vs Dynamic

Static Array Dynamic Array
Ukuran tetap Ukuran dinamis
Alokasi memori dilakukan selama waktu compile (pembuatan program) Alokasi memori dilakukan selama waktu runtime (saat program dijalankan)
Bagus digunakan apabila ukuran data diketahui dan tetap. Bagus digunakan apabila ukuran data tidak tetap.
Sangat mungkin wasting memori Kecil kemungkinan wasting memori apabila diimplementasikan dengan benar
Lokasi di Stack Memory space Lokasi di Heap Memory space

Operasi Dasar

Beikut merupakan operasi dasar pada dynamic array.

  • pushBack

    Untuk menambah data baru ke array. Data akan bertambah di posisi paling akhir/ belakang.

  • popBack

    Untuk menghapus data paling akhir/ belakang.

  • back

    Untuk mendapatkan data paling akhir/ belakang.

  • front

    Untuk mendapatkan data paling awal/ depan.

  • getAt(i)

    Untuk mendapatkan data indeks ke-i.

  • setAt(i, value) Untuk memodifikasi/ mengubah data indeks ke-i dengan value baru.

  • isEmpty

    Untuk memeriksa apakah array sudah ada isinya atau kosong.

Contoh ADT - Dynamic Array

  • Struktur Dynamic Array

    _arr : variabel array

    _size : variabel ukuran array

    _capacity : variabel kapasitas array

    typedef struct dynamicarr_t {
        int *_arr;
        unsigned _size, _capacity;
    } DynamicArray;
  • isEmpty

    Untuk memeriksa apakah array kosong, cukup dengan memeriksa _size (ukurannya) apakah bernilai 0.

    bool dArray_isEmpty(DynamicArray *darray) {
        return (darray->_size == 0);
    }
  • pushBack

    Terdapat dua kasus pada saat melakukan pushBack, yakni.

    Kasus 1: kapasitas array masih cukup

    • Cukup dengan memasukkan data pada index selanjutnya.

    Kasus 2: kapasitas array sudah penuh

    • Jika kapasitas array sudah penuh, maka perlu dibuat array baru.
    • Alokasikan array baru dengan ukuran dua kali dari kapasitas semula.
    • Salin semua data pada array lama ke array baru.
    • Referensikan array yang sekarang ke array baru.
    • Hapus array yang lama.
    • Masukkan data baru pada index selanjutnya.
    void dArray_pushBack(DynamicArray *darray, int value)
    {
        if (darray->_size + 1 > darray->_capacity) {
            unsigned it;
            darray->_capacity *= 2;
            int *newArr = (int*) malloc(sizeof(int) * darray->_capacity);
    
            for (it=0; it < darray->_size; ++it)
                newArr[it] = darray->_arr[it];
            
            int *oldArray = darray->_arr;
            darray->_arr = newArr;
            free(oldArray);
        }
        darray->_arr[darray->_size++] = value;
    }
  • popBack

    Melakukan popBack cukup dengan menurunkan ukuran dari array, sehingga index yang diakses tidak akan melebihi size. Pastikan saat melakukan popBack, array tidak kosong.

    void dArray_popBack(DynamicArray *darray) {
        if (!dArray_isEmpty(darray)) darray->_size--;
        else return;
    }
  • back

    Untuk mendapatkan data paling belakang, sangat sederhana, yakni ambil nilai index size-1 pada array.

    int dArray_back(DynamicArray *darray) {
        if (!dArray_isEmpty(darray))
            return darray->_arr[darray->_size-1];
        else return 0;
    }
  • front

    Untuk mendapatkan data paling depan, cukup dengan mengambil data pada indeks 0 pada array.

    int dArray_front(DynamicArray *darray) { if (!dArray_isEmpty(darray)) return darray->_arr[0]; else return 0; }

  • setAt

    Operasi setAt dapat dilakukan dengan sangat mudah yakni cukup ubah nilai pada indeks yang diinginkan.

    Selain itu, lakukanlah validasi apakah indeks yang diinputkan sesuai.

    void dArray_setAt(
        DynamicArray *darray, unsigned index, int value)
    {
        if (!dArray_isEmpty(darray)) {
            if (index >= darray->_size)
                darray->_arr[darray->_size-1] = value;
            else
                darray->_arr[index] = value;
        }
    }
  • getAt

    Operasi getAt dapat dilakukan dengan sangat mudah yakni cukup ubah menggunakan indeks yang diinginkan pada array.

    Selain itu, lakukanlah validasi apakah indeks yang diinputkan sesuai dan array memang tidak kosong.

    int dArray_getAt(DynamicArray *darray, unsigned index)
    {
        if (!dArray_isEmpty(darray)) {
            if (index >= darray->_size)
                return darray->_arr[darray->_size-1];
            else
                return darray->_arr[index];
        }
    }
⚠️ **GitHub.com Fallback** ⚠️