Linked Lists (Bağlı Listeler)
2019-12-19
Linked Lists yapısını sıralı bir şekilde tutulması gereken veriler için kullanılırız. Linked Lists, Array'lerin tam aksine boyutları otomatik olarak büyütülebilir veya küçültülebilir. Her bir Linked Lists elamanına "node" (düğüm) adını veririz. Her düğüm, biri saklanması gereken veri diğeri de "pointer" (işaretçi) denilen kendinden sonra gelen düğümün adresini tutan iki kısımdan oluşur. Bağlı listelerde ilk düğüme genelde "head", son düğüme de "tail" adı verilir. Teknik terimleri öğrendikten sonra uygulamaya geçelim. Ben bu yazımda bağlı liste yapısı oluştururken programlama dili olarak Java'yı IDE olarak da IntelliJ IDEA kullanıyor olacağım. Bu arada daha önce C ile bazı temel veri yapılarını oluşturmuştum onları da incelemek isterseniz şurdan buyrun.
Yeni bir Java projesi oluşturalım ve bağlı listeyi oluşturmaya başlayalım. C gibi daha düşük bir seviye dil kullanmıyorsanız eğer veri yapılarıyla çalışmak çok daha az zahmet gerektiriyor. Örneğin C'de düğüm yapısını tanımlamak, daha sonra gerçekleştirmek istediğiniz işlemler için gerekli fonksiyonları yazmak tamamen size kalıyor. Yüksek seviyeli dillerde bu fonksiyonlar ve yapılar kullanıma hazır size sunuluyor. Lafı daha fazla uzatmadan bağlı listeyi oluşturalım.
|package com.ufukcanli;|
|import java.util.LinkedList;|
|public class Main {|
|public static void main(String[] args) {|
|LinkedList list = new LinkedList(); // bu sınıfı projeye dahil etmeliyiz|
|list.addLast(10); // listenin sonuna eleman ekler|
|list.addLast(20); // listenin sonuna eleman ekler|
|list.addFirst(5); // listenin başına eleman ekler|
|System.out.println(list); // [5, 10, 20]|
|list.addLast(30);|
|System.out.println(list.contains(10)); // true|
|System.out.println(list.indexOf(10)); // 1|
|System.out.println(list.size()); // 4|
|list.removeFirst(); // listenin başındaki elemanı siler|
|System.out.println(list); // [10, 20, 30]|
|list.removeLast(); // listenin sonundaki elemanı siler|
|System.out.println(list); // [10, 20]|
|}|
|}|
Yukarıda da gördüğünüz gibi Java'da birçok yapı geliştiriciye kullanıma hazır olarak sunuluyor. Şimdi bu yapıyı ve gerekli metotları daha iyi anlamak için biz kendimiz oluşturalım ve kullanalım. Aynı proje içerisine "LinkedList" adında bir sınıf oluşturalım sonra onun içerisinde gerekli işlemleri yapmaya başlayalım.
Yukarıda "Node" adındaki sınıfı "LinkedList" içerisine yazmamızın sebebi, "Node" sınıfı içerisindeki değişkenleri private olarak tanımladığımız için onlara erişebilmek ve manipüle edebilmek için getter ve setter metotları yazmamız gerekiyor olacaktı. Şimdi listenin sonuna eleman eklemek için kullanacağımız metotu tanımlayalım.
Yukarıdaki metodu "LinkedList" sınıfımız içerisinde tanımladıktan sonra "main" metot içerisinde bu sınıftan bir liste örneği türetebilir ve yazdığımız metodu kullanabiliriz.
|package com.ufukcanli;|
|public class Main {|
|public static void main(String[] args) {|
|var list = new LinkedList();|
|list.addLast(10);|
|list.addLast(20);|
|list.addLast(30);|
|}|
|}|
Yukarıda oluşturdğumuz listeyi görebilmek için ayrı bir metot yazmak gerekiyor fakat o metodu yazmadan "debugger" kullanarak listemizin başarılı bir şekilde oluşturulduğuna emin olabilirsiniz. Şimdi listenin başına eleman eklemeyi öğrenelim ayrıca yazdığımız kodun okurken daha anlaşılabilir olmasını sağlamak için ekstra bir metot yazalım ve kullanalım.
Sıra geldi herhangi bir değer verildikten sonra o değerin tutulduğu düğümün indeksini veren metodu yazmaya.
Peki bir listenin sadece aradığımız bir elemanı içerip içermediği bilgisini sunan metodu nasıl yazardık?
Listenin başındaki bir elemanı silmek için de bir metoda ihtiyacımız var. Bunu da hemen aşağıda oluşturalım.
Listenin sonundaki elemanı silmek için sondan bir önceki düğüme ulaşmamız gerekiyor. Sondan bir önceki düğüme ulaşmak için liste üzerinde daha önce yaptığımız gibi "traverse" işlemi yapmalıyız. Daha temiz bir "removeLast" metodu yazabilmek için "getPrevious" adında bize listenin sondan bir önceki düğümünü geriye döndürecek olan metodu yazalım daha sonra asıl metodumuzu oluşturalım.
Listenin boyutunu nasıl hesaplardık? Bunu da basit bir "traverse" işlemi yapan bir method yazıp her bir düğümde değeri bir arttırıp en sonunda sonucu geriye döndürebilirdik. Fakat daha verimli bir program olması için "LinkedList" sınıfına yeni bir "field" (sınıf değişkeni) ekleyip, ekleme ve silme işlemlerinde bu değişkenin değerini güncelleyebiliriz. Daha sonra da basit bir "getter" metoduyla bu değere ulaşabiliriz. Lafı daha fazla uzatmadan bahsettiğim işlemler sonunda en baştan beri geliştiriyor olduğumuz "LinkedList" sınıfının en güncel halini görelim. Bu aşamada yapılan değişiklikler yorum satırlarıyla belirtildi.
Şimdi aşırı gerekli olmayan fakat olsa güzel olurdu dediğimiz işlemlere geçelim. Bu işlemlere oluşturduğumuz bağlı liste yapısını dizi olarak geriye döndüren bir metot eklemekle başlayalım.
Yukarıdaki işlemin başarılı olduğunu anlayabilmek için "main" metodu içerisinden şu işlemleri yapabilirsiniz.
// oluşturduğumuz metot ile listenin dizi olarak çıktısını alır var array = list.toArray(); // elde ettiğimiz diziyi stringe çevirip yazdırır System.out.println(Arrays.toString(array));
İyi güzel hoş da biz başından beri neden dizi tanımlamıyoruz ki zaten? Gelin bu sorunun cevabını öğrenelim. Daha önce de değindiğim gibi diziler daha doğrusu statik diziler sabit bir boyuta sahiptir bu sebeple sakladığımız veriler azaldığında ya da arttığında dizinin boyutunu değiştirmek gibi bir lüksümüz olmuyor. Buna alternatif olarak dinamik diziler kullanılabilir fakat onlar da bağlı listelere oranla hafızada (geçici bellekte) daha fazla yer işgal ederler. Dolayısıyla eğer kaç eleman saklayacağınızı biliyorsanız dizi yapısını kullanmak daha mantıklı olabilir fakat bu sayı belirsiz ise bağlı listeler bu soruna çok iyi bir çözüm olarak emrinize amade bekliyor olacaklar.
Şimdiye kadar oluşturduğumuz bağlı liste yapısı aslında "tek bağlı" listeye bir örnekti. Buna alternatif olarak "çift bağlı" listeler de düşünülebilir. Çift bağlı listeler basitçe anlatmak gerekirse her düğümde sonra gelen düğümün adresini tuttuğumuz gibi önce gelen düğümün de adresini tutarız. Tek bağlı listeler ve çift bağlı listeler "dairesel" listelere dönüştürülebilir. Kısaca dairesel listelerin farkını anlatmak gerekirse, listenin en son düğümü yani "tail" bir sonraki düğüm olarak listenin en başını yani "head" düğümünü gösterir. Bu yapı da karşılaştığımız problemlerde bize avantaj sağlayabilir.
Aşağıyı yukarı çalışan bir bağlı liste yapısını oluşturduğumuza göre yazıyı daha fazla uzatmadan bitirelim. Bu yapıya elbette ihtiyaca göre yeni metotlar eklenebilir veya çıkartılabilir. Herhangi bir yazım hatası keşfettiyseniz veya tartışmak istediğiniz bir konu olursa bana Twitter'dan hızlıca ulaşabilirsiniz. Kapanışı yapmadan önce bu makale 2019 yılında yazdığım muhtemelen son makale olacağı için herkese şimdiden mutlu yıllar dilerim. Seneye daha fazla makale ve projeyle görüşmek üzere hoşçakalın.