JS ALGORITHMS
Linked List (Bağlı Liste) Yapısı ve Liste Sürekli Başa Dönüyor mu (Circular)
Bu yazıda Linked List yapısını inceleyip bu listenin son elemanı tekrar başa dönüp, circular bir döngü yol açıp açmadığını inceleyeceğiz.
Linked List yani bağlı listeler. Birbirine bağlı şekilde oluşan düğüm(node) oluşur. Bu düğümü tek yönlü bağladığınızda Singly Linked List, çift yönlü bağladığınızda ise Doubly Linked List diyoruz.
Tabi bu düğümlerin birbirlerine neden bazen tek yönlü, bazende çift yönlü bağlandıklarını merak ediyor olabilirsiniz. Temel sebebi iteration (yani) düğümler üzerinde ilerlerken birisinde sadece baştan sona doğru veya herhangi bir düğümden ileriye doğru ilerlerken, doubly linked list de hem ileriye hemde geriye doğru ilerleme imkanını bize sunar.
Neyse konumuz bu değil. Konumuz Singly Linked Listi nasıl oluşturabiliriz. Aşağıdaki yapıyı oluşturmak için bize bir Düğüm(node) yapısı lazım. Düğüm yapımız bir value ve next pointer tutacak.
Öncelikle düğüm yapımızı oluşturalım.
function createNode(val) {
return { val: val, next: null };
}
Yukarıdaki yapıyı oluşturmak için oluşturduğumuz düğümleri arka arkaya eklememiz yeterli.
head = createNode(6);
head.next = createNode(3);
head.next.next = createNode(2);
head.next.next.next = createNode(1);
head.next.next.next.next = createNode(4);
Peki bunun yerine circular bir bağlantı listesi oluşturmak istersek bunu nasıl yapacağız ? Son düğüm üzerinden next → Head bağlantı kurarak bu işlemi gerçekleştireceğiz.
head1 = createNode(6);
head1.next = createNode(3);
head1.next.next = createNode(2);
head1.next.next.next = createNode(1);
head1.next.next.next.next = head1;
Gelelim bunlardan hangisi Circular , hangisi değil ? Bunu anlamanın yöntemi isCircular fonksiyonu yazıp , bunun içerisine bağlantılı listemisin ilk düğümü geçirmek. while döngüsü içerisinde dönerek düğümün elemanlarının head ile aynı olup olmadığını kontrol ederiz.
function isCircular(head) {
if (head == null) return false;
let tempNode = head.next;
while (tempNode != null) {
if (tempNode === head) return true;
else tempNode = tempNode.next;
}
return false;
}
Aşağıdaki resimde gözükeceği gibi Head için isCircular:false iken Head1 için isCircular:true değerini alır.
Kaynak
Okumaya Devam Et 😃
Bu yazının devamı veya yazı grubundaki diğer yazılara erişmek için bu linke tıklayabilirsiniz.