My first Magazine pemrograman-kompetitif-dasar | Page 90

8
Struktur Data Dasar
Struktur data merupakan tata cara untuk merepresentasikan dan menyimpan data, sehingga
mendukung operasi terhadap data tersebut secara efisien. Struktur data paling sederhana yang
telah kita pelajari adalah array . Pada bab ini, kita akan mempelajari struktur data dynamic array ,
stack , dan queue . Kita akan menggunakan struktur data ini pada pembelajaran Bab 9 mengenai
graf.
8.1 Dynamic Array
Dynamic array merupakan array yang ukurannya dapat bertambah atau berkurang mengikuti
banyaknya data yang sedang disimpan. Kemampuan menyesuaikan ukuran ini memberi keuntungan
apabila kita tidak tahu berapa banyak elemen yang akan disimpan pada array , dan kita tidak mau
membuat array yang ukurannya sebanyak elemen maksimum yang akan disimpan. Kebutuhan
memori yang diperlukan kini disesuaikan dengan banyaknya elemen. Kita akan mempelajari
dynamic array yang ukurannya hanya dapat bertambah.
Sama seperti array , kita dapat mengakses atau mengubah nilai pada suatu indeks yang
ada pada dynamic array dalam O(1). Pada dynamic array , terdapat operasi tambahan berupa
penyisipan suatu elemen sebagai elemen terakhir. Operasi ini biasa disebut dengan push .
Untuk membuat dynamic array , kita perlu membuat array biasa dengan ukuran maxSize.
Misalnya array ini bernama A, dan indeksnya dimulai dari 0. Nilai maxSize dapat diinisialisasi
dengan suatu nilai yang kecil, misalnya 1. Kita juga memerlukan sebuah variabel yang menyatakan
banyaknya elemen yang telah disimpan, misalnya bernama size. Nilai awal dari size adalah 0.
Ketika dilakukan operasi push , terdapat dua kemungkinan kasus:
1. Dipenuhi size < maxSize
Pada kasus ini, simpan elemen terbaru pada A[size], dan tambahkan nilai size dengan 1.
Seluruh operasi ini memerlukan kompleksitas O(1).
2. Dipenuhi size = maxSize
Kini array A tidak dapat menyimpan elemen yang baru. Untuk mengatasi hal ini, buat sebuah
array baru dengan ukuran dua kali maxSize, lalu salin seluruh isi A ke array baru ini. Hapus
array A, lalu ubah referensi A ke array yang baru. Kini maxSize menjadi berlipat ganda, dan
kita dapat menyimpan elemen baru dengan melakukan langkah seperti kasus sebelumnya.
Karena diperlukan penyalinan elemen ke array yang baru, kompleksitasnya kasus ini O(K)
jika terdapat K elemen yang telah disimpan.
80