Skip to content

Latest commit

 

History

History
129 lines (112 loc) · 7.72 KB

struktur-data.md

File metadata and controls

129 lines (112 loc) · 7.72 KB
Raw

Struktur Data

Arrays

  • Menerapkan vektor yang mengubah ukuran secara otomatis.
  • Deskripsi:
  • Menerapkan vektor (array yang bisa berubah dengan ukuran otomatis):
    • Berlatih coding menggunakan array dan pointer, dan matematika pointer untuk melompat ke indeks daripada menggunakan pengindeksan.
    • Array data mentah baru dengan memori yang dialokasikan
      • dapat mengalokasikan array int di bawah tenda, hanya saja tidak menggunakan fitur-fiturnya
      • start dengan 16, atau jika angka awal lebih besar, gunakan pangkat 2 - 16, 32, 64, 128
    • size() - jumlah item
    • capacity() - jumlah barang yang bisa ditampungnya
    • is_empty()
    • at(index) - mengembalikan item pada indeks tertentu, meledak jika indeks di luar batas
    • push(item)
    • insert(index, item) - menyisipkan item pada indeks, menggeser nilai indeks dan elemen tambahan ke kanan
    • prepend(item) - dapat menggunakan sisipan di atas pada indeks 0
    • pop() - hapus dari akhir, nilai kembali
    • delete(index) - hapus item pada indeks, menggeser semua elemen tertinggal ke kiri
    • remove(item) - mencari nilai dan menghapus indeks yang menahannya (meskipun di banyak tempat)
    • find(item) - mencari nilai dan mengembalikan indeks pertama dengan nilai itu, -1 jika tidak ditemukan
    • resize(new_capacity) // fungsi pribadi
      • saat Anda mencapai kapasitas, ubah ukurannya menjadi dua kali lipat
      • saat memunculkan item, jika ukurannya 1/4 dari kapasitas, ubah ukurannya menjadi setengah
  • Waktu
    • O(1) untuk menambah/menghapus di akhir (diamortisasi untuk alokasi untuk lebih banyak ruang), indeks, atau pembaruan
    • O(n) untuk memasukkan/menghapus di tempat lain
  • Ruang
    • berdekatan dalam memori, jadi kedekatan membantu kinerja
    • ruang yang dibutuhkan = (kapasitas array, yaitu >= n)*ukuran item, tetapi meskipun 2n, tetap O(n)

Linked Lists

  • Deskripsi:
  • Kode C (video) - bukan keseluruhan video, hanya bagian tentang struct Node dan alokasi memori
  • Linked List vs Array:
  • mengapa Anda harus menghindari linked list (video)
  • Gotcha: Anda perlu pengetahuan pointer ke pointer: (untuk saat Anda meneruskan pointer ke fungsi yang dapat mengubah alamat tempat pointer itu menunjuk) Halaman ini hanya untuk memahami pointer ke pointer. Saya tidak merekomendasikan gaya traversal daftar ini. Keterbacaan dan pemeliharaan menderita karena kepintaran.
  • Implementasikan (saya lakukan dengan tail pointer & tanpa):
    • size() - mengembalikan jumlah elemen data dalam daftar
    • empty() - bool mengembalikan nilai true jika kosong
    • value_at(index) - mengembalikan nilai item ke-n (mulai dari 0 untuk yang pertama)
    • push_front(value) - menambahkan item ke depan daftar
    • pop_front() - hapus item depan dan kembalikan nilainya
    • push_back(value) - menambahkan item di akhir
    • pop_back() - menghapus item akhir dan mengembalikan nilainya
    • front() - dapatkan nilai barang depan
    • back() - dapatkan nilai item akhir
    • insert(index, value) - masukkan nilai pada indeks, maka item saat ini pada indeks tersebut ditunjuk oleh item baru pada indeks
    • erase(index) - menghapus node pada indeks tertentu
    • value_n_from_end(n) - mengembalikan nilai node pada posisi ke-n dari akhir daftar
    • reverse() - membalikkan daftar
    • remove_value(value) - menghapus item pertama dalam daftar dengan nilai ini
  • Doubly-linked List

Stack

  • Stack (video)
  • Tidak akan diterapkan. Implementasi dengan array itu sepele

Queue

  • Queue (Antrean)
  • Queue (video)
  • Circular buffer/FIFO
  • Implementasikan menggunakan linked-list, dengan tail pointer:
    • enqueue(value) - menambah nilai pada posisi di ekor
    • dequeue() - mengembalikan nilai dan menghapus elemen yang paling baru ditambahkan (depan)
    • empty()
  • Menerapkan menggunakan array berukuran tetap:
    • enqueue(value) - menambahkan item di akhir penyimpanan yang tersedia
    • dequeue() - mengembalikan nilai dan menghapus elemen yang paling baru ditambahkan
    • empty()
    • full()
  • Biaya:
    • implementasi yang buruk menggunakan daftar tertaut di mana Anda mengantre di bagian depan dan antrean di bagian ekor akan menjadi O(n) karena Anda memerlukan elemen di sebelah terakhir, menyebabkan traversal penuh setiap dequeue
    • enqueue: O(1) (diamortisasi, daftar tertaut dan larik [probing])
    • dequeue: O(1) (daftar dan larik tertaut)
    • empty: O(1) (daftar dan larik tertaut)

Hash table

Selanjutnya - Lebih Banyak Pengetahuan