Bağlı Listeler Veri Yapısı Açıklaması

Bağlı Liste, öğelerin düğümler olarak depolandığı doğrusal bir veri yapısıdır. Her düğüm veri ve başka bir düğüme referans içerir. Dizilerin aksine, bağlı listeler öğelerin bellekte yan yana depolanmasını gerektirmez.

Bağlı Listeler, Dinamik Veri Yapıları ve Algoritmalar derslerinde önemlidir çünkü dinamik veri yapılarının nasıl çalıştığını öğretirler. Bellek referanslarını, ekleme, silme, dolaşma işlemlerini ve yığınlar, kuyruklar, hash tabloları, graflar ve komşuluk listeleri gibi daha gelişmiş yapıların nasıl inşa edilebileceğini anlamak için faydalıdırlar.

Giriş

Programlamada, veriler genellikle koleksiyonlarda depolanır. Diziler en yaygın koleksiyonlardan biridir çünkü basittirler ve dizinle hızlı erişime izin verirler. Ancak, dizilerde özellikle koleksiyonun ortasında veya başında sık sık ekleme ve silme işlemleri gerektiğinde sınırlamalar bulunur.

Bağlı Liste farklı bir sorun türünü çözer. Tüm öğeleri sürekli bellek konumlarına yerleştirmek yerine, her öğeyi bir düğümün içine depolar. Her düğüm bir sonraki düğümün nerede olduğunu bilir.

Bu durum Bağlı Listeleri esnek yapar. Düğümler program çalışırken dinamik olarak oluşturulabilir ve birbirine bağlanabilir. Bağlı Listeleri anlamak, geliştiricilerin referansları, işaretçileri, bellek tahsisini ve birçok veri yapısının dahili tasarımını anlamalarına yardımcı olur.

Bağlı Liste Nedir?

Bağlı Liste, referanslar kullanılarak birbirine bağlanmış düğümler dizisidir. Her düğüm genellikle iki bölümden oluşur:

  • Veri: Düğümde saklanan gerçek değer.

  • Sonraki referans: Listedeki bir sonraki düğüme bir referans veya işaretçi.

Basit bir bağlı liste şu şekilde temsil edilebilir:

[10 | next] → [20 | next] → [30 | null]

İlk düğüm 10 içerir ve ikinci düğümü işaret eder. İkinci düğüm 20 içerir ve üçüncü düğümü işaret eder. Üçüncü düğüm 30 içerir ve listeyi bitiren null değerini işaret eder.

İlk düğüme genellikle bağlı listenin başı (head) denir.

Bağlı Liste Terminolojisi

Bağlı Liste operasyonlarını incelemeden önce, ortak terimleri anlamak önemlidir.

  • Düğüm (Node): Bağlı listedeki tek bir öğe.

  • Baş (Head): Bağlı listedeki ilk düğüm.

  • Kuyruk (Tail): Bağlı listedeki son düğüm.

  • Sonraki (Next): Bir düğümden sonraki düğüme referans.

  • Önceki (Previous): Önceki düğüme referans, çift yönlü bağlı listelerde kullanılır.

  • Null: Sonraki düğümün olmadığını belirten bir değer.

Bu terimler hemen hemen her bağlı liste uygulamasında karşımıza çıkar.

Bağlı Listeler Neden VYA'da Önemlidir?

Bağlı Listeler önemlidir çünkü verileri dizinlere dayanmak yerine referanslar kullanarak bağlama fikrini tanıtırlar. Bu, Veri Yapıları ve Algoritmaları öğrenmede önemli bir adımdır.

Bağlı Listeler geliştiricilerin şunları anlamasına yardımcı olur:

  • Dinamik bellek tahsisi.

  • Referanslar ve işaretçiler.

  • Düğüm tabanlı veri yapıları.

  • Verimli ekleme ve silme.

  • Dolaşım mantığı.

  • Yığınların ve kuyrukların nasıl uygulanabileceği.

  • Graf komşuluk listelerinin nasıl çalıştığı.

Geliştiriciler bağlı listeleri her gün manuel olarak uygulamasa bile, arkalarındaki kavramlar birçok gerçek sistemde karşımıza çıkar.

Bağlı Listeler ve Diziler

Diziler ve Bağlı Listeler her ikisi de doğrusal veri yapılarıdır, ancak verileri farklı şekillerde saklar ve yönetirler.

Bir dizi, öğeleri bitişik bellek konumlarında saklar. Bu, öğelerin bellekte yan yana yerleştirildiği ve her öğeye bir dizin kullanılarak hızlı bir şekilde erişilebileceği anlamına gelir.

Array:
Index:  0   1   2
Value: 10  20  30

Bağlı Liste, öğeleri ayrı düğümler olarak depolar. Her düğüm bir sonraki düğümü işaret eder.

Linked List:
[10] → [20] → [30] → null

Temel farklar şunlardır:

  • Diziler, dizinler kullanarak hızlı rastgele erişim sağlar.

  • Bağlı Listeler belirli bir konuma ulaşmak için dolaşım (traversal) gerektirir.

  • Diziler, ekleme veya silme sırasında öğeleri kaydırmayı gerektirebilir.

  • Bağlı Listeler, konumu bilindiğinde düğümleri verimli bir şekilde ekleyebilir veya silebilir.

  • Diziler sürekli bellek kullanır.

  • Bağlı Listeler, farklı bellek konumlarında saklanabilen düğümler kullanır.

Her iki yapı da her zaman daha iyi değildir. En iyi seçim probleme bağlıdır.

VYA Bağlı Listeleri Bellekte

Bağlı Listelerin arkasındaki en önemli fikirlerden biri, bellekte nasıl depolandıklarıdır.

Bir dizide, öğeler yan yana depolanır:

Memory:
Address 1000 → 10
Address 1004 → 20
Address 1008 → 30
Address 1012 → 40

Öğeler bitişik olduğu için, program temel adresi ve dizini kullanarak herhangi bir öğenin adresini hesaplayabilir.

Bağlı Listede, düğümlerin yan yana depolanması gerekmez:

Memory:
Address 2040 → [10 | next: 9000]
Address 9000 → [20 | next: 3050]
Address 3050 → [30 | next: null]

Düğümler belleğin herhangi bir yerinde bulunabilir. Her düğüm bir sonraki düğüme bir referans depolar, böylece liste bir düğümden diğerine takip edilebilir.

Bellek Gösterimi Neden Önemli?

Bellek gösterimi önemlidir çünkü Bağlı Listelerin güçlü ve zayıf yönlerini açıklar.

Düğümler referanslarla birbirine bağlandığı için, yeni bir düğüm eklemek bir dizi gibi tüm öğeleri kaydırmayı gerektirmez. Program sadece referansları değiştirir.

Örneğin, 10 ile 20 arasına 15 eklemek için:

Before:
[10] → [20] → [30]

After:
[10] → [15] → [20] → [30]

Yeni düğüm belleğin herhangi bir yerinde oluşturulabilir. 10'dan gelen referans 15'i işaret edecek şekilde değiştirilir ve 15 de 20'yi işaret eder.

Ancak, bu aynı zamanda Bağlı Listelerin doğrudan dizin erişimini verimli bir şekilde desteklemediği anlamına gelir. Üçüncü düğüme ulaşmak için, program baştan başlamalı ve bağlantıları adım adım takip etmelidir.

Düğümün Yapısı

Bir düğüm, Bağlı Listenin temel yapı taşıdır. Tek yönlü bağlı listede, bir düğüm veri ve bir sonraki referans içerir.

Node:
+------+------+
| data | next |
+------+------+

Örneğin:

+------+------+
|  10  |  →   |
+------+------+

Kodda, bir düğüm bir nesne veya sınıf olarak temsil edilebilir.

PHP'de Düğüm Örneği

<?php

class Node
{
    public mixed $data;
    public ?Node $next = null;

    public function __construct(mixed $data)
    {
        $this->data = $data;
    }
}

Bu PHP sınıfı basit bir düğümü temsil eder. data özelliği değeri, ve next özelliği bir sonraki düğüme referansı depolar.

JavaScript'te Düğüm Örneği

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

JavaScript sürümü aynı yapıyı takip eder. Her düğüm veri ve bir sonraki düğüme referans depolar.

Bağlı Liste Türleri

Çeşitli Bağlı Liste türleri vardır. Her tür, düğümlerin nasıl bağlandığını ve hangi işlemlerin daha kolay yapılabileceğini değiştirir.

Ana türler şunlardır:

  • Tek Yönlü Bağlı Liste.

  • Çift Yönlü Bağlı Liste.

  • Dairesel Bağlı Liste.

  • Dairesel Çift Yönlü Bağlı Liste.

Bu türleri anlamak, geliştiricilerin farklı problemler için doğru yapıyı seçmelerine yardımcı olur.

Tek Yönlü Bağlı Liste

Tek Yönlü Bağlı Liste, en basit bağlı liste türüdür. Her düğüm veri ve bir sonraki düğüme referans içerir.

[10] → [20] → [30] → null

Dolaşım sadece tek yönde mümkündür: baştan kuyruğa.

Tek Yönlü Bağlı Liste şunlar için faydalıdır:

  • İleri yönde dolaşım yeterlidir.

  • Bellek kullanımı çift yönlü bağlı listeden daha az olmalıdır.

  • Ekleme ve silme işlemleri genellikle başta yapılır.

  • Basit bir düğüm tabanlı yapıya ihtiyaç vardır.

Sınırlama şudur: geriye doğru hareket mümkün değildir çünkü düğümler önceki düğümlere referans depolamaz.

Çift Yönlü Bağlı Liste

Çift Yönlü Bağlı Liste, her düğümde iki referans depolar: biri sonraki düğüme, diğeri önceki düğüme.

null ← [10] ⇄ [20] ⇄ [30] → null

Bu, her iki yönde de dolaşım yapılmasına izin verir.

Çift yönlü bağlı listedeki bir düğüm genellikle şunları içerir:

  • Veri.

  • Sonraki referans.

  • Önceki referans.

Çift Yönlü Bağlı Listeler şunlar için faydalıdır:

  • İleri ve geri yönde dolaşım gerektiğinde.

  • Bilinen bir düğümü silme verimli olmalıdır.

  • Navigasyon benzeri davranışa ihtiyaç duyulduğunda.

  • Geri alma (undo) ve yineleme (redo) sistemleri uygulandığında.

Dezavantajı, her düğümün önceki referans için ekstra bellek gerektirmesidir.

Dairesel Bağlı Liste

Dairesel Bağlı Liste, son düğümün null'ı işaret etmek yerine ilk düğümü işaret ettiği bir bağlı listedir.

[10] → [20] → [30]
 ↑              ↓
 └──────────────┘

Bu bir döngü oluşturur.

Dairesel Bağlı Listeler şunlar için faydalıdır:

  • Sürecin öğeler arasında sürekli olarak dönmesi gerektiğinde.

  • Round-robin zamanlaması gerektiğinde.

  • Dairesel bir çalma listesi veya sıra tabanlı bir sistem gerektiğinde.

  • Sonun doğal olarak başlangıca bağlanması gerektiğinde.

Önemli uyarı şudur: dolaşımın bir durdurma koşulu olmalıdır. Aksi takdirde, program sonsuz döngüye girebilir.

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

Dairesel Çift Yönlü Bağlı Liste her iki fikri birleştirir. Her düğümün sonraki ve önceki referansları vardır ve son düğüm ilk düğüme, ilk düğüm ise son düğüme geri bağlanır.

┌──────────────────────┐
↓                      ↑
[10] ⇄ [20] ⇄ [30]
↑                      ↓
└──────────────────────┘

Bu tür, ileri ve geri yönde dairesel dolaşımı destekler.

Dairesel tamponlar, gelişmiş çalma listeleri ve bazı düşük seviyeli veri yapıları gibi sürekli navigasyonun gerektiği sistemlerde faydalıdır.

Dezavantajı, daha yüksek uygulama karmaşıklığı ve düğüm başına ekstra bellektir.

Bağlı Liste İşlemleri

Bağlı Listeler birkaç önemli işlemi destekler. En yaygın işlemler şunlardır:

  • Dolaşım.

  • Başa Ekleme.

  • Sona Ekleme.

  • Belirli Bir Konuma Ekleme.

  • Baştan Silme.

  • Sondan Silme.

  • Değere Göre Silme.

  • Arama.

  • Güncelleme.

  • Ters Çevirme.

Her işlem, referansları doğru bir şekilde değiştirmeye bağlıdır.

Dolaşım İşlemi

Dolaşım, bağlı listedeki her düğümü baştan sona ziyaret etmek anlamına gelir.

Örneğin:

[10] → [20] → [30] → null

Dolaşım sırası şöyledir:

10
20
30

Dolaşım, baş düğümden başlar ve null'a ulaşılana kadar sonraki referansları takip eder.

Dolaşım Sözde Kodu

current = head

while current is not null:
    print current.data
    current = current.next

Geçerli işaretçi her seferinde bir düğüm ilerler.

Başa Ekleme

Başa ekleme, mevcut baş düğümden önce yeni bir düğüm eklemek anlamına gelir.

Liste şöyle olsun:

[20] → [30] → null

Başa 10 eklemek istiyoruz.

Adımlar şunlardır:

  1. 10 değeriyle yeni bir düğüm oluşturun.

  2. Yeni düğümü mevcut başı işaret edecek şekilde ayarlayın.

  3. Başı (head) yeni düğüme güncelleyin.

Sonuç şöyledir:

[10] → [20] → [30] → null

Bu işlem verimlidir çünkü listeyi dolaşmayı gerektirmez.

Sona Ekleme

Sona ekleme, son düğümden sonra yeni bir düğüm eklemek anlamına gelir.

Liste şöyle olsun:

[10] → [20] → null

Sona 30 eklemek istiyoruz.

Adımlar şunlardır:

  1. 30 değeriyle yeni bir düğüm oluşturun.

  2. Baştan başlayın.

  3. Son düğüme ulaşana kadar ilerleyin.

  4. Son düğümün yeni düğümü işaret etmesini sağlayın.

Sonuç şöyledir:

[10] → [20] → [30] → null

Liste bir kuyruk (tail) referansı tutuyorsa, sona ekleme O(1) olabilir. Kuyruk referansı olmadan, dolaşım gerektiği için O(n) olur.

Belirli Bir Konuma Ekleme

Belirli bir konuma ekleme, mevcut düğümler arasına bir düğüm eklemek anlamına gelir.

Liste şöyle olsun:

[10] → [30] → null

10 ile 30 arasına 20 eklemek istiyoruz.

Adımlar şunlardır:

  1. 20 değeriyle yeni bir düğüm oluşturun.

  2. Yeni düğümün ekleneceği düğümü bulun.

  3. Yeni düğümün sonraki düğümü işaret etmesini sağlayın.

  4. Önceki düğümün yeni düğümü işaret etmesini sağlayın.

Sonuç şöyledir:

[10] → [20] → [30] → null

Referans güncellemelerinin sırası önemlidir. Referanslar yanlış değiştirilirse, listenin bir kısmı kaybolabilir.

Baştan Silme

Baştan silme, baş düğümü kaldırır.

Liste şöyle olsun:

[10] → [20] → [30] → null

10'u kaldırmak için, başı bir sonraki düğümü işaret edecek şekilde güncelleriz.

head = head.next

Sonuç şöyledir:

[20] → [30] → null

Bu işlem O(1)'dir çünkü dolaşım gerekmez.

Sondan Silme

Sondan silme, son düğümü kaldırır.

Liste şöyle olsun:

[10] → [20] → [30] → null

Tek yönlü bağlı listede 30'u silmek için, son düğümden önceki düğümü bulmamız gerekir.

30'dan önceki düğüm 20'dir. Onun sonraki referansını null olarak ayarlarız.

[10] → [20] → null

Bu işlem, tek yönlü bağlı listede O(n)'dir çünkü sondan bir önceki düğümü bulmak için dolaşım yapmalıyız.

Değere Göre Silme

Değere göre silme, belirli bir değeri içeren ilk düğümü kaldırmak anlamına gelir.

Liste şöyle olsun:

[10] → [20] → [30] → null

20'yi silmek istiyoruz.

Algoritma, 20 değerini içeren düğümü arar ve önceki düğümün kaydını tutar. Ardından önceki düğümün sonraki referansını değiştirir.

Before:
[10] → [20] → [30] → null

After:
[10] → [30] → null

Değer başta bulunursa, baş güncellenmelidir.

Arama İşlemi

Arama, bağlı listede bir değerin var olup olmadığını bulmak anlamına gelir.

Bağlı Listeler, diziler gibi doğrudan dizin erişimini desteklemediği için, arama dolaşım gerektirir.

[10] → [20] → [30] → null

30'u aramak için algoritma şunları kontrol eder:

10 → not found
20 → not found
30 → found

Arama işleminin zaman karmaşıklığı O(n)'dir çünkü en kötü durumda algoritmanın her düğümü kontrol etmesi gerekebilir.

Güncelleme İşlemi

Güncelleme, bir düğümün değerini değiştirmek anlamına gelir.

Örneğin:

[10] → [20] → [30] → null

20'yi 25'e güncellemek istersek, önce 20'yi ararız, sonra verisini değiştiririz.

[10] → [25] → [30] → null

Arama kısmı O(n) sürerken, düğüm bulunduğunda gerçek güncelleme O(1)'dir.

Ters Çevirme İşlemi

Bir bağlı listeyi ters çevirmek, tüm sonraki referansların yönünü değiştirmek anlamına gelir.

Ters çevirmeden önce:

[10] → [20] → [30] → null

Ters çevirdikten sonra:

[30] → [20] → [10] → null

Bu, referansların anlaşılmasını test ettiği için yaygın bir mülakat ve algoritma problemidir.

Tipik iteratif çözüm üç işaretçi kullanır:

  • previous (önceki): Önceki düğüm.

  • current (mevcut): Mevcut düğüm.

  • next (sonraki): Bağlantıyı değiştirmeden önce kaydedilen sonraki düğüm.

Bağlı Liste İşlemleri İçin Manuel Çalıştırma

Bu diziyi manuel olarak çalıştıralım:

insertFirst(20)
insertFirst(10)
insertLast(30)
search(20)
delete(20)
insertLast(40)

Boş bir liste ile başlayın:

head = null

insertFirst(20) işleminden sonra:

[20] → null

insertFirst(10) işleminden sonra:

[10] → [20] → null

insertLast(30) işleminden sonra:

[10] → [20] → [30] → null

Şimdi 20'yi arayın:

Check 10 → not found
Check 20 → found

Şimdi 20'yi silin:

[10] → [30] → null

Şimdi sona 40 ekleyin:

[10] → [30] → [40] → null

Bu manuel çalıştırma, bağlı liste işlemlerinin düğüm referanslarını değiştirmeye nasıl bağlı olduğunu gösterir.

PHP'de Tek Yönlü Bağlı Liste Uygulaması

İşte yaygın işlemleri içeren Tek Yönlü Bağlı Listenin temiz bir PHP uygulaması.

<?php

class ListNode
{
    public mixed $data;
    public ?ListNode $next = null;

    public function __construct(mixed $data)
    {
        $this->data = $data;
    }
}

class LinkedList
{
    private ?ListNode $head = null;

    public function insertFirst(mixed $data): void
    {
        $newNode = new ListNode($data);
        $newNode->next = $this->head;
        $this->head = $newNode;
    }

    public function insertLast(mixed $data): void
    {
        $newNode = new ListNode($data);

        if ($this->head === null) {
            $this->head = $newNode;
            return;
        }

        $current = $this->head;

        while ($current->next !== null) {
            $current = $current->next;
        }

        $current->next = $newNode;
    }

    public function search(mixed $target): bool
    {
        $current = $this->head;

        while ($current !== null) {
            if ($current->data === $target) {
                return true;
            }

            $current = $current->next;
        }

        return false;
    }

    public function delete(mixed $target): bool
    {
        if ($this->head === null) {
            return false;
        }

        if ($this->head->data === $target) {
            $this->head = $this->head->next;
            return true;
        }

        $current = $this->head;

        while ($current->next !== null) {
            if ($current->next->data === $target) {
                $current->next = $current->next->next;
                return true;
            }

            $current = $current->next;
        }

        return false;
    }

    public function toArray(): array
    {
        $items = [];
        $current = $this->head;

        while ($current !== null) {
            $items[] = $current->data;
            $current = $current->next;
        }

        return $items;
    }
}

$list = new LinkedList();

$list->insertFirst(20);
$list->insertFirst(10);
$list->insertLast(30);

print_r($list->toArray());

var_dump($list->search(20));

$list->delete(20);

print_r($list->toArray());

Bu uygulama, başa ekleme, sona ekleme, arama, silme ve görüntüleme için bir diziye dönüştürme işlemlerini içerir.

JavaScript'te Tek Yönlü Bağlı Liste Uygulaması

İşte Tek Yönlü Bağlı Listenin bir JavaScript uygulaması.

class ListNode {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
    }

    insertFirst(data) {
        const newNode = new ListNode(data);
        newNode.next = this.head;
        this.head = newNode;
    }

    insertLast(data) {
        const newNode = new ListNode(data);

        if (this.head === null) {
            this.head = newNode;
            return;
        }

        let current = this.head;

        while (current.next !== null) {
            current = current.next;
        }

        current.next = newNode;
    }

    search(target) {
        let current = this.head;

        while (current !== null) {
            if (current.data === target) {
                return true;
            }

            current = current.next;
        }

        return false;
    }

    delete(target) {
        if (this.head === null) {
            return false;
        }

        if (this.head.data === target) {
            this.head = this.head.next;
            return true;
        }

        let current = this.head;

        while (current.next !== null) {
            if (current.next.data === target) {
                current.next = current.next.next;
                return true;
            }

            current = current.next;
        }

        return false;
    }

    toArray() {
        const items = [];
        let current = this.head;

        while (current !== null) {
            items.push(current.data);
            current = current.next;
        }

        return items;
    }
}

const list = new LinkedList();

list.insertFirst(20);
list.insertFirst(10);
list.insertLast(30);

console.log(list.toArray());
console.log(list.search(20));

list.delete(20);

console.log(list.toArray());

JavaScript sürümü, PHP sürümüyle aynı mantığı takip eder. Bağlı liste düğümlerden oluşur ve her düğüm bir sonraki düğümü işaret eder.

JavaScript'te Bağlı Listeyi Ters Çevirme

Bir bağlı listeyi ters çevirmek, en önemli bağlı liste problemlerinden biridir.

reverse() {
    let previous = null;
    let current = this.head;

    while (current !== null) {
        const nextNode = current.next;
        current.next = previous;
        previous = current;
        current = nextNode;
    }

    this.head = previous;
}

Fikir, her bir bağlantıyı tek tek ters çevirmektir. current.next değiştirmeden önce, listenin geri kalanının kaybolmaması için sonraki düğümü kaydederiz.

Bağlı Liste İşlemlerinin Zaman Karmaşıklığı

Zaman karmaşıklığı, bir işlemin çalışma süresinin düğüm sayısı arttıkça nasıl arttığını açıklar.

Tek Yönlü Bağlı Liste için yaygın karmaşıklıklar şunlardır:

  • Dizinle erişim: O(n)

  • Arama: O(n)

  • Dolaşım: O(n)

  • Başa ekleme: O(1)

  • Baştan silme: O(1)

  • Kuyruk olmadan sona ekleme: O(n)

  • Kuyruk ile sona ekleme: O(1)

  • Sondan silme: O(n)

  • Önceki düğümden sonra bilinen düğümü silme: O(1)

Temel fikir şudur: Bağlı Listeler, bilinen konumlara yakın yerlerde ekleme veya silme yaparken güçlüdür, ancak rastgele erişim gerektiğinde zayıftır.

Bağlı Listelerin Alan Karmaşıklığı

Bir Bağlı Listenin alan karmaşıklığı O(n)'dir, burada n düğüm sayısıdır.

Her düğüm veri ve en az bir referans depolar. Bu, bağlı listelerin aynı sayıda değer için dizilerden genellikle daha fazla bellek kullandığı anlamına gelir, çünkü her düğümün referans ek yükü vardır.

Tek Yönlü Bağlı Liste için:

Node = data + next reference

Çift Yönlü Bağlı Liste için:

Node = previous reference + data + next reference

Çift Yönlü Bağlı Listeler daha fazla esneklik sağlar ancak daha fazla bellek gerektirir.

Bağlı Listelerin Avantajları

Bağlı Listelerin çeşitli avantajları vardır.

  • Dinamik olarak büyüyebilir ve küçülebilirler.

  • Başa ekleme O(1)'dir.

  • Baştan silme O(1)'dir.

  • Bitişik bellek gerektirmezler.

  • Yığın ve kuyrukları uygulamak için kullanışlıdırlar.

  • Referansları ve dinamik yapıları anlamaya yardımcı olurlar.

Bu avantajlar, verilerin sık sık değiştiği problemlerde Bağlı Listeleri kullanışlı kılar.

Bağlı Listelerin Dezavantajları

Bağlı Listelerin önemli dezavantajları da vardır.

  • Hızlı rastgele erişimi desteklemezler.

  • Arama O(n) sürer.

  • Bir öğeye dizinle erişim O(n) sürer.

  • Referanslar için ekstra bellek kullanırlar.

  • Dizilere göre doğru bir şekilde uygulamak daha zor olabilir.

  • Kötü referans yönetimi listeyi bozabilir.

Bu dezavantajlar nedeniyle, hızlı dizinleme gerektiğinde diziler genellikle daha iyidir.

Gerçek Yazılım Projelerinde Bağlı Listeler

Üst düzey web geliştirmede, geliştiriciler bağlı listeleri sık sık manuel olarak uygulamayabilir. Diller ve framework'ler genellikle yerleşik diziler, listeler, koleksiyonlar, kuyruklar ve haritalar sağlar.

Ancak, Bağlı Liste fikirleri birçok yerde karşımıza çıkar:

  • Yığınlar ve kuyruklar.

  • Geri alma (undo) ve yineleme (redo) sistemleri.

  • Tarayıcı geçmişi navigasyonu.

  • Müzik çalma listeleri.

  • Bellek yönetimi.

  • Graf komşuluk listeleri.

  • Bazı uygulamalarda hash tablosu çarpışma yönetimi.

  • İşletim sistemi zamanlaması.

Bağlı Listeleri anlamak, bu sistemlerin dahili olarak nasıl tasarlanabileceğini anlamayı kolaylaştırır.

Bağlı Listeleri Öğrenirken Yapılan Yaygın Hatalar

Bağlı Listeler dikkatli referans yönetimi gerektirdiğinden, yeni başlayanlar genellikle hata yaparlar.

Yaygın hatalar şunlardır:

  • Ekleme veya silme işleminden sonra başı güncellemeyi unutmak.

  • Referansları değiştirirken listenin geri kalanını kaybetmek.

  • Boş bir listeyi işlememek.

  • İlk düğümün silinmesini işlememek.

  • Dairesel bağlı listelerde sonsuz döngü oluşturmak.

  • Düğüm verisini düğüm referansıyla karıştırmak.

  • Bağlı liste öğelerine dizi dizinleri gibi erişmeye çalışmak.

En güvenli yaklaşım, kod yazmadan önce düğümleri ve referansları çizmektir.

Bağlı Listeleri Anlamak İçin Pratik Kontrol Listesi

Gelişmiş veri yapılarına geçmeden önce, geliştiriciler şu soruları yanıtlayabilmelidir:

  • Düğüm nedir?

  • Bağlı listenin başı nedir?

  • Bağlı liste düğümlerinin bellekte bitişik olması neden gerekmez?

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

  • Başa ekleme nasıl çalışır?

  • Değere göre silme nasıl çalışır?

  • Arama neden O(n)'dir?

  • Başa ekleme neden O(1)'dir?

  • Referanslar yanlış sırada güncellenirse ne olur?

  • Bir bağlı liste nasıl ters çevrilebilir?

Bu sorular netse, geliştirici Bağlı Listelerin gerçek mantığını anlamıştır.

Sonuç

Bağlı Liste, referanslarla birbirine bağlanan düğümlerden oluşan doğrusal bir veri yapısıdır. Her düğüm veri ve başka bir düğüme bağlantı depolar. Dizilerin aksine, bağlı listeler öğelerin bitişik bellek konumlarında depolanmasını gerektirmez.

Bağlı Listeler önemlidir çünkü dinamik bellek, referanslar, düğüm tabanlı düşünme, ekleme, silme, dolaşım ve birçok veri yapısının dahili davranışını öğretirler.

Ana türler Tek Yönlü Bağlı Listeler, Çift Yönlü Bağlı Listeler, Dairesel Bağlı Listeler ve Dairesel Çift Yönlü Bağlı Listelerdir. Her türün farklı güçlü yönleri ve dezavantajları vardır.

Bağlı Liste işlemleri dolaşım, ekleme, silme, arama, güncelleme ve ters çevirme işlemlerini içerir. Konum bilindiğinde ekleme ve silme işlemleri verimli olabilir, ancak arama ve rastgele erişim O(n) zaman gerektirir.

Veri Yapıları ve Algoritmaları öğrenen geliştiriciler için Bağlı Listeler temel bir konudur. Yığınları, kuyrukları, grafları, bellek referanslarını ve birçok gelişmiş algoritmik problemi anlamak için temel oluştururlar.