Temel Veri Yapıları ve STL 2 - Liste
Temel Veri Yapıları ve STL 1 - Vektörler isimli ilk dökümanımızda STL kütüphanesinden
biraz bahsetmiş, ve daha sonra dizi veri yapısı yerine kullanabileceğimiz ve bize dizi
veri yapısının sağladığı avantajları ve daha fazlasını sunan vektor veri tipinin
kullanımını incelemiştik.
Serimizin bu ikinci dökümanında Liste veri yapısını inceleyecek, kullanımını
örneklerle açıklayacağız, aynı zamanda Iterator kavramıyla tanışacak ve yararlarını
öğreneceğiz. İlk dökümanı okumamış arkadaşlara bu dökümanı okumaya başlamadan
önce ilk dökümanı okumalarını veya en azından hızlıca bir göz gezdirmelerini
tavsiye ederim. STL içerisindeki veri yapılarına erişimde kullanılan yordam ve yapılar
birbirlerine çok benzemektedirler. İlk dökümanda anlatılan kavramları
anlayabildiyseniz bu belgede anlatılanları da çok kolay öğrenebileceğinizden şüphe
duymayın..
Liste
STL listeleri iki bağlaçlı (ön ve arka) standart liste veri yapılarıdır.
Elinizde eleman ekleyebileceğiniz bir listeniz olduğunu düşünün. Bu listeye yeni
gelen elemanları ister listenin başına istersenizde sonuna ekleyebilirsiniz. Hatta
listenin ortalarında istediğiniz bir yere de yeni elemanları yerleştirebilirsiniz. Geçen
dökümanda öğrendiğimiz vector veri yapısı bize böyle bir kolaylık sağlamıyordu.
Listenin başı head , sonu ise tail olarak adlandırılmaktadır. Vector veri yapısında
bir yordam ile devamlı vektörün sonuna eleman ekleyebiliyorduk. Listelerde ise farklı
yordamlar ile ister sondan istersekte baştan eleman ekleme ve çıkarma yapabiliyoruz.
Şimdi bazı örneklerle bu veri yapısının kullanımını inceleyelim. Listeleri
kullanmadan önce ilgili include tanımını yapmamız gerekiyor:
#include <list>
using namespace std;
Diğer tüm STL veri yapılarında olduğu gibi list veri yapısı da ancak bir tür
eleman içerebilecek şekilde kullanılır. Biz şimdi aynen geçen dersimizde olduğu
gibi bir integer listesi oluşturalım:
list<int> liste;
Listemizi oluşturduk. Henüz eleman içermeyen bu listemize elemanlar yüklemeye başlayabiliriz.
İlk olrak listenin önünden elemanları eklemeyi görelim. Listenin önüne eleman
eklemek için .push_front() yordamı kullanılır.
liste.push_front(1);
liste.push_front(2);
liste.push_front(3);
liste.push_front(4);
Yukarıdaki kod ile listemize 1,2,3 ve 4 elemanlarını ekledik. Ekleme işini baştan
yaptığımız için listenin bellekteki görünümünde ilk eleman (yani head elemanı)
4, son eleman (tail elemanı) ise 1 dir. Eklemeyi baştan yapmak demek: eklenen her yeni
elemanın listenin başına getirilmesi anlamına gelmektedir.
Listenin başında (head) bulunan elemanı almak istersek .pop_front() yordamını
kullanırız. Bu yordamın kullanımı sonucu listenin başındaki eleman bize verilirken
bu eleman listeden çıkarılır. Bu elemandan sonra gelen eleman listenin yeni baş
elemanı olur.
int basEleman = liste.pop_front();
// basEleman = 4 ( liste görünümü: head = 3,
2, tail = 1)
Listenin sonunda (tail) bulunan elemanı almak istersek .pop_back() yordamını kullanırız.
Bu yordamın kullanımı sonucu listenin sonundaki eleman bize verilirken bu eleman
listeden çıkarılır. Bu elemandan önce gelen eleman listenin yeni son elemanı olur.
int sonEleman = liste.pop_back();
// sonEleman = 1 ( liste görünümü: head = 3,
tail = 2)
Listenin içinde bulunan elemanlarının sayısını ise .size() yordamı ile
öğrenebiliriz:
int elemanSayisi = liste.size();
// elemanSayisi = 2
Bir listenin eleman içerip içermediğini öğrenmek için .empty() yordamı
kullanılır. Liste eleman içeriyorsa bu yordam false, içermiyorsa true değerini
döndürür:
bool bos = liste.emtpy();
// bos = false
Bir listeyi boşaltmak için .clear() yordamını kullanabilirsiniz. Bu işlemden sonra
listenin eleman sayısı 0 olacaktır.
liste.clear();
Listeye sondan eleman eklemek için .push_back() yordamı kullanılır. Bu yordam ile
her eklenen yeni eleman listenin yeni son (tail) elemanı olur.
liste.push_back(100);
liste.push_back(200);
liste.push_back(300);
liste.push_back(400);
// ( liste görünümü: head = 100, 200, 300,
tail = 400)
Şimdiye kadar çeşitli yordamlar vasıtası ile listemize elemanlar ekledik ve çıkardık.
Peki listemizdeki tüm elemanlara sırası ile erişmek istersek ne yapacağız. Örneğin
listenin tüm elemanlarını yazdırmak isteyelim. Bu işi sırası ile tüm elemanları
listeden çıkartıp, daha sonra ekrana yazdırıp ve listeye son taraftan ekleyerek gerçekleştirebiliriz.
Fakat bu işin çok kolay (ve de hızlı) bir başka yöntemi daha var.
Iterator denilen yapıları kullanarak listenin elemanlarına hızlı bir biçimde erişim
sağlayabiliriz. Iterator leri basitçe liste elemanlarını gösteren pointer lar olarak
düşünebilirsiniz. Bu yapılara ++ ve -- operatörlerini uygulayarak listemizde sonraki
ve önceki elemanlar arasında gezinebilir, * operatörü ile elemanın içeriğine erişebilir
ve değiştirebiliriz. Şimdi son oluşan listemizdeki elemanları baştan sona ekrana
yazdıralım:
for (list::iterator i = liste.begin(); i !=
liste.end(); i++)
printf("%d ",*i);
Yukarıdaki kod parçası ile ekrana sırası ile 100, 200, 300 ve 400 değerleri yazılacaktır.
liste.begin() yordamı bize listenin ilk (head) elemanını simgeleyen bir iterator
nesnesi sağlar. Bu iterator nesnesi üzerinde ++ operatörünü kullandığımız zaman
listenin bir sonraki elemanına erişiriz. * operatörü ile iterator nesnesinin simgelediği
liste elemanının içeriğine erişilebilir. liste.end() yordamı ise listenin son (tail)
elemanından sonraki, yani doğal olarak bir NULL elemanını simgelemektedir. Dikkat
ederseniz döngüde bu elemana gelindiğinde döngüden çıkma işlemi yapılmaktadır.
Liste veri yapısı üzerinde birkaç yararlı işlem yapan yordamımız da bulunmakta. Örneğin
.reverse() yordamı ile liste elemanlarının dizilişini tersine çevirebiliriz. .sort()
yordamı ile elemanları küçükten büyüğe sıralayabiliriz, .unique() yordamı ile
listede birbiri ardına gelen aynı elemanları tek bir eleman haline getirebiliriz.
sort() yordamını kullanırken eğer listemiz kendi tanımladığımız bir veri
tipindeki elemanları içeriyorsa (Point, Vertex vb..) bu veri tipi içerisinde < operaörünün
overload edilmiş olması gerekmektedir, bu noktayı da unutmayın.
Sonuç olarak: eğer elinizdeki elemanlara sıra ile erişim sağlıyor iseniz list
veri yapısını , rastgele erişim sağlıyor iseniz vector veri yapısını kullanmanız
yararınıza olacaktır. Her zaman olduğu gibi anlamadığınız noktalar ile ilgili
sorularınızı, ya da yanlış bulduğunuz noktalar ile ilgili düzeltme, öneri ve her türlü
görüşlerinizi sitemiz forumlarını kullanarak bana ulaştırabilirsiniz. Serinin
ilerki dökümanlarında buluşmak üzere, hoşçakalın.
M.Deniz Aydınoğlu :: 2002 :: www.oyunyapimi.org
