Çift Yönlü Bağlı Liste

Q: Tek yönlü ve çift yönlü bağlı liste arasındaki fark nedir?

Tek yönlü bağlı listede düğüm başına bir işaretçi vardır (`next`), bu yüzden yalnızca ileri gidebilirsiniz. Çift yönlü bağlı liste bir `prev` işaretçisi ekler; bu, geriye gezinmeyi ve referansını tuttuğunuz bir düğümü `O(1)` sürede silmeyi sağlar; bunun bedeli düğüm başına ek bir işaretçi ve her değişiklikte iki bağlantıyı güncellemektir.

Q: Çift yönlü bağlı liste ve dizi: hangisini kullanmalıyım?

İndeksle `O(1)` erişime ve önbellek dostu yinelemeye ihtiyaç duyduğunuzda ve eklemeler çoğunlukla sonda olduğunda dizi kullanın. Bir düğüm referansıyla ortada veya her iki uçta sık sık ekleyip çıkarıyorsanız çift yönlü bağlı liste kullanın; çünkü bu, dizinin `O(n)` kaydırmasına karşı `O(1)`'dir. Diziler bellek ve yerellikte kazanır; liste yapısal düzenlemelerde kazanır.

Q: Çift yönlü bağlı listeden silerken en yaygın hata nedir?

İlk veya son düğümü silerken `head` ya da `tail`'i güncellemeyi unutmak; bu, serbest bırakılmış bir düğüme sarkan bir işaretçi bırakır. Komşuları yeniden bağlamadan önce `node.prev`'in `null` olup olmadığını (`head`'i güncelle) veya `node.next`'in `null` olup olmadığını (`tail`'i güncelle) her zaman kontrol edin.

Son güncelleme 1 Temmuz 2026

Çift yönlü bağlı liste, her düğümün iki işaretçi tuttuğu bir bağlı listedir: next (sonraki düğüme) ve prev (önceki düğüme). Bu ek geriye dönük bağlantı, her iki yönde de gezinmenizi ve zaten bir referansınız olan bir düğümü O(1) sürede silmenizi sağlar; çünkü baştan yürümek yerine önceki düğüme doğrudan ulaşabilirsiniz. Düğümlerin her iki yönde bağlanıp yeniden bağlanmasını izlemek için yukarıdaki oynat düğmesine basın.

Bunun maliyeti, düğüm başına fazladan bir işaretçi ve daha fazla defter tutmadır: her ekleme ve silme, komşulardaki hem next hem de prev alanını güncellemelidir. Bu, her iki uçtan hızlı silmenin önemli olduğu birçok deque ve LRU önbelleğinin arkasındaki yapıdır.

Zaman karmaşıklığı

İşlem	Karmaşıklık	Notlar
Başa/sona ekleme	O(1)	Baş ve son işaretçileriyle
Bilinen bir düğümü silme	O(1)	prev'e doğrudan ulaşılır, yürüme yok
Arama	O(n)	Yine doğrusal tarama
İndeksle erişim	O(n)	Rastgele erişim yok

Tek yönlü ve çift yönlü bağlı liste

Yön	Tek yönlü	Çift yönlü
Düğüm başına işaretçi	1 (next)	2 (next + prev)
Geriye gezinme	Hayır	Evet
Bilinen bir düğümü silme	O(n) (prev'i bul)	O(1)
Bellek ek yükü	Daha düşük	Daha yüksek

Çözümlü örnek

Sona ekleyerek [10, 20, 30] oluşturma, ardından 20 düğümünü silme:

Adım	Yapı	Eylem
Başlangıç	`null`	Boş liste: `head` ve `tail` ikisi de `null`
10 ekle	`10`	İlk düğüm; `head` ve `tail` ona işaret eder, `prev` = `next` = `null`
20 ekle	`10 <-> 20`	`10.next = 20` ve `20.prev = 10` ayarlanır; `tail` = `20`
30 ekle	`10 <-> 20 <-> 30`	`20.next = 30` ve `30.prev = 20` ayarlanır; `tail` = `30`
20'yi sil	`10 <-> 30`	`20.prev` ve `20.next` kullanılarak: `10.next = 30` ve `30.prev = 10` `O(1)` sürede ayarlanır

Çift yönlü bağlı liste ne zaman kullanılır

Şu durumda kullan	Şu durumda kaçın
Her iki yönde gezinmen veya bağlaman gerekir	Yalnızca ileri gidersin: tek yönlü liste daha hafiftir
Zaten referansını tuttuğun rastgele düğümleri silersin (`O(1)`)	Genellikle konuma göre indekslersin: `O(1)` erişim için dizi kullan
Bir deque, LRU önbelleği veya geri alma geçmişi uygularsın	Bellek dardır: ek `prev` işaretçisi bağlantı ek yükünü ikiye katlar
Eklemeler ve çıkarmalar sık sık her iki uçta olur	Veri küçüktür ve nadiren değişir: dizi kopyalamak daha ucuzdur

Doubly Linked List kodu

Python, JavaScript, Java, C++, C dillerinde temiz ve çalıştırılabilir bir Doubly Linked List uygulaması. Bir dil seçin, kodu kopyalayın veya Coddy Playground'da hazır yüklenmiş olarak açın.

Python ile Doubly Linked List koduPython
1class Node:2    def __init__(self, value):3        self.value = value4        self.prev = None5        self.next = None6
7
8class DoublyLinkedList:9    def __init__(self):10        self.head = None11        self.tail = None12
13    def append(self, value):14        node = Node(value)15        if self.tail is None:16            self.head = self.tail = node17            return18        # Wire both directions: old tail <-> new node19        node.prev = self.tail20        self.tail.next = node21        self.tail = node22
23    def prepend(self, value):24        node = Node(value)25        if self.head is None:26            self.head = self.tail = node27            return28        node.next = self.head29        self.head.prev = node30        self.head = node31
32    def forward(self):33        values, current = [], self.head34        while current:35            values.append(current.value)36            current = current.next37        return values38
39    def backward(self):40        values, current = [], self.tail41        while current:42            values.append(current.value)43            current = current.prev44        return values45
46
47lst = DoublyLinkedList()48for value in [2, 3, 4]:49    lst.append(value)50lst.prepend(1)51
52print("Forward: ", lst.forward())53print("Backward:", lst.backward())
Bu kodu Python Playground'da çalıştır

JavaScript ile Doubly Linked List koduJavaScript
1class Node {2    constructor(value) {3        this.value = value;4        this.prev = null;5        this.next = null;6    }7}8
9class DoublyLinkedList {10    constructor() {11        this.head = null;12        this.tail = null;13    }14
15    // Tail pointer makes append O(1)16    append(value) {17        const node = new Node(value);18        if (!this.tail) {19            this.head = node;20            this.tail = node;21            return;22        }23        node.prev = this.tail;24        this.tail.next = node;25        this.tail = node;26    }27
28    forward() {29        const out = [];30        for (let n = this.head; n; n = n.next) out.push(n.value);31        return out;32    }33
34    backward() {35        const out = [];36        for (let n = this.tail; n; n = n.prev) out.push(n.value);37        return out;38    }39}40
41const list = new DoublyLinkedList();42for (const value of [10, 20, 30, 40]) list.append(value);43console.log("Forward: ", list.forward().join(" <-> "));44console.log("Backward:", list.backward().join(" <-> "));
Bu kodu JavaScript Playground'da çalıştır

Java ile Doubly Linked List koduJava
1public class Main {2    static class Node {3        int value;4        Node prev, next;5        Node(int value) { this.value = value; }6    }7
  static Node head, tail;9
  static void append(int value) {11        Node node = new Node(value);12        if (head == null) { head = tail = node; return; }13        node.prev = tail;14        tail.next = node;15        tail = node;16    }17
  // Unlink in O(1) once found: fix both neighbor pointers19    static void delete(int value) {20        for (Node cur = head; cur != null; cur = cur.next) {21            if (cur.value != value) continue;22            if (cur.prev != null) cur.prev.next = cur.next; else head = cur.next;23            if (cur.next != null) cur.next.prev = cur.prev; else tail = cur.prev;24            return;25        }26    }27
  public static void main(String[] args) {29        append(1);30        append(2);31        append(3);32        append(4);33
      StringBuilder forward = new StringBuilder("Forward:");35        for (Node cur = head; cur != null; cur = cur.next) forward.append(" ").append(cur.value);36        System.out.println(forward);37
      StringBuilder backward = new StringBuilder("Backward:");39        for (Node cur = tail; cur != null; cur = cur.prev) backward.append(" ").append(cur.value);40        System.out.println(backward);41
      delete(3);43        StringBuilder after = new StringBuilder("After delete 3:");44        for (Node cur = head; cur != null; cur = cur.next) after.append(" ").append(cur.value);45        System.out.println(after);46    }47}
Bu kodu Java Playground'da çalıştır

C++ ile Doubly Linked List koduC++
1#include <iostream>2
3struct Node {4    int value;5    Node* prev = nullptr;6    Node* next = nullptr;7    explicit Node(int v) : value(v) {}8};9
10struct DoublyLinkedList {11    Node* head = nullptr;12    Node* tail = nullptr;13
14    void append(int value) {15        Node* node = new Node(value);16        if (tail == nullptr) {17            head = tail = node;18            return;19        }20        node->prev = tail;  // link both directions21        tail->next = node;22        tail = node;23    }24
25    void prepend(int value) {26        Node* node = new Node(value);27        if (head == nullptr) {28            head = tail = node;29            return;30        }31        node->next = head;32        head->prev = node;33        head = node;34    }35
36    void printForward() const {37        for (Node* cur = head; cur != nullptr; cur = cur->next) {38            std::cout << cur->value << " <-> ";39        }40        std::cout << "null\n";41    }42
43    void printBackward() const {44        for (Node* cur = tail; cur != nullptr; cur = cur->prev) {45            std::cout << cur->value << " <-> ";46        }47        std::cout << "null\n";48    }49};50
51int main() {52    DoublyLinkedList list;53    for (int value : {10, 20, 30}) list.append(value);54    list.prepend(5);55    std::cout << "Forward:  ";56    list.printForward();57    std::cout << "Backward: ";58    list.printBackward();59    return 0;60}
Bu kodu C++ Playground'da çalıştır

C ile Doubly Linked List koduC
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5    int value;6    struct Node* prev;7    struct Node* next;8} Node;9
10Node* head = NULL;11Node* tail = NULL;12
13Node* newNode(int value) {14    Node* n = calloc(1, sizeof(Node));15    n->value = value;16    return n;17}18
19void append(int value) {20    Node* node = newNode(value);21    if (tail == NULL) {22        head = tail = node;23        return;24    }25    node->prev = tail;  // link both directions26    tail->next = node;27    tail = node;28}29
30void prepend(int value) {31    Node* node = newNode(value);32    if (head == NULL) {33        head = tail = node;34        return;35    }36    node->next = head;37    head->prev = node;38    head = node;39}40
41void printForward(void) {42    for (Node* cur = head; cur != NULL; cur = cur->next) {43        printf("%d <-> ", cur->value);44    }45    printf("NULL\n");46}47
48void printBackward(void) {49    for (Node* cur = tail; cur != NULL; cur = cur->prev) {50        printf("%d <-> ", cur->value);51    }52    printf("NULL\n");53}54
55int main(void) {56    int values[] = {10, 20, 30};57    for (int i = 0; i < 3; i++) append(values[i]);58    prepend(5);59    printf("Forward:  ");60    printForward();61    printf("Backward: ");62    printBackward();63    return 0;64}
Bu kodu C Playground'da çalıştır

Çift Yönlü Bağlı Liste SSS

Tek yönlü ve çift yönlü bağlı liste arasındaki fark nedir?

Tek yönlü bağlı listede düğüm başına bir işaretçi vardır (next), bu yüzden yalnızca ileri gidebilirsiniz. Çift yönlü bağlı liste bir prev işaretçisi ekler; bu, geriye gezinmeyi ve referansını tuttuğunuz bir düğümü O(1) sürede silmeyi sağlar; bunun bedeli düğüm başına ek bir işaretçi ve her değişiklikte iki bağlantıyı güncellemektir.

Çift yönlü bağlı liste ek belleğe ne zaman değer?

Geriye gezinmeye ya da zaten referans verdiğiniz rastgele düğümlerin O(1) silinmesine ihtiyaç duyduğunuzda; klasik örnekler, girdilerin her iki uçtan sık sık taşındığı ve atıldığı deque'ler (çift uçlu kuyruklar) ve LRU önbellekleridir.

Çift yönlü bağlı liste neden bir düğümü O(1) sürede silebilir?

Bir düğümü kaldırmak için öncülünü ardılına bağlamanız gerekir. Tek yönlü bağlı listede öncülü bulmak için baştan yürümeniz gerekir (O(n)); çift yönlü bağlı listede düğümün prev işaretçisi öncülü doğrudan verir, bu yüzden yeniden bağlama O(1) olur.

Çift yönlü bağlı liste ve dizi: hangisini kullanmalıyım?

İndeksle O(1) erişime ve önbellek dostu yinelemeye ihtiyaç duyduğunuzda ve eklemeler çoğunlukla sonda olduğunda dizi kullanın. Bir düğüm referansıyla ortada veya her iki uçta sık sık ekleyip çıkarıyorsanız çift yönlü bağlı liste kullanın; çünkü bu, dizinin O(n) kaydırmasına karşı O(1)'dir. Diziler bellek ve yerellikte kazanır; liste yapısal düzenlemelerde kazanır.

Çift yönlü bağlı listede nöbetçi (sentinel) düğüm nedir?

Nöbetçi (veya kukla) düğüm, listenin hiçbir zaman gerçekten boş olmaması için başın önünde ve/veya sonun ardında duran bir yer tutucudur. head, tail ve sınır ekleme/silmeleri için null kontrollerini ortadan kaldırarak her işlemin aynı yeniden bağlama kod yolunu izlemesini sağlar. Birçok üretim LRU önbellek uygulaması, uçları özel durum olarak ele almamak için iki nöbetçi kullanır.

Çift yönlü bağlı listeden silerken en yaygın hata nedir?

İlk veya son düğümü silerken head ya da tail'i güncellemeyi unutmak; bu, serbest bırakılmış bir düğüme sarkan bir işaretçi bırakır. Komşuları yeniden bağlamadan önce node.prev'in null olup olmadığını (head'i güncelle) veya node.next'in null olup olmadığını (tail'i güncelle) her zaman kontrol edin.

İlgili kaynaklar

Daha fazla görselleştirme

Coddy programming languages illustration

Coddy ile algoritmalarda ustalaş

BAŞLA