10 Struktur Data Umum Dijelaskan dengan Video + Latihan

“Programer yang buruk mengkhawatirkan kodenya. Pemrogram yang baik mengkhawatirkan struktur data dan hubungannya. " - Linus Torvalds, pencipta Linux ** Perbarui ** Kursus video saya tentang Algoritma sekarang ditayangkan! Lihat Algoritma yang Bergerak dari Manning Publications. Dapatkan diskon 39% untuk kursus saya dengan menggunakan kode ' 39carnes '! Atau Anda bisa mendapatkan diskon 50% dari kursus Deep Learning in Motion saya dengan kode ' vlcarnes2 '.

Struktur data adalah bagian penting dari pengembangan perangkat lunak, dan salah satu topik paling umum untuk pertanyaan wawancara kerja pengembang.

Kabar baiknya adalah bahwa mereka pada dasarnya hanya format khusus untuk mengatur dan menyimpan data.

Saya akan mengajari Anda 10 dari struktur data yang paling umum - di sini, di artikel singkat ini.

Saya telah menyematkan video yang saya buat untuk masing-masing struktur data ini. Saya juga telah menautkan ke contoh kode untuk masing-masing, yang menunjukkan bagaimana menerapkannya di JavaScript.

Dan untuk memberi Anda beberapa latihan, saya telah menautkan ke tantangan dari kurikulum freeCodeCamp.

Perhatikan bahwa beberapa dari struktur data ini menyertakan kompleksitas waktu dalam notasi Big O. Ini tidak termasuk untuk semuanya karena kompleksitas waktu terkadang didasarkan pada bagaimana penerapannya. Jika Anda ingin mempelajari lebih lanjut tentang Big O Notation, lihat artikel saya tentang itu atau video oleh Briana Marie ini.

Perhatikan juga bahwa meskipun saya menunjukkan cara mengimplementasikan struktur data ini dalam JavaScript, untuk sebagian besar dari mereka Anda tidak perlu menerapkannya sendiri, kecuali Anda menggunakan bahasa tingkat rendah seperti C.

JavaScript (seperti kebanyakan bahasa tingkat tinggi) memiliki implementasi bawaan dari banyak struktur data ini.

Namun, mengetahui cara menerapkan struktur data ini akan memberi Anda keunggulan besar dalam pencarian pekerjaan developer Anda, dan mungkin berguna saat Anda mencoba menulis kode performa tinggi.

Daftar Tertaut

Daftar tertaut adalah salah satu struktur data paling dasar. Ini sering dibandingkan dengan larik karena banyak struktur data lainnya dapat diimplementasikan dengan larik atau daftar tertaut. Mereka masing-masing memiliki kelebihan dan kekurangan.

Daftar tertaut terdiri dari sekelompok node yang bersama-sama mewakili sebuah urutan. Setiap node berisi dua hal: data aktual yang disimpan (yang pada dasarnya dapat berupa semua jenis data) dan penunjuk (atau tautan) ke node berikutnya dalam urutan. Ada juga daftar tertaut ganda di mana setiap node memiliki penunjuk ke item berikutnya dan item sebelumnya dalam daftar.

Operasi paling dasar dalam daftar tertaut adalah menambahkan item ke daftar, menghapus item dari daftar, dan mencari item di daftar.

Lihat kode untuk daftar tertaut di JavaScript di sini.

Kompleksitas waktu daftar yang ditautkan

AlgoritmaRata-rataKasus terburuk
Ruang0 (n)0 (n)
Cari0 (n)0 (n)
Memasukkan0 (1)0 (1)
Menghapus0 (1)0 (1)

tantangan freeCodeCamp

  • Bekerja dengan Node dalam Daftar Tertaut
  • Buat Kelas Daftar Tertaut
  • Hapus Elemen dari Daftar Tertaut
  • Cari di dalam Daftar Tertaut
  • Hapus Elemen dari Daftar Tertaut dengan Indeks
  • Tambahkan Elemen pada Indeks Tertentu dalam Daftar Tertaut
  • Buat Daftar Tertaut Ganda
  • Membalikkan Daftar Tertaut Ganda

Tumpukan

Tumpukan adalah struktur data dasar tempat Anda hanya dapat menyisipkan atau menghapus item di bagian atas tumpukan. Ini seperti tumpukan buku. Jika Anda ingin melihat buku di tengah tumpukan, Anda harus melepaskan semua buku di atasnya terlebih dahulu.

Tumpukan dianggap LIFO (Last In First Out) - artinya barang terakhir yang Anda masukkan ke dalam tumpukan adalah barang pertama yang keluar dari tumpukan

Ada tiga operasi utama yang dapat dilakukan pada tumpukan: memasukkan item ke dalam tumpukan (disebut 'push'), menghapus item dari tumpukan (disebut 'pop'), dan menampilkan konten tumpukan (terkadang disebut 'pip ').

Lihat kode tumpukan JavaScript di sini.

Tumpuk kerumitan waktu

AlgoritmaRata-rataKasus terburuk
Ruang0 (n)0 (n)
Cari0 (n)0 (n)
Memasukkan0 (1)0 (1)
Menghapus0 (1)0 (1)

tantangan freeCodeCamp

  • Pelajari cara Kerja Stack
  • Buat Kelas Stack

Antrian

Anda dapat menganggap antrian sebagai antrean orang di toko bahan makanan. Yang pertama di antrean adalah yang pertama disajikan. Persis seperti antrian.

Antrian dianggap FIFO (First In First Out) untuk mendemonstrasikan cara mengakses data. Ini berarti bahwa setelah elemen baru ditambahkan, semua elemen yang telah ditambahkan sebelumnya harus dihilangkan sebelum elemen baru dapat dihapus.

Antrian hanya memiliki dua operasi utama: enqueue dan dequeue. Enqueue berarti memasukkan item ke belakang antrian dan dequeue berarti menghapus item depan.

Lihat kode antrian di JavaScript di sini.

Kompleksitas waktu antrian

AlgoritmaRata-rataKasus terburuk
Ruang0 (n)0 (n)
Cari0 (n)0 (n)
Memasukkan0 (1)0 (1)
Menghapus0 (1)0 (1)

tantangan freeCodeCamp

  • Buat Kelas Antrian
  • Buat Kelas Antrian Prioritas
  • Buat Antrian Edaran

Set

Struktur data himpunan menyimpan nilai tanpa urutan tertentu dan tanpa nilai berulang. Selain dapat menambah dan menghapus elemen ke sebuah set, ada beberapa fungsi set penting lainnya yang bekerja dengan dua set sekaligus.

  • Union - Ini menggabungkan semua item dari dua set berbeda dan mengembalikannya sebagai set baru (tanpa duplikat).
  • Intersection - Diberikan dua set, fungsi ini mengembalikan set lain yang memiliki semua item yang merupakan bagian dari kedua set.
  • Selisih - Ini mengembalikan daftar item yang ada dalam satu set tetapi BUKAN dalam set yang berbeda.
  • Subset - Ini mengembalikan nilai boolean yang menunjukkan jika semua elemen dalam satu set disertakan dalam set berbeda.

Lihat kode untuk menerapkan satu set dalam JavaScript di sini.

tantangan freeCodeCamp

  • Buat Kelas Set
  • Hapus dari Set
  • Ukuran Set
  • Lakukan Gabungan pada Dua Set
  • Lakukan Persimpangan pada Dua Kumpulan Data
  • Lakukan Perbedaan pada Dua Kumpulan Data
  • Lakukan Pemeriksaan Subset pada Dua Kumpulan Data
  • Buat dan Tambahkan ke Set di ES6
  • Hapus item dari satu set di ES6
  • Gunakan .has dan .size pada Set ES6
  • Gunakan Spread dan Notes untuk Integrasi ES5 Set ()

Maps

Peta adalah struktur data yang menyimpan data dalam pasangan kunci / nilai yang setiap kuncinya unik. Peta terkadang disebut larik asosiatif atau kamus. Ini sering digunakan untuk mencari data dengan cepat. Peta memungkinkan hal-hal berikut:

  • penambahan sepasang ke dalam koleksi
  • penghapusan sepasang dari koleksi
  • modifikasi dari pasangan yang sudah ada
  • pencarian nilai yang terkait dengan kunci tertentu

Lihat kode untuk menerapkan peta dalam JavaScript di sini.

tantangan freeCodeCamp

  • Buat Struktur Data Peta
  • Buat Peta JavaScript ES6

Tabel Hash

Tabel hash adalah struktur data peta yang berisi pasangan kunci / nilai. Ini menggunakan fungsi hash untuk menghitung indeks ke dalam array keranjang atau slot, dari mana nilai yang diinginkan dapat ditemukan.

Fungsi hash biasanya mengambil string sebagai input dan mengeluarkan nilai numerik. Fungsi hash harus selalu memberikan nomor keluaran yang sama untuk masukan yang sama. Jika dua input memiliki hash ke output numerik yang sama, ini disebut collision. Tujuannya adalah agar sedikit tabrakan.

Jadi ketika Anda memasukkan pasangan kunci / nilai ke dalam tabel hash, kunci tersebut dijalankan melalui fungsi hash dan berubah menjadi angka. Nilai numerik ini kemudian digunakan sebagai kunci sebenarnya yang menyimpan nilai tersebut. Saat Anda mencoba mengakses kunci yang sama lagi, fungsi hashing akan memproses kunci tersebut dan mengembalikan hasil numerik yang sama. Nomor tersebut kemudian akan digunakan untuk mencari nilai terkait. Ini memberikan rata-rata waktu pencarian O (1) yang sangat efisien.

Lihat kode untuk tabel hash di sini.

Kompleksitas waktu tabel hash

AlgoritmaRata-rataKasus terburuk
Ruang0 (n)0 (n)
Cari0 (1)0 (n)
Memasukkan0 (1)0 (n)
Menghapus0 (1)0 (n)

tantangan freeCodeCamp

  • Buat Tabel Hash

Pohon Pencarian Biner

Pohon adalah struktur data yang terdiri dari node. Pohon memiliki karakteristik sebagai berikut:

  1. Setiap pohon memiliki simpul akar (di atas).
  2. Node akar memiliki nol atau lebih simpul anak.
  3. Setiap simpul anak memiliki nol atau lebih simpul anak, dan seterusnya.

Sebuah biner pencarian pohon menambahkan dua karakteristik ini:

  1. Setiap node memiliki hingga dua anak.
  2. Untuk setiap node, turunan kirinya lebih kecil dari node saat ini, yang lebih kecil dari turunan kanan.

Pohon pencarian biner memungkinkan pencarian cepat, penambahan dan penghapusan item. Cara pengaturannya berarti bahwa, rata-rata, setiap perbandingan memungkinkan operasi untuk melewati sekitar setengah dari pohon, sehingga setiap pencarian, penyisipan atau penghapusan membutuhkan waktu yang sebanding dengan logaritma jumlah item yang disimpan dalam pohon.

Lihat kode untuk pohon pencarian biner dalam JavaScript di sini.

Kompleksitas waktu pencarian biner

AlgoritmaRata-rataKasus terburuk
Ruang0 (n)0 (n)
Cari0 (log n)0 (n)
Memasukkan0 (log n)0 (n)
Menghapus0 (log n)0 (n)

tantangan freeCodeCamp

  • Temukan Nilai Minimum dan Maksimum dalam Pohon Pencarian Biner
  • Tambahkan Elemen Baru ke Pohon Pencarian Biner
  • Periksa apakah Elemen Ada di Pohon Pencarian Biner
  • Temukan Tinggi Minimum dan Maksimum dari Pohon Pencarian Biner
  • Gunakan Pencarian Kedalaman Pertama di Pohon Pencarian Biner
  • Gunakan Breadth First Search di Binary Search Tree
  • Hapus Leaf Node di Binary Search Tree
  • Hapus Node dengan Satu Anak di Pohon Pencarian Biner
  • Hapus Node dengan Dua Anak di Pohon Pencarian Biner
  • Balikkan Pohon Biner

Trie

Trie (dibaca 'try'), atau pohon awalan, adalah sejenis pohon pencarian. Trie menyimpan data dalam langkah-langkah di mana setiap langkah adalah node di trie. Percobaan sering kali digunakan untuk menyimpan kata untuk pencarian cepat, seperti fitur pelengkapan otomatis kata.

Setiap node dalam trie bahasa berisi satu huruf dari sebuah kata. Anda mengikuti cabang trie untuk mengeja sebuah kata, satu huruf pada satu waktu. Langkah-langkahnya mulai bercabang ketika urutan hurufnya berbeda dari kata lain di trie, atau ketika sebuah kata berakhir. Setiap node berisi huruf (data) dan boolean yang menunjukkan apakah node tersebut adalah node terakhir dalam sebuah kata.

Lihatlah gambarnya dan Anda dapat membentuk kata-kata. Selalu mulai dari simpul akar di atas dan ke bawah. Trie yang ditampilkan di sini berisi kata ball, bat, doll, do, dork, dorm, send, sense.

Lihat kode untuk mencoba JavaScript di sini.

tantangan freeCodeCamp

  • Buat Pohon Pencarian Trie

Heap Biner

Heap biner adalah tipe lain dari struktur data pohon. Setiap node memiliki paling banyak dua anak. Juga, itu adalah pohon yang lengkap. Artinya semua level terisi penuh sampai level terakhir dan level terakhir diisi dari kiri ke kanan.

Heap biner bisa berupa min heap atau max heap. Dalam heap maks, kunci node induk selalu lebih besar dari atau sama dengan kunci turunannya. Dalam heap min, kunci node induk kurang dari atau sama dengan kunci anak-anak.

Urutan antar level itu penting tetapi urutan node pada level yang sama tidak penting. Pada gambar, Anda dapat melihat bahwa level ketiga dari tumpukan minimum memiliki nilai 10, 6, dan 12. Angka-angka itu tidak berurutan.

Lihat kode untuk tumpukan di JavaScript di sini.

Kompleksitas waktu heap biner

AlgoritmaRata-rataKasus terburuk
Ruang0 (n)0 (n)
Cari0 (1)0 (log n)
Memasukkan0 (log n)0 (log n)
Menghapus0 (1)0 (1)

tantangan freeCodeCamp

  • Sisipkan Elemen ke dalam Max Heap
  • Hapus Elemen dari Max Heap
  • Menerapkan Urutan Heap dengan Min Heap

Grafik

Grafik adalah kumpulan node (juga disebut simpul) dan koneksi (disebut tepi) di antara mereka. Grafik juga dikenal sebagai jaringan.

Salah satu contoh grafik adalah jejaring sosial. Node adalah orang dan ujungnya adalah persahabatan.

Ada dua jenis grafik utama: diarahkan dan tidak diarahkan. Grafik tidak berarah adalah grafik tanpa arah pada tepi antar node. Grafik berarah, sebaliknya, adalah grafik dengan arah di tepinya.

Dua cara umum untuk merepresentasikan grafik adalah daftar kedekatan dan matriks kedekatan.

Daftar kedekatan dapat direpresentasikan sebagai daftar di mana sisi kiri adalah node dan sisi kanan mendaftar semua node lain yang terhubung dengannya.

Matriks kedekatan adalah kisi angka, di mana setiap baris atau kolom mewakili node yang berbeda dalam grafik. Di perpotongan baris dan kolom adalah angka yang menunjukkan hubungan. Nol berarti tidak ada tepi atau hubungan. Yang berarti ada hubungan. Angka yang lebih tinggi dari satu dapat digunakan untuk menunjukkan bobot yang berbeda.

Algoritma traversal adalah algoritma untuk melintasi atau mengunjungi node dalam sebuah grafik. Jenis utama dari algoritme traversal adalah pencarian luas-pertama dan pencarian mendalam-pertama. Salah satu kegunaannya adalah untuk menentukan seberapa dekat node ke node root. Lihat bagaimana menerapkan pencarian luas-pertama di JavaScript pada video di bawah ini.

Lihat kode untuk penelusuran luas-pertama pada grafik matriks ketetanggaan di JavaScript.

Kompleksitas waktu pencarian biner

AlgoritmaWaktu
PenyimpananO (| V | + | E |)
Tambahkan VertexO (1)
Tambahkan EdgeO (1)
Hapus VertexO (| V | + | E |)
Hapus EdgeO (| E |)
PertanyaanO (| V |)

tantangan freeCodeCamp

  • Daftar Adjacency
  • Matriks Adjacency
  • Matriks Insiden
  • Pencarian Luas-Pertama
  • Pencarian Kedalaman-Pertama

Lebih

Buku Algoritma Grokking adalah buku terbaik tentang topik ini jika Anda baru mengenal struktur / algoritme data dan tidak memiliki latar belakang ilmu komputer. Ini menggunakan penjelasan yang mudah dipahami dan ilustrasi yang lucu dan digambar dengan tangan (oleh penulis yang merupakan pengembang utama di Etsy) untuk menjelaskan beberapa struktur data yang ditampilkan dalam artikel ini.

Algoritma Grokking: Panduan bergambar untuk programmer dan orang-orang yang ingin tahu lainnya

Ringkasan Algoritma Grokking adalah panduan ramah yang diilustrasikan lengkap yang mengajarkan Anda bagaimana menerapkan algoritma umum ke… www.amazon.com

Atau Anda dapat melihat kursus video saya berdasarkan buku itu: Algorithms in Motion dari Manning Publications. Dapatkan diskon 39% untuk kursus saya dengan menggunakan kode ' 39carnes '!