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]
}
}
view raw Main.java hosted with ❤ by GitHub

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.

package com.ufukcanli;
public class LinkedList {
private class Node {
private int data; // düğümdeki veriyi tutacak
private Node next; // bir sonraki düğümün adresini tutacak
// düğüm oluştururken kullanacağımız constructor
public Node(int data) {
this.data = data;
}
}
private Node head; // listenin başındaki elemanı temsil edecek
private Node tail; // listenin sonundaki elemanı temsil edecek
}
view raw LinkedList.java hosted with ❤ by GitHub

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.

public void addLast(int value) {
var node = new Node(value); // yeni bir düğüm oluşturduk
// liste boşsa, listenin başı da sonu da yeni düğümü göstersin
if (head == null)
head = tail = node;
else {
// liste doluysa listenin sonundaki eleman yeni düğümü göstersin
tail.next = node;
// listenin sonundaki eleman yeni düğüm olsun
tail = node;
}
}
view raw LinkedList.java hosted with ❤ by GitHub

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);
}
}
view raw Main.java hosted with ❤ by GitHub

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.

public void addFirst(int value) {
var node = new Node(value);
if (isEmpty())
head = tail = node;
else {
node.next = head;
head = node;
}
}
// bu metodu "addLast()" içerisinde de kullanabilirsiniz
private boolean isEmpty() {
return head == null;
}
view raw LinkedList.java hosted with ❤ by GitHub

Sıra geldi herhangi bir değer verildikten sonra o değerin tutulduğu düğümün indeksini veren metodu yazmaya.

public int indexOf(int value) {
int index = 0;
var current = head;
while (current != null) { // baştan sonra kadar git
// eğer tutulan değer aranan değerse indeksini dön
if (current.data == value) return index;
current = current.next; // değilse bir sonraki düğüme geç
index++; // her geçişte indeksi bir arttır
}
return -1; // aranan eleman listede yoksa -1 dön
}
view raw LinkedList.java hosted with ❤ by GitHub

Peki bir listenin sadece aradığımız bir elemanı içerip içermediği bilgisini sunan metodu nasıl yazardık?

public boolean contains(int value) {
var current = head;
while (current != null) { // baştan sonra kadar git
// eğer tutulan değer aranan değerse "true" dön
if (current.data == value) return true;
current = current.next; // değilse bir sonraki düğüme geç
}
return false; // değer listede bulunamadıysa "false" dön
}
// Alternatif ve daha kısa olan yöntem
public boolean contains(int value) {
return indexOf(value) != -1;
}
view raw LinkedList.java hosted with ❤ by GitHub

Listenin başındaki bir elemanı silmek için de bir metoda ihtiyacımız var. Bunu da hemen aşağıda oluşturalım.

public void removeFirst() {
// liste boşsa hata mesajı fırlat
if (isEmpty()) throw new NoSuchElementException();
// listede sadece bir tane eleman varsa
if (head == tail) {
head = tail = null;
return;
}
// yukarıdakilerin hiçbiri geçerli değilse
// en baştaki düğümden sonra gelen düğüme "second" adını verdik
var second = head.next;
// en baştaki düğümün işaret ettiği adresi kaldırdık
head.next = null;
// ikinci düğüm artık en baştaki düğüm oldu
head = second;
}
view raw LinkedList.java hosted with ❤ by GitHub

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.

private Node getPrevious(Node node) {
var current = head;
while(current != null) { // baştan başla sona kadar git
// sondan bir önceki düğüme ulaşınca geri döndür
if (current.next == tail) return current;
current = current.next;
}
return null; // yukarıdaki işlemler başarısız ise "null" döndür
}
public void removeLast() {
// liste boş mu?
if (isEmpty()) throw new NoSuchElementException();
// listede sadece bir eleman varsa
if (head == tail) {
head = tail = null;
return;
}
// sondan bir önceki düğümü al
var previous = getPrevious(tail);
// listenin yeni son düğümü, sondan bir önceki düğüm olsun
tail = previous;
tail.next = null;
}
view raw LinkedList.java hosted with ❤ by GitHub

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.

package com.ufukcanli;
import java.util.NoSuchElementException;
public class LinkedList {
private class Node {
private int data;
private Node next;
public Node(int data) {
this.data = data;
}
}
private Node head;
private Node tail;
private int size; // buraya yeni bir field eklendi
public void addLast(int value) {
var node = new Node(value);
if (isEmpty())
head = tail = node;
else {
tail.next = node;
tail = node;
}
size++; // düğüm ekleme işleminden sonra size +1 oldu
}
public void addFirst(int value) {
var node = new Node(value);
if (isEmpty())
head = tail = node;
else {
node.next = head;
head = node;
}
size++; // düğüm ekleme işleminden sonra size +1 oldu
}
private boolean isEmpty() {
return head == null;
}
public int indexOf(int value) {
int index = 0;
var current = head;
while (current != null) {
if (current.data == value) return index;
current = current.next;
index++;
}
return -1;
}
public boolean contains(int value) {
var current = head;
while (current != null) {
if (current.data == value) return true;
current = current.next;
}
return false;
}
/* public boolean contains(int value) {
return indexOf(value) != -1;
} */
public void removeFirst() {
if (isEmpty()) throw new NoSuchElementException();
if (head == tail) {
head = tail = null;
return;
}
var second = head.next;
head.next = null;
head = second;
size--; // düğüm ekleme işleminden sonra size -1 oldu
}
private Node getPrevious(Node node) {
var current = head;
while(current != null) {
if (current.next == tail) return current;
current = current.next;
}
return null;
}
public void removeLast() {
if (isEmpty()) throw new NoSuchElementException();
// burada da değişiklikler oldu!
// eğer listede 1 adet düğüm olsaydı
// daha önce uyguladığımız mantık başarısız sonuç verecekti
if (head == tail) {
head = tail = null;
} else {
var previous = getPrevious(tail);
tail = previous;
tail.next = null;
}
size--;
}
// size değerini geri döndürür
public int size() {
return size;
}
}
view raw LinkedList.java hosted with ❤ by GitHub

Ş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.

public int[] toArray() {
// tuttuğumu "size" değişkeni boyutunda bir dizi tanımlayalım
int[] array = new int[size];
var current = head;
int index = 0;
// baştan sona doğru gidelim
while(current != null) {
// her düğümdeki değeri, ona karşılık gelen indeksteki dizi elemanına atayalım
array[index++] = current.data;
current = current.next;
}
return array;
}
view raw LinkedList.java hosted with ❤ by GitHub

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.