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

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şlemi:Belirli bir durumda belirli bir konuma yeni bir düğüm eklemek için kullanılır.Silme işlemi:Belirli bir durumda bir düğümü silmek için kullanılır.Arama İşlemi:Arama işlemi, atlama listesindeki belirli bir düğümü aramak için kullanılı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.

1. 6. seviye ile 1.
2. 29, seviye 1 ile.
3. 22. seviye 4.
4. 9. seviye 3.
5. 1. seviye ile 17.
6. 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ı

1. Atlama listesine yeni bir düğüm eklemek istiyorsanız, atlama listesinde herhangi bir dönüş olmadığından düğümü çok hızlı ekleyecektir.
2. Atlama listesinin uygulanması karma tablo ve ikili arama ağacına kıyasla basittir.
3. Listede bir düğümü bulmak çok basittir çünkü düğümleri sıralanmış biçimde saklar.
4. 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.
5. Atlama listesi sağlam ve güvenilir bir listedir.

Atlama listesinin dezavantajları

1. Dengeli ağaçtan daha fazla bellek gerektirir.
2. Ters aramaya izin verilmez.
3. Atlama listesi, düğümü bağlantılı listeden çok daha yavaş arar.

Atlama listesinin uygulamaları

1. Dağıtılmış uygulamalarda kullanılır ve dağıtılmış uygulamalardaki işaretçileri ve sistemi temsil eder.
2. Düşük kilit çekişmeli dinamik elastik eşzamanlı kuyruk uygulamak için kullanılır.
3. Aynı zamanda QMap şablon sınıfıyla da kullanılır.
4. Atlama listesinin indekslenmesi medyan problemlerinin çalıştırılmasında kullanılır.
5. Atlama listesi, Lucene aramasında delta kodlamalı gönderim için kullanılır.