Bir önceki yazımızda tek yönlü bağlı liste oluşturma işlemine kısaca değinmiştik. Bu yazımızda bağlı listelerde traverse işlemine değineceğiz. Tabii ki öncelikle traverse ne anlama geliyor bunu açıklayalım. Traverse dolaşmak anlamına gelen bir ifadedir. Search (arama) işleminin temelini oluşturur. Bir veri yapısı üzerindeki elemanları dolaşmak için ya da belirli bir elemana ulaşmak için traverse işlemi yaparız.
Şu ana kadar bağlı listelerde eleman ekleme işlemini görmedik. Bu yüzden şimdilik elemanları manual olarak birbirlerine bağlayacağız.
Direkt kodu yazmak yerine mantığı anlamaya yönelelim. Tek yönlü Bağlı listelerde düğümler başlangıç düğümünden başlar ve herbir düğüm kendisinden sonra gelen düğümü işaret eder. Son düğüm ise yapısı gereği NULL’u işaret eder. Yani bağlı listede traverse yaparken eğer mevcut düğümün işaretçisi NULL ise son düğüme geldiğimiz anlamını taşır. Şimdi geçen yazımızda yazdığımız temel kodları tekrar hatırlayalım.
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* next;
};
struct node* start = NULL;
struct node* createNewNode(int data) {
struct node* newNode = (struct node*)malloc(sizeof(struct node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}Yukarıdaki yapıda dikkat etmemiz gereken 3 nokta var. Birinci husus struct node* yapısı. Struct C programlama dilinde class benzeri bir yapıdır. Aynı class’larda olduğu gibi new’lemek gereklidir. ANSI C programlama dilinde new ibaresi yoktur. Bunun yerine malloc adı verdiğimiz bir fonksiyon bulunur. Malloc fonksiyonu ile struct içerisindeki alan kadar (sizeof(struct node)) alan oluştururuz.
İkinci dikkat etmemiz gereken husus struct node* start ibaresidir. Bu ifade genelde global olarak tutulur. Başlangıç düğümü mutlaka ama mutlaka ayrı bir şekilde tutulmalıdır. Bağlı listelerin ana adresini start isimli düğümde tutarız. (Adı start olmak zorunda değil, kurallara uygun bir şekilde istediğiniz ismi verebilirsiniz.)
Üçüncü husus ise createNewNode fonksiyonudur. Bu fonksiyon bir düğüm oluşturmak istediğimizde kullandığımız bir fonksiyondur. New’lemek işlemini yapar. Yani oluşturduğumuz düğüm için ram üzerinde dinamik şekilde alan oluşturur. Şunu unutmayın düğüm dediğimiz yapıda tek bir değişken tipi tutmak zorunda değiliz. Onlarca sayıda değişken tutmamız hatta başka struct yapıları tutmamız mümkündür.
şimdi main fonksiyonumuzun içerisinde düğümlerimizi oluşturalım.
int main() {
struct node* baslangicDugumu = createNewNode(5);
struct node* ikinciDugum = createNewNode(10);
struct node* ucuncuDugum = createNewNode(15);
start = baslangicDugumu;
start->next = ikinciDugum;
ikinciDugum->next = ucuncuDugum;
traverseLinked();
return 0;
}yukarıdaki kod yapısında baslangicDugumu, ikinciDugum ve ucuncuDugum olarak 3 tane değişken oluşturduk. En önemli kısım bu düğümlerden bir tanesini start düğümüne atadık. Böylece başlangıç düğümünü belirlemiş olduk. Ve diğer adımlarda bu düğümleri birbirine bağladık. start => ikinciDugum => ucuncuDugum => NULL durumu oluştu. Traverse fonksiyonunu ise aşağıda paylaşıyorum.
Traverse Fonksiyonu
Şimdi Traverse fonksiyonumuzu yazalım.
void traverseLinked()
{
struct node* temp = start;
while(temp != NULL)
{
printf("\n%d", temp->data);
temp = temp->next;
}
}Yukarıdaki fonksiyonda dikkat etmeniz gereken temp değişkenidir. Mevcut yapıyı maniple etmemek için bağlı listedeki düğümleri tutacağımız geçici bir değişken oluşturuyoruz.
Temp, temporary yani geçici ifadesinin kısaltmasıdır. Bağlı listelerde sık sık bu ismi kullanacağız. Siz kodlama yaparken bu ismi vermek zorunda değilsiniz. Biz sadece anlaşılması açısından belli başlı değişken isimlerini sürekli aynı şekilde kullanacağız.
oluşturduğumuz temp değişkenine başlangıç düğümünü yani start’ı atıyoruz. ve while döngüsüne giriyoruz. Dikkat ederseniz while döngüsünün şartı temp’in null olmaması. Daha önce de bahsettiğimiz gibi, son düğümün işaretçisi her zaman null’dur. Son düğüme geldiğimizi düğümün işaretçisinin null olmasından anlarız.
While döngüsü içerisinde maniplasyon yapıyoruz. Yani mevcut düğümün data değerini yazdırdıktan sonra, temp = temp->next diyerek diğer düğüme atlıyoruz.
Bağlı Listelerde (ve diğer veri yapılarında) traverse kavramı çok önemlidir. yapı içerisinde arama yapmak için ya da tüm düğümlere (node) erişmek için traverse işlemi gerçekleştiririz. Ve her veri yapısının traverse işlemi kendine hastır. Bizim anlattığımız yapı bağlı listeler özelindedir. Şimdi aşağıda kodun tümünü paylaşıyorum.
Tek Yönlü Bağlı Listede Eleman Ekleme ve Traverse İşlemi
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* next;
};
struct node* start = NULL;
struct node* createNewNode(int data) {
struct node* newNode = (struct node*)malloc(sizeof(struct node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void traverseLinked()
{
struct node* temp = start;
while(temp != NULL)
{
printf("\n%d", temp->data);
temp = temp->next;
}
}
int main() {
struct node* baslangicDugumu = createNewNode(5);
struct node* ikinciDugum = createNewNode(10);
struct node* ucuncuDugum = createNewNode(15);
start = baslangicDugumu;
start->next = ikinciDugum;
ikinciDugum->next = ucuncuDugum;
traverseLinked();
return 0;
}
Python ile Bağlı Listeye Eleman Ekleme ve Traverse İşlemi
Aşağıda, yukarıdaki C kodunun Python halini paylaşıyorum Python’da malloc fonksiyonuna gerek yok. Struct yapısı yerine de class yapısını kullanıyoruz.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.start = None
def create_new_node(self, data):
new_node = Node(data)
new_node.next = None
return new_node
def traverse_linked(self):
temp = self.start
while temp is not None:
print(temp.data)
temp = temp.next
if __name__ == "__main__":
linked_list = LinkedList()
baslangic_dugumu = linked_list.create_new_node(5)
ikinci_dugum = linked_list.create_new_node(10)
ucuncu_dugum = linked_list.create_new_node(15)
linked_list.start = baslangic_dugumu
linked_list.start.next = ikinci_dugum
ikinci_dugum.next = ucuncu_dugum
linked_list.traverse_linked()
