Atlama listesi nedir?
Atlama listesi olasılıksal bir veri yapısıdır. Atlama listesi, bağlantılı bir listeyle sıralanmış bir öğe veya veri listesini depolamak için kullanılır. Öğelerin veya verilerin sürecinin verimli bir şekilde görüntülenmesini sağlar. Tek bir adımda tüm listenin birçok öğesini atlar, bu nedenle atlama listesi olarak bilinir.
Atlama listesi bağlantılı listenin genişletilmiş versiyonudur. Kullanıcının öğeyi çok hızlı bir şekilde aramasına, kaldırmasına ve eklemesine olanak tanır. Sonraki öğelerin bağlantı hiyerarşisini koruyan bir dizi öğeyi içeren bir temel listeden oluşur.
Liste yapısını atla
İki katmandan oluşur: En alt katman ve Üst katman.
Atlama listesinin en alt katmanı ortak sıralanmış bağlantılı bir listedir ve atlama listesinin üst katmanları, öğelerin atlandığı bir 'ekspres satır' gibidir.
Atlama listesinin karmaşıklık tablosu
| Evet Hayır | Karmaşıklık | Ortalama durum | En kötü durumda |
|---|---|---|---|
| 1. | Erişim karmaşıklığı | O(giriş) | Açık) |
| 2. | Arama karmaşıklığı | O(giriş) | Açık) |
| 3. | Karmaşıklığı silin | O(giriş) | Açık) |
| 4. | Karmaşıklık ekleyin | O(giriş) | Açık) |
| 5. | Uzay karmaşıklığı | - | O(nlogn) |
Atlama listesinin çalışması
Atlama listesinin çalışmasını anlamak için bir örnek verelim. Bu örnekte 14 düğümümüz var, öyle ki bu düğümler şemada gösterildiği gibi iki katmana bölünmüş durumda.
Alt katman, tüm düğümleri birbirine bağlayan ortak bir çizgidir ve üst katman, şemada görebileceğiniz gibi yalnızca ana düğümleri birbirine bağlayan ekspres bir çizgidir.
Bu örnekte 47'yi bulmak istediğinizi varsayalım. Aramaya ekspres hattın ilk düğümünden başlayacak ve 47'ye eşit veya 47'den büyük bir düğüm bulana kadar ekspres hatta koşmaya devam edeceksiniz.
Örnekte ekspres satırda 47'nin bulunmadığını görüyorsunuz, dolayısıyla 47'den küçük bir düğüm ararsınız, yani 40. Şimdi 40'ın yardımıyla normal satıra gidip 47'yi ararsınız, şemada gösterildiği gibi.
Not: 'Ekspres hat' üzerinde buna benzer bir düğüm bulduğunuzda, bir işaretçi kullanarak bu düğümden 'normal şeride' gidersiniz ve düğümü normal satırda aradığınızda.
Liste Temel İşlemlerini Atla
Atlama listesinde aşağıdaki işlem türleri vardır.
Ekleme işleminin algoritması
Insertion (L, Key) local update [0...Max_Level + 1] a = L → header for i = L → level down to 0 do. while a → forward[i] → key forward[i] update[i] = a a = a → forward[0] lvl = random_Level() if lvl > L → level then for i = L → level + 1 to lvl do update[i] = L → header L → level = lvl a = makeNode(lvl, Key, value) for i = 0 to level do a → forward[i] = update[i] → forward[i] update[i] → forward[i] = a
Silme işleminin algoritması
Deletion (L, Key) local update [0... Max_Level + 1] a = L → header for i = L → level down to 0 do. while a → forward[i] → key forward[i] update[i] = a a = a → forward[0] if a → key = Key then for i = 0 to L → level do if update[i] → forward[i] ? a then break update[i] → forward[i] = a → forward[i] free(a) while L → level > 0 and L → header → forward[L → level] = NIL do L → level = L → level - 1
Arama işleminin algoritması
Searching (L, SKey) a = L → header loop invariant: a → key level down to 0 do. while a → forward[i] → key forward[i] a = a → forward[0] if a → key = SKey then return a → value else return failure
Örnek 1: Bir atlama listesi oluşturun, aşağıdaki tuşları boş atlama listesine eklemek istiyoruz.
- 6. seviye ile 1.
- 29, seviye 1 ile.
- 22. seviye 4.
- 9. seviye 3.
- 1. seviye ile 17.
- 4. seviye ile 2.
Yıllar:
Aşama 1: Düzey 1 ile 6'yı ekleyin
Adım 2: Düzey 1 ile 29'u ekleyin
Aşama 3: Düzey 4 ile 22'yi ekleyin
Adım 4: Seviye 3 ile 9'u ekleyin
Adım 5: Düzey 1 ile 17'yi ekleyin
Adım 6: Seviye 2 ile 4'ü ekleyin
Örnek 2: Anahtar 17'yi aramak istediğimiz bu örneği düşünün.
Yıllar:
Atlama listesinin avantajları
- Atlama listesine yeni bir düğüm eklemek istiyorsanız, atlama listesinde herhangi bir dönüş olmadığından düğümü çok hızlı ekleyecektir.
- Atlama listesinin uygulanması karma tablo ve ikili arama ağacına kıyasla basittir.
- Listede bir düğümü bulmak çok basittir çünkü düğümleri sıralanmış biçimde saklar.
- Atlama listesi algoritması, indekslenebilir atlama listeleri, ağaçlar veya öncelik kuyrukları gibi daha spesifik bir yapıda çok kolay bir şekilde değiştirilebilir.
- Atlama listesi sağlam ve güvenilir bir listedir.
Atlama listesinin dezavantajları
- Dengeli ağaçtan daha fazla bellek gerektirir.
- Ters aramaya izin verilmez.
- Atlama listesi, düğümü bağlantılı listeden çok daha yavaş arar.
Atlama listesinin uygulamaları
- Dağıtılmış uygulamalarda kullanılır ve dağıtılmış uygulamalardaki işaretçileri ve sistemi temsil eder.
- Düşük kilit çekişmeli dinamik elastik eşzamanlı kuyruk uygulamak için kullanılır.
- Aynı zamanda QMap şablon sınıfıyla da kullanılır.
- Atlama listesinin indekslenmesi medyan problemlerinin çalıştırılmasında kullanılır.
- Atlama listesi, Lucene aramasında delta kodlamalı gönderim için kullanılır.