Veri Yapıları #02 | Soyut Veri Tipi ve Liste: Başa Eklemek Neden Pahalı?

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

Veri Yapıları dersinin ikinci videosu. Bir öğrencinin not listesine 75'i eklediğimizde ekranda yalnızca bir satır değişiyor; ama perde arkasında 3 eleman yerinden kayıyor. Bu kaymalar neden oluyor ve ne zaman sorun olur? Önce iki kavramı ayırıyoruz: veri yapısı verinin bellekte nasıl düzenlendiğidir; soyut veri tipi ise nesneler ve onlar üzerindeki işlemlerdir, bu işlemlerin nasıl gerçekleştirileceğini söylemez. Liste soyut veri tipinin işlemlerini (oluştur, ekle, sil, bul, kaçıncı eleman, yazdır) bir başlık dosyasına, liste.h dosyasına yazıyoruz; listenin içi orada yok, yalnızca adı var. Listeyi kullanan program içine bakmaya çalışınca gcc derlemeyi durduruyor: bu bir aksaklık değil, bilgi gizleme. Sonra listeyi 100 elemanlık bir diziyle gerçekleştiriyoruz: eklemek için elemanlar bir adım sağa, silmek için bir adım sola kayıyor; dizinin sınırını ve dolunca iki kat büyüyen dizileri görüyoruz. Hangi işlemin ne kadar iş yaptığını tek tek inceliyor, sonra gerçekten ölçüyoruz: boş bir diziye N elemanı teker teker başa eklemek N bin iken 499 500, N 16 bin iken 127 992 000 kayma demek; N iki katına çıkınca kayma dört katına çıkıyor, sona eklemede ise hiç kayma yok. Toplamın N·(N−1)/2 olduğunu ve bunun Büyük O gösteriminde O(N²) büyüme olduğunu gösteriyoruz. Son olarak bağlı listenin kaydırmadan nasıl eklediğini ve bunun bedelini görüyoruz. Ekrandaki her çıktı, kodun gerçekten derlenip çalıştırılmasından geliyor. Bu derste: 1. Veri yapısı ile soyut veri tipi arasındaki fark 2. liste.h arayüzü ve bilgi gizleme: gcc'nin eksik tip hatası 3. Listeyi diziyle gerçekleştirmek: ekleme sağa, silme sola kaydırır 4. Gerçek ölçüm: N kez başa eklemede N·(N−1)/2 kayma 5. Büyük O: O(1), O(N), O(N²) ve bağlı listeye ilk bakış Bölümler: 0:00 Veri yapısı ve soyut veri tipi 0:16 Bir not eklemek: 3 eleman kayıyor 0:43 Veri yapısı mı, soyut veri tipi mi? 1:18 Bilgi gizleme: liste.h ve gcc hatası 1:43 Listeyi diziyle gerçekleştirmek 2:22 Hangi işlem ne kadar iş yapar? 2:48 Ölçüm: N elemanı başa eklemek 3:29 Büyük O: O(1), O(N), O(N²) 3:54 Bağlı liste: kaydırmadan eklemek 4:23 Bugünün dört kuralı 4:48 Sonraki ders: bağlı liste, aynı arayüz Kaynak kitap: Mark Allen Weiss — Data Structures and Algorithm Analysis in C++, 4. baskı (2014), §3.1–3.2 ve §2.1. 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 (diziler, fonksiyonlar, struct, işaretçiler) ve bu serinin 1. dersi.