Temel Veri Yapıları ve STL 2 - Liste

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




Bu haberin geldigi yer: oyunyapimi.org
http://www.oyunyapimi.org

Bu haber icin adres:
http://www.oyunyapimi.org/modules.php?name=Sections&op=viewarticle&artid=16