Çift yönlü, sıralı ve dairesel listeler

Geçen hafta tek yönlü listede iki zayıf nokta gördük: sondan silmek O(n), ve bir düğümü silmek için öncekini aramak gerekiyor. Bu hafta üç varyasyon var. Çift yönlü liste her düğüme bir de prev referansı ekler ve geriye gidebilir. Sıralı liste (ordered list) elemanları her zaman küçükten büyüğe tutar. Dairesel liste (circular list) son düğümü başa bağlar. Sınav soruları yine iz sürme ve metot yazma; bu sefer güncellenecek referans sayısı arttığı için hata payı da arttı.

Altın kurallar:

1. Çift yönlü listede her bağlantı iki taraflıdır. a.next = b yaptıysan b.prev = a da yapmalısın.
2. head ve tail her işlemde aday. Boş listeye ekleme ve son elemanı silme ikisini birden değiştirir.
3. Sıralı ekleme = doğru yeri bul + normal ekleme.
4. Dairesel listede null yok. Döngüyü “başa döndüm mü” ile bitir.

Çift yönlü liste (doubly linked list)

class DNode {
    int data;
    DNode prev, next;
    DNode(int d) { data = d; }
}

class DoublyLinkedList {
    DNode head, tail;
    int size;
}

head                               tail
 |                                  |
 v                                  v
[null|5|*] <-> [*|10|*] <-> [*|20|null]

Her düğüm iki yönü bilir. Bedeli: düğüm başına bir referans fazla bellek ve her işlemde iki kat referans güncellemesi.

Ekleme

void addFirst(int x) {
    DNode n = new DNode(x);
    if (head == null) { head = tail = n; }
    else { n.next = head; head.prev = n; head = n; }
    size++;
}

void addLast(int x) {
    DNode n = new DNode(x);
    if (tail == null) { head = tail = n; }
    else { n.prev = tail; tail.next = n; tail = n; }
    size++;
}

void insertAfter(DNode p, int x) {
    if (p == tail) { addLast(x); return; }
    DNode n = new DNode(x);
    n.prev = p;          // 1
    n.next = p.next;     // 2
    p.next.prev = n;     // 3  (sağdaki komşu geri n'yi göstersin)
    p.next = n;          // 4  (en son: p.next'i hâlâ kullanıyorduk)
    size++;
}

Araya eklemede dört referans değişir. 3 ve 4’ün sırası önemli: önce p.next = n yaparsan p.next.prev artık n’nin kendisinin prev’i olur ve sağdaki komşu güncellenmez.

Silme

Elinde silinecek düğümün kendisi varsa, öncesini aramana gerek yok. Bu çift yönlü listenin en büyük avantajı.

void removeNode(DNode p) {
    if (p.prev == null) head = p.next; else p.prev.next = p.next;
    if (p.next == null) tail = p.prev; else p.next.prev = p.prev;
    size--;
}

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

removeLast artık O(1). Tek yönlüde O(n) idi.

Çözümlü örnek

d.addLast(10); d.addLast(20); d.addLast(40); d.addFirst(5);
d.insertAfter(d.find(20), 30);
d.printForward(); d.printBackward();
d.removeNode(d.find(20));
System.out.println("removeLast=" + d.removeLast());
d.printForward(); d.printBackward();

5 10 20 30 40 
40 30 20 10 5 
removeLast=40
5 10 30 
30 10 5 

İPUCU · İki yönden yazdır. Bir çift yönlü liste metodunu test etmenin en iyi yolu hem ileri hem geri yazdırmak. İleri doğru doğru görünüp geri doğru farklı çıkıyorsa bir prev’i unutmuşsundur. Sınavda da izi iki yönden kontrol et.

Sıralı bağlı liste (ordered linked list)

Elemanlar her zaman artan sırada tutulur. Kullanıcı nereye ekleyeceğini söylemez; liste doğru yeri kendi bulur.

void insertSorted(int x) {
    Node n = new Node(x);
    if (head == null || x < head.data) {   // boş ya da en küçük → başa
        n.next = head;
        head = n;
        return;
    }
    Node p = head;
    while (p.next != null && p.next.data <= x)
        p = p.next;                         // x'ten büyük ilk düğümün öncesinde dur
    n.next = p.next;
    p.next = n;
}

5, 2, 8, 2, 6 sırasıyla ekleyip her adımdan sonra yazdıralım:

5 
2 5 
2 5 8 
2 2 5 8 
2 2 5 6 8 

<= ile eşit değer var olanların arkasına girer; < yazsaydın önüne girerdi. İkisi de sıralı bir liste verir, ama soruda “equal values go after” denirse fark eder.

Sıralı listede arama

Liste sıralı olduğu için aradığın değeri geçtiğin an durabilirsin:

boolean contains(int x) {
    for (Node p = head; p != null; p = p.next) {
        if (p.data == x) return true;
        if (p.data > x) return false;   // erken çıkış
    }
    return false;
}

2 2 5 6 8 listesinde 7’yi ararken 5 düğüme bakılır (8’de durur), 1’i ararken tek düğüme bakılır (2 > 1). Ortalama durum iyileşir ama en kötü durum yine O(n). Bağlı listede ikili arama (binary search) yapamazsın, çünkü ortadaki elemana O(1)‘de atlayamazsın.

Dairesel liste (circular linked list)

Son düğümün next’i null yerine ilk düğümü gösterir. Pratik bir hile: sadece tail tut. İlk düğüm her zaman tail.next. Böylece hem başa hem sona O(1) erişirsin.

          +-----------------------------+
          v                             |
 tail.next=[0] -> [1] -> [2] -> [3]=tail-+

void addFirst(int x) {
    Node n = new Node(x);
    if (tail == null) { tail = n; n.next = n; }   // tek düğüm kendini gösterir
    else { n.next = tail.next; tail.next = n; }
}

void addLast(int x) { addFirst(x); tail = tail.next; }   // başa ekle, tail'i kaydır

int removeFirst() {
    Node first = tail.next;
    if (first == tail) tail = null;    // tek eleman vardı
    else tail.next = first.next;
    return first.data;
}

void rotate() { if (tail != null) tail = tail.next; }   // ilk eleman sona geçer

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

addLast hilesine dikkat: başa ekleyip tail’i bir ileri kaydırınca yeni düğüm son olur. Çözümlü örnek:

c.addLast(1); c.addLast(2); c.addLast(3); c.addFirst(0);
c.print();
c.rotate(); c.print();
System.out.println("removeFirst=" + c.removeFirst());
c.print();

0 1 2 3 
1 2 3 0 
removeFirst=1
2 3 0 

TUZAK · while (p != null) dairesel listede sonsuz döngüdür. Hiçbir düğümün next’i null değil. do-while kullan ve başa dönünce dur. while (p != tail.next) ile başlarsan döngü hiç çalışmaz, çünkü p zaten tail.next’ten başlıyor.

Dairesel listenin tipik kullanımları: sırayla dönen işler (round-robin zamanlayıcı), çok oyunculu oyunda sıra, ve Josephus problemi (çemberde her k. kişiyi elemek).

Sık yapılan hatalar

list.addFirst(2);
list.addLast(4);
list.addFirst(1);
list.addLast(6);
list.removeFirst();
list.addFirst(8);

DNode p = head.next;
System.out.println(p.prev.data + p.next.next.data);
System.out.println(tail.prev.prev.data);
p.next.data = p.prev.data * 10;
printForward();

int removeLast() {
    if (tail == null) throw new RuntimeException("empty list");
    int x = tail.data;
    tail = tail.prev;
    if (tail == null)      // tek eleman vardı
        head = null;
    else
        tail.next = null;  // yeni son düğüm
    size--;
    return x;
}

void insertSorted(int x) {
    Node n = new Node(x);
    if (head == null || x < head.data) {
        n.next = head;
        head = n;
        return;
    }
    Node p = head;
    while (p.next != null && p.next.data <= x)
        p = p.next;
    n.next = p.next;
    p.next = n;
}

c.addLast(4);
c.addFirst(7);
c.addLast(9);
c.rotate();      // tail = tail.next
c.addFirst(1);
c.removeFirst();
c.rotate();
c.print();       // from tail.next around to tail

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

p.prev.next = p.next;
p.next.prev = p.prev;

if (p.prev == null) head = p.next;
else p.prev.next = p.next;
if (p.next == null) tail = p.prev;
else p.next.prev = p.prev;