Struktur data adalah cara mengorganisir dan menyimpan data dalam memori sehingga dapat diakses dan diubah secara efisien. Jenis data abstrak (ADT) adalah model logis — operasi dan perilakunya — yang tidak tergantung pada cara implementasinya.
ADT menggambarkan yang ada; struktur data menentukan data disimpan dan seberapa cepat operasi berjalan.
ADT: Stack → push, pop, peek (LIFO behavior)
Implementations: → array-backed OR linked-list-backed
ADT: List → get(i), insert, remove
Implementations: → dynamic array OR linked list
# Both satisfy the "Stack" ADT, but have different cost profiles
stack = [] # list-backed stack
stack.append(10) # push -> amortized O(1)
top = stack[-1] # peek -> O(1)
stack.pop() # pop -> O(1)
| Pertimbangan | Pertanyaan yang harus diajukan |
|---|---|
| Pola akses | Akses acak atau berurutan? |
| Mutasi | Penyisipan/penghapusan yang sering di tengah? |
| Pengurutan | Terurut, FIFO, LIFO, atau tidak ada? |
| Pencarian | Dengan indeks atau dengan kunci? |
Pilihan yang tepat adalah pilihan yang operasi umum murah untuk beban kerja Anda.
Memilih struktur yang salah mengubah operasi O(1) menjadi O(n), yang dapat membuat kode ribuan kali lebih lambat dalam skala besar.
Berpikir dalam istilah ADT memungkinkan Anda untuk memikirkan tentang perilaku terlebih dahulu, kemudian menukar implementasi nanti tanpa menulis ulang pemanggil.