4.2: Singly Linked List (Tek Yönlü Liste)

📋 Temel Operasyonlar

1️⃣ Başa Ekleme (prepend) O(1)

Yeni node oluştur, next'ini head'e bağla, head'i güncelle.

HEAD →

A

→

B

→

→ NULL

⬇️ prepend("X")

HEAD →

X

→

A

→

B

→

→ NULL

💡 Neden O(1)? Sadece 2 işlem: new_node.next = head, head = new_node

2️⃣ Sona Ekleme (append) O(n)

Son node'u bulmak için tüm listeyi dolaşmak gerekir.

HEAD →

A

→

B

→

C
null

← Son node'u bul

⬇️ append("X")

HEAD →

A

→

B

→

C

→

X

null

💡 Neden O(n)? Son node'u bulmak için n eleman gezilmeli. (Tail pointer ile O(1) yapılabilir!)

3️⃣ Silme (delete) O(n)

Silinecek node'un önceki node'unu bulmak gerekir.

HEAD →

A

→

B
→

→

C

null

← "B"yi sil

⬇️ delete("B")

HEAD →

A

→

C

null

✅ A.next = C

💡 Önemli: Silmek için önceki node'u bilmek gerekir. Tek yönlü listede geri gidemeyiz!

4️⃣ Arama (search) O(n)

Baştan itibaren tek tek kontrol edilir.

💻 Tam Python Implementasyonu

Python Kodu

class Node:
    """Tek yönlü bağlı liste düğümü"""
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    """Tek Yönlü Bağlı Liste"""
    
    def __init__(self):
        self.head = None
        self.size = 0
    
    def prepend(self, data):
        """Başa ekle - O(1)"""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        self.size += 1
        print(f"✅ Başa eklendi: {data}")
    
    def append(self, data):
        """Sona ekle - O(n)"""
        new_node = Node(data)
        
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:  # Son node'u bul
                current = current.next
            current.next = new_node
        
        self.size += 1
        print(f"✅ Sona eklendi: {data}")
    
    def delete(self, data):
        """Belirli değeri sil - O(n)"""
        if not self.head:
            print("❌ Liste boş!")
            return
        
        # Silinecek head ise
        if self.head.data == data:
            self.head = self.head.next
            self.size -= 1
            print(f"🗑️ Silindi: {data}")
            return
        
        # Ara ve sil
        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                self.size -= 1
                print(f"🗑️ Silindi: {data}")
                return
            current = current.next
        
        print(f"❌ Bulunamadı: {data}")
    
    def search(self, data):
        """Değeri ara - O(n)"""
        current = self.head
        index = 0
        while current:
            if current.data == data:
                print(f"🔍 Bulundu: {data} (index: {index})")
                return index
            current = current.next
            index += 1
        print(f"🔍 Bulunamadı: {data}")
        return -1
    
    def display(self):
        """Listeyi göster"""
        if not self.head:
            print("Liste: [BOŞ]")
            return
        
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        
        print(f"Liste: HEAD → {' → '.join(elements)} → NULL")
        print(f"Boyut: {self.size}")

# Test
print("🔗 Singly Linked List Demo\n")
liste = SinglyLinkedList()

liste.append(10)
liste.append(20)
liste.append(30)
liste.display()

print()
liste.prepend(5)
liste.display()

print()
liste.delete(20)
liste.display()

print()
liste.search(30)
liste.search(100)

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.size = 0
    
    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        self.size += 1
        print(f"✅ Başa eklendi: {data}")
    
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
        self.size += 1
        print(f"✅ Sona eklendi: {data}")
    
    def delete(self, data):
        if not self.head: return
        if self.head.data == data:
            self.head = self.head.next
            self.size -= 1
            print(f"🗑️ Silindi: {data}")
            return
        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                self.size -= 1
                print(f"🗑️ Silindi: {data}")
                return
            current = current.next
    
    def display(self):
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        print(f"Liste: {' → '.join(elements) if elements else '[BOŞ]'}")

liste = SinglyLinkedList()
liste.append(10)
liste.append(20)
liste.append(30)
liste.display()
liste.prepend(5)
liste.display()
liste.delete(20)
liste.display()

Çıktı bekleniyor...

⚡ Tail Pointer ile Optimizasyon

Sona ekleme işlemini O(1) yapmak için tail pointer kullanabiliriz:

Python Kodu

class OptimizedLinkedList:
    """Tail pointer ile optimize edilmiş liste"""
    
    def __init__(self):
        self.head = None
        self.tail = None  # Son node'u takip et!
        self.size = 0
    
    def append(self, data):
        """Sona ekle - Artık O(1)!"""
        new_node = Node(data)
        
        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node  # Direkt tail'e bağla
            self.tail = new_node       # Tail'i güncelle
        
        self.size += 1
    
    def prepend(self, data):
        """Başa ekle - O(1)"""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        
        if not self.tail:  # İlk elemansa tail'i de ayarla
            self.tail = new_node
        
        self.size += 1
    
    def display(self):
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        print(f"HEAD → {' → '.join(elements)} → NULL")
        print(f"(head={self.head.data if self.head else 'None'}, tail={self.tail.data if self.tail else 'None'})")

# Test
print("⚡ Optimized Linked List (Tail Pointer)\n")
opt_list = OptimizedLinkedList()

import time
N = 10000

# Normal append (simüle)
start = time.time()
for i in range(N):
    opt_list.append(i)
print(f"✅ {N} eleman O(1) append: {time.time()-start:.4f} sn")
print(f"Son eleman: {opt_list.tail.data}")

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class OptimizedLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
    
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1
    
    def display(self):
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        print(f"HEAD → {' → '.join(elements)} → NULL")

import time
opt_list = OptimizedLinkedList()
N = 10000
start = time.time()
for i in range(N):
    opt_list.append(i)
print(f"✅ {N} eleman O(1) append: {time.time()-start:.4f} sn")
print(f"Tail: {opt_list.tail.data}")

Çıktı bekleniyor...

📊 Zaman Karmaşıklığı Özeti

Operasyon	Temel	Tail ile
Başa Ekleme	O(1)	O(1)
Sona Ekleme	O(n)	O(1)
Baştan Silme	O(1)	O(1)
Sondan Silme	O(n)	O(n)
Arama	O(n)	O(n)

⚠️ Sondan silme her zaman O(n) çünkü önceki node'u bulmak gerekir (tek yönlü!)