AKBAR PERMATA PUTERA./PENGERTIAN STRUKTUR DATA
1.Pengertian Array
Array atau dalam bahasa indonesia disebut larik, merupakan salah satu teknik menyimpan kumpulan data dalam memori dengan cara meletakkannya secara berdekatan. Tujuannya agar beberapa item data dari jenis yang sama berada di satu tempat dan memudahkan ketika hendak dilakukan operasi pada data.
Array adalah kumpulan item data yang disimpan di lokasi memori yang berdekatan
Dalam strukur data, array termasuk jenis struktur data linier, yaitu struktur dimana elemen datanya disusun dalam satu dimensi.
Ketika ingin mengakses data dalam array, kita cukup menghitung posisi setiap elemen, yaitu dengan menambahkan offset ke nilai awal. Nilai awal adalah lokasi memori elemen pertama array yang berada pada indeks 0 dan perbedaan antara kedua indeks adalah nilai offset-nya.
Untuk mempermudah penjelasan, kita dapat misalkan array sebagai tangga yang terdiri atas beberapa anak tangga. Masing-masing anak tangga diletakkan satu jenis buah. Contoh: tangga pertama apel, kedua anggur, ketiga jeruk, dst.
Di sini, kita dapat mengidentifikasi lokasi buah tersebut hanya dengan menghitung jumlah langkah dari anak tangga pertama ke anak tangga tempat buah tersebut berada.
Berikut adalah contoh kode dari ilustrasi di atas
Karakteristik Array
Apapun karakteristik yang dimiliki oleh struktur data array adalah sebagai berikut:
- Array menggunakan struktur data berbasis indeks yang membantu mengidentifikasi setiap elemen dalam array dengan mudah menggunakan indeks.
- Jika pengguna ingin menyimpan beberapa nilai dari tipe data yang sama, maka array dapat digunakan secara efisien.
- Array juga dapat menangani struktur data yang kompleks dengan menyimpan data dalam array dua dimensi.
- Array juga digunakan untuk mengimplementasikan struktur data lain seperti stack, queue, heap, hash table, dll.
- Proses pencarian dalam sebuah array dapat dilakukan dengan sangat mudah.
Jenis-jenis Array
Berdasarkan dimensinya array dapat dikelompokkan dalam 2 jenis, yaitu: satu-dimensi (one dimensional array) dan multidimensi (multidimensional array).
- Array satu dimensi, yaitu array yang menyimpan list elemen tunggal. Array jenis ini merepresentasikan beberapa item data sebagai satu list
- Array multidimensi, yaitu array yang menyimpan list elemen dalam banyak dimensi. Istilah sederhananya, "array di dalam array". Array jenis ini mewakili beberapa item data sebagai tabel yang terdiri dari baris dan kolom.
Fungsi dan Kegunaan Array
Adapun fungsi dan kegunaan array adalah sebagai berikut:
- Digunakan untuk menyelesaikan masalah matriks.
- Membantu dalam menerapkan algoritma sorting.
- Digunakan untuk mengimplementasikan struktur data lain seperti stack, queue, heap, hash table, dll.
- Array juga dapat digunakan untuk penjadwalan CPU (CPU Scheduling).
- Dapat diterapkan sebagai tabel pencarian di komputer.
- Array dapat digunakan dalam pemrosesan suara di mana setiap sinyal suara adalah array.
Operasi-Operasi pada Array
Array memungkinkan kita mengakses elemen data secara acak. Cara ini membuat akses ke elemen array berdasarkan posisi tertentu menjadi lebih cepat dan efisien.
Operasi-operasi yang dapat dilakukan pada array, diantaranya menyisipkan data (insertion), mengakses data (access), dan mencari data (searching).
2.Pengertian Linked List
Linked list adalah strukur data linier berbentuk rantai simpul di mana setiap simpul menyimpan 2 item, yaitu nilai data dan pointer ke simpul elemen berikutnya. Berbeda dengan array, elemen linked list tidak ditempatkan dalam alamat memori yang berdekatan melainkan elemen ditautkan menggunakan pointer.
Simpul pertama dari linked list disebut sebagai head atau simpul kepala. Apabila linked list berisi elemen kosong, maka nilai pointer dari head menunjuk ke NULL. Begitu juga untuk pointer berikutnya dari simpul terakhir atau simpul ekor akan menunjuk ke NULL.
Ukuran elemen dari linked list dapat bertambah secara dinamis dan mudah untuk menyisipkan dan menghapus elemen karena tidak seperti array, kita hanya perlu mengubah pointer elemen sebelumnya dan elemen berikutnya untuk menyisipkan atau menghapus elemen.
Linked list biasanya digunakan untuk membuat file system, adjacency list, dan hash table.
Karakteristik Linked List
Sebuah linked list memiliki beberapa karakteristik sebagai berikut:
- Linked list menggunakan memori tambahan untuk menyimpan link (tautan)
- Untuk inisialiasi awal linked list, kita tidak perlu tahu ukuran dari elemen.
- Linked list umumnya dapat digunakan untuk mengimplementasikan struktur data lain seperti stack, queue, ataupun graf
- Simpul pertama dari linked list disebut sebagai Head.
- Pointer setelah simpul terakhir selalu bernilai NULL
- Dalam struktur data linked list, operasi penyisipan dan penghapusan dapat dilakukan dengan mudah
- Tiap-tiap simpul dari linked list berisi pointer atau tautan yang menjadi alamat dari simpul berikutnya
- Linked list bisa menyusut atau bertambah kapan saja dengan mudah.
Operasi-operasi pada Linked List
Ada beberapa operasi yang bisa kita lakukan pada struktur data linked list. Misalnya, operasi insertion yaitu tindakan menambahkan elemen baru ke linked list.
Berikut adalah daftar operasi dasar pada linked list:
- Traversal - mengakses setiap elemen dari linked list
- Insertion - menambahkan elemen baru ke linked list
- Deletion - menghapus elemen yang ada
- Searching - menemukan simpul pada linked list
- Sorting - mengurutkan simpul dari struktur linked list
Fungsi dan Kegunaan Linked List
Adapun fungsi dan kegunaan linked list adalah sebagai berikut:
- Linked list dapat digunakan untuk mengimplementasikan struktur data lain seperti stack, queue, graf, dll.
- Digunakan untuk melakukan operasi aritmatika pada bilangan long integer
- Dipakai untuk representasi matriks rongga.
- Digunakan dalam alokasi file yang ditautkan.
- Membantu dalam manajemen memori.
Penerapan linked list banyak ditemui dalam beberapa kasus berikut:
- Linked list digunakan dalam penjadwalan Round-Robin untuk melacak giliran dalam permainan multi-pemain.
- Digunakan dalam aplikasi penampil gambar. Gambar sebelumnya dan berikutnya ditautkan, sehingga dapat diakses oleh tombol prev dan next.
- Dalam playlist musik, lagu yang sedang diputar ditautkan ke lagu sebelumnya dan berikutnya.
Kelebihan Linked List
Berikut ini dalah keunggulan menggunakan linked list:
- Struktur data dinamis: Linked list adalah himpunan dinamis sehingga dapat bertambah dan menyusut saat runtime dengan mengalokasikan dan membatalkan alokasi memori. Jadi kita tidak perlu memberikan ukuran awal dari linked list.
- Tidak boros memori: Dalam linked list, pemanfaatan memori yang efisien dapat dicapai karena ukuran linked list bertambah atau berkurang pada runtime sehingga tidak ada pemborosan memori dan tidak perlu mengalokasikan memori sebelumnya.
- Implementasi: Struktur data linier seperti stack dan queue seringkali mudah diimplementasikan menggunakan linked list.
- Operasi penyisipan dan penghapusan: Operasi penyisipan dan penghapusan cukup mudah dalam linked list. Kita tidak perlu menggeser elemen setelah operasi penyisipan atau penghapusan elemen, hanya alamat yang ada di pointer berikutnya saja yang perlu diperbarui.
Kelemahan Linked List
Adapun kelemahan menggunakan linked list adalah sebagai berikut:
- Penggunaan memori: Linked list memerlukan lebih banyak memori dibandingkan dengan array. Karena dalam linked list, pointer juga perlu menyimpan alamat elemen berikutnya dan membutuhkan memori tambahan untuk dirinya sendiri.
- Traversal: Dalam traversal, linked list lebih banyak memakan waktu dibandingkan dengan array. Akses langsung ke elemen tidak bisa dilakukan pada linked list seperti array yang dapat akses elemen berdasarkan indeks. Untuk mengakses sebuah simpul pada posisi n dari linked list, kita harus melintasi semua simpul sebelumnya.
- Reverse Traversing: Dalam single linked list, reverse traversing tidak dimungkinkan, tetapi dalam kasus double-linked list, ini dapat dimungkinkan karena berisi pointer ke node yang terhubung sebelumnya dengan setiap node. Untuk melakukannya, diperlukan memori tambahan untuk pointer sebelumnya sehingga ada pemborosan memori.
- Akses Acak: Akses acak tidak bisa dilakukan dalam linked list karena alokasi memorinya yang dinamis.
3.Pengertian Struktur Data Heap
Heap adalah struktur data berbentuk complete binary tree yang memenuhi heap property.
Complete binary tree sendiri dapat didefinisikan sebagai binary tree di mana semua level terisi penuh, kecuali level terakhir. Semua kunci atau nilai pada level terakhir harus rata kiri apabila tidak terisi penuh.
Gambar di bawah ini adalah contoh dari complete binary tree.
Adapun jenis-jenis heap property di antaranya:
- Max-Heap: Kunci atau nilai yang ada di simpul mana pun harus lebih besar dari kunci/nilai yang ada di kedua simpul anaknya. Kunci terbesar ada di simpul akar (root node).
- Min-Heap: Kunci yang ada di simpul mana pun harus lebih kecil dari kunci yang ada di kedua anaknya. Kunci terkecil ada di simpul akar.
Karakteristik Struktur Data Heap
Heap memiliki ciri-ciri sebagai berikut:
- Sistem menetapkan heap identifier unik untuk setiap heap dalam grup aktivasi. Heap identifier untuk heap default selalu bernilai nol. API bindable manajemen penyimpanan, dipanggil oleh program atau prosedur, menggunakan heap identifier untuk mengidentifikasi heap yang akan digunakan untuk bertindak. API bindable harus dijalankan dalam grup aktivasi yang memiliki heap.
- Ukuran heap diperluas secara dinamis untuk memenuhi permintaan alokasi. Ukuran maksimum heap adalah (4GB – 512KB). Ukuran tersebut adalah ukuran heap maksimum jika jumlah total alokasi (pada satu waktu) tidak melebihi 128.000.
- Ukuran maksimum alokasi tunggal apa pun dari heap dibatasi hingga (16MB – 64KB).
Operasi-operasi pada Struktur Data Heap
Operasi umum yang terlibat dalam heap di antaranya:
- Heapify: Proses untuk mengatur ulang heap untuk mempertahankan properti heap.
- Find-max (atau Find-min): Menemukan item maksimum dari max-heap, atau item minimum dari min-heap.
- Insertion: Menambahkan item baru di heap.
- Deletion: Menghapus item dari heap.
- Extract Min-Max: Mengembalikan dan menghapus elemen maksimum atau minimum masing-masing di max-heap dan min-heap.
Heapify
Heapify adalah proses untuk mengatur ulang elemen heap untuk mempertahankan properti heap. Ini dilakukan ketika node tertentu menyebabkan ketidakseimbangan di heap karena beberapa operasi pada node tersebut.
Heapify dapat dilakukan dalam dua metodologi:
- up_heapify()
Metodologi heapify yang mengikuti pendekatan bottom-up. Kita akan memeriksa apakah node mengikuti properti heap dengan menuju ke arah rootNode atau tidak. Apabila tidak mengikuti, kita melakukan operasi tertentu agar tree mengikuti properti heap. - down_heapify()
Kebalikan dari up heapify, dimana down heapify mengikuti pendekatan top-down.Kita memeriksa apakah node mengikuti properti heap dengan menuju ke arah node daun. Jika node tidak mengikuti properti heap, kita melakukan operasi tertentu agar tree mengikuti properti heap.
Find-max (atau Find-min)
Elemen maksimum dan elemen minimum di max-heap dan min-heap ditemukan di simpul akar (root node) dari heap.
Insertion
Operasi insertion pada heap mengikuti langkah-langkah berikut
- Sisipkan elemen baru di ujung heap.
- Karena elemen yang baru dimasukkan dapat mendistorsi properti Heap. Jadi, kita perlu melakukan operasi up_heapify() , untuk menjaga properti heap dalam pendekatan bottom-up.
Deletion
Operasi deletion atau penghapusan standar pada heap adalah menghapus elemen yang ada di simpul akar heap. Operasi deletion mengikuti langkah berikut:
- Ganti elemen yang akan dihapus oleh elemen terakhir di heap.
- Hapus item terakhir dari heap.
- Sekarang, elemen terakhir ditempatkan pada beberapa posisi di heap, dimana ada kemungkinan tree tidak mengikuti properti heap, jadi kita perlu melakukan operasi down_heapify() untuk mempertahankan struktur heap. Operasi down_heapify() melakukan heapify dalam pendekatan top-bottom.
Extract Min-Max
Operasi ini mengembalikan dan menghapus elemen maksimum atau minimum masing-masing di max-heap dan min-heap. Elemen maksimum ditemukan di simpul akar.
Kegunaan Struktur Data Heap
- Heap digunakan untuk membuat antrian prioritas (priority queue).
- Heap sort adalah salah satu algoritma sorting tercepat dengan kompleksitas waktu O(N* log(N), dan mudah diimplementasikan.
- Best First Search (BFS) adalah teknik informed search, di mana teknik ini diimplementasikan menggunakan antrian prioritas yang dibuat dengan heap.
Kelebihan Struktur Data Heap
Struktur data heap memiliki keunggulan atau kelebihan sebagai berikut:
- Kompleksitas waktu pada struktur data heap cenderung lebih sedikit. Untuk memasukkan atau menghapus elemen di heap, kompleksitas waktunya hanya O(log N).
- Membantu untuk menemukan jumlah minimum dan jumlah terbesar.
- Untuk operasi peek elemen paling awal, kompleksitas waktunya konstan O(1).
- Dapat diimplementasikan menggunakan array, tidak memerlukan ruang ekstra untuk pointer.
- Binary heap adalah pohon biner yang seimbang, dan mudah diterapkan.
- Heap dapat dibuat dengan O(N) waktu.
Kekurangan Struktur Data Heap
Berikut ini adalah beberapa kekurangan dari struktur data heap:
- Kompleksitas waktu untuk mencari elemen di Heap adalah O(N).
- Untuk menemukan penerus atau pendahulu dari suatu elemen, heap membutuhkan waktu O(N), sedangkan BST hanya membutuhkan waktu O(log N).
- Untuk mencetak semua elemen heap dalam urutan kompleksitas waktu adalah O(N*log N), sedangkan untuk BST, hanya dibutuhkan waktu O(N).
- Manajemen memori lebih kompleks dalam tumpukan memori karena digunakan secara global. Memori heap dibagi menjadi dua bagian - generasi lama dan generasi muda dll. pada garbage collection milik java.
4.Struktur Data Stack
Cara struktur data stack dalam menyimpan sebuah nilai dapat kita bayangkan seperti piring yang disusun rapi secara bertumpuk ke atas. Apabila kita ingin mengambil piring bagian bawah, kita harus terlebih dahulu menyisihkan semua piring yang ada di atas.
Dalam istilah pemrograman, upaya menambahkan elemen pada struktur data stack disebut dengan push. Sedangkan proses menghapus atau menghilangkan elemen data dari stack disebut pop.
Dari gambar di atas, dapat terlihat bahwa meskipun elemen ke-3 adalah yang paling terakhir ditambahkan, namun elemen tersebut justru yang pertama dihapus. Operasi inilah yang kemudian disebut sebagai prinsip operasi LIFO (Last In First Out).
Kita dapat mengimplementasikan stack dengan bahasa pemrograman seperti C, C++, Java, Python, atau C#.
Contoh kode implementasi stack dengan bahasa pemrograman C++
Jenis-jenis Stack
Berdasarkan kemampuan menyimpan data, struktur data stack dapat dibagi menjadi 2 jenis, yaitu: register stack dan memory stack.
1. Register stack
Register stack merupakan stack yang hanya mampu menampung data dalam jumlah yang kecil. Kedalaman maksimum pada register stack cenderung dibatasi karena ukuran unit memorinya sangat kecil dibandingkan dengan memory stack.
2. Memory stack
Pada stack jenis ini, kedalaman dari stack cukup fleksibel dan mampu menangani dalam dalam skala yang lebih besar dibandingkan jenis sebelumnya.
Karakteristik Stack
Struktur data stack memiliki ciri sebagai berikut:
- Stack digunakan pada banyak algoritma yang berbeda seperti Tower of Hanoi, Tree traversal, rekursi dll.
- Stack diimplementasikan dengan struktur data array atau linked list.
- Mengikuti prinsip operasi Last In First Out, yaitu elemen yang dimasukkan pertama akan muncul terakhir dan sebaliknya.
- Penyisipan dan penghapusan terjadi di satu ujung yaitu dari atas tumpukan.
- Apabila ruang memori yang dialokasikan untuk struktur data stack sudah penuh namun masih dilakukan operasi penyisipan elemen maka akan terjadi stack overflow.
- Apabila struktur data tidak memiliki elemen data atau kosong, namun tetap dilakukan operasi penghapusan maka akan terjadi stack underflow
Operasi-operasi Dasar pada Stack
Ada beberapa operasi dasar yang bisa kita untuk lakukan terhadap struktur data stack. Operasi-operasi tersebut meliputi
- Push: Menyisipkan elemen ke bagian atas stack
- Pop: Menghapus elemen atas dari stack
- IsEmpty: Memeriksa apakah stack kosong
- IsFull: Memerika apakah stack sudah penuh
- Peek: Mendapatkan nilai elemen teratas tanpa menghapusnya
Fungsi dan Kegunaan Stack
Adapun fungsi dan kegunaan struktur data stack adalah sebagai berikut:
- Struktur data stack digunakan dalam evaluasi dan konversi ekspresi aritmatika. Proses ini banyak dipakai untuk program kompiler.
- Stack digunakan dalam pemrograman rekursi.
- Digunakan untuk pemeriksaan tanda kurung.
- Stack digunakan dalam manajemen memori.
- Dipakai untuk memproses pemanggilan sebuah fungsi.
Salah satu contoh penerapan struktur data stack adalah fitur tombol back pada browser. Dimana browser akan menyimpan semua URL yang telah kita kunjungi sebelumnya dalam stack.
Setiap kali kita mengunjungi halaman baru, halaman itu ditambahkan di atas stack. Saat kita menekan tombol kembali, URL saat ini dihapus dari tumpukan, dan URL sebelumnya diakses.
Kelebihan Menggunakan Stack
Adapun kelebihan menggunakan struktur data stack di antaranya:
- Manajemen data yang efisien: Stack membantu mengelola data berdasarkan prinsip operasi LIFO yang tidak bisa dilakukan dengan linked list dan array.
- Manajemen fungsi yang efisien: Ketika suatu fungsi dipanggil, variabel lokal disimpan dalam stack, dan secara otomatis dihancurkan setelah dikembalikan.
- Kontrol atas memori: Stack memungkinkan kita untuk mengontrol bagaimana memori dialokasikan dan tidak dialokasikan.
- Manajemen memori cerdas: Stack secara otomatis membersihkan objek.
- Tidak mudah rusak: Stack tidak mudah rusak, oleh karena itu stack cenderung lebih aman dan dapat diandalkan.
- Tidak mengizinkan pengubahan ukuran variabel: Variabel pada stack tidak dapat diubah ukurannya.
Kekurangan Menggunakan Stack
- Ukuran memori terbatas: Memori pada stack cukup terbatas.
- Kemungkinan stack overflow: Terlalu banyak membuat objek di stack dapat meningkatkan risiko stack overflow.
- Akses acak tidak dimungkinkan: Dalam stack, akses data secara acak tidak bisa dilakukan. Data yang dapat diakses adalah data yang berada pada elemen atas.
- Dapat menyebabkan fungsi tidak tedefinisi: Ketika penyimpanan variabel akan ditimpa, kadang-kadang akan menyebabkan perilaku fungsi atau program yang tidak terdefinisi.
- Penghentian yang tidak diinginkan: Jika stack berada di luar memori maka dapat menyebabkan penghentian yang tidak normal.
5.Pengertian Byte
Jenis Byte
Konversi Byte
- 1 Kilobyte= 1024 Bytes.
- 1 Megabyte = 1.024 Kilobytes = 1.048.576 Bytes.
- 1 Gigabyte = 1.024 Megabytes = 1.073.741.824 Bytes.
- 1 Terrabyte = 1.024 Gigabytes = 1.099.511.627.776 Bytes.
- 1 Petabyte = 1.024 Terabytes = 1.125.899.906.842.624 Bytes.
- 1 Exabyte = 1.024 Petabytes = 1.152.921.504.606.846.976 Bytes.
- 1 Zettabyte = 1.024 Exabytes = 1.180.591.620.717.411.303.424 Bytes.
- 1 Yottabyte = 1.024 Zettabytes = 1. 208.925.819.614.629.174.706. 176 Bytes.
Komentar
Posting Komentar