İçerisinde pek çok node ve bu node’larda veriler olan bir linked list’imiz olsun. Yapmak isteyeceğimiz en doğal şey bu linked list’teki node’ları tek tek gezinerek içerisindeki verilere ulaşmak olacaktır. Bu durumda gerçekleştireceğimiz şey gezinme yaygın tabiriyle traversal olarak isimlendirilen işlem olacaktır.
Dört çeşit linked list bulunmaktadır. Singly ve Doubly linked list için farklı, Circular ve Doubly Circular linked list için farklı yöntemlerle gezinme sağlanabilmektedir. Yöntem farklılığının temel sebebi ise singly ve doubly linked list’in son node’u NULL‘u işaret ederken, circular ve doubly circular linked list’in son node’u head‘i işaret etmesidir.
Sırasıyla dört çeşit linked list için gezinme işlemlerini yapalım.
Singly Linked List Traversal
Gezinme işleminde uygulanacak olan mantık gezinilen node’un next değerini kontrol etmek olacaktır. Eğer node’un next’i bir adres ise next node’u gezilecek, NULL ise gezinme sonlanacaktır.
Yukarıdaki singly linked list’in gezinme işlemini kod kullanmadan mantıksal olarak yapalım.
Head node’una erişimimiz var. Head NULL mu? Hayır. Head’in data değerini yazalım: 6. Sonrasında head node’unun next değerini kontrol edelim: NULL değil. Öyleyse diğer next node’una geçelim. Node’un data değerini yazalım: 13. 13 node’unun next’i NULL mu? Hayır. 13 Node’unun next node’una geçelim. Data’sını yazalım: 4. 4 Node’unun next’i NULL mu? Hayır. 4 Node’unun next’ine geçelim. Data değerini yazalım: 74. 74 Node’unun next değeri NULL mu? Evet. Ve gezinmeyi son node’a geldiğimiz için bitirelim. Sonuç olarak 6, 13, 4, 74 değerlerini yazdırdık ve linked list üzerinde gezinmiş olduk.
Şimdi bu işlemleri C ile yapalım.
Elimizdeki linked list’in içeriğini bilemeyeceğimizdem dolayı linked list tamamen boş olabilir. Öncelikle Head node’unu kontrol ederek linked list’in boş mu dolu mu olduğunun kontrolunu yapalım eğer doluysa gezinme işlemine başlayalım.
Gezinilen node’u atayacağımız bir temp değişkeni oluşturalım ve ilk değer olarak head’i atayalım. Eğer temp değişkeni oluşturmazsak, gezinmeyi head üzerinden yaparsak gezinme işlemi bittikten sonra o linked list’e olan erişimimizi kaybederiz. Bunu önlemek amacıyla bir temp değişkeni kullanıyoruz. Sonrasında temp’in değeri NULL olmadığı sürece çalışacak bir while döngüsü oluşturuyoruz. Döngünün içerisinde temp’in data değerini ekrana yazdırıp temp’e temp’in next’ini atayarak diğer node’a geçmiş oluyoruz.
if(head == NULL) {
printf("Linked list boş");
}
else {
struct node *temp = head;
while(temp != NULL) {
printf("%d", temp->data);
temp4 = temp->next;
}
}Bu şekilde bir single linked list ile gezinme işlemini tamamlamış oluyoruz.
Doubly Linked List Traversal
Doubly linked list ile gezinmeyi aynen singly linked list’te olduğu gibi hiçbir şeyi değiştirmeden gerçekleştirebiliriz.
Yukarıdaki doubly linked list’in gezinme işlemini kod kullanmadan mantıksal olarak yapalım.
Head NULL mu? Hayır. Head’in data değerini yazalım: 11. Head’in next’i Null mu? Hayır. Next node’una geçelim. Node’un data değerini yazalım: 2. 2 node’unun next’i NULL mu? Hayır. Next node’una geçelim. Node’un data değerini yazalım: 26. 26 node’unun next’i NULL mu? Evet. Gezinme işlemini sonlandıralım.
Doubly linked list’in traversal kodlaması’da singly linked list’te olduğu gibi olacaktır.
Circular Linked List Traversal
Circular linked list ile gezinme işlemi, son node’un NULL’U işaret etmediğinden dolayı singly ve doubly linked list’ten küçük bit fark ile gerçekleştirilir Gezinme işlemi yapılırken Node’un next değerinin NULL yerine head node’una işaret edip etmediği kontrol edilir.
Yukarıdaki circular linked list’in gezinme işlemini kod kullanmadan mantıksal olarak yapalım.
Yukarıda diğer linked list’ler için kullandığımız masntığı kullanırsak: Head head’e eşit mi? Evet eşit. Ama gezinme tamamlanmadı. Burada farklı bit metot kullanmalıyız. Öyleyse head node’unu eğer NULL değilse yazdıralım. Sonrasında head node’undan başlayarak node’ların next’nin head olup olmadığını kontrol edelim.
Head node’nunn data değerini yazalım: 17. 17 node’unun next’i head mi? Hayır. Next node’una geçelim. Node’un data değerini yazalım. 81. 81 node’unun next’i head mi? Hayır. Sıradaki node’a geçelim. Node’un data değerini yazalım. 9. 9 node’unun next’i head mi? Evet, head. Gezinmeyi bitirelim.
Şimdi bu gezinme işlemine kod ile daha iyi bir şekilde bakalım.
Öncelikle listenin boş olup olmadığını kontrol ediyoruz. Eğer boş değilse head’in data değerini ekrana yazdırıp temp değişkenine head’in head’i atıyoruz. temp’in next’i head olmadığı sürece çalışacak bir döngü ile gezinme işlemini sağlıyoruz.
if(head == NULL) {
printf("Linked list boş");
}
else {
printf("%d", head->data);
struct node *temp4 = head;
while(temp4->next != head) {
printf("%d", temp4->next->data);
temp4 = temp4->next;
}
}Doubly Circular Linked List Traversal
Doubly circular linked list için gezinmeyi circular linked list’teki gibi aynı şekilde gerçekleştiriyoruz.
Yukarıdaki doubly circular linked list’in gezinme işlemini kod kullanmadan mantıksal olarak yapalım.
Head’in data değerini yazalım: 44. 44 node’unun next’i head mi? Hayır. Next node’una geçelim. Node’un data değerine yazalım: 3. 3 node’unun next’i head mi? Hayır. Next node’una geçelim. Node’un data değerini yazalım: 65. 65 node’unun next’i head mi? Evet. Gezinme işlemini bitirelim.
Doubly circular linked list’in traversal kodlaması’da circular linked list’te olduğu gibi olacaktır.
Sonuç olarak, singly ve doubly linked list için ayrı, circular ve doubly circular linked list için birer yol izleyerek yani iki farklı yöntem kullanarak dört linked list türü için gezinme işlemlerini incelemiş olduk.