Java Bağlantılı Listeler (Linked List in Java)

Tek yönlü bağlantılı listeleri ve çalışma mantığını içerir.

Herkese merhaba , sonunda okulda veri yapıları dersi almaya başladım. Programlama için veri yapılarının ne kadar önemli olduğunu bildiğinizi düşünüyorum. Bende derste işlendikçe buraya veri yapıları ile ilgili yazılar paylaşacağım. İlk gördüğüm veri  yapısı olan   linked list  ‘ e dair birkaç bir şey anlatmaya çalışacağım.  Aslında video çekmeye müsait ortam olsa veri yapıları daha iyi anlatılır kanısındayım , neyse hadi başlayalım.

Bu arada önceden söyleyeyim ben ilk tek yönlü (singly )  den bahsedeceğim daha sonra bu yazının üstüne diğer linked list leri ekleyeceğim. Java da ki linkedlist sınıfınındaki metotları anlatmak yerine linked list sınıfı nasıl oluşturuluyor onu anlatmaya çalışacağım.

Linked list adı üstünde bağlantılı listeler , birbirine bağlı . Nasıl bağlı olduğuda şuanlık kısaca şöyle söyleyim , birinin index(indeks, id,address) ini diğeri gösteriyor. C dilin de anlatsaydım pointers kelimesini kullanırdım  ama bildiğiniz üzere java da pointers yok onun yerine referanslar var.Neyse konuyu fazla dağıtmayayım.

Linked list in  gerçek bir nesne gibi düşünecek olursak tren vagonlarına benzetebiliriz. Vagonların kendisini veri , vagonlar arasında bağlantıya da bir sonraki vagonun adresinin tutulduğu yer olarak düşünülebilir.  (bu örnek tıpa tıp benzeyecek diye bir şey yok sadece mantığının görsel olarak anlaşılması için verdim )

Linked list in hafızasından bahsedecek olursa dinamik bir yapıya sahip olduğundan dizi gibi bir sınır bulunmuyor.

Tek yönlü (singly linked list ) den bahsettiğimizde göre bu sözün anlamından biraz bahsedeyim. Şöyle ki linked listte bir sonraki index tutuluyorsa buna tek yönlü deniliyor . Hem bir sonraki index i hem bir önceki index i de tutabiliriz ama bu yazı da tek yönlü linked list den bahsedeceğim.

Yukarıda ki gibi , veri ve bir sonraki verinin indeksinin tutulduğu yerlere NODE deniliyor. Önemli olan şey ise her linked list in bir başlangıç verisi olması gerekir. Bu başlangıç verisine root yada head deniliyor.

Linked list in dezavantajlarından birini söyleyecek olursak , şöyle bir senoryo kuralım, biz çok verilerden oluşan bir linked list oluşturduk diyelim ve ortalarda bir yerlerdeki bir node  a ulaşmak istiyoruz diyelim , işte bu node a ulaşmak için her node birbirine bağlı durumda olduğundan dolayı  en baştaki root dediğimiz den taramamız gerekiyor. Birazdan yazacağımız  getNextNode() metodu bu işe yarayacak.

Şimdi ilk Node sınıfından konuşalım. Kendimize şu soruyu soruyoruz node un nesi var ? 🙂

Şimdi, Node class ı aslında fazla karışık değil , bir int tipinde verisi var ve kendi tipinde , bir sonraki node u gösteren nextNode değişkeni var. Burada ben örnek olsun diye int tipinde veri ekledim , ilerde generics konusunu anlatabilirsek buraya istediğimiz tipte veri yazabiliriz.

 

Asıl metotları yazacağım olan sınıfa geçelim şimdi

 

Şimdi buradaki metotların çalışma mantığından bahsedelim.

Öncelikle addFirst() metodundan bahsedeyim

Bildiğiniz üzere linked list te (head) adında ilk eleman vardı . Biz linked list in başına bir eleman eklemek istiyorsak ilk önce bu head ı kaldırıp yeni bir node oluşturmamız lazım ve bu node da artık yeni head imiz olacaktır.

Bu sınıfta tutuğumuz count değişkeni ise bizim eleman sayımızı tutuyor.

Sınıftaki metotlara dikkatlice bakarsanız bir ekleme işlemi olduğunda sadece veri çekmek  yetmiyor. Bir de node oluşturmamız gerekiyor. Tren vagonlarını hatırlayın.

addfirst() metotdu bu kadardı kısaca burda yeni bir node oluşturduk ve yeni head belirledik.

 


Şimdi removeEnd() metodunu ele alalım.

Şimdi ilk satırdan sırayla başlayalım

  • Doğrudan head in üzerinde işlem yapmayacağımızdan head i başka bir değişkende tuttuk.
  • while ilk baktığınız da biraz karışık gelebilir ama sakin olun . Sizde deneyin ve şunu görün current.getNextNode()…. böyle abartayım sonsuza kadar gidersiniz. While içinde 2 tane kullanmamızın sebebi var. Kontrol etmeye 2 node önceden başlıyoruz çünkü dikkat ederseniz orada getNextNode() metodu var.
  • Asıl önemli olan current=current.getNextNode(); satırı burada tam öyle değil ama  en basitinden for un içinde yaptığımız toplam=toplam +i gibi düşünebilirsiniz burada bu işlemi yapmamızın sebebi en başta değindiğim linked list in dezavantajı na  dayanıyor. while döngüsünden en sonuncu node dan bir önceki node u bulduğu zaman çıkıyor.
  • ve bir altta satırda null değeri gönderiyoruz.
  • ve eleman sildiğimiz den dolayı count– yaparak eleman sayısını azaltıyoruz.

Şimdi delete() metoduna bakalım bu metotda sondan silme değil istediğimiz indeks den silme işlemi yapıyor.

  • for döngümüzü şu amaçla çalıştırıyoruz. Biz parametre olarak bir indeks değeri girdiğimizde o indeks değerine kadar head dan başlayıp sürekli getNextNode() diyerek bir sonraki node  a gidecek. İstediğimiz node a geldiğinde ise for dan çıkacak
  • aradaki node u kesip , şuanki node u kestiğimiz node un önüne bağlamalıyız bu nedenle de current.setNextNode(current.getNextNode().getNextNode()); satırını kullanıyoruz.
  • yine sildiğimizden dolayı count — yapıyoruz.

Özet olarak  linked list e eleman eklerken yeni bir düğüm oluşturuyoruz ve araya bağlantılar ekliyoruz. Silerken ise aralardaki bağlantıları koparıyoruz.


Test sınıfımız aşağıdaki gibidir

 

İngilizce kaynak isterseniz buyrun 🙂


Şimdilik bu kadar yazıyorum ilerleyen zamanlarda eklemeler yapmayı planlıyorum. Eksik ve yanlış olduğunu düşündüğünüz yerleri ve önerilerinizi yorumda belirtirseniz sevinirim.

[poll id=”4″]