Struktur Data Adalah? 8 Struktur Data Umum yang Wajib Diketahui Programmer

Last Updated on October 23, 2020 by

Struktur Data adalah cara khusus mengatur dan menyimpan data di komputer sedemikian rupa sehingga kita dapat melakukan operasi pada data yang disimpan dengan lebih efisien. Struktur data memiliki cakupan penggunaan yang luas dan beragam di seluruh bidang Ilmu Komputer dan Rekayasa Perangkat Lunak.

Struktur data kini digunakan di hampir setiap program atau sistem perangkat lunak yang telah dikembangkan. Selain itu, struktur data datang di bawah dasar-dasar Ilmu Komputer dan Rekayasa Perangkat Lunak. Ini adalah topik utama dalam pertanyaan wawancara Rekayasa Perangkat Lunak. Karenanya sebagai pengembang, kita harus memiliki pengetahuan yang baik tentang struktur data.

Jenis Struktur Data

Struktur data adalah hal yang wajib diketahui oleh programmer. Pada artikel ini, saya akan menjelaskan secara singkat 8 struktur data yang biasa digunakan setiap programmer harus tahu.

1. Arrays

 
Array adalah struktur ukuran tetap, yang dapat menampung item dengan tipe data yang sama. Ini bisa berupa array bilangan bulat, array angka floating-point, array string atau bahkan array array (seperti array 2 dimensi). Array diindeks, artinya akses acak dimungkinkan.

Operasi Array

• Traverse: Telusuri elemen-elemen dan cetaklah.
• Cari: Mencari elemen dalam array. Anda dapat mencari elemen berdasarkan nilainya atau indeksnya
• Pembaruan: Perbarui nilai elemen yang ada pada indeks yang diberikan

 
Memasukkan elemen ke array dan menghapus elemen dari array tidak dapat langsung dilakukan karena array memiliki ukuran yang tetap. Jika Anda ingin menyisipkan elemen ke array, pertama-tama Anda harus membuat array baru dengan peningkatan ukuran (ukuran saat ini + 1), salin elemen yang ada dan tambahkan elemen baru. Hal yang sama berlaku untuk penghapusan dengan array baru ukuran yang diperkecil.

Penerapan Array

• Digunakan sebagai blok penyusun untuk membangun struktur data lain seperti daftar susunan, tumpukan, tabel hash, vektor dan matriks.
• Digunakan untuk berbagai algoritma penyortiran seperti penyisipan, penyortiran cepat, penyortiran gelembung dan penggabungan.

2. Linked Lists

Daftar tertaut adalah struktur berurutan yang terdiri dari urutan item dalam urutan linier yang dihubungkan satu sama lain. Karenanya, Anda harus mengakses data secara berurutan dan akses acak tidak dimungkinkan. Linked Linked menyediakan representasi sederhana dan fleksibel dari set dinamis.

Mari kita pertimbangkan persyaratan berikut tentang daftar tertaut. Anda bisa mendapatkan ide yang jelas dengan merujuk pada Gambar 2.

• Elemen dalam daftar tertaut dikenal sebagai node.
• Setiap node berisi kunci dan pointer ke node penggantinya, yang dikenal sebagai next.
• Atribut yang bernama head points ke elemen pertama dari daftar tertaut.
• Elemen terakhir dari daftar tertaut dikenal sebagai ekor.

 
Berikut ini adalah berbagai jenis daftar tertaut yang tersedia.

• Singly linked list —Traversal item hanya dapat dilakukan ke arah depan.
• Doubly linked list — Traversal of items can be done in both forward and backward directions. Nodes consist of an additional pointer known as prev, pointing to the previous node.
• Circular linked lists — Linked lists where the prev pointer of the head points to the tail and the next pointer of the tail points to the head.

Pengoperasian Linked list

• Cari: Temukan elemen pertama dengan kunci k dalam daftar tertaut yang diberikan oleh pencarian linear sederhana dan mengembalikan pointer ke elemen ini
• Sisipkan: Sisipkan kunci ke daftar tertaut. Penyisipan dapat dilakukan dengan 3 cara berbeda; masukkan di awal daftar, masukkan di akhir daftar dan masukkan di tengah daftar.
• Hapus: Menghapus elemen x dari daftar tertaut yang diberikan. Anda tidak dapat menghapus simpul dengan satu langkah. Penghapusan dapat dilakukan dengan 3 cara berbeda; hapus dari awal daftar, hapus dari akhir daftar dan hapus dari tengah daftar.

Applications of linked lists

• Digunakan untuk manajemen tabel simbol dalam desain kompiler.
• Digunakan untuk beralih antar program menggunakan Alt + Tab (diimplementasikan menggunakan Circular Linked List).

3. Stacks

 
Stacks adalah struktur LIFO (Last In First Out – elemen yang ditempatkan pada akhirnya dapat diakses pada awalnya) yang biasanya ditemukan dalam banyak bahasa pemrograman. Struktur ini dinamai “tumpukan” karena menyerupai tumpukan dunia nyata – tumpukan piring.

Pengoperasian Stack

 
Diberikan di bawah ini adalah 2 operasi dasar yang dapat dilakukan pada tumpukan. Silakan lihat Gambar 3 untuk mendapatkan pemahaman yang lebih baik tentang operasi stack.

• Push: Masukkan elemen ke atas stack.
• Pop: Hapus elemen paling atas dan kembalikan.

 
Selanjutnya, fungsi tambahan berikut disediakan untuk stack untuk memeriksa statusnya.

• Peek: Kembalikan elemen atas tumpukan tanpa menghapusnya.
• isEmpty: Check jika stack nya kosong.
• isFull: Mengecek jika stack penuh

Pengaplikasian Stack struktur data adalah sebagai berikut:

• Digunakan untuk evaluasi ekspresi (mis .: algoritma shunting-yard untuk mem-parsing dan mengevaluasi ekspresi matematika).
• Digunakan untuk mengimplementasikan panggilan fungsi dalam pemrograman rekursi.

4. Queues

Antrian adalah struktur FIFO (First In First Out – elemen yang ditempatkan pada awalnya dapat diakses pada awalnya) yang dapat ditemukan dalam banyak bahasa pemrograman. Struktur ini dinamai “antrian” karena menyerupai antrian dunia nyata – orang yang menunggu dalam antrian.

Queue operations

 
Diberikan di bawah ini adalah 2 operasi dasar yang dapat dilakukan pada antrian. Silakan lihat Gambar 4 untuk mendapatkan pemahaman yang lebih baik tentang operasi antrian.

• Enqueue: Masukkan elemen ke ujung antrian.
• Dequeue: Hapus elemen dari awal antrian.

Applications of queues

• Digunakan untuk mengelola utas dalam multithreading.
• Digunakan untuk menerapkan sistem antrian (mis .: antrian prioritas).

5. Hash Tables

 
Tabel Hash adalah struktur data yang menyimpan nilai yang memiliki kunci yang terkait dengan masing-masingnya. Selain itu, ini mendukung pencarian secara efisien jika kita tahu kunci yang terkait dengan nilai. Oleh karena itu sangat efisien dalam memasukkan dan mencari, terlepas dari ukuran data.

Pengalamatan Langsung menggunakan pemetaan satu-ke-satu antara nilai dan kunci saat menyimpan dalam sebuah tabel. Namun, ada masalah dengan pendekatan ini ketika ada sejumlah besar pasangan nilai kunci. Tabel akan sangat besar dengan begitu banyak catatan dan mungkin tidak praktis atau bahkan tidak mungkin untuk disimpan, mengingat memori yang tersedia pada komputer biasa. Untuk menghindari masalah ini, kami menggunakan tabel hash.

Fungsi Hash

 
Fungsi khusus bernama fungsi hash (h) digunakan untuk mengatasi masalah yang disebutkan di atas dalam pengalamatan langsung.

Dalam mengakses langsung, nilai dengan kunci k disimpan dalam slot k. Menggunakan fungsi hash, kami menghitung indeks tabel (slot) yang digunakan untuk setiap nilai. Nilai yang dihitung menggunakan fungsi hash untuk kunci yang diberikan disebut nilai hash yang menunjukkan indeks tabel yang nilainya dipetakan.

h(k) = k % m

• h: Fungsi hash
• k: Kunci yang nilai hashnya harus ditentukan
• m: Ukuran tabel hash (jumlah slot tersedia). Nilai prima yang tidak mendekati kekuatan tepat 2 adalah pilihan yang baik untuk m.

Pertimbangkan fungsi hash h (k) = k% 20, di mana ukuran tabel hash adalah 20. Diberikan seperangkat kunci, kami ingin menghitung nilai hash masing-masing untuk menentukan indeks di mana ia harus pergi dalam tabel hash . Anggap kita memiliki kunci berikut, indeks hash dan tabel hash.

• 1 → 1%20 → 1
• 5 → 5%20 → 5
• 23 → 23%20 → 3
• 63 → 63%20 → 3

Dari dua contoh terakhir yang diberikan di atas, kita dapat melihat bahwa tabrakan dapat muncul ketika fungsi hash menghasilkan indeks yang sama untuk lebih dari satu kunci. Kita dapat menyelesaikan tabrakan dengan memilih fungsi hash yang sesuai dan menggunakan teknik seperti chaining dan open addressing.

Applications of hash tables

• Digunakan untuk mengimplementasikan indeks basis data.
• Digunakan untuk mengimplementasikan array asosiatif.
• Digunakan untuk mengimplementasikan struktur data “set”.

6. Trees

 
Pohon adalah struktur hierarkis di mana data disusun secara hierarkis dan dihubungkan bersama. Struktur ini berbeda dari daftar yang ditautkan sedangkan, dalam daftar yang ditautkan, barang ditautkan dalam urutan linier.

Berbagai jenis pohon telah dikembangkan selama beberapa dekade terakhir, agar sesuai dengan aplikasi tertentu dan memenuhi kendala tertentu. Beberapa contoh adalah pohon pencarian biner, pohon B, pohon treap, pohon merah-hitam, pohon splay, pohon AVL dan pohon n-ary.

Binary Search Trees

 
Pohon pencarian biner (BST), seperti namanya, adalah pohon biner di mana data disusun dalam struktur hierarkis. Struktur data ini menyimpan nilai dalam urutan diurutkan.

Setiap node dalam pohon pencarian biner terdiri dari atribut berikut.

1. key: Nilai yang disimpan dalam node.
2. Left: Penunjuk ke anak kiri.
3. Right: Penunjuk ke anak yang tepat.
4. p: Penunjuk ke simpul induk.

 
Tree Search binary memperlihatkan properti unik yang membedakannya dari pohon lain. Properti ini dikenal sebagai properti pohon pencarian biner.

Biarkan x menjadi simpul pada trees search biner.

• Jika y adalah simpul di subtree kiri x, maka y.key ≤ x.key
• Jika y adalah simpul di subtree kanan x, maka y.key ≥ x.key

Pengaplikasian trees

• Binary Trees: Digunakan untuk mengimplementasikan parser ekspresi dan pemecah ekspresi.
• Binary Search Tree: digunakan dalam banyak aplikasi pencarian di mana data secara konstan masuk dan keluar.
• Heaps: digunakan oleh JVM (Java Virtual Machine) untuk menyimpan objek Java.
• Treaps: digunakan dalam jaringan nirkabel.

7. Heaps

Struktur data Heap adalah kasus khusus dari pohon biner di mana node induk dibandingkan dengan anak-anak mereka dengan nilai-nilai mereka dan diatur sesuai.

Mari kita lihat bagaimana kita bisa mewakili banyak. Tumpukan dapat direpresentasikan menggunakan pohon dan juga array. Gambar 7 dan 8 menunjukkan bagaimana kita bisa mewakili tumpukan biner menggunakan pohon biner dan array.

Heaps bisa terdiri dari 2 jenis.

1. Min Heap Struktur data adalah  yang mana kunci dari orang tua kurang dari atau sama dengan anak-anaknya. Ini disebut properti min-heap. Root akan berisi nilai minimum heap.
2. Max Heap  struktur data adalah di mana kunci parents lebih besar atau sama dengan anak-anaknya. Ini disebut properti max-heap. Root akan berisi nilai maksimum heap.

Pengaplikasian heaps

• Digunakan dalam algoritma heapsort.
• Digunakan untuk mengimplementasikan antrian prioritas karena nilai prioritas dapat dipesan sesuai dengan properti heap di mana heap dapat diimplementasikan menggunakan array.
• Fungsi antrian dapat diimplementasikan menggunakan tumpukan dalam waktu O (log n).
• Digunakan untuk menemukan nilai kᵗʰ terkecil (atau terbesar) dalam array yang diberikan.

8. Graphs

 
Grafik terdiri dari sekumpulan simpul atau node hingga dan satu set tepi yang menghubungkan simpul-simpul ini. Urutan grafik adalah jumlah simpul dalam grafik. Ukuran grafik adalah jumlah sisi dalam grafik. Dua node dikatakan berdekatan jika mereka terhubung satu sama lain dengan tepi yang sama.

Directed Graphs

 
Grafik G dikatakan sebagai grafik berarah jika semua tepinya memiliki arah yang menunjukkan apa itu start vertex dan apa itu end vertex.

Kami mengatakan bahwa (u, v) adalah insiden dari atau meninggalkan simpul u dan merupakan kejadian atau memasuki simpul v.

Self-loop: Tepi dari puncak ke dirinya sendiri.

Undirected Graphs

 
Grafik G dikatakan sebagai grafik tidak terarah jika semua tepinya tidak memiliki arah. Ini bisa terjadi dengan dua cara antara dua simpul.

Jika sebuah titik tidak terhubung ke simpul lain dalam grafik, dikatakan titik itu terisolasi.

Pengaplikasian graphs

• Digunakan untuk mewakili jaringan media sosial. Setiap pengguna adalah simpul, dan ketika pengguna terhubung mereka menciptakan keunggulan.
• Digunakan untuk mewakili halaman web dan tautan oleh mesin pencari. Halaman web di internet dihubungkan satu sama lain oleh hyperlink. Setiap halaman adalah simpul dan hyperlink antara dua halaman adalah keunggulan. Digunakan untuk Peringkat Halaman di Google.
• Digunakan untuk mewakili lokasi dan rute di GPS. Lokasi adalah simpul dan rute yang menghubungkan lokasi adalah pinggiran. Digunakan untuk menghitung rute terpendek antara dua lokasi.

Kesimpulan

 
Sebagai seorang programmer atau Anda ingin menjadi seorang programmer, struktur data adalah komponen pemrograman yang wajib dikuasai. 8 Jenis struktu data di atas adalah yang umum digunakan. Namun penggunaannya sendiri adalah sesuai dengan jenis project yang dikembangkan. Demikian ulasan kami tentang struktur data. Semoga bermanfaat.