PHP ile İleri Konular, Bağlı Liste Oluşturma

Bilgisayar Mühendisliğinde  Veri Yapıları (Data Structures) dersi alanlar bilir, Veri Yapılarında Bağlı Listeler (Link List) en önemli konulardan biridir. Genelde bu konuyu C++ programlama dili ile anlatırlar, başka programlama dillerinde de hazır fonksiyonlar vardır. C# ve Java içinde Bağlı Listeler için özel fonksiyonlar vardır, PHP hiç geri kalır mı? PHP içinde de Bağlı Listeler ile ilgili SplDoublyLinkedList() fonksiyonu var.

Aşağıdaki örnekte basit bir bağlı liste var, verinin tutulduğu bir veri hücresi var ve her hücreden sonra hangi hücrenin geleceği bilgisini tutan bir gösterici hücre bölümü var.  Bu ikisine birden düğüm (node) adını veriyoruz. Bu bölümde çok fazla Veri Yapıları anlatmayacağım, zira geniş bir konu. 



İşin mantığını anlamanız için Kaynaklar bölümündeki Türkçe Bağlı Liste anlatımını izleyebilir, sonra kodlara göz atabilirsiniz.

Biz şimdi kendi Bağlı Listemizi oluşturacağız.

<?php
class DugumListele
{
    public $veri;
    public $sonraki;
    function __construct($veri)
    {
        $this->veri = $veri;
        $this->sonraki = NULL;
    }
 
    function dugumOku()
    {
        return $this->veri;
    }
}
 
class BagliListe
{
    private $ilkDugum;
    private $sonDugum;
    private $sayac;
 
    function __construct()
    {
        $this->ilkDugum = NULL;
        $this->sonDugum = NULL;
        $this->sayac = 0;
    }
 
    //BagliListe'ye ilk düğüm ekle
    public function ilkDugumEkle($veri)
    {
        $link = new DugumListele($veri);
        $link->sonraki = $this->ilkDugum;
        $this->ilkDugum = &$link;
 
        /* Eğer ilk düğümse ve başka düğüm yoksa son düğüm olarak da ilk düğümü gösterilir. */
 
        if($this->sonDugum == NULL)
            $this->sonDugum = &$link;
            $this->sayac++;
    }
 
 
    //BagliListe'deki tüm düğümler listeleniyor
    public function dugumOku()
    {
        $listveri = array();
        $aktifDugum = $this->ilkDugum;
        while($aktifDugum != NULL)
        {
            array_push($listveri, $aktifDugum->dugumOku());
            $aktifDugum = $aktifDugum->sonraki;
        }
        foreach($listveri as $v){
            echo $v."<br>";
        }
    }
 
    //BagliListe'deki tüm düğümler ters çevriliyor.
    public function tersCevir()
    {
        if($this->ilkDugum != NULL)
        {
            if($this->ilkDugum->sonraki != NULL)
            {
                $aktifDugum = $this->ilkDugum;
                $yeni = NULL;
 
                while ($aktifDugum != NULL)
                {
                    $gecici = $aktifDugum->sonraki;
                    $aktifDugum->sonraki = $yeni;
                    $yeni = $aktifDugum;
                    $aktifDugum = $gecici;
                }
                $this->ilkDugum = $yeni;
            }
        }
    }
 
 
 
    //anahtar(key) değere göre istenilen düğümü siler
    public function dugumSil($key)
    {
        $aktifDugum = $this->ilkDugum;
        $onceki = $this->ilkDugum;
 
        while($aktifDugum->veri != $key)
        {
            if($aktifDugum->sonraki == NULL)
                return NULL;
            else
            {
                $onceki = $aktifDugum;
                $aktifDugum = $aktifDugum->sonraki;
            }
        }
 
        if($aktifDugum == $this->ilkDugum)
         {
              if($this->sayac == 1)
               {
                  $this->sonDugum = $this->ilkDugum;
               }
               $this->ilkDugum = $this->ilkDugum->sonraki;
        }
        else
        {
            if($this->sonDugum == $aktifDugum)
            {
                 $this->sonDugum = $onceki;
             }
            $onceki->sonraki = $aktifDugum->sonraki;
        }
        $this->sayac--;  
    }
 
 
       //Bağlı Listeyi tamamen boşaltır
    public function emptyList()
    {
        $this->ilkDugum == NULL;
 
    }
 
 
    //Bağlı Listemizde verilen key(sıra) değerine göre araya eleman ekler.
 
    public function arayaEkle($YeniGelen,$key){
        if($key == 0){
        $this->ilkDugumEkle($YeniGelen);
    }
    else{
        $link = new DugumListele($YeniGelen);
        $aktifDugum = $this->ilkDugum;
        $onceki = $this->ilkDugum;
 
        for($i=0;$i<$key;$i++)
        {       
                $onceki = $aktifDugum;
                $aktifDugum = $aktifDugum->sonraki;
        }
 
           $onceki->sonraki = $link;
           $link->sonraki = $aktifDugum; 
           $this->sayac++;
    }
 
    }   
}
 
/* Yeni bağlı liste oluşturuluyor */
$nesne = new BagliListe();
 
/* Listeye ilk olarak Elazig ili ekleniyor */
$vilayet="Elazig";
$nesne->ilkDugumEkle($vilayet);
$nesne->dugumOku();
echo "<br><br>";
 
/* Sonra Ankara ili ekleniyor */
$key=1;
$vilayet="Ankara";
$nesne->arayaEkle($vilayet,$key); 
$nesne->dugumOku();
echo "<br><br>";
 
/* Sonra Gaziantep ili ekleniyor */
$key=2;
$vilayet="Gaziantep";
$nesne->arayaEkle($vilayet,$key); 
$nesne->dugumOku();
echo "<br><br>";
 
/* Elazig ile Ankara arasına Kars ekleniyor */
$key=1;
$vilayet="Kars";
$nesne->arayaEkle($vilayet,$key); 
$nesne->dugumOku();
echo "<br><br>";
 
/* Listeden Ankara İli siliniyor */
$vilayet="Ankara";
$nesne->dugumSil($vilayet);
$nesne->dugumOku();
echo "<br><br>";


Çalışan halini aşağıdaki linke tıklayarak görebilirsiniz.

ONLİNE DEMO

KAYNAKLAR
1) Bağlı Liste Anlatımı, http://www.youtube.com/watch?v=-5y2ArGzX-I
2) Data Structures and Algorithm Analysis in Java, Mark WEISS, Addison Wesley
3) http://www.stoimen.com/blog/2012/07/24/php-arrays-or-linked-lists/
4) http://www.codediesel.com/php/linked-list-in-php/
5) http://learnprogramming.machinesentience.com/
6) http://code.activestate.com/recipes/576498-implementation-of-a-single-linked-list-in-php/

İyi çalışmalar,

Oğuzhan TAŞ
Ocak - 2015 
 
Bookmark and Share
Dil Değiştir(Change Language)