Singly Linked List , Circular Detection

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.

Singly vs. Doubly Linked List.

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.

Singly Linked List

Ö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.

Singly Linked List Circular

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.

Head ve Head1 çıktıları

Kaynak

Kaynak Kod

Okumaya Devam Et 😃

Bu yazının devamı veya yazı grubundaki diğer yazılara erişmek için bu linke tıklayabilirsiniz.