Bağlı Listeler

Bu yazı BLM212 Veri Yapıları dersinin bağlı listeler konusu için hazırlanmış bir çalışma dosyası. Ders notlarından yola çıkılarak yapay zekâ ile derlendi ve düzenlendi. Ekleme ve silme bölümündeki altı senaryo adım adım ilerletilebilir — o bölümün asıl dersi bir sıra kuralı ve sıra, bitmiş bir şemada görünmüyor.

Doğrusal liste

Doğrusal liste, her elemanın tek bir halefi olduğu bir listedir. Üzerinde tanımlı dört temel işlem var: araya sığdıran insertion, çıkaran deletion, veriyi listeden çıkarmadan okuyan retrieval ve baştan sona her düğüme tam bir kez uğrayan traversal.

Bu dört işlem her doğrusal liste ADT'sinin çekirdeğidir. Yığın ve kuyruk da doğrusal listedir — onlarda kısıtlanan şey işlemlerin nerede yapılabileceğidir, ve kısıtlı listelerde gezinme yoktur.

Bütün konu tek bir gerilimin üstüne kurulu: sıralı verilerde ekleme ve silme gerektiğinde diziler verimsizdir, çünkü her şeyi kaydırmak gerekir. Bağlı liste bunu çözer, ama karşılığında arama ve erişim verimsizleşir, çünkü artık rastgele erişim yoktur.

Dizi mi, bağlı liste mi?

N elemanlı bir liste için dört işlemin maliyeti

işlem	dizi	bağlı liste	neden
başa ekle / sil	○O(N)— pahalı	●O(1)— ucuz	dizide her eleman bir kayar; listede iki bağ değişir
sona ekle / sil	●O(1)— ucuz	●O(1)— ucuz	iki tarafta da kaydırma yok
tümünü yazdır	◐O(N)— orta	◐O(N)— orta	her elemana bir kez uğranır
i. elemana eriş	●O(1)— ucuz	○O(i)— pahalı	dizide indeksle; listede baştan yürüyerek

Uygulaman yalnızca listenin sonuna ekleme ve i. elemana erişim yapıyorsa dizi uygundur; ikisi de sabit zamanlıdır. Ekleme ve silmeler listenin her noktasında, özellikle de başında oluyorsa dizi iyi bir seçim değildir — boyut önceden bilinmiyorsa da öyle.

Bedeli şu: bağlı listede düğümler fiziksel olarak ardışık değildir, bu yüzden ikili arama yapılamaz, yalnızca sıralı arama mümkündür. findKth artık listeyi gezmeyi gerektirir.

İki yapı

Listeyi tanımlamak için teknik olarak tek bir işaretçi yeterlidir. Ama pratikte baş yapısı (head structure) kurmak çok daha kullanışlıdır: baş işaretçinin yanına listeyle ilgili başka bilgiler de konur.

Algorithm createList
   Bağlı liste baş düğümü için dinamik bellek ayırır ve adresini döndürür.
1 if (memory available)
   1  allocate (pNew)
   2  pNew->head  = null pointer
   3  pNew->count = 0
2 else
   1  pNew = null pointer
3 return pNew
end createList

Boş liste demek, baş yapısı var ama head null demektir. Liste "yok" değildir — sadece içi boştur.

Ekleme ve silme

Ekleme üç adımdır: ① yeni düğüme yer aç ve veriyi koy, ② yeni düğümden önce gelen düğümü (pPre) bul, ③ o düğümün yeni düğümü göstermesini sağla. Kritik nokta sıra: önce yeni düğümün bağı, sonra öncekinin bağı. Tersi olursa listenin kuyruğu kaybolur.

Ekleme tek bir if ile iki dala ayrılır. pPre null ise (boş listeye ya da başa ekleme) yeni düğümün bağı head'e, head ise yeni düğüme çevrilir. pPre null değilse (ortaya ya da sona ekleme) yeni düğümün bağı pPre->link'e, pPre->link ise yeni düğüme çevrilir. Dört durumun tamamı bu iki dalla karşılanır; sona ekleme için ayrı bir kod yoktur.

Silme aynı iki dalı kullanır. pPre null ise (ilk düğümü silme) head = pLoc->link; değilse pPre->link = pLoc->link. Her iki dalda da sonunda sayaç azaltılır ve pLoc'un belleği geri verilir.

En sık yapılan hata, ekleme sırasında önce pPre->link = pNew yazmaktır. O anda pPre->link'in eski değeri — yani listenin geri kalanı — kaybolur ve geri getirilemez. Sıra daima önce yeni düğümün bağı. Yukarıdaki senaryolarda "ortaya ekle" adımlarını izlersen, kuyruğun bir adım boyunca iki yerden birden tutulduğu anı görürsün; sıranın sebebi tam olarak o an.

Arama

Ekleme için önceki düğümü, silme için silinecek düğümü ve öncekini, erişim için düğümün kendisini bilmek gerekir. Üçünü de tek bir arama fonksiyonu sağlar — bu yüzden geriye iki işaretçi döndürür.

Düğümler arasında fiziksel bir ilişki olmadığı için sıralı arama zorunludur. Klasik sıralı aramadan farkı şu: liste sıralı olduğu için, aranan bulunamadığında da olması gereken yer döndürülür.

Algorithm searchList (pList, pPre, pLoc, target)
1 pPre = null
2 pLoc = pList->head
3 loop (pLoc not null AND target > pLoc->data.key)
   1  pPre = pLoc
   2  pLoc = pLoc->link
4 if (pLoc is null)  found = false
5 else
   1  if (target equal pLoc->data.key)  found = true
   2  else                              found = false
6 return found

Döngüdeki iki koşul iki ayrı işi yapar: birincisi listenin sonundan taşmayı engeller, ikincisi hedef bulunduğunda ya da hedeften büyük bir düğüme gelindiğinde — yani hedef listede yoksa — döngüyü durdurur.

searchList fonksiyonunun altı durumda döndürdükleri

koşul	pPre	pLoc	dönüş
target < ilk düğüm	null	ilk düğüm	○false
target = ilk düğüm	null	ilk düğüm	●true
ilk < target < son	target'tan küçük en büyük düğüm	target'tan büyük ilk düğüm	○false
target = ortadaki düğüm	düğümün selefi	eşit düğüm	●true
target = son düğüm	sonun selefi	son düğüm	●true
target > son düğüm	son düğüm	null	○false

Gezinme ve yok etme

Gezinmenin çekirdeği dört satırdır. Zor kısım, ADT'de her çağrının bir sonraki elemanı döndürmesi gerektiğidir; bu yüzden baş yapısında pos alanı tutulur.

pWalker = pList->head
loop (pWalker not null)
    process (pWalker->data)
    pWalker = pWalker->link

ADT içinde aynı iş, kaldığı yeri hatırlamak zorunda olduğu için biraz daha uzar:

if (fromWhere is 0)   // baştan başla
   pList->pos = pList->head
else                  // kaldığın yerden
   if (pList->pos->link is null)
        return false   // liste bitti
   pList->pos = pList->pos->link

Uygulama programcısının liste yapısına erişimi olmadığı için, nerede kalındığını ADT'nin kendisi hatırlamalıdır.

Listeyi yok etmek üç iştir: ① listedeki düğümleri silip belleklerini geri ver, ② baş yapısının belleğini geri ver, ③ listenin artık var olmadığını gösteren null işaretçiyi döndür.

algorithm destroyList (ref pList)
1 loop (pList->count not zero)
   1  dltPtr       = pList->head
   2  pList->head  = dltPtr->link      // önce zinciri kurtar
   3  pList->count = pList->count - 1
   4  release (dltPtr)                 // sonra sil
2 release (pList)
3 return null pointer

Yine aynı sıra kuralı: düğümü serbest bırakmadan önce bağını kopyala. Önce release yaparsan, listenin geri kalanının adresini okuyacağın yer artık senin değildir.

List ADT

Bağlı liste gerçekleştirmesini bir ADT'ye çevirmek iki problem doğurur: ADT verinin türünü bilmez, ama listeyi anahtar sırasında tutmak zorundadır. Sıralamak için karşılaştırmak, karşılaştırmak için türü bilmek gerekir.

Veriyi uygulama programı tutar: belleği o ayırır ve düğümün adresini ADT'ye geçirir. C strongly typed olduğu için veri işaretçisi void* olarak geçer. Sıralama sorununun çözümü ise uygulamanın bir compare fonksiyonu yazması ve ADT'nin onun adresini baş yapısında metadata olarak saklamasıdır. Sözleşme basit: arg < key → −1, arg = key → 0, arg > key → +1. Programcı yapıya erişemediği için emptyList, fullList ve listCount gibi durum fonksiyonları da gerekir.

Buradaki iki araç, ADT dersinde görülen ikisinin ta kendisi: void* veriyi tür bilmeden taşır, fonksiyon işaretçisi işlemi tür bilmeden yaptırır. Liste ADT'si bunların ilk gerçek uygulaması.

Liste çeşitleri

Tek yönlü listenin iki eksiği var: geriye gidilemez ve sondan başa dönülemez. Üç kullanışlı çeşit bu eksikleri kapatır.

Dairesel bağlı liste

Son düğümdeki bağ ilk düğümü (ya da başlık düğümünü) gösterir. Ekleme ve silme tek bağlı listeyle aynıdır — tek fark son düğümün bağı. Asıl mesele arama: döngü ne zaman duracak?

Çift bağlı liste

Her düğümde iki işaretçi: selefini gösteren back ve halefini gösteren fore. Bedeli, her ekleme ve silmede dört bağın güncellenmesidir.

Silmede iki bağımsız kontrol gerekir, çünkü silinen düğüm başta ya da sonda olabilir:

if (pDlt->back <> null)   // ilk düğüm değil
     pDlt->back->fore = pDlt->fore
else pList->head       = pDlt->fore

if (pDlt->fore <> null)   // son düğüm değil
     pDlt->fore->back = pDlt->back
else pList->rear       = pDlt->back

Diğer iki çeşit

Çok bağlı listede aynı düğüm kümesi iki veya daha fazla mantıksal sıraya göre ayrı bağ zincirleriyle bağlanır. Veriler çoğaltılmaz, yalnızca ek bağlar eklenir. Ders örneği ABD başkanları listesi: kronolojik sıranın yanına başkanın adına ve eşinin adına göre iki zincir daha.

Bağlı liste dizisinde ise dizinin her elemanı bir bağlı listenin başıdır: her bağlı liste bir satırı, listedeki düğümler sütunları temsil eder. Satır sayısı sabit, satır uzunlukları değişkendir.

İkisinin birleşimi de mümkün: çift bağlı dairesel liste hem iki yönde gezilir hem de uçları birbirine bağlıdır, baş ile son düğüm arasındaki geçiş tek adımdır.

Kendini yokla