Ana içeriğe geç

Bağlı Liste (Linked List) Nedir

Bağlı Liste (Linked List), verilerin bellekte dinamik olarak depolanması için kullanılan bir veri yapısıdır. Veriler, birbirine bağlı düğümlerden oluşur ve her bir düğüm, veriyi ve bir sonraki düğümün adresini içerir.

Bağlı Listeler, sabit boyutlu dizilere göre daha esnek bir veri yapısıdır. Çünkü dizilerin boyutu önceden belirlenirken, Bağlı Listelerin boyutu çalışma zamanında dinamik olarak değiştirilebilir.

Bağlı Listeler, çeşitli veri yapıları ve algoritmalar için kullanılır. Örneğin, yığın (stack) ve kuyruk (queue) gibi diğer veri yapıları, Bağlı Listelerin bir uygulamasıdır.

Bağlı Listelerin dezavantajı, bellek yönetimi için daha fazla zaman ve kaynak gerektirmeleridir. Ayrıca, elemanlara doğrudan erişim sağlamak için dizilere kıyasla daha fazla işlem yapılması gerekebilir.

Tek Yönlü Bağlı Liste Oluşturma​

C dilinde tek yönlü bağlı liste oluşturmak için aşağıdaki adımları takip edebilirsiniz:

  1. İlk olarak, düğümleri temsil etmek için bir yapı (struct) tanımlayın. Bu yapı, iki alan içerecektir: veri (data) ve bir sonraki düğümün adresi (next).
struct Node {
   int data;
   struct Node* next;
};
  1. Ardından, başlangıç düğümünü temsil eden bir işaretçi (pointer) tanımlayın. Bu işaretçi, listenin ilk düğümünün adresini tutacaktır. Başlangıçta, listenin boş olduğu için bu işaretçi NULL değerine eşitlenir.
struct Node* head = NULL;
  1. Listenin başına düğüm eklemek için, önce yeni bir düğüm oluşturmanız gerekir. Bu düğümün veri alanı, eklenmek istenen veri ile doldurulur. Ardından, next alanı NULL değerine eşitlenir, çünkü yeni düğüm henüz hiçbir düğüme bağlanmamıştır.
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = veri;
new_node->next = NULL;

  1. Yeni düğüm, listenin başına eklenir. Bunun için, yeni düğümün next alanı, başlangıç düğümünün adresini tutan head işaretçisine eşitlenir. Son olarak, head işaretçisi, yeni düğümün adresine güncellenir.
new_node->next = head;
head = new_node;
  1. Listenin başından düğüm silmek için, öncelikle head işaretçisi güncellenir, böylece ikinci düğüm listenin başı olur. Ardından, silinecek düğüm bellekten serbest bırakılır.
struct Node* temp = head;
head = head->next;
free(temp);
  1. Listenin tüm elemanlarını yazdırmak için, başlangıç düğümünden başlayarak tüm düğümler dolaşılır ve her bir düğümün veri alanı yazdırılır.

struct Node* current = head;
while (current != NULL) {
   printf("%d ", current->data);
   current = current->next;
}

Bu adımları takip ederek, C dilinde tek yönlü bağlı liste oluşturabilir ve temel işlemleri gerçekleştirebilirsiniz.

Tek Yönlü Bağlı Listelerde Sona Eleman Ekleme​

  1. Yeni bir düğüm oluşturulur ve bu düğümün veri alanı eklenmek istenen eleman ile doldurulur. Ayrıca, yeni düğümün next alanı NULL değerine eşitlenir, çünkü yeni düğüm listenin sonuna eklenecektir.
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = eleman;
new_node->next = NULL;
  1. Listenin son düğümüne ulaşmak için, başlangıç düğümünden başlayarak tüm düğümler dolaşılır ve son düğümün next alanı NULL değeri ile karşılaşıldığında durulur.
struct Node* current = head;
while (current->next != NULL) {
   current = current->next;
}
  1. Son düğümün next alanı, yeni düğümün adresine güncellenir. Böylece yeni düğüm listenin sonuna eklenmiş olur.
current->next = new_node;

Tamamlanan kod aşağıdaki gibi olabilir:


struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = eleman;
new_node->next = NULL;

if (head == NULL) { // Eğer liste boş ise, yeni düğüm listenin başı olur
    head = new_node;
} else {
    struct Node* current = head;
    while (current->next != NULL) { // Son düğüme ulaşana kadar dolaşılır
        current = current->next;
    }
    current->next = new_node; // Son düğümün next alanı, yeni düğümün adresine güncellenir
}

Bu şekilde, C dilinde tek yönlü bağlı listelerde sona eleman ekleme işlemini gerçekleştirebilirsiniz.

Tek Yönlü Bağlı Listelerde Başa Eleman Ekleme (Add First)​

  1. Yeni bir düğüm oluşturulur ve bu düğümün veri alanı eklenmek istenen eleman ile doldurulur. Ayrıca, yeni düğümün next alanı, listenin mevcut baş düğümünün adresine eşitlenir, çünkü yeni düğüm listenin başına eklenecektir.

struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = eleman;
new_node->next = head;
  1. Listenin başına, yeni düğümün adresi atanır. Böylece yeni düğüm, listenin başına eklenmiş olur.
head = new_node;

Tamamlanan kod aşağıdaki gibi olabilir:

struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = eleman;
new_node->next = head;

head = new_node;

Bu şekilde, C dilinde tek yönlü bağlı listelerde başa eleman ekleme işlemini gerçekleştirebilirsiniz.

Tek Yönlü Bağlı Listelerde Araya Eleman Ekleme​

Tek yönlü bağlı listelerde araya eleman eklemek için şu adımları takip edebilirsiniz:

  1. Yeni eleman için bellekten yer ayırın (malloc veya calloc fonksiyonları ile)
  2. Yeni elemanın verilerini ve bağlantılarını ayarlayın. Yeni elemanın bir sonraki elemanı, ekleyeceğiniz elemanın bir sonraki elemanı olacak. Ekleyeceğiniz elemanın bir sonraki elemanı, yeni eleman olacak.
  3. Eklenecek elemanın önceki elemanını bulun. Bunu yapmak için, listenin başlangıcından başlayarak elemanları gezin ve ekleyeceğiniz elemandan önceki elemanı bulun.
  4. Eklenecek elemanın önceki elemanının bağlantısını yeni elemana bağlayın ve yeni elemanın bağlantısını önceki elemanın bir sonraki elemanına bağlayın.

Aşağıda C dilinde örnek bir kod verilmiştir. Bu kod, integer veri tipi için tek yönlü bir bağlı liste oluşturur ve belirli bir pozisyona yeni bir eleman ekler.

#include <stdio.h>
#include <stdlib.h>

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

void insert(struct Node** head_ref, int new_data, int position) {
   struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
   new_node->data = new_data;
   int i;
   struct Node* temp = *head_ref;
   if (position == 0) {
      new_node->next = *head_ref;
      *head_ref = new_node;
      return;
   }
   for (i = 0; i < position - 1 && temp != NULL; i++) {
      temp = temp->next;
   }
   if (temp == NULL) {
      printf("Invalid position\n");
      return;
   }
   new_node->next = temp->next;
   temp->next = new_node;
}

void printList(struct Node* node) {
   while (node != NULL) {
      printf("%d ", node->data);
      node = node->next;
   }
}

int main() {
   struct Node* head = NULL;
   insert(&head, 2, 0);
   insert(&head, 3, 1);
   insert(&head, 4, 2);
   insert(&head, 5, 1);
   printf("Linked list: ");
   printList(head);
   return 0;
}

Bu kod, 2, 3 ve 4 sayılarını ekleyerek başlangıçta 2-3-4 şeklinde bir liste oluşturur. Daha sonra, 5 sayısını 1. pozisyona ekleyerek 2-5-3-4 şeklinde bir liste elde ederiz.

Tek Yönlü Bağlı Listelerde Sondan Eleman Silme İşlemi​

Tek yönlü bağlı listelerde sondan eleman silmek için aşağıdaki adımları izleyebilirsiniz:

  1. Son elemanı bulmak için listenin başından başlayarak elemanları gezin ve son elemanı bulun.
  2. Son elemanın bir önceki elemanını bulun. Bunu yapmak için, listenin başından başlayarak elemanları gezin ve son elemandan önceki elemanı bulun.
  3. Son elemanın bir önceki elemanının bağlantısını NULL olarak ayarlayın. Bu, son elemanın listeden çıkarılmasını sağlayacaktır.
  4. Son elemanın bellekte ayrılmış yerini serbest bırakın (free fonksiyonu ile).

Aşağıda C programlama dilinde bir örnek kod verilmiştir. Bu kod, integer veri tipi için tek yönlü bir bağlı liste oluşturur ve sondan eleman silme işlemi yapar.

#include <stdio.h>
#include <stdlib.h>

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

void deleteLast(struct Node** head_ref) {
   struct Node* temp = *head_ref;
   if (*head_ref == NULL) {
      printf("List is empty\n");
      return;
   }
   if (temp->next == NULL) {
      *head_ref = NULL;
      free(temp);
      return;
   }
   while (temp->next->next != NULL) {
      temp = temp->next;
   }
   free(temp->next);
   temp->next = NULL;
}

void printList(struct Node* node) {
   while (node != NULL) {
      printf("%d ", node->data);
      node = node->next;
   }
}

int main() {
   struct Node* head = NULL;
   head = (struct Node*)malloc(sizeof(struct Node));
   head->data = 2;
   head->next = NULL;
   struct Node* second = (struct Node*)malloc(sizeof(struct Node));
   second->data = 3;
   second->next = NULL;
   head->next = second;
   struct Node* third = (struct Node*)malloc(sizeof(struct Node));
   third->data = 4;
   third->next = NULL;
   second->next = third;
   printf("Initial linked list: ");
   printList(head);
   printf("\n");
   deleteLast(&head);
   printf("Linked list after deleting last element: ");
   printList(head);
   printf("\n");
   return 0;
}

Bu kod, başlangıçta 2-3-4 şeklinde bir liste oluşturur. Daha sonra, sondan eleman silme işlemi yaparak son elemanı listeden çıkarırız. Sonuç olarak, 2-3 şeklinde bir liste elde ederiz.

Tek Yönlü Bağlı Listelerde Baştan Eleman Silme İşlemi​

Tek yönlü bağlı listelerde baştan eleman silmek için aşağıdaki adımları izleyebilirsiniz:

  1. Listenin başındaki elemanı bulun.
  2. Listenin başlangıcını, ikinci elemanla değiştirin. Bunu yapmak için, head değişkenine ikinci elemanın adresini atayın.
  3. Başlangıçta bulduğunuz ilk elemanın bellekte ayrılmış yerini serbest bırakın (free fonksiyonu ile).

Aşağıda C programlama dilinde bir örnek kod verilmiştir. Bu kod, integer veri tipi için tek yönlü bir bağlı liste oluşturur ve baştan eleman silme işlemi yapar.

#include <stdio.h>
#include <stdlib.h>

// Tek yönlü bağlı listenin düğüm yapısı
struct node {
    int data;
    struct node* next;
};

// Yeni düğüm oluşturma fonksiyonu
struct node* newNode(int data) {
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->data = data;
    temp->next = NULL;
    return temp;
}

// Listenin başındaki elemanı silme fonksiyonu
void deleteFirst(struct node** head) {
    if (*head == NULL) {
        printf("Liste bos!\n");
        return;
    }
    struct node* temp = *head;
    *head = temp->next;
    free(temp);
}

// Listenin tüm elemanlarını yazdırma fonksiyonu
void printList(struct node* head) {
    struct node* temp = head;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

// Test fonksiyonu
int main() {
    // Boş bir liste oluşturma
    struct node* head = NULL;

    // Düğümler ekleme
    head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);

    printf("Liste: ");
    printList(head);

    // Başındaki elemanı silme
    deleteFirst(&head);
    printf("Liste: ");
    printList(head);

    // Başındaki elemanı silme
    deleteFirst(&head);
    printf("Liste: ");
    printList(head);

    // Başındaki elemanı silme
    deleteFirst(&head);
    printf("Liste: ");
    printList(head);

    return 0;
}

Bu kodu çalıştırdığınızda, önce 1, 2 ve 3 elemanları içeren bir liste oluşturulur ve daha sonra listenin başındaki elemanlar silinir. Sonuç olarak, listenin elemanları sırayla yazdırılır. Başındaki elemanı silmek için "deleteFirst" fonksiyonu kullanılır. Bu fonksiyona, başlangıçta oluşturulan liste işaretçisinin adresi (head) gönderilir. Fonksiyon, listenin boş olup olmadığını kontrol eder ve ardından listenin başındaki düğümü siler ve liste işaretçisini günceller. Son olarak, listenin elemanlarını yazdırmak için "printList" fonksiyonu kullanılır.

Tek Yönlü Bağlı Listelerde Aradan Eleman Silme İşlemi (Pozisyona Göre)​

Aşağıdaki C kodu, tek yönlü bağlı listelerde belirli bir pozisyondaki elemanı silme işlemini gerçekleştirir:

#include <stdio.h>
#include <stdlib.h>

// Tek yönlü bağlı listenin düğüm yapısı
struct node {
    int data;
    struct node* next;
};

// Yeni düğüm oluşturma fonksiyonu
struct node* newNode(int data) {
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->data = data;
    temp->next = NULL;
    return temp;
}

// Listenin belirli bir pozisyonundaki elemanı silme fonksiyonu
void deleteAtPosition(struct node** head, int position) {
    if (*head == NULL) {
        printf("Liste bos!\n");
        return;
    }
    struct node* temp = *head;

    // İlk elemanı silme durumu
    if (position == 0) {
        *head = temp->next;
        free(temp);
        return;
    }

    // Silinecek elemanın öncesindeki düğümü bulma
    for (int i = 0; temp != NULL && i < position - 1; i++) {
        temp = temp->next;
    }

    // Eğer pozisyon sayısı listedeki eleman sayısından fazlaysa
    if (temp == NULL || temp->next == NULL) {
        printf("Pozisyon listedeki eleman sayisindan fazla!\n");
        return;
    }

    // Silinecek düğümü belirlenen pozisyondan çıkarma
    struct node* next = temp->next->next;
    free(temp->next);
    temp->next = next;
}

// Listenin tüm elemanlarını yazdırma fonksiyonu
void printList(struct node* head) {
    struct node* temp = head;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

// Test fonksiyonu
int main() {
    // Boş bir liste oluşturma
    struct node* head = NULL;

    // Düğümler ekleme
    head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);

    printf("Liste: ");
    printList(head);

    // 2. pozisyondaki elemanı silme
    deleteAtPosition(&head, 1);
    printf("Liste: ");
    printList(head);

    // 1. pozisyondaki elemanı silme
    deleteAtPosition(&head, 0);
    printf("Liste: ");
    printList(head);

    // 3. pozisyondaki elemanı silme
    deleteAtPosition(&head, 2);
    printf("Liste: ");
    printList(head);

    return 0;
}

Bu kodu çalıştırdığınızda, önce 1, 2 ve 3 elemanları içeren bir liste oluşturulur ve daha sonra listenin belirli bir pozisyonundaki elemanlar silinir. Sonuç olarak, listenin elemanları sırayla yazdırılır. Belirli bir pozisyondaki elemanı silmek için "deleteAtPosition" fonksiyonu kullanılır.

Tek Yönlü Bağlı Listelerde Aradan Eleman Silme (Elemana Göre)​

Tabii, aşağıda tek yönlü bağlı listelerde bir elemanı belirli bir anahtara göre silen bir C kodu örneği verilmiştir:


#include <stdio.h>
#include <stdlib.h>

// Tek yönlü bağlı listenin düğüm yapısı
struct Node {
    int data;
    struct Node* next;
};

// Yeni bir düğüm oluşturma işlemi
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->next = NULL;
    return node;
}

// Bağlı listeye yeni bir eleman ekleme işlemi
void insert(struct Node** head, int data) {
    struct Node* node = newNode(data);
    node->next = *head;
    *head = node;
}

// Bağlı listeden belirli bir anahtara sahip olan elemanı silme işlemi
void deleteNode(struct Node** head, int key) {
    // Başlangıç düğümünü tutan bir referans oluşturma
    struct Node* temp = *head;
    struct Node* prev = NULL;
    
    // Başlangıç düğümü anahtarına sahip elemanı arama
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    // Eleman bulunamadıysa işlemi sonlandırma
    if (temp == NULL) {
        printf("Eleman bulunamadi\n");
        return;
    }

    // Bulunan elemanı bağlı listeden çıkarma
    if (prev == NULL) {
        *head = temp->next;
    } else {
        prev->next = temp->next;
    }

    free(temp); // Bellekten elemanın hafızasını silme
}

// Bağlı listeyi yazdırma işlemi
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}

// Test kodu
int main() {
    struct Node* head = NULL;
    insert(&head, 7);
    insert(&head, 1);
    insert(&head, 3);
    insert(&head, 2);
 
    printf("Bağlı liste: ");
    printList(head);
 
    deleteNode(&head, 1);
    printf("1 elemanı silindi: ");
    printList(head);
 
    deleteNode(&head, 3);
    printf("3 elemanı silindi: ");
    printList(head);
 
    deleteNode(&head, 7);
    printf("7 elemanı silindi: ");
    printList(head);
 
    return 0;
}

Bu kod, bağlı listenin başlangıç düğümünü işaret eden bir referans alır ve belirtilen anahtara sahip olan düğümü arar. Düğüm bulunduğunda, düğümü bağlı listeden çıkarır ve hafızasını serbest bırakır. Kod, anahtarın bağlı listede olmadığı durumları da ele alır ve bir hata mesajı yazdırır.

Tek yönlü bağlı listeyi ters çevirme (iterative)​

Aşağıda, tek yönlü bir bağlı listeyi tersine çevirmek için iteratif bir C kodu örneği verilmiştir:

#include <stdio.h>
#include <stdlib.h>

// Tek yönlü bağlı listenin düğüm yapısı
struct Node {
    int data;
    struct Node* next;
};

// Yeni bir düğüm oluşturma işlemi
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->next = NULL;
    return node;
}

// Bağlı listeye yeni bir eleman ekleme işlemi
void insert(struct Node** head, int data) {
    struct Node* node = newNode(data);
    node->next = *head;
    *head = node;
}

// Bağlı listeyi tersine çevirme işlemi
void reverseList(struct Node** head) {
    struct Node* prev = NULL;
    struct Node* current = *head;
    struct Node* next = NULL;
    
    while (current != NULL) {
        next = current->next; // Next düğümünü kaydet
        current->next = prev; // Mevcut düğümün next'ini önceki düğüm yap
        prev = current; // Önceki düğümü güncelle
        current = next; // Mevcut düğümü güncelle
    }
    
    *head = prev; // Başlangıç düğümünü önceki düğüm yap
}

// Bağlı listeyi yazdırma işlemi
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}

// Test kodu
int main() {
    struct Node* head = NULL;
    insert(&head, 7);
    insert(&head, 1);
    insert(&head, 3);
    insert(&head, 2);
    
    printf("Orijinal bağlı liste: ");
    printList(head);
    
    reverseList(&head);
    printf("Ters çevrilmiş bağlı liste: ");
    printList(head);
    
    return 0;
}


Bu kod, bir önceki düğümü tutmak için bir prev işaretçisi kullanır ve mevcut düğümün next işaretçisini önceki düğümün adresine ayarlar. Daha sonra, işaretçileri güncellemek için mevcut düğümü ve next düğümünü ileriye taşır. Son olarak, işaretçileri güncellemek için başlangıç düğümünü önceki düğüme ayarlar ve bağlı listeyi ters çevirir.

Bağlı Listeyi Recursive (Özyinelemeli) Olarak Ters Çevirme​

Aşağıda, bir bağlı listeyi özyinelemeli olarak tersine çevirmek için C kodu örneği verilmiştir:

#include <stdio.h>
#include <stdlib.h>

// Tek yönlü bağlı listenin düğüm yapısı
struct Node {
    int data;
    struct Node* next;
};

// Yeni bir düğüm oluşturma işlemi
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->next = NULL;
    return node;
}

// Bağlı listeye yeni bir eleman ekleme işlemi
void insert(struct Node** head, int data) {
    struct Node* node = newNode(data);
    node->next = *head;
    *head = node;
}

// Bağlı listeyi özyinelemeli olarak tersine çevirme işlemi
void reverseListRecursive(struct Node** head) {
    if (*head == NULL || (*head)->next == NULL) {
        // Listenin boş ya da tek elemanlı olduğu durumda geri dön
        return;
    }
    
    struct Node* rest = (*head)->next;
    reverseListRecursive(&rest); // Rest of the list'i ters çevir
    
    (*head)->next->next = *head;
    (*head)->next = NULL;
    *head = rest;
}

// Bağlı listeyi yazdırma işlemi
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}

// Test kodu
int main() {
    struct Node* head = NULL;
    insert(&head, 7);
    insert(&head, 1);
    insert(&head, 3);
    insert(&head, 2);
    
    printf("Orijinal bağlı liste: ");
    printList(head);
    
    reverseListRecursive(&head);
    printf("Ters çevrilmiş bağlı liste: ");
    printList(head);
    
    return 0;
}

Bu kod, listenin son elemanına kadar özyinelemeli olarak ilerler ve son düğümün next işaretçisini önceki düğüme ayarlar. Daha sonra, önceki düğümün next işaretçisini NULL olarak ayarlar ve önceki düğümü geri döndürür. Özyinelemeli işlem sonunda, başlangıç düğümü yeni tersine çevrilmiş listenin son düğümüne işaret eder.

Bu özyinelemeli algoritma, bağlı listeyi iteratif olarak tersine çeviren algoritmaya göre daha yavaş olabilir. Ancak özyinelemeli yapısı sayesinde daha basit bir kod yapısına sahiptir.