Atlamalı halka: Dairesel ve atlamalı liste temelli yeni bir veri yapısı

Atlamalı liste (skip list) veri yapısında bağlı listeler kullanılır. Katmanlı bir yapıdan oluşur ve en alt katmanda tüm düğümler bulunur; bu düğümler üst katmanlara doğru yarıya düşürülerek piramit şeklinde bir yapı oluşturulur. Böylece arama, ekleme, silme işlemlerinde kolaylık sağlanması amaçlanır. Bunun yanında bu veri yapısı daha da iyileştirilebilir. Bu tez çalışmasındaki amacımız; Atlamalı liste veri yapısını analiz ederek bu veri yapısındaki problemleri tespit edip, tespit edilen problemleri çözerek atlamalı liste veri yapısında iyileştirmeler yapmak ve daha sonra bu iyileştirmeleri önereceğimiz yeni veri yapısına uygulamaktır. Atlamalı listedeki iyileştirmeler dikkate alınarak önerilen yeni veri yapısı atlamalı halka (skip ring), dairesel bağlı liste ve atlamalı liste veri yapılarından faydalanılarak oluşturulmuştur. Önerdiğimiz yeni veri yapısı koni şeklinde birbirine bağlı katmanlar halinde dairesel bağlı listelerden oluşur. Böylece N elemanlı bir atlamalı halka veri yapısında arama, ekleme, silme işlemlerinin zaman karmaşıklığı O(lgN) olur. Önerilen yeni veri yapısı uygulamalı olarak ikili arama ağaçları, kırmızı-siyah ağaçlar ve atlamalı liste veri yapıları ile kıyaslanmış sonuçları incelenmiştir. Ayrıca atlamalı halka temelli yeni bir sıralama ve arama algoritması önerilmiştir. Önerilen bu algoritmalar mevcut sıralama ve arama algoritmaları ile uygulamalı karşılaştırılmıştır. Sonuç olarak, atlamalı liste ve dairesel bağlı listelerin özeliklerinden faydalanılarak geliştirilen atlamalı halka (skip ring) veri yapısı ağaç temelli bazı veri yapıları ile karşılaştırılmış iyi sonuçlar elde edilmiştir. Ayrıca sıralama (sorting), arama (searching) gibi her zaman güncel bazı alanlara etkin bir şekilde uygulanabilirliği gösterilmiştir.