İkili bağlı listeler (Doubly Linked Lists) veri yapılarından biridir. Bu yapıda her düğüm kendisinden önceki ve sonraki düğümlerin referanslarını tutar. Bu, verilerin iki yönde de gezinilmesine olanak tanır. İkili bağlı bir listenin her bir düğümü genellikle bir veri kısmı ve iki referans kısmı içerir. Bu referanslar, düğümün kendisinden önceki ve sonraki düğümlere işaret eder.

İkili bağlı listenin bir şeması şu şekilde olabilir:

İkili bağlı listelerin bazı özellikleri şunlardır:

Çift Yönlü Gezinme: Her düğüm, kendisinden önceki ve sonraki düğümlere işaret ettiği için, listeyi hem ileri hem de geri yönde gezebilirsiniz.

Ekleme ve Silme: İkili bağlı listelerde ekleme ve silme işlemleri, düğüm referanslarının doğru şekilde güncellenmesiyle kolaylıkla yapılabilir. Bir düğümü silmek veya eklemek istediğinizde, sadece o düğüme komşu olan düğümlerin referanslarını güncellemeniz gerekir.

Hafıza Kullanımı: İkili bağlı listeler, her düğümde bir ek referans sakladığından, tek yönlü bağlı listelere göre daha fazla hafıza kullanır.

Başlangıç ve Son Noktada Erişim: İkili bağlı listeler, başlangıç ve son noktaya erişim sağlamak için genellikle baş ve kuyruk referansları içerir. Bu, listenin her iki ucunda da işlemleri hızlandırır.

Karmaşıklık: İkili bağlı listelerde ekleme ve silme işlemleri genellikle O(1) zaman karmaşıklığına sahip olabilir, ancak arama işlemi O(n) zaman karmaşıklığına sahip olabilir, çünkü aranan öğeyi bulmak için listeyi taramanız gerekir (burada n, listenin boyutudur).

İkili bağlı listeler, bir dizi uygulama için kullanışlıdır, özellikle de verilerin iki yönde de gezinilmesi gerektiğinde. Bununla birlikte, ekstra referansların hafıza maliyeti göz önünde bulundurulmalıdır.

Bir sentinel, bir veri yapısında işlemleri kolaylaştırmak amacıyla kullanılan özel bir düğüm veya değerdir. İkili bağlı listelerle birlikte kullanıldığında, bazı işlemlerin daha etkili bir şekilde gerçekleştirilmesine yardımcı olabilir.

Sentinel kullanmanın avantajları şunlar olabilir:

Kod Karmaşıklığının Azalması: Sentineller, bazı durumları basitleştirerek kod karmaşıklığını azaltabilir. Özellikle boş liste veya listenin sonuna ulaşıldığında özel durumları işlemek yerine, sentinel düğümleri bu durumları otomatik olarak ele alabilir.

Hızlı Ekleme ve Silme: İkili bağlı bir listede başa veya sona ekleme veya silme yaparken, sentinel kullanmak bu işlemleri hızlandırabilir. Sentinel'in bulunduğu yerlerde ekstra kontrol yapmanıza gerek kalmaz, bu da işlemlerin daha hızlı yapılmasını sağlar.

Daha Az Hata Olasılığı: Kod daha basit ve daha az durum içerdiğinde, hata yapma olasılığı genellikle azalır. Sentineller, ikili bağlı listenin başlangıcını ve sonunu işaret etmek için kullanılabileceğinden, yanlışlıkla geçersiz bir referansa erişmek veya geçersiz bir düğüm oluşturmak gibi hataların oluşma olasılığını azaltabilir.

Daha Kolay Gezinme: Bazı algoritmalar, listenin başından sonuna veya sonundan başına doğru gezinmeyi gerektirir. Sentineller, bu tür algoritmaları daha düzenli ve etkili hale getirebilir, çünkü ekstra durumları kontrol etmek zorunda kalmazsınız.

Ancak, sentinellerin de bir maliyeti olabilir. Ekstra sentinel düğümleri, hafıza kullanımını artırabilir ve bazı durumlarda kodu daha karmaşık hale getirebilir. Bununla birlikte, doğru bir şekilde kullanıldığında, sentineller ikili bağlı liste işlemlerinin verimliliğini artırabilir ve kodun okunabilirliğini ve bakımını kolaylaştırabilir.

class Node:
    def __init__(self, value, prev_node=None, next_node=None):
        self.value = value
        self.prev = prev_node
        self.next = next_node

class DoublyLinkedList:
    def __init__(self):
        self.header = Node(None)  # başlık sentinel
        self.trailer = Node(None)  # kuyruk sentinel
        self.header.next = self.trailer
        self.trailer.prev = self.header
        self.size = 0

    def append(self, value):
        new_node = Node(value)
        prev_node = self.trailer.prev
        prev_node.next = new_node
        new_node.prev = prev_node
        new_node.next = self.trailer
        self.trailer.prev = new_node
        self.size += 1

    def print_list(self):
        current = self.header.next
        while current is not self.trailer:
            print(current.value, end=' ')
            current = current.next
        print()


dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.print_list()  # 1 2 3

İkili bağlı bir liste (Doubly Linked List) kullanırken ekleme (inserting) ve silme (deleting) işlemleri, düğümlerin birbirine olan referanslarının doğru bir şekilde güncellenmesini gerektirir. İşte her iki işlemin de nasıl çalıştığına dair bir açıklama:

Ekleme (Inserting)

Bir ikili bağlı listeye bir düğüm eklemek istediğinizde, eklemek istediğiniz yere bağlı olarak birkaç adımı takip etmeniz gerekir:

Düğüm Oluşturma: Yeni bir düğüm oluşturun ve eklemek istediğiniz değeri içine koyun.

Yer Bulma: Eklemek istediğiniz yeri bulun. Bu, listenin başı, sonu veya belirli bir indeks olabilir.

Referansları Güncelleme: Yeni düğümün önceki ve sonraki referanslarını güncelleyin, böylece doğru düğümlere işaret eder. Ayrıca, yeni düğüme komşu olan düğümlerin referanslarını da güncelleyin, böylece yeni düğüme işaret ederler.

Boyutu Güncelleme: Listenin boyutunu bir artırın (eğer boyutu takip ediyorsanız).

Silme (Deleting)

Bir ikili bağlı listeden bir düğüm silmek istediğinizde, aşağıdaki adımları takip etmeniz gerekir:

Düğümü Bulma: Silmek istediğiniz düğümü bulun.

Referansları Güncelleme: Silmek istediğiniz düğümün önceki ve sonraki düğümlerinin referanslarını güncelleyin, böylece silinen düğümü atlayacak şekilde işaret ederler.

Düğümü Temizleme: İlgili düğümü bellekten silmek için referansları temizleyin (Python gibi dillerde bu, genellikle otomatik olarak gerçekleşir).

Boyutu Güncelleme: Listenin boyutunu bir azaltın (eğer boyutu takip ediyorsanız).

Örnek Kod

Aşağıda, önceki örneğe ekleme ve silme işlevleri eklenmiş bir Python kodu bulunmaktadır:

# ... (Önceki sınıflar: Node ve DoublyLinkedList'in başlangıcı)

    def insert(self, value, position):
        if position < 0 or position > self.size:
            print("Invalid position")
            return
        new_node = Node(value)
        current = self.header if position <= self.size // 2 else self.trailer
        for _ in range(position if position <= self.size // 2 else self.size - position + 1):
            current = current.next if position <= self.size // 2 else current.prev
        new_node.prev = current.prev
        new_node.next = current
        current.prev.next = new_node
        current.prev = new_node
        self.size += 1

    def delete(self, position):
        if position < 0 or position >= self.size:
            print("Invalid position")
            return
        current = self.header.next if position <= self.size // 2 else self.trailer.prev
        for _ in range(position if position <= self.size // 2 else self.size - position - 1):
            current = current.next if position <= self.size // 2 else current.prev
        current.prev.next = current.next
        current.next.prev = current.prev
        self.size -= 1

# ... (Önceki sınıfların devamı ve kullanım örnekleri)

Bu kod, belirli bir konuma bir düğüm eklemek ve belirli bir konumdaki bir düğümü silmek için iki işlev içermektedir. Her iki durumda da, düğümlerin referanslarının doğru bir şekilde güncellenmesi çok önemlidir, aksi takdirde liste bozulabilir.