Bağlı Listeler (Linked Lists): Tekli ve Çift Yönlü Listeler
Bağlı listeler, dinamik veri yapılarının temel örneklerinden biridir ve özellikle bellek kullanımında esneklik sağlayarak veri elemanlarının sıralı şekilde depolanmasına imkan verir. Dizilerden farklı olarak, bağlı listeler elemanların bellek üzerinde ardışık yer almasını gerektirmez ve boyutları çalışma sırasında dinamik olarak değiştirilebilir. Bu özellikleriyle pek çok algoritma ve uygulamada önemli rol oynar.
Bağlı Liste Nedir?
Bağlı liste, her elemanın kendisinden sonraki (ve çift yönlü listelerde bir önceki) elemanın adresini (referansını) tuttuğu veri yapısıdır. Her eleman, düğüm (node) olarak adlandırılır ve genellikle veri kısmı ile bağlantı kısmından oluşur.
Tekli Bağlı Liste (Singly Linked List)
Tekli bağlı listede, her düğüm yalnızca bir sonraki düğümün adresini tutar. Listenin başı (head) genellikle dışarıdan erişilir ve son düğümün bağlantısı null (boş) olarak işaretlenir.
Özellikleri:
- Yön: Tek yönlü, sadece ileri doğru hareket edilebilir.
- Ekleme: Başta, ortada veya sonda kolaylıkla yapılabilir, ancak ortada ekleme için önceki düğüme ulaşmak gerekir.
- Silme: Benzer şekilde, silme işlemi yapılabilir ancak öncesindeki düğüme erişim gereklidir.
- Bellek kullanımı: Her düğüm sadece bir pointer içerdiği için bellek verimlidir.
Avantajları:
- Basit ve hafif yapıdır.
- Bellek tüketimi azdır.
Dezavantajları:
- Geriye doğru gezinmek mümkün değildir.
- Belirli düğüme ulaşmak için sıralı tarama gerekir (O(n) zaman).
Çift Yönlü Bağlı Liste (Doubly Linked List)
Çift yönlü bağlı listede, her düğüm hem bir sonraki hem de bir önceki düğümün adresini tutar. Bu sayede liste içerisinde hem ileri hem de geri yönde gezinmek mümkündür.
Özellikleri:
- Yön: İki yönlü, ileri ve geri hareket mümkündür.
- Ekleme: Başta, ortada ve sonda kolaylıkla yapılabilir.
- Silme: Belirli bir düğümü silmek için hem önceki hem sonraki düğüme erişim vardır.
- Bellek kullanımı: Her düğümde iki pointer bulunduğu için daha fazla bellek kullanır.
Avantajları:
- İleri ve geri hareket özgürlüğü sağlar.
- Silme ve ekleme işlemleri daha esnek ve hızlıdır.
Dezavantajları:
- Tekli bağlı listeye göre daha fazla bellek tüketir.
- Karmaşık yapı nedeniyle hata yapma riski artabilir.
Bağlı Listelerin Kullanım Alanları
- Dinamik veri yönetimi: Bellekte yer tutmayan, boyutu çalışma sırasında değişebilen yapılar gerektiren uygulamalar.
- Sıralı veri yapıları: Kuyruk (queue), yığın (stack), grafik ve ağaç yapılarının temelini oluşturur.
- Gerçek zamanlı sistemler: Veri ekleme ve silme işlemlerinin hızlı yapılması gereken durumlarda.
- Metin düzenleyiciler: Geri alma/ileri alma işlemleri için çift yönlü bağlı listeler kullanılır.
Bağlı Listelerde İşlem Karmaşıklıkları
| İşlem | Tekli Bağlı Liste | Çift Yönlü Bağlı Liste |
|---|---|---|
| Erişim (random) | O(n) | O(n) |
| Başına ekleme | O(1) | O(1) |
| Sona ekleme | O(n) veya O(1)* | O(1) |
| Ortaya ekleme | O(n) | O(n) |
| Silme | O(n) | O(n) |
*Sonuna ekleme tekli listede eğer son düğüm referansı yoksa O(n), referans varsa O(1) zaman alır.
Bağlı Listelerle İlgili Örnek Durumlar
- Tekli liste: Basit bir görev listesi uygulamasında, görevler sırayla işlenirken tekli bağlı liste tercih edilebilir.
- Çift yönlü liste: Tarayıcı geçmişinde ileri-geri hareket için çift yönlü liste kullanılır.
Bu makale bilgilendirme amaçlıdır. Veri yapıları ve algoritmalar konusunda daha derin ve uygulamalı bilgi almak için bilgisayar bilimleri veya yazılım mühendisliği alanında uzman bir profesyonele danışılması önerilir.
Anahtar kelimeler: bağlı liste, linked list, tekli bağlı liste, çift yönlü bağlı liste, düğüm, node, veri yapıları, dinamik yapı, algoritma, bellek yönetimi, yazılım geliştirme, bilgisayar bilimi