Veri Yapıları #03 | Bağlı Liste: Düğüm, malloc ve Hiç Kaymayan Elemanlar

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

Veri Yapıları dersinin üçüncü videosu. Geçen derste diziyle gerçekleştirdiğimiz listeyi bu kez bağlı listeyle gerçekleştiriyoruz; listeyi kullanan programın tek satırına dokunmadan. Çıktı satır satır aynı, ama içeride artık hiçbir eleman kaymıyor. Bağlı listenin yapı taşı düğüm: bir değer ve bir sonraki düğümün adresi. sizeof ile bakınca düğüm 12 değil 16 bayt çıkıyor; ilk derste gördüğümüz hizalama yüzünden değerden sonra 4 dolgu baytı geliyor. Her düğüm gerektiği anda malloc ile ayrılıyor, son düğümün sonraki alanında NULL var. Düğümlerin adreslerini yazdırınca liste sırasının bellek sırası olmadığını görüyoruz: sonradan eklenen 75 listede ikinci, bellekte en sonda. Araya eklemek için önceki düğüme kadar ilerleyip yalnızca iki bağlantıyı değiştiriyoruz; bu iki satırın sırası ters olursa gcc hiçbir şey söylemiyor ama liste hiç bitmiyor, çünkü son düğüm kendini gösteriyor. Silmek tek bağlantı değişikliği; silinen düğüm free ile geri veriliyor, unutulursa bellek sızar. Geçen dersin hesabını da gerçekten çalıştırıyoruz: yüz bin elemanı başa eklemek diziyle bu Mac'te 27 saniyeden fazla, bağlı listeyle 5 milisaniye sürüyor. Son olarak bedeli görüyoruz: kaçıncı elemana ulaşmak için baştan yürümek gerekiyor ve bir not 4 yerine 16 bayt tutuyor. Ekrandaki her çıktı, kodun gerçekten derlenip çalıştırılmasından geliyor. Bu derste: 1. Aynı liste.h arayüzü, yeni gerçekleştirme: kullan.c hiç değişmeden çalışır 2. Düğüm: değer + sonraki adres; sizeof 16 ve dolgu baytları 3. malloc, NULL ve düğümlerin bellekteki gerçek adresleri 4. Ekleme iki, silme bir bağlantı; ters sıradaki iki satırın sonsuz döngüsü 5. Ölçüm: 100 000 başa ekleme, dizi ile bağlı liste; bağlı listenin bedeli Bölümler: 0:00 Aynı arayüz, yeni gerçekleştirme 0:22 Aynı program, aynı çıktı 0:51 Düğüm: değer ve sonraki adres 1:31 malloc, NULL ve gerçek adresler 2:08 Araya ve başa eklemek 2:44 İki satırın sırası: hiç bitmeyen liste 3:17 Silmek ve free 3:43 Ölçüm: 100 000 başa ekleme 4:05 Bağlı listenin bedeli 4:34 Bugünün dört kuralı 4:57 Sonraki ders: dairesel liste Kaynak kitap: Mark Allen Weiss — Data Structures and Algorithm Analysis in C++, 4. baskı (2014), §3.2.2. 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 ilk iki dersi.