Veri Yapıları #05 | Çift Bağlı Liste ve Bekçi Düğümler: Geri Gitmenin Bedeli

Eğitmen: Dr. Süleyman Burak ÇELİK

Veri Yapıları dersinin beşinci videosu. Tek bağlı bir listeyi sondan başa gezmek için her eleman için baştan yürümek gerekiyor: on bin elemanda yaklaşık 50 milyon adım. Her düğüme bir de önceki düğümün adresini ekleyince aynı iş 9999 adım. Bugün çift bağlı listeyi kuruyoruz. Çift bağlı listenin düğümünde üç alan var: değer, önceki düğümün adresi ve sonraki düğümün adresi; bu Mac'te 24 bayt, tek bağlı düğümden 8 bayt fazla. Kitaptaki gerçekleştirme gibi listenin iki ucuna gerçek veri taşımayan birer bekçi düğüm koyuyoruz; böylece her gerçek düğümün hem öncekisi hem sonrakisi oluyor ve ilk elemanı silmek ya da sona eklemek özel durum olmaktan çıkıyor. Bir düğümün önüne eklemenin dört bağlantısını tek tek izliyoruz; son iki adımın sırası ters olursa ileri yazınca 75 kayboluyor, geri yazınca görünüyor, gcc ise hiçbir şey söylemiyor. Silmenin yalnızca iki bağlantı olduğunu görüyoruz. Ardından tek bekçili çift bağlı dairesel listeyi kuruyoruz: bekçinin sonrakisi ilk, öncekisi son düğüm. Son olarak tek ve çift bağlı listeyi işlemler ve bellek açısından karşılaştırıyoruz. Ekrandaki her çıktı, kodun gerçekten derlenip çalıştırılmasından geliyor. Bu derste: 1. Tersten gezmek: tek bağlıda N·(N−1)/2, çift bağlıda N − 1 adım 2. Düğüm: önceki, değer, sonraki (24 bayt) 3. Bekçi düğümler ve özel durumların ortadan kalkması 4. Önüne ekleme dört, silme iki bağlantı; sıranın önemi 5. Tek bekçili çift bağlı dairesel liste ve seçim Bölümler: 0:00 Çift bağlı liste 0:17 Listeyi sondan başa gezmek 0:53 Düğüm: önceki, değer, sonraki 1:13 Bekçi düğümler 1:51 Önüne eklemek: dört bağlantı 2:35 Son iki adımın sırası 3:14 Silmek: iki bağlantı 3:43 Çift bağlı dairesel liste: tek bekçi 4:16 Hangisini seçmeli? 4:39 Bugünün dört kuralı 5:00 Sonraki ders: yığın Kaynak kitap: Mark Allen Weiss — Data Structures and Algorithm Analysis in C++, 4. baskı (2014), §3.5 (çift bağlı liste, başta ve sonda bekçi düğüm, ekleme ve silme). Konu sırası ve kavramlar kaynak kitaptan izlenir; programlar C ile özgün yazıldı, anlatım ve ekranlar özgündür. Hedef kitle: veri yapılarına başlayan mühendislik ve bilgisayar/yazılım öğrencileri. Ön koşul: temel C (struct, işaretçiler, malloc) ve bu serinin 3. ve 4. dersleri.