Swift Veri Yapıları — Linked List

Linked List bir array gibi verileri gruplamamıza yarayan bir yapıdır. Array yapısından farkı ise verileri bellekte bir arada tutmaktan ziyade her bir element bellekte dağınık bir biçimde tutulur.

Linked List yapısının temelinde düğüm mantığı vardır. Her bir element kendisinden sonra gelecek bir diğer elementin bellekteki referansını tutarak birbirleri ile bir nevi düğümler oluştururlar. Böylece bellekte ayrık şekilde tutulan bu modeller arasında bir ilişki oluşarak veriler gruplandırılmış olur.

Pratikte daha iyi anlaşılacağını düşündüğüm için lafı fazla uzatmadan linked list yapısını kodlayarak oluşturalım.

Node (Düğüm)

Node sınıfı listemizin her bir değerini sarmalayacak bir yapı olarak oluşturuldu. Value değeri o elementin değerini (Int, String, object vb.) temsil ediyorken next değeri ise bir sonraki düğümü işaret eder. Next değerini nullable olarak oluşturmamızın sebebi ise doğal olarak listenin sonsuza kadar gidiyor olmamasıdır. Eninde sonunda son düğüme gelindiğinde next değerinin nil olması gerekir.

Debug

Bu kısmı tamamen ilerlemeyi görselleştirme amaçlı ekledim. Listemizi oluştururken doğru çalışıp çalışmadığını kontrol etmek istediğimizde ilk düğümümüzü yazdırıp kontroller sağlıyor olacağız.

Normalde referans tipli bir objeyi print etmek istediğimizde log kısmında bu sınıfın bellekteki adresini görürüz. Burada CustomStringConvertible protocol yapısı sunduğu description değeri ile bizlere objeyi print ederken özelleştirilmiş bir açıklamayı log kısmına basmamızı sağlar.

Manuel Bağlama

Liste yapımızı oluşturmadan evvel birkaç düğüm oluşturalım ve bunları manuel bir şekilde bağlayalım.

Yukarıda görüldüğü gibi oluşturulan düğümler sırası ile birbirlerine bağlandılar. Element1'den sonra element2 geleceği için element1'in next değeri element2 olarak verildi. Element2'den sonra element3 geleceği için element2'ye ait next değeri element3 olarak verildi. Print ettiğimizde konsolda ‘ 1 -> 2 -> 3 ‘ ifadesini görmemiz gerekir.

Linked List

Yukarıdaki örnekte oluşturduğumuz düğümleri manuel olarak birbirlerine bağladık. Şimdi bu tarz operasyonlarda bize yardımcı olurken düğümleri yönetmemizi sağlayacak Linked List sınıfımızı oluşturalım.

Sınıf içerisinde iki adet değer görüyoruz. Head değeri listemizin birinci elemanını temsil ediyorken tail değeri son elemanını temsil ediyor. Şimdi de yardımcı fonksiyonlarımızı yazalım.

Push()

Push fonksiyonu ile listemizin ilk elemanını değiştiririz. Değiştirme yaparken ilk eleman silinmez sadece bir index geri kaydırılır. Bir insan kuyruğunun uç kısmına yeni bir insan eklemek gibi düşünülebilir. Yeni gelen kişi head olurken önceki kişi sırada bir adım geri kayar.

Yukarıda görüldüğü gibi listeye yeni bir eleman push yöntemi ile eklenilirken head yeni eklenen düğüm olur. Yeni eklenen düğümün de next değeri eski head olur.

Bu durumda çıktımız : 9 -> 2 -> 1 olması gerekir

append()

Append fonksiyonu listemize yeni bir eleman eklerken bu elemanı kuyruğun ucuna eklememize olanak tanıyacak. Push fonksiyonunda verdiğim örnek gibi düşünebilirsiniz. İnsan kuyruğunun başına değil de sonuna yeni birisini ekliyormuşuz gibi.

Öncelikle head değerinin nil olup olmadığını kontrol ediyoruz yani bir nevi listemizde eleman var mı yok mu diye. Eğer listemiz boş ise halı hazırda yazdığımız push fonksiyonu ile ilk elemanı ekleyebiliyor olacağız. Devamında eklenilmek istenilen değer ile yeni bir düğüm oluşturuyoruz. Bu düğüm son sırada olacağı için next değerini nil olarak veriyoruz. Eskiden sonuncu olan düğümün bir sonraki değerini ve kuyruk değerlerini yeni düğüm ile eşitliyoruz.

Bu durumda beklenen çıktı 9 -> 2 -> 1 -> 12 şeklinde olmalıdır.

node()

Spesifik olarak bir index ile bir düğümü elde etmek istediğimiz zaman bu fonksiyonu kullanıyor olacağız. Return edeceği değer aynı şekilde bir düğüm olurken var olmama ihtimali ile nullable dönecektir.

Bu fonksiyondaki mantığımız aslında basit. Head düğümünden başlayıp bir döngü yardımı ile sürekli olarak next değeri ile bir sonraki düğüme geçiyoruz ve her geçişte sayacımızı bir arttırıyoruz. Beklenen index i yakaladığımız zaman elimizdeki düğümü dönüyoruz.

Bu durumda beklenilen çıktı 2 olmalıdır.

insert()

Insert yöntemi ile beraber listeye yeni bir eleman eklerken elemanın var olacağı index numarasını belirleyebiliriz. İnsan kuyruğu örneğimizden devam edecek olursak bu sefer kuyruğa yeni ekleyeceğimiz kişiyi dilediğimiz yere yerleştiriyoruz ve bunu yapmak için tek söylememiz gereken bir önceki kişinin index numarası. Örneğin 3 nolu kişi der isek yeni eklenen kişi 4 numaraya geliyor olacak.

Öncelikle var olmayan bir index in devamı da olamayacağı için bizlere verilen index hali hazırda var mı yok mu diye daha önceden yazmış olduğumuz node fonksiyonunu kullanarak kontrol sağlıyoruz. Sonrasında swap işlemini gerçekleştirerek yeni bir elemanı istenilen index e eklemiş oluyoruz.

Bu durumda çıktı 1 -> 2 -> 3 -> 4 -> 5 şeklinde olur.

pop()

Pop fonksiyonu head de var olan düğümü siler. Bir sonraki elemanı da doğal olarak head yerine geçirir.

Yukarıda görüldüğü gibi head artık bir sonraki düğüme eşit oldu. Dikkat edilmesi gerekilen bir nokta ise bu kısımda son eleman için pop() fonksiyonunu kullanmak. Bunu yaptığımızda son elemanın next değeri nil olacağı için otomatik olarak head değerimizde nil olacaktır. Bu durumda tail değerini de nil yapmak zorundayız.

Bu durumda çıktımız 2 -> 3 -> 4 olacaktır.

removeLast()

Bu fonksiyon pop fonksiyonun tam tersi olarak sonuncu düğümü (tail) siler. Kendisinden önceki düğümü de tail olarak tanımlar.

Listenin boş olup olmadığını anlamak ve head değerini non-optional bir biçimde almak için guard-let yapısını kullanıyoruz. Sonrasında liste içerisinde sadece bir eleman var ise pop() fonksiyonumuzu çalıştırıyoruz.

removeLast() fonksiyonu son değeri silip bir önceki değeri tail yapacağı için bu durumda iki farklı pointer a ihtiyaç duyuyoruz. Current değeri tek tek düğümlerde ilerlerken previous değeri hemen bir önceki düğümde on takip ediyor olacak. Current son değere geldiğinde while koşulundan ötürü döngü sonlanacaktır. Devamında son düğümü nil yapıyor ve tail değerini previous değerine eşitliyoruz.

Bu durumda çıktımız 1 -> 2 -> 3 olması gerekir.

removeAfter()

Bu fonksiyon ile parametre olarak verdiğimiz düğümün bağlı olduğu sonraki düğümü silebiliyoruz. Bu işlemi yaparken silinmesi istenen düğümden önceki ve sonraki düğümler birbirlerine bağlanırlar.

Parametre olarak verilen düğümden sonraki düğüm silindiğinde önceki düğümün sonraki düğüm ile bağlanılması için çift next ile yapacağımız atama bizim için yeterli olacaktır.

Silinmek istenen düğümün tail değerine gelme ihtimaline karşı ilk başta bir kontrol gerçekleştiriyoruz. Silinmek istenen değer tail değerine denk geliyorsa kuyruğu güncelliyoruz.

Bu yazının sonuna gelmiş bulunmaktayız. Umarım yazı yararlı olmuştur. Bir başka yazıda görüşmek üzere kendinize iyi bakın.

Kaynakça:

https://www.udemy.com/course/data-structures-and-algorithms-in-swift/

https://www.raywenderlich.com/books/data-structures-algorithms-in-swift/v3.0/chapters/6-linked-list