Linked list
Dalam ilmu computer, Linked list adalah kumpulan linier elemen data, yang urutannya tidak diberikan oleh penempatan fisik mereka dalam memori. Sebaliknya, setiap elemen menunjuk ke yang berikutnya. Ini adalah struktur data yang terdiri dari kumpulan node yang bersama-sama mewakili urutan . Dalam bentuknya yang paling mendasar, setiap simpul berisi: data , dan referensi (dengan kata lain, tautan ) ke simpul berikutnya dalam urutan. Struktur ini memungkinkan penyisipan atau penghapusan elemen yang efisien dari posisi apa pun dalam urutan selama iterasi. Varian yang lebih kompleks menambah tautan tambahan, yang memungkinkan penyisipan atau penghapusan node yang lebih efisien pada posisi sewenang-wenang. Kelemahan dari linked list adalah bahwa waktu akses adalah linier (dan sulit untuk disalurkan ). Akses yang lebih cepat, seperti akses acak, tidak layak. Array memiliki lokalitas cache yang lebih baik dibandingkan dengan linked list.circuar single linked list
Dalam singly linked list, untuk mengakses simpul mana pun dari daftar tertaut, kita mulai melintasi dari simpul pertama (first node). Jika kita berada pada titik di tengah daftar, maka tidak mungkin untuk mengakses node yang mendahului node yang diberikan. Masalah ini dapat diselesaikan dengan sedikit mengubah struktur singly linked list. Dalam singly linked list, bagian selanjutnya (pointer ke node berikutnya) adalah NULL, jika kita menggunakan tautan ini untuk menunjuk ke node pertama maka kita dapat mencapai node sebelumnya.Singly Linked List
Single : artinya field pointer-nya hanya satu buah saja dan satu arah serta pada akhir node, pointernya menunjuk NULL
Linked List : artinya node-node tersebut saling terhubung satu sama lain.
Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data.
Node terakhir akan menunjuk ke NULL yang akan digunakan sebagai kondisi berhenti pada saat pembacaan isi linked list.
Pointer pokok yang digunakan yaitu head (menunjuk pada node awal) dan tail (menunjuk pada node terakhir)
doubly linked list
Dalam ilmu komputer, doubly linked list adalah struktur data tertaut yang terdiri dari sekumpulan catatan yang terhubung secara berurutan yang disebut simpul. Setiap node berisi tiga bidang: dua bidang tautan (referensi ke simpul sebelumnya dan ke simpul berikutnya dalam urutan simpul) dan satu bidang data. Tautan awal dan akhir dari nodes 'sebelumnya dan selanjutnya, masing-masing, menunjuk ke semacam terminator, biasanya node atau null sentinel, untuk memfasilitasi traversal dari daftar. Jika hanya ada satu simpul sentinel, maka daftar itu terhubung secara melingkar melalui simpul sentinel. Ini dapat dikonseptualisasikan sebagai dua daftar tertaut tunggal yang dibentuk dari item data yang sama, tetapi dalam urutan berurutan yang berlawanan.Harshing
Hashing adalah Struktur Data penting yang dirancang untuk menggunakan fungsi khusus yang disebut fungsi Hash yang digunakan untuk memetakan nilai yang diberikan dengan kunci tertentu untuk akses elemen yang lebih cepat. Efisiensi pemetaan tergantung pada efisiensi fungsi hash yang digunakan.Collision
Karena fungsi hash memberi kita sejumlah kecil untuk kunci yang merupakan integer atau string,
ada kemungkinan
bahwa dua kunci menghasilkan nilai yang sama. Situasi di mana peta kunci yang baru dimasukkan
ke slot yang sudah ditempati di tabel hash disebut collision dan harus ditangani menggunakan
beberapa teknik penanganan collision.
Ada dua metode utama untuk menangani tabrakan:
1) Separate Chaining
2) Open Addressing
Separate Chaining
idenya adalah untuk membuat setiap sel tabel hash menunjuk ke daftar catatan terkait yang memiliki
nilai fungsi hash yang sama.Separate Chaining idenya adalah untuk membuat setiap sel tabel hash
menunjuk ke daftar catatan terkait yang memiliki nilai fungsi hash yang sama.
Open Addressing
Seperti Separate Chaining, Open Addressing adalah metode untuk menangani collision. Di Open Addressing, semua elemen disimpan di tabel hash itu sendiri. Jadi pada titik mana pun, ukuran tabel harus lebih besar dari atau sama dengan jumlah total kunci (Perhatikan bahwa kami dapat menambah ukuran tabel dengan menyalin data lama jika diperlukan).insert (k): Terus selidiki sampai slot kosong ditemukan. Setelah slot kosong ditemukan, masukkan k.
search (k): Terus selidiki sampai kunci slot tidak menjadi sama dengan k atau slot kosong tercapai.
delete (k): Hapus operasi itu menarik. Jika kami hanya menghapus kunci, maka pencarian mungkin
gagal. Jadi slot kunci yang dihapus ditandai secara khusus sebagai "dihapus". Sisipan dapat
menyisipkan item di slot yang dihapus, tetapi pencarian tidak berhenti di slot yang dihapus.
