🔗 Linked List - Bağlı Listeler

📋 İçindekiler

🎯 Giriş

Linked List (Bağlı Liste), her elemanın kendinden sonraki elemana işaret ettiği, dinamik bir veri yapısıdır. Veriler bellekte ardışık olarak saklanmaz; her node (düğüm) bir sonrakinin adresini içerir.

💡 Temel Özellik: Boyut dinamik olarak değişir, sabit boyut sınırı yoktur!

Neden Linked List?

  • ✅ Dinamik boyutlandırma
  • ✅ Kolay ekleme/silme işlemleri
  • ✅ Bellek verimliliği
  • ✅ Esnek veri yönetimi

🏗️ Temel Yapı - Node (Düğüm)

Her node iki temel bölümden oluşur:

  1. Data (Veri): Saklanacak bilgi
  2. Next (Pointer): Bir sonraki node’un adresi

Görsel Temsil

┌─────────────────┐
│     NODE        │
├─────────────────┤
│  Data: 42       │  ← Veri kısmı
│  Next: 0x1A2B   │  ← Sonraki node'un adresi
└─────────────────┘

Tam Bir Linked List Örneği

HEAD
 ↓
┌────┬────┐    ┌────┬────┐    ┌────┬────┐    ┌────┬──────┐
│ 10 │ ●──┼───→│ 20 │ ●──┼───→│ 30 │ ●──┼───→│ 40 │ NULL │
└────┴────┘    └────┴────┘    └────┴────┘    └────┴──────┘

Açıklama:

  • HEAD: Listenin başlangıç işaretçisi
  • ●: Pointer (işaretçi)
  • NULL: Listenin sonu

🎨 Linked List Türleri

1️⃣ Singly Linked List (Tekli Bağlı Liste)

Her node sadece bir sonraki node’u işaret eder.

A → B → C → D → NULL

Özellikler:

  • Tek yönlü hareket
  • Daha az bellek kullanımı
  • Geriye doğru hareket mümkün değil

2️⃣ Doubly Linked List (Çift Bağlı Liste)

Her node hem önceki hem de sonraki node’u işaret eder.

NULL ← A ⇄ B ⇄ C ⇄ D → NULL
     prev next

Yapı:

┌──────┬──────┬──────┐
│ PREV │ DATA │ NEXT │
└──────┴──────┴──────┘

Özellikler:

  • Çift yönlü hareket
  • Daha fazla bellek kullanımı
  • Geriye doğru hareket kolay

3️⃣ Circular Linked List (Dairesel Bağlı Liste)

Son node, ilk node‘u işaret eder ve döngü oluşturur.

    ┌──────────────────┐
    ↓                  │
    A → B → C → D ─────┘

Özellikler:

  • Sonsuz döngü oluşturur
  • Round-robin algoritmalarda kullanılır
  • NULL pointer yok

⚙️ Temel İşlemler

🔹 1. Başa Ekleme (Insert at Head)

Zaman Karmaşıklığı: O(1) ⚡

ÖNCE:
HEAD → 20 → 30 → NULL

SONRA:
HEAD → 10 → 20 → 30 → NULL

Adımlar:

  1. Yeni node oluştur
  2. Yeni node’un next’ini mevcut HEAD’e işaret ettir
  3. HEAD’i yeni node’a güncelle

🔹 2. Sona Ekleme (Insert at Tail)

Zaman Karmaşıklığı: O(n) 🐌

ÖNCE:
HEAD → 10 → 20 → NULL

SONRA:
HEAD → 10 → 20 → 30 → NULL

Adımlar:

  1. Yeni node oluştur
  2. Listeyi sonuna kadar tara
  3. Son node’un next’ini yeni node’a işaret ettir

🔹 3. Araya Ekleme (Insert at Position)

Zaman Karmaşıklığı: O(n) 🐌

ÖNCE:
HEAD → 10 → 30 → NULL

SONRA (pozisyon 2'ye ekle):
HEAD → 10 → 20 → 30 → NULL

Adımlar:

  1. İstenilen pozisyona git
  2. Yeni node’u önceki ve sonraki node arasına yerleştir

🔹 4. Silme (Delete)

Zaman Karmaşıklığı: O(n) 🐌

ÖNCE:
HEAD → 10 → 20 → 30 → NULL

SONRA (20'yi sil):
HEAD → 10 → 30 → NULL

Adımlar:

  1. Silinecek node’u bul
  2. Önceki node’un next’ini, silinecek node’un next’ine yönlendir
  3. Silinecek node’u bellekten sil

🔹 5. Arama (Search)

Zaman Karmaşıklığı: O(n) 🐌

Liste baştan sona taranır ve aranan değer bulunur.

current = head
while current:
    if current.data == target:
        return True
    current = current.next
return False

⏱️ Zaman Karmaşıklığı

İşlem Zaman Karmaşıklığı Açıklama
Başa Ekleme O(1) ✅ Direkt HEAD’e ekleme
Sona Ekleme O(n) ⚠️ Tüm listeyi taramak gerekir
Araya Ekleme O(n) ⚠️ Pozisyona ulaşmak gerekir
Silme O(n) ⚠️ Elemanı bulmak gerekir
Arama O(n) ⚠️ Linear search
İndeksle Erişim O(n) ⚠️ Baştan saymak gerekir

⚖️ Avantaj ve Dezavantajlar

✅ Avantajlar

Özellik Açıklama
🔄 Dinamik Boyut Sabit boyut sınırı yoktur, çalışma zamanında büyür/küçülür
⚡ Kolay Ekleme/Silme Özellikle baştan ekleme/silme O(1)‘dir
💾 Bellek Verimliliği Sadece ihtiyaç kadar bellek kullanır
🎯 Esneklik Elemanlar bellekte dağınık olabilir

❌ Dezavantajlar

Sorun Açıklama
🐌 Yavaş Erişim İndeksle direkt erişim yoktur, O(n)
📦 Ekstra Bellek Her node için pointer bellekte yer kaplar
⬅️ Tersine Dolaşma Singly linked list’te geriye dolaşmak zordur
🔄 Cache Locality Bellekte ardışık olmadığı için cache performansı düşüktür

💻 Kod Örnekleri

Python İmplementasyonu

class Node:
    """Linked List için Node sınıfı"""
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    """Singly Linked List implementasyonu"""
    def __init__(self):
        self.head = None
    
    def insert_at_head(self, data):
        """Başa eleman ekle - O(1)"""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
    
    def insert_at_tail(self, data):
        """Sona eleman ekle - O(n)"""
        new_node = Node(data)
        
        if not self.head:
            self.head = new_node
            return
        
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
    
    def delete(self, key):
        """Belirtilen değeri sil - O(n)"""
        current = self.head
        
        # Silinecek node HEAD ise
        if current and current.data == key:
            self.head = current.next
            current = None
            return
        
        # Silinecek node'u ara
        prev = None
        while current and current.data != key:
            prev = current
            current = current.next
        
        # Bulunamadıysa
        if not current:
            return
        
        # Bağı kır ve sil
        prev.next = current.next
        current = None
    
    def search(self, key):
        """Değer ara - O(n)"""
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False
    
    def print_list(self):
        """Listeyi yazdır"""
        current = self.head
        while current:
            print(current.data, end=" → ")
            current = current.next
        print("NULL")
    
    def get_length(self):
        """Liste uzunluğunu bul - O(n)"""
        count = 0
        current = self.head
        while current:
            count += 1
            current = current.next
        return count

# Kullanım Örneği
if __name__ == "__main__":
    ll = LinkedList()
    
    # Eleman ekleme
    ll.insert_at_head(30)
    ll.insert_at_head(20)
    ll.insert_at_head(10)
    ll.insert_at_tail(40)
    
    print("Liste:")
    ll.print_list()  # Çıktı: 10 → 20 → 30 → 40 → NULL
    
    # Arama
    print(f"\n20 var mı? {ll.search(20)}")  # True
    print(f"50 var mı? {ll.search(50)}")    # False
    
    # Silme
    ll.delete(20)
    print("\n20 silindikten sonra:")
    ll.print_list()  # Çıktı: 10 → 30 → 40 → NULL
    
    # Uzunluk
    print(f"\nListe uzunluğu: {ll.get_length()}")  # 3

C++ İmplementasyonu

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    
    Node(int value) {
        data = value;
        next = nullptr;
    }
};

class LinkedList {
private:
    Node* head;
    
public:
    LinkedList() {
        head = nullptr;
    }
    
    // Başa ekle - O(1)
    void insertAtHead(int data) {
        Node* newNode = new Node(data);
        newNode->next = head;
        head = newNode;
    }
    
    // Sona ekle - O(n)
    void insertAtTail(int data) {
        Node* newNode = new Node(data);
        
        if (head == nullptr) {
            head = newNode;
            return;
        }
        
        Node* current = head;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newNode;
    }
    
    // Yazdır
    void printList() {
        Node* current = head;
        while (current != nullptr) {
            cout << current->data << " → ";
            current = current->next;
        }
        cout << "NULL" << endl;
    }
    
    // Destructor - bellek temizliği
    ~LinkedList() {
        Node* current = head;
        while (current != nullptr) {
            Node* temp = current;
            current = current->next;
            delete temp;
        }
    }
};

int main() {
    LinkedList ll;
    ll.insertAtHead(30);
    ll.insertAtHead(20);
    ll.insertAtHead(10);
    ll.insertAtTail(40);
    
    ll.printList();  // 10 → 20 → 30 → 40 → NULL
    
    return 0;
}

🎓 Kullanım Alanları

🎵 Müzik Çalarlar

  • Çalma listeleri (playlist)
  • İleri/geri şarkı geçişi
  • Shuffle modu

🌐 Web Tarayıcıları

  • Sayfa geçmişi (ileri/geri butonları)
  • Sekme yönetimi

🖼️ Görüntü Görüntüleyiciler

  • Fotoğraf galerisi gezintisi
  • Slideshow

🧠 Bellek Yönetimi

  • Free block listesi
  • Garbage collection

📚 Veri Yapıları

  • Stack implementasyonu
  • Queue implementasyonu
  • Graph adjacency list

🎮 Oyunlar

  • Undo/Redo sistemleri
  • Turn-based oyun sıralaması

📊 Array vs Linked List Karşılaştırması

Özellik Array Linked List
Erişim Hızı O(1) ✅ O(n) ❌
Ekleme (Başa) O(n) ❌ O(1) ✅
Silme O(n) ❌ O(1) ✅ (node biliniyorsa)
Bellek Ardışık 📦 Dağınık 📦📦
Boyut Sabit ⚠️ Dinamik ✅
Cache Performansı İyi ✅ Kötü ❌

🚀 İleri Seviye Konular

Linked List ile İlgili Yaygın Algoritma Soruları

  1. Orta Elemanı Bulma - İki pointer (slow & fast)
  2. Döngü Tespiti - Floyd’s Cycle Detection
  3. Listeyi Ters Çevirme - Reverse linked list
  4. İki Liste Birleştirme - Merge two sorted lists
  5. Palindrome Kontrolü - Check if palindrome

Örnek: Listeyi Ters Çevirme

def reverse_list(head):
    """Linked list'i ters çevir"""
    prev = None
    current = head
    
    while current:
        next_node = current.next  # Sonrakini kaydet
        current.next = prev       # Pointer'ı ters çevir
        prev = current            # İlerle
        current = next_node       # İlerle
    
    return prev  # Yeni head

💡 En İyi Pratikler

  1. ✅ Null kontrolü yapın: Her zaman pointer’ların null olup olmadığını kontrol edin
  2. ✅ Bellek yönetimi: C/C++‘da belleği düzgün temizleyin
  3. ✅ Edge case’leri düşünün: Boş liste, tek elemanlı liste
  4. ✅ Dummy node kullanın: Bazı işlemleri basitleştirir
  5. ✅ İki pointer tekniği: Birçok problemde işe yarar

🎯 Sonuç

Linked List, dinamik veri yönetimi gereken durumlarda güçlü bir araçtır. Array’e göre daha esnek ama erişim hızı daha yavaştır. Doğru senaryoda kullanıldığında çok etkilidir!

Ne Zaman Kullanmalı?

✅ Linked List Kullan:

  • Sık ekleme/silme işlemleri yapılacaksa
  • Boyut önceden bilinmiyorsa
  • Random erişim gerekmiyorsa

❌ Array Kullan:

  • Random erişim önemliyse
  • Bellek cache performansı kritikse
  • Boyut sabitse