Tek yönlü bağlı liste (singly linked list) nedir ve ne zaman kullanırsınız?

Question

Accepted Answer

**Tek yönlü bağlı liste**, her biri bir değer ve sonraki **node** ya da başvuru tutan **node**'ların bir zinciridir. Dizi aksine, node'lar bitişik değildir — bellekte herhangi bir yerde olabilirler ve referanslar tarafından bağlanırlar.

## Yapı

```text
head
  |
  v
[10|*]--->[20|*]--->[30|null]
 val next   val next  val next
```

## Örnek

```python
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

# Insert at head -> O(1)
def push_front(head, val):
    node = Node(val)
    node.next = head     # point new node at old head
    return node          # new head

# Search -> O(n): must walk the chain
def find(head, target):
    cur = head
    while cur:
        if cur.val == target:
            return cur
        cur = cur.next
    return None
```

## Karmaşıklık

| İşlem | Zaman |
|---|---|
| Başta ekleme/silme | O(1) |
| İndekse göre erişim | O(n) |
| Arama | O(n) |

## Değiş Tokuş

- **Güçlü Yönler:** başta O(1) ekleme/silme; yeniden tahsis olmaksızın büyüme; israf edilen kapasite yok.
- **Zayıf Yönler:** rastgele erişim yok; her node işaretçi ek yükü taşır; kötü cache lokalitesi (dağınık bellek).

## Neden önemli

Bağlı listeler sık sık uçlarda eklediğiniz veya çıkardığınız ve ortaya nadiren indekslediğiniz zaman — örneğin yığın (stack), kuyruk (queue) ve komşuluk listelerinin omurgası olarak.

Buradaki işaretçi manipülasyonunu anlamak, ağaçlar, grafikler ve birçok mülakat sorusu için temeldir.