Bagaimana cara kerja daftar lewati?

Untuk tugas pekerjaan rumah, saya perlu memahami cara kerja daftar lompatan .

Saya sudah pemrograman selama lebih dari 2 tahun sekarang (saya tahu itu tidak terlalu lama dalam kenyataan), dan saya belum pernah mendengar tentang daftar lompatan.

Saya telah melihat-lihat semua panduan yang dapat saya temukan, dan saya masih hampir tidak mengerti bagaimana cara kerjanya. Saya bahkan mencari Peninjauan Kode untuk contoh implementasi, dan hanya menemukan satu ulasan; dan itu bahkan bukan implementasi yang lengkap. Saya melihat penerapan sampel yang disediakan oleh kursus, dan itu benar-benar mengerikan. Antara kurangnya metode yang tepat, dan nama variabel satu huruf, saya tidak tahu cara kerjanya.

Bagaimana cara kerja daftar lewati? Apakah pengetahuan tentang daftar lewati diperlukan untuk memahami struktur data yang lebih maju?

Di masa lalu, di kelas struktur data kami belajar bagaimana pohon AVL bekerja . Saya akan memilikinya di salah satu kelas saya, tetapi instruktur mengatakan "Anda tidak akan pernah benar-benar menggunakan ini" dan sebaliknya meminta kami belajar 2-3 pohon dan b * pohon sebagai gantinya. Itu adalah hari-hari ketika ingatan sedang ketat dan proses-proses tunggal dijalin. Anda tidak menggunakan deque ketika daftar yang terhubung sendiri akan bekerja dengan baik.

Daftar lompatan jauh lebih umum hari ini dengan lebih banyak memori dan konkurensi menjadi masalah (Anda tidak perlu mengunci sama sekali ketika bertindak sebagai penulis dalam daftar lompatan - dibandingkan dengan segala sesuatu dengan pohon AVL).

Terus terang, itu adalah struktur data favorit saya sekarang karena ini sesuatu yang saya dapat dengan mudah beralasan tentang cara kerjanya di bawah dan di mana itu akan menguntungkan atau tidak menguntungkan untuk digunakan.

Anda tidak perlu menulis satu dari awal (kecuali jika Anda mendapatkannya sebagai pertanyaan wawancara - tetapi kemudian Anda kemungkinan akan menerapkan pohon AVL).

Anda yang akan perlu memahami mengapa Anda ingin memilih ConcurrentSkipListMapdi Jawa daripada HashMapatau TreeMapatau salah satu implementasi peta lainnya.

Untuk memahami cara kerjanya, Anda perlu memahami cara kerja pohon biner. Tunggu, biarkan saya mengubah itu. Anda perlu memahami cara kerja pohon biner seimbang . Tanpa menyeimbangkan pohon biner, Anda tidak mendapatkan keuntungan nyata dengan pencariannya.

Katakanlah kita punya pohon ini:

Dan kami memasukkan '8' ke dalamnya. Sekarang kita punya:

Dan itu tidak seimbang. Jadi, kami pergi dan melakukan keajaiban menyeimbangkannya melalui beberapa implementasi ...

Dan Anda mendapatkan pohon seimbang lagi. Tapi itu adalah banyak sihir yang aku lambaikan tangan.

Mari kita ambil daftar lewati.

Yang ini kebetulan yang ideal. Sedikit, tetapi ini menunjukkan sifat pohon biner seimbang yang mendekati perkiraan ideal.

Sekarang, kami ingin memasukkan 6 ke sana. Ini memasukkannya seperti daftar tertaut. Namun, kita mulai dari atas dan turun. Poin teratas ke 5. Apakah 6> 5? Iya. Ok, poin teratas sampai akhir sekarang, jadi kita turun tumpukan (kita di 5). Yang berikutnya adalah 7. Apakah 6> 7? Nggak. Jadi kita turun satu level dan kita di level dasar jadi kita masukkan 6 di sebelah kanan 5.

Kami melempar koin - kepala yang kami bangun, kami tinggal. Ekor. Tidak ada lagi yang perlu dilakukan.

Mari kita masukkan 8 itu sekarang. 8> 5? ya. 8> 7? Ya. Dan sekarang kita berada di level bawah lagi setelah mengikuti panah dan tumpukan sekitar dan kita menguji 8> 11? Nggak. Jadi kita masukkan 8 di sebelah kanan 7.

Kami melempar koin - kepala yang kami bangun, kami tinggal. Ekor. Tidak ada lagi yang perlu dilakukan.

Di pohon seimbang, kita semua akan beres tentang pohon yang tidak seimbang sekarang. Tapi ini bukan pohon - ini daftar lompatan. Kami memperkirakan pohon seimbang.

Sekarang mari kita masukkan 10. Saya akan menghindari semua perbandingan.

Kami melempar koin - kepala yang kami bangun, kami tinggal. Kepala! Dan balik lagi, Kepala lagi! Balikkan lagi, ok, ada buntut. Dua tingkat di atas daftar yang ditautkan basis.

Keuntungannya di sini adalah sekarang jika kita akan memasukkan angka 12, kita dapat melewati dari 5 hingga 10 tanpa melakukan semua perbandingan lainnya. Kita dapat melewati mereka dengan daftar lewati. Dan kita tidak perlu khawatir tentang pohon seimbang - sifat probabilistik dari penumpukan melakukan itu untuk kita.

Mengapa ini sangat berguna? Karena ketika memasukkan 10 saya bisa melakukannya dengan mengunci tulisan pada pointer 5 dan 7 dan 8 daripada seluruh struktur. Dan sementara saya melakukan itu, para pembaca masih bisa melalui daftar lewati tanpa memiliki keadaan yang tidak konsisten. Untuk penggunaan bersamaan, lebih cepat tidak harus mengunci. Untuk iterasi di atas lapisan bawah, ini lebih cepat daripada pohon (kegembiraan algoritma BFS dan DFS untuk navigasi pohon - Anda tidak perlu khawatir tentang mereka).

Apakah Anda akan menemukannya? Anda mungkin akan melihatnya digunakan di beberapa tempat. Dan kemudian Anda akan tahu mengapa penulis memilih yang pelaksanaan daripada TreeMapatau HashMapuntuk struktur.

Banyak dari ini telah dipinjam dari posting blog saya: Daftar Lewati