Tek Yönlü Bağlı Listeler (Veri Yapıları Dersi Konu Anlatımı (C++ İle))

Verilerin bilgisayar hafızasının belli bir bölümüne yerleştirilip saklanması olayıdır. Bu veriler birbiri ile bağlantılı olacak şekilde hafızaya yerleştirilir. İhtiyaç duyduğumuz herhani bir zamanda ise, en baştaki veriden başlayarak hafızanın o bölgesindeki diğer tüm verilere istediğimiz zaman ulaşabilme imkanını sağlayan bir veri yapısıdır.

Kısacası amaç, hafızada bir veri kümesi oluşturmak ve oluşturduğumuz bu veri kümesindeki, istediğimiz herhangi bir bilgiye ulaşmak.

Daha somut bir örnek vermek gerekirse, bir iş yerindeki personelleri düşünün. Tüm bu personellerin bilgilerini içeren bir dosya düşünün. O dosya, bizim veri kümemizdir. İhtiyaç duyduğumuz herhangi bir zamanda ise o dosyanın sayfalarını tek tek kurcalayarak istediğimiz zaman istediğimiz personelin bilgisine nasıl ulaşabiliyorsak, bilgisayar hafızasında oluşturacağımız veri kümemesindeki, istediğimiz bir veriye de aynı şekilde ulaşabileceğiz.

Veri kümesindeki tüm bilgiler birbirine şu mantıkla bağlanıyorlar :

Resmi büyütmek için üzerine tıklayınız.

Yapacağımız örnek üzerinde konuyu anlatmaya çalışacağım. Üstteki örnekte olduğu gibi çalışmamızı integer veriler üzerinde yapacağız. Zaten okullarda da genelde öyle gösterilir.

İlk önce Dugum adında bir sınıf oluşturalım. (Struct ile de yapılabilir.) Bu Liste bizim veri kümemiz olacak. Sınıfa düğüm adını vermek demek, oluşturacağımız listenin adı "Dugum"dur demek oluyor. Yani listemize "Dugum" adını verdik.Düğüm adlı sınıf yapımızdan düğümler oluşturacağız. Bu kısım size karışık gelmesin. Demek istediğim şey, "Dugum" adında bir listemiz var ve biz bu "Dugum" adını verdiğimiz listede kullanmak üzere, "Dugum" sınıfından çift bölmeli olan düğümlerden oluşturacağız. Düğümlerin birleşimi ise bize "listeyi" oluşturacaktır.

Bakınız :

Oluşturduğum liste içindeki düğümlerde ortak olarak kullanacağımız 2 farklı yapıya ihtiyaç duyacağız. Bunların biri, verileri saklayacak olan int tanımlı bir yapı olacak. Diğeri ise, bir sonraki düğüme ulaşmamızı sağlayacak olan bir pointer yapısı olacak.

Oluşturduğumuz listeden yola çıkarak her bir düğümü;

Dugum p1 =  new Dugum();

şeklinde oluşturacağız. Şuanda p1 adında bir düğüm oluşturmuş olduk.

Dugumlerimizi oluşturduktan sonra, her bir düğüme veri ataması yaptık.
Çünkü biz iliyoruz ki  her bir düğüm;
1- Veri saklar.
2 - Sonraki düğümün verisinin adresini saklar.

biz ilk önce veri atamalarını yaptık. Birinci düğüm olan p1'e 1 verisini atadık. p1 düğümünün verisi 1'dir dedik ve bilgisayar bellekte, p1 düğümünün veri kutucuğunda 1'yi sakladı.
p2 düğümüne 4 verisini atadık,
p3 düğümünün veri kısmı 3 bilgisini saklıyor,
p4 düğümü de 5 bilgisini içeriyor.

Daha sonra ise, p1 -> pSonraki = p2 ifadesinden başlamak üzere tüm düğümleri birbirine bağladık. Yani, p1 düğümünün adres saklayan kısmı olan 2. bölmesine; p2 verisinin adresini sakladık.

p2'nin verisi neydi? - p2'nin verisi 4'idi. Bir önceki aşamada p2 -> veri = 4 yaparak p2 düğümüne veri olarak 4'ü atamıştık çünkü. Dolayısıyla p1 düğümünün adres kısmı, 4 sayısının adresini tutuyor.

p2'düğümü ise, p4 verisinin adresini tutuyor.
p4 düğümü, p3 düğümünün verisinin adresini tutuyor.
p3 düğümü ise, adres kısmında hiçbir verinin adresini tutmuyor. Çünkü p3 düğümü listenin son düğmüdür ve kendisinden sonra başka düğüm gelmemektedir. p3'ün adres taşıyan kısmına bu yüzden de direkt olarak NULL yazıyoruz.

Dikkat ettiyseniz her bir düğüm bir sonraki düğümü işaret ederek aslında bir liste oluşturdular.
p1'den sonra p2'yi işaret ederek, aynı zamanda p1'den sonra p2 geliyor dedik.
p2'den sonra p4 geliyor dedik.
p4'ten sonra p3 geliyor dedik.
p3'ten sonra bir şey gelmiyor, NULL yazarakda başka bir düğüm gelmediğini belirttik.

Ben bu şekilde bağladım. Siz kafanıza göre daha farklı şekillerde de bağlayabilirsiniz düğümleri.

Gördüğünüz gibi, tüm düğümler birbiri ile bağlantı içinde oldu ve bir liste meydana geldi :

Liste İçinde Gezmek / Listedeki Tüm Verileri Konsolda Listelemek

Şimdide programı çalıştırıp, girdiğimiz tüm verileri yazacağımız kodlar aracılığıyla konsol ekranında listeleyeceğiz.

Verileri listelemek için sadece ilk düğümü bilmek bize yetecektir. Tek yönlü bağlı listelerde ilk düğüm çok önemlidir. Çünkü tüm işlemler ilk düğüm üzerinden gerçekleştiriliyor. İlk düğümü kaybetmek demek, listeyi kaybetmek demektir. Gezme işlemini de ilk düğümümüz olan p1'den başlatacağız.

Ben elemanları listelemek için yazmamız gereken kodu, ayrı bir fonksiyon oluşturarak yazacağım. Hepsini main içine yazıp, main içini karıştırmaktansa ayrı bir fonksiyonda yazmak göze daha hoş gelir. İsteyen kodları main içinde yazabilir. Ben ayrı bir fonksiyon oluşturacağım için ilk önce main'in hemen üst kısmında, yani class ile main arasında "listele" adında bir fonksiyon oluşturdum ve kodları da onun içine yazdım.

Bakınız :

*** Eğer siz de listeleme işlemini benim gibi bu şekilde ayrı bir fonksiyon içinde yapacaksınız, fonksiyonun çağrılıp ekrana basılması için, main kısmına listele(p1); yazmayı unutmayınız!

Burada bilmeniz gereken şey, p1 düğümünü olduğu gibi while içinde kullanmamanız gerektiğidir. Ben p1 düğümünü, pBas dügümüne atadım. Resimde de gördüğünüz üzere bunu fonksiyon içinde yaptım. Eğer siz bu while döngüsünü main içinde yaptıysanız, şunu yapmanız gerekiyor :

Dugum *pBas;
pBas = p1; 

daha sonra ise, pBas'ı while içinde kullanmanız gerekiyor. Bunu yapmamızdaki amaç, orjinal düğümümüz olan p1'i kaybetmemektir. Bundan sonraki yapacağımız ekleme, çıkarma vs. gibi işlemlerde hatalı sonuç çıkmasının önüne geçmektir.

pBas aslında yine p1'dir. Bunlar birbirinin aynısıdır. Bunu yaparak p1'i sonraki işlemlerde kullanmak üzere saklamış olduk. pBas ise, ilk dügüm olduğu için kendisinden başlanarak while döngüsü içinde tüm düğümlere tek tek uğrayıp verisini ekrana yazdırarak listeyi gezmiş olduk.

Şuanda pBas'ın p1 olduğunu düşünerek while döngüsünü inceleyelim.

Satır satır açıklayacak olursam;

13. Satır : While döngüsüne, pBas NULL olmadığı sürece verileri ekrana yazdırmaya devam et dedim.

15. Satır : pBas'ın o an için sahip olduğu veriyi yazdır anlamına geliyor.

16. Satır : pBas'tan sonraki veri hangisi ise onu al, pBas'a ata.


1. kez While içine girdiğimiz zaman;
pBas = p1 olduğu için, ekrana p1'in verisi olan 1 yazıldı.
pBas'a, p1'den sonraki düğüm olan p2 atandı ve pBas artık p2 olmuş oldu.


2. kez While içine girdiğimiz zaman;
pBas artık p2 olduğu için p2'nin verisi olan 4 ekrana yazıldı.
pBas'a, p2'den sonraki düğüm olan p4 atandı ve pBas artık p4 olmuş oldu.
(Daha önceki yaptığımız işlemlere dikkat ederseniz eğer, p2 -> pSonraki = p4 yapmıştık. O yüzden p2'den sonra p4 geldi. Rakamsal sıraya göre gitmiyoruz. Düğümleri bağladığımız sıraya göre ilerliyoruz.)


3. kez While içine girdiğimiz zaman;
pBas artık p4 olduğu için p4'nin verisi olan 5 ekrana yazıldı.
pBas'a, p2'den sonraki düğüm olan p3 atandı ve pBas artık p3 olmuş oldu.

4. kez While içine girdiğimiz zaman;
pBas artık p3 olduğu için p3'nin verisi olan 3 ekrana yazıldı.
pBas'a, p3'den sonraki düğümü atamayamıyoruz çünkü p3 listemizin son düğümüydü. Kendisinden sonra başka bir düğüm yok. Eğer hatırlarsanız, p3'ün adres kısmına herhangi bir düğümün verisinin adresini yazamadığımız için NULL yazmıştık. Bu sebeple pBas = NULL olmuş oldu.

pBas == NULL olduğu için ise, döngüye bir daha girmiyor program ve işlemimiz burada sonlanıyor.

----------------------------------------------------------------------------------------------------------------------

Listeye düğüm ekleme
Listeden düğüm silme
Araya düğüm ekleme
Aradan düğüm silme

işlemlerini ileriki zamanlarda başka bir konu başlığı altında, bu konun devamı olarak anlatmaya çalışacağım.

Benim anlatacaklarım şimdilik bu kadar. Umarım yeterince açıklayıcı ve faydalı olabilmişimdir. Eğer anlamadığınız yerler olursa aşağı yorum olarak bildirin. İnsalık halidir, yanlış yaptığım yerler olabilme ihtimali de vardır. Bu sebeple aklınıza takılan soruları hemen alt kısımdan yorum olarak bana iletebilirsiniz. Elimden geldiğince yardımcı olmaya çalışacağım.