Tek yönlü bağlı liste (singly linked list)

Dizi (array) güzel bir yapı ama iki dertlidir: boyutu baştan sabittir ve ortaya eleman eklemek için diğerlerini kaydırman gerekir. Bağlı liste (linked list) bu iki derdi çözer. Her eleman kendi küçük kutusunda (node) durur ve bir sonraki kutunun adresini taşır. Sınavda iki tip soru gelir: bir dizi işlemden sonra listenin son halini yazmak, ve addLast, remove, countNodes gibi bir metodu sıfırdan yazmak.

Altın kurallar:

1. Liste = head referansı. Head’i kaybedersen listeyi kaybedersin.
2. Gezinme her zaman p = p.next ile. Bitiş koşulu p != null (her düğümü gez) ya da p.next != null (son düğümde dur).
3. Ekleme sırasında önce yeni düğümü bağla, sonra eskisini yönlendir.
4. Silmek için öncekini bul. Tek yönlü listede geri gidemezsin.
5. Boş liste, tek elemanlı liste ve head her zaman özel durumdur.

Node sınıfı

Bir düğüm iki şey taşır: veri (data) ve bir sonraki düğüme referans (next). Son düğümün next’i null’dır.

class Node {
    int data;
    Node next;
    Node(int data) { this.data = data; }   // next otomatik null
}

class SinglyLinkedList {
    Node head;   // ilk düğüm; boş listede null
    int size;
}

Bellekte 10 → 20 → 30 listesi şöyle görünür:

head
 |
 v
[10 | *]--->[20 | *]--->[30 | null]

Her kutu bellekte farklı bir yerde durabilir. Diziden farkı bu: a[2] doğrudan hesaplanır, ama listede üçüncü elemana ulaşmak için head’den başlayıp iki kez next izlemen gerekir. Bu yüzden indeksle erişim O(n).

TUZAK · Node p = head; yeni düğüm yaratmaz. Sadece var olan düğümü gösteren ikinci bir ok oluşturur. p.data = 99 yaparsan head’in verisi de 99 olur, çünkü aynı kutu.

Gezinme (traversal)

Listeyi yazdırmak, toplamını almak, eleman aramak: hepsi aynı kalıp.

void print() {
    Node p = head;
    while (p != null) {
        System.out.print(p.data + " ");
        p = p.next;
    }
    System.out.println();
}

boolean contains(int x) {
    for (Node p = head; p != null; p = p.next)
        if (p.data == x) return true;
    return false;
}

head’in kendisini ilerletme (head = head.next). Yazdırdıktan sonra liste boş görünür. Her zaman yardımcı bir p kullan.

Ekleme

Başa ekleme (addFirst)

void addFirst(int x) {
    Node n = new Node(x);
    n.next = head;   // yeni düğüm eski ilk düğümü göstersin
    head = n;        // head yeni düğüm olsun
    size++;
}

İki satır, döngü yok: O(1). Boş listede de çalışır (head null ise n.next = null olur).

Sona ekleme (addLast)

Sadece head varsa son düğüme yürümek zorundasın.

void addLast(int x) {
    Node n = new Node(x);
    if (head == null) { head = n; size++; return; }
    Node p = head;
    while (p.next != null) p = p.next;   // p artık son düğüm
    p.next = n;
    size++;
}

Süre O(n). Sınıfa bir tail referansı eklersen tail.next = n; tail = n; ile O(1) olur, ama o zaman her silmede tail’i de güncellemen gerekir.

Araya ekleme (insertAt)

İndeks index konumuna eklemek için index - 1 konumundaki düğüme git.

void insertAt(int index, int x) {   // 0 = başa
    if (index == 0) { addFirst(x); return; }
    Node p = head;
    for (int i = 0; i < index - 1; i++) p = p.next;
    Node n = new Node(x);
    n.next = p.next;   // 1) yeni düğüm, p'nin eski sonrakini göstersin
    p.next = n;        // 2) p yeni düğümü göstersin
    size++;
}

Önce:   p=[20] ---> [30]
1)      [25] ---> [30]   (n.next = p.next)
2)      [20] ---> [25] ---> [30]   (p.next = n)

TUZAK · Satırların sırası. Önce p.next = n; yazarsan p.next’in eski değeri (30) kaybolur. Sonra n.next = p.next; aslında n.next = n olur. Düğüm kendini gösterir, liste sonsuz döngüye girer.

Silme

Baştan silme

int removeFirst() {
    if (head == null) throw new RuntimeException("empty list");
    int x = head.data;
    head = head.next;
    size--;
    return x;
}

Eski ilk düğümü gösteren kimse kalmaz, Java’nın çöp toplayıcısı (garbage collector) onu temizler. O(1).

Sondan silme

Son düğümü silmek için sondan bir önceki düğümün next’ini null yapmalısın.

int removeLast() {
    if (head == null) throw new RuntimeException("empty list");
    if (head.next == null) {            // tek eleman
        int x = head.data; head = null; size--; return x;
    }
    Node p = head;
    while (p.next.next != null) p = p.next;   // p = sondan bir önceki
    int x = p.next.data;
    p.next = null;
    size--;
    return x;
}

Tail referansı olsa bile bu O(n). Tail sana son düğümü verir ama sondan öncekini vermez.

Değere göre silme

boolean remove(int x) {
    if (head == null) return false;
    if (head.data == x) { head = head.next; size--; return true; }
    Node p = head;
    while (p.next != null && p.next.data != x) p = p.next;
    if (p.next == null) return false;
    p.next = p.next.next;   // hedefi atla
    size--;
    return true;
}

Döngü koşulunun sırası önemli: p.next != null önce kontrol edilir, böylece p.next.data null üzerinde çağrılmaz (&& kısa devre yapar).

Çözümlü örnek: işlem izi

Boş listeyle başla ve her adımda listeyi yaz:

list.addFirst(20);
list.addFirst(10);
list.addLast(30);
list.addLast(40);
list.print();
list.insertAt(2, 25);
list.print();
System.out.println("removeFirst=" + list.removeFirst());
System.out.println("removeLast=" + list.removeLast());
list.print();
System.out.println(list.remove(25) + " " + list.remove(99));
list.print();

10 20 30 40 
10 20 25 30 40 
removeFirst=10
removeLast=40
20 25 30 
true false
20 30 

addFirst(20)   [20]
addFirst(10)   [10, 20]
addLast(30)    [10, 20, 30]
addLast(40)    [10, 20, 30, 40]
insertAt(2,25) [10, 20, 25, 30, 40]   (indeks 1'deki 20'den sonra)
removeFirst    [20, 25, 30, 40]   döner 10
removeLast     [20, 25, 30]       döner 40
remove(25)     [20, 30]           true
remove(99)     [20, 30]           false, değişmedi

Sınavda bu tabloyu kendin çiz. Her satırda listenin tamamını yazmak hata yapmanı engeller.

Karmaşıklık özeti

Sık yapılan hatalar

list.addFirst(3);
list.addFirst(7);
list.addLast(5);
list.addFirst(1);
list.print();

list.addLast(4);
list.addLast(8);
list.addFirst(2);
list.addLast(6);
list.removeFirst();
list.addFirst(9);
list.removeLast();
list.print();

Node a = new Node(1);
a.next = new Node(2);
a.next.next = new Node(3);
a.next.next.next = new Node(4);
a.next = a.next.next;
for (Node p = a; p != null; p = p.next)
    System.out.print(p.data + " ");

Node h = new Node(5);
h.next = new Node(10);
h.next.next = new Node(15);
Node t = h.next;
t.next.data = t.data + h.data;
h.data = t.next.data * 2;
for (Node p = h; p != null; p = p.next)
    System.out.print(p.data + " ");

list.insertAt(1, 9);
list.insertAt(4, 7);
list.insertAt(0, 5);
list.print();
list.remove(2);
list.remove(5);
list.print();

int countNodes() {
    int c = 0;
    Node p = head;
    while (p != null) {
        c++;
        p = p.next;
    }
    return c;
}

void addLast(int x) {
    Node n = new Node(x);
    if (head == null) {
        head = n;
        return;
    }
    Node p = head;
    while (p.next != null)
        p = p.next;
    p.next = n;
}

boolean remove(int x) {
    if (head == null) return false;
    if (head.data == x) {
        head = head.next;
        return true;
    }
    Node p = head;
    while (p.next != null && p.next.data != x)
        p = p.next;
    if (p.next == null) return false;   // bulunamadı
    p.next = p.next.next;               // atla
    return true;
}

p.next = n;
n.next = p.next;

for (Node p = head; p != null; p = p.next.next)
    System.out.print(p.data + " ");

int mx = head.data, cnt = 0;
for (Node r = head; r != null; r = r.next) {
    if (r.data > mx) mx = r.data;
    if (r.data % 2 == 1) cnt++;
}
System.out.println(mx + " " + cnt);