Linked List Reverse - (Bağlı Liste Ters Çevirme)

Linked List Reverse işlemi adıyla da bilinen Bağlı Liste Ters Çevirme işlemi hocaların sık sık öğrencilerine sorduğu bir konudur. Ters çevrilmiş bir Linked List'de ilk eleman son eleman olurken son eleman da ilk eleman olmaktadır. Ancak aralarındaki ilişki de ters olur. Hemen aşağıdaki görsele bakalım;

linked list ters çevirme - linked list reverse
bağlı liste ters çevirme
Yukarıdaki işleme dikkat edin, sıralama değişmemiş gibi ama outpu yazan yerde adresleme tam tersine dönmüş. yani

10 => 20 => 30 => 40 => 50 => 60 => NULL

60 => 50 => 40 => 30 => 20 => 10 => NULL

olmuş. 10 sayısının bulunduğu düğüm ilk başta start düğümüyken, ters çevrilince son eleman haline gelmiş.

Linked List Reverse işlemi Algoritması

Üstteki şekilden de göreceğiniz üzere, her bir düğümün adresi tersini gösterdiğinde aslında tersten sıralamış oluyoruz.

Bu bağlamda traverse işlemi gerekli. Yani start düğümünden başlayıp tüm adresleri tersine çevirmemiz gerekiyor. Yazması kolay ama nasıl yapacağız?

1. Yaklaşım:

start düğümünü geçici düğüme atayıp traverse yaparsak tüm düğümleri dolaşırız.

temp = start;
while(temp!=NULL)
      temp = temp->next;

peki dolaşırken ne yapalım?

Eğer ilk düğümün next değerini NULL yaparsak;

while(temp!=NULL){
       ilkdugum->next = NULL;
       temp = temp->next;}

ikinci düğüme nasıl ulaşacağız? çünkü ikinci düğümümüz ilkdugum->next değerine sahip. Böylece ilk yaklaşımımız patladı :)

2. Yaklaşım.

ikinci düğümü elimizde tutalım next ismini verelim. Döngü içerisinde devamlı değer atayalım

while(temp!=NULL){
       next = temp->next;
       ilkdugum->next = NULL;
       temp = temp->next;}

Peki şimdi ne oldu? ilk düğüm değerimiz de elimizde patladı. çünkü ilkdugum->next = next desek sürekli Null atayacak. Halbuki NULL değeri sadece başlangıç için olmalı. Sonraki adımlarda bir önceki düğümü işaret etmeli. Yani sonuç olarak 2. yaklaşım da patladı.

3. Yaklaşım.

Bu sefer de önceki düğümü elimizde tutalım. prev düğümü ismini verelim. başlangıç olarak NULL değeri atadığımızı varsayalım. temp->next değerine prev değerini atayalım. sonra da prev değerine şuanki değeri atayalım ki sürekli döngüye girsin ve bir önceki düğüme adres versin.

while(temp!=NULL){
       next = temp->next;
       temp->next = prev
       prev = temp;
       temp = next;}

bak bu defa oldu :) demek ki sonraki düğüm ve önceki düğüm için geçisi düğümler oluşturmamız gerekiyor. Ama bitmedi, start değerimizin de değişmesi lazım. Bu yüzden while döngümüzün dışına 

start = prev; 

yazmamız gerekiyor. çünkü neden? Temp değeri zaten traverse sonucu en son elemana ulaşacak, en son düğüme geldiğinde son düğüm temp düğümüne eşitlenecek. Böylece start değerine prev değerini aktardığımız anda iş bitmiş olacak.


Bağlı Liste Ters Çevirme C Kodu


void reverseList()
{
    struct node* onceki = NULL;
    struct node* sonraki;
    struct node* bas;
    bas = start;

    while(bas!=NULL)
    {
        sonraki = bas->next;
        bas->next = onceki;
        onceki = bas;
        bas = sonraki;
    }
    start = onceki;
}

Etiketler: , , ,