Veri Yapıları ve Programlama

5 - Bağlı Listeler (Linked Lists)

Emre Can Yılmaz

Ondokuz Mayıs Üniversitesi

2025

Bağlı Listeler

Her bir düğümün (node) bir veri parçası ve bir sonraki düğümün adresini içerdiği bir dizi düğümden oluşan veri yapısına “Bağlı Liste” denir.

Bağlı Listeler

Bağlı listeler en basit ve en çok kullanılan veri yapılarındandır.
Diziler bellekte ardışık bir şekilde dururken, bağlı listeler sayesinde bellekte rastgele konumlardaki verileri birbirine bu şekilde bağlayabilirsiniz.
Yığın, kuyruk gibi diğer soyut veri yapılarını gerçeklemek için sıklıkla kullanılır.

Bağlı Listeler

Bağlı listelerde listenin başlangıcını ifade eden bir Head (head pointer), bir de liste sonunu ifade eden Tail (tail pointer) bulunur. Son düğümün göstereceği bir düğüm olmadığında ‘NULL’ değerini işaret eder.

Avantajları

Bağlı liste bir dinamik veri yapısıdır ve programın çalışması sırasında büyüyüp küçülebilir.
Ekleme ve çıkarma işlemleri, dizilerin aksine kaydırma işlemi gerektirmeden kolayca yapılabilir.
Yığın ve kuyruk gibi veri yapıları bağlı liste kullanılarak gerçeklenebilir.
Bağlı liste oluşturulurken bir başlangıç boyutu belirtilmesine gerek yoktur.
Listenin ortasına veri eklenebilir ya da ortasından veri kaldırılabilir.

Dezavantajları

Bağlı listelerin düğümlerine direk erişim yoktur. Bağlı listelerin düğümlerine ancak sıralı erişim yapılabilir.
Bağlı listelerin düğümleri ana bellekte ardışık olarak yerleşmez. Liste içindeki bir düğüme erişmek için baştan sona ya da sondan başa doğru bütün düğümleri ziyaret etmek gerekir (sıralı erişim).
Bellek Kullanımı: Her düğüm, veriyle birlikte bir de işaretçi (pointer) içerdiği için, dizilere kıyasla daha fazla bellek kullanabilir. (Özellikle çok sayıda küçük veri öğesi saklanıyorsa bu dezavantaj daha belirgin olur.)
Tersine Tarama Zorluğu: Tek yönlü bağlı listelerde, listede geriye doğru gitmek (örneğin, bir önceki elemana erişmek) verimli bir işlem değildir. (Çift yönlü bağlı listeler bu sorunu çözer, ancak daha fazla bellek kullanırlar.)

C Dilinde Gerçekleme

Bağlı listenin her bir düğümünün nasıl temsil edildiğini görelim. Her düğüm şunlardan oluşur:

Bir veri öğesi
Başka bir düğümün adresi

Düğüm (Node) Temsili

Hem veri öğesini hem de bir sonraki düğüm referansını şu şekilde bir struct içine yazıyoruz:

struct node {
  int data;
  struct node *next;
};

Bir bağlı liste düğümünün yapısını anlamak, onu kavramanın anahtarıdır.

Bağlı Liste Türleri

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

Tek Yönlü Bağlı Liste

Her düğümün yalnızca listedeki bir sonraki düğüme referansı vardır.

Düğüm şu şekilde temsil edilir:

struct node {
    int data;
    struct node *next;
}

Üç üyeli tek yönlü bağlı liste şu şekilde oluşturulabilir:

/* Initialize nodes */
struct node *head = NULL; //Başlangıçta boş
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Assign data values */
one->data = 1;
two->data = 2;
three->data = 3;

/* Connect nodes */
one->next = two;
two->next = three;
three->next = NULL;

/* Save address of first node in head */
head = one;

Çift Yönlü Bağlı Liste

Her düğümün listedeki hem önceki hem de sonraki düğümlere referansı vardır. Dolayısıyla, her iki yönde de ilerleyebiliriz: ileri ya da geri.

Örnek

Bir düğüm şu şekilde gösterilir:

struct node {
    int data;
    struct node *next;
    struct node *prev;
}

Üç üyeli çift bağlı liste şu şekilde oluşturulabilir:

/* Initialize nodes */
struct node *head = NULL; // Başlangıçta boş
struct node *tail = NULL; // Listenin sonunu takip etmek için
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Assign data values */
one->data = 1;
two->data = 2;
three->data = 3;

/* Connect nodes */
one->next = two;
one->prev = NULL;

two->next = three;
two->prev = one;

three->next = NULL;
three->prev = two;

/* Save address of first and last node */
head = one;
tail = three; // Listenin sonu 'three'

Yukarıdaki kodda, one, two ve three sırasıyla 1, 2 ve 3 veri öğelerine sahip düğümlerdir.

Birinci düğüm için: next, ikinin adresini saklar ve prev null’u saklar (ondan önce düğüm yoktur)

İkinci düğüm için: next üçün adresini, prev ise birin adresini saklar.

Üçüncü düğüm için: next null’u (ondan sonra düğüm yoktur) ve prev ikinin adresini saklar.

Not: Baş(HEAD) düğüm durumunda prev null’a işaret eder ve kuyruk(TAIL) işaretçisi durumunda next null’a işaret eder. Burada, one baş düğüm ve three kuyruk düğümüdür.

Dairesel Bağlı Liste

Dairesel bağlı liste, son elemanın ilk elemanı işaret ettiği bir bağlı liste çeşididir. Bu dairesel bir döngü oluşturur.

Dairesel bağlı liste tek bağlı ya da çift bağlı olabilir.

Tek bağlı liste için, son öğenin sonraki işaretçisi ilk öğeyi gösterir.
Çift bağlı listede, ilk öğenin prev işaretçisi son öğeyi de işaret eder.

Örnek

Bir düğüm şu şekilde gösterilir:

struct Node {
    int data;
    struct Node * next;
};

Üç üyeli dairesel tek bağlı liste şu şekilde oluşturulabilir:

/* Initialize nodes */
struct node *head = NULL; // Başlangıçta boş liste
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Assign data values */
one->data = 1;
two->data = 2;
three->data = 3;

/* Connect nodes */
one->next = two;
two->next = three;
three->next = one; // Dairesel bağlantı

/* Save address of first node in head */
head = one; // 'head', listenin başını gösteriyor

Üç üyeli dairesel çift bağlı liste şu şekilde oluşturulabilir:

 /* Initialize nodes */
 struct node *head = NULL;
 struct node *tail = NULL;
 struct node *one   = NULL;
 struct node *two   = NULL;
 struct node *three = NULL;

 /* Allocate memory */
 one   = malloc(sizeof(struct node));
 two   = malloc(sizeof(struct node));
 three = malloc(sizeof(struct node));

 /* Assign data values */
 one->data   = 1;
 two->data   = 2;
 three->data = 3;

 /* Connect nodes */
 one->next   = two;
 one->prev   = three; //ilk elemanın prev'i son elemanı gösteriyor.

 two->next   = three;
 two->prev   = one;

 three->next = one; // son elemanın next'i ilk elemanı gösteriyor
 three->prev = two;

 /* Save address of first node in head */
 head = one;
 tail = three;

Yukarıdaki kodda, one, two ve three sırasıyla 1, 2 ve 3 veri öğelerine sahip düğümlerdir.

Birinci düğüm için next, twodüğümünün adresini saklar

İkinci düğüm için next, three düğümünün adresini saklar.

Üçüncü düğüm için next, one düğümünü işaret eder. Bu sayede dairesellik elde edilmiş olur.

Bağlı Liste İşlemleri

Bağlı listeler üzerinde farklı eylemler gerçekleştirmemize olanak tanıyan çeşitli bağlı liste işlemleri vardır.

Geçiş(Traversal): Bağlı listenin her bir öğesine erişim
Ekleme(Insertion): Bağlı listeye yeni bir eleman ekler
Silme(Deletion): Mevcut öğeleri kaldırır.
Arama(Search): Bağlı listede bir düğüm bulma

Gerçek Hayat Uygulamaları

Müzik Çalarlar: Sonraki/önceki şarkıya geçme (bağlı liste veya çift yönlü bağlı liste).
Web Tarayıcıları: Geri/ileri butonları (çift yönlü bağlı liste).
İşletim Sistemleri: Proses yönetimi (proseslerin listesi).
Undo/Redo İşlevleri: Yapılan işlemlerin listesi (çift yönlü bağlı liste).
Metin Editörleri: Metin satırlarının birbirine bağlanması (çift yönlü bağlı liste).

ÖZET

Her bir düğümün (node) bir veri parçası ve bir sonraki düğümün adresini içerdiği bir dizi düğümden oluşan veri yapısına “Bağlı Liste” denir.
Bağlı listelerde listenin başlangıcını ifade eden bir Head (head pointer), bir de liste sonunu ifade eden Tail (tail pointer) bulunur. Son düğümün göstereceği bir düğüm olmadığında ‘NULL’ değerini işaret eder.
Veri yapısı şöyledir:

struct node {
  int data;
  struct node *next;
};

ÖZET

Bağlı Liste Türleri:

Tek Yönlü Bağlı Liste: Her düğümün yalnızca listedeki bir sonraki düğüme referansı vardır.
Çift Yönlü Bağlı Liste: Her düğümün listedeki hem önceki hem de sonraki düğümlere referansı vardır. Dolayısıyla, her iki yönde de ilerleyebiliriz: ileri ya da geri.
Dairesel Bağlı Liste: Dairesel bağlı liste, son elemanın ilk elemanı işaret ettiği bir bağlı liste çeşididir. Bu dairesel bir döngü oluşturur.

Yukarıdaki türlerin görsel olarak nasıl göründüklerini hayal edebilmelisiniz!

Çalışma Soruları

Çift yönlü bağlı listelerde arama ve silme işlemleri nasıl yapılır?
Dairesel bağlı listelerin avantaj ve dezavantajları nelerdir?
Bağlı listeler ve diziler arasındaki temel farklar nelerdir? Hangi durumlarda hangisi tercih edilmelidir?
Bir bağlı listede döngü (cycle) olup olmadığını nasıl kontrol edersiniz? (Floyd’s Cycle-Finding Algorithm - “Tavşan ve Kaplumbağa” algoritması)
Verilen iki sıralı bağlı listeyi birleştiren (merge) bir fonksiyon yazın.