Bağlı Liste
- İngilizcesi
- Linked List
- Türkçe karşılığı
- bağlantılı liste
- Okunuşu
- linkt list
Günlük kullanımda iki ad da yaygın.
Kısaca
Bağlı liste, öğeleri ayrı düğümlerde saklayan bir veri yapısıdır; her düğüm bir değer ile zincirdeki sonraki düğüme bir referans tutar.
Bağlı liste (linked list) nedir?
Bağlı liste, düğümlerden oluşan doğrusal bir veri yapısıdır. Her düğüm bir değerin yanı sıra sonraki düğüme bir referans ya da işaretçi (pointer) saklar; liste ise yalnızca ilk düğümü, yani baş (head) düğümü hatırlamak zorundadır. Son düğüm hiçbir yere işaret etmez; bu durum JavaScript'te null, Python'da None olarak yazılır.
Düğümlerin bellekte yan yana durması gerekmediği için başa öğe eklemek ya da baştan öğe silmek O(1) sürer: diğer öğeleri kaydırmak yerine yalnızca bir iki referansı güncellersiniz. Ödünleşim, konuma göre erişimdir. 500. öğeye ulaşmak için baştan başlayıp 499 bağı izlemeniz gerekir; bu yüzden indeksle erişim ve arama O(n) sürer. Çift yönlü bağlı liste ayrıca önceki düğüme de bir referans saklar; bu, geriye doğru yürümenize ve elinizde zaten bulunan bir düğümü O(1)'de silmenize olanak tanır.
Her ipucunun bir sonrakinin nerede olduğunu söylediği bir hazine avını düşünün: kendisinden önceki dokuz ipucunu okumadan doğrudan onuncu ipucuna atlayamazsınız. Bağlı listeler yığınların, kuyrukların ve bazı hash tablolarındaki çakışma zincirlerinin yapı taşı olarak kullanılır. Ayrıca en az kullanılan kaydı ilk atan önbellekler olan LRU önbelleklerinde de görülür; burada çift yönlü bağlı liste kayıtları kullanım sırasına göre tutar.
Bağlı listeler sıklıkla dizilerle karıştırılır. Dizi öğeleri tek ve sürekli bir bellek bloğunda saklar; bu yüzden herhangi bir indeksi okumak O(1)'dir, ancak ortaya eklemek kendisinden sonraki her şeyi kaydırmak demektir. Adına rağmen Python'daki bir list ve JavaScript'teki bir Array bağlı liste değil dinamik dizidir; günlük kodda öğeleri bellekte birbirine yakın durduğu, bu da CPU önbelleğine uygun olduğu için genellikle daha hızlıdır.
Bir bakışta
Önemli noktalar
- Her düğüm bir değer ve sonraki düğüme bir referans tutar.
- Başa ekleme ya da baştan silme O(1) sürer.
- Zinciri yürümeniz gerektiği için indeksle erişim ya da arama O(n) sürer.
- Çift yönlü bağlı liste her düğümü öncekine de bağlar; böylece iki yönde de gezilebilir.
- Python listeleri ve JavaScript dizileri bağlı liste değil, dinamik dizidir.
Örnek
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node # the next node, or None at the end
# Build 1 -> 2 -> 3, then insert 0 at the front in O(1) time
head = Node(1, Node(2, Node(3)))
head = Node(0, head)
# Visiting the items means following the links one by one: O(n)
node = head
while node is not None:
print(node.value) # 0, 1, 2, 3
node = node.nextSık sorulan sorular
Ne zaman dizi yerine bağlı liste kullanmalıyım?
Uçlara sık sık öğe ekliyor ya da uçlardan öğe siliyorsanız, ya da referansını zaten elinizde tuttuğunuz düğümlerin yanına ekleme yapıyorsanız ve nadiren bir indekse atlamanız gerekiyorsa bağlı liste kullanın. Günlük işlerin çoğunda dizi ya da dilinizin yerleşik listesi daha basit ve daha hızlıdır.
Tek yönlü ile çift yönlü bağlı liste arasındaki fark nedir?
Tek yönlü bağlı listede her düğüm yalnızca sonraki düğüme işaret eder. Çift yönlü bağlı listede her düğüm ayrıca öncekine de işaret eder; bu daha fazla bellek kullanır ama geriye doğru yürümenize ve bilinen bir düğümü O(1)'de silmenize olanak tanır.
Bağlı listeye ekleme O(1) mi yoksa O(n) mi?
Kendisinden önceki düğümün referansına zaten sahipseniz ya da başa ekliyorsanız yeni bir düğümü bağlamak O(1)'dir. Rastgele bir konumu bulmak önce O(n) sürer; dolayısıyla belirli bir indekse eklemek toplamda O(n)'dir.
Sık karşılaştırılanlar
İlgili sayfalar
- DiziProgramlamanın Temelleri, s. 15Dizi, tek bir ad altında saklanan ve her öğesine genellikle 0'dan başlayan indeks adlı sayısal konumuyla erişilen, sıralı bir değerler koleksiyonudur.
- YığınVeri Yapıları, s. 36Yığın, öğeleri son giren ilk çıkar (LIFO) sırasıyla saklayan bir veri yapısıdır; en son eklenen öğe her zaman ilk çıkarılan öğedir.
- KuyrukVeri Yapıları, s. 24Kuyruk, öğeleri ilk giren ilk çıkar (FIFO) sırasıyla saklayan bir veri yapısıdır; en uzun süre bekleyen öğe her zaman çıkarılacak sonraki öğedir.
- Hash TablosuVeri Yapıları, s. 18Hash tablosu, anahtar-değer çiftlerini saklayan ve hash fonksiyonuyla herhangi bir anahtarın değerini ortalamada sabit sürede bulan bir veri yapısıdır.
- Big O gösterimiProgramlamanın Temelleri, s. 4Big O gösterimi, girdi büyüdükçe bir algoritmanın çalışma süresinin ya da bellek kullanımının nasıl arttığını, kesin hız yerine büyüme oranıyla anlatır.
- AğaçVeri Yapıları, s. 2Ağaç, kenarlarla bağlı düğümlerden oluşan hiyerarşik bir veri yapısıdır; en üstte tek bir kök düğüm ve altında dallanan çocuk düğümler bulunur.
- Two PointersVeri Yapıları, s. 34Two pointers tekniği, bir dizi ya da listeyi basit kurallarla ilerleyen iki indeksle tarar; iç içe döngü ister gibi görünen birçok problemi tek geçişte çözer.
- LRU CacheVeri Yapıları, s. 25LRU (least recently used) cache, sabit sayıda öğe tutar ve dolunca en uzun süredir kullanılmayanı atar; son kullanılan verinin yine gerekeceğini varsayar.
Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin