Veri Yapılarından Linked List

Merhabalar, leetcode’da algoritma çözerken karşıma çıkan Linked List’i araştırmak ve öğrendiklerimi sizlere paylaşmak istedim. Keyifli okumalar..

Linked List en önemli özelliği 2 veriyi aynı yerde tutmasıdır: Şu anki değeri ve kendisinden sonra gelecek olan adresi. Bu özellik sayesinde veriler birbirine bağlı olmaktadır. Birbiri ardınca gelen bağlı verilere bakarsak Linked List’i aslında bir düğüm zincirine benzetebiliriz.

Linked List’in her düğümü bağlantılı olduğu düğümün adresini bildiğinden bellekte ardışık olarak yer tutmalarına gerek yoktur, düğümler bellekte başka boş buldukları alana yerleşebilirler. Linked List’i tanımlarken de boyutunu girmemize gerek yoktur. Ve böylelikle Linked List’ in boyutuna da dinamik diyebiliriz.

Singly-Linked List Yapısı

Head Linked List’in ilk elemanının adresidir. Tail ise son elemanın adresidir. Tail.next = null’dır.

Linked List’in 3 türü vardır.

Singly-Linked List( Tek Yönlü Bağlı Liste): Düğüm içerisinde sadece iki adet değişken bulunur. Bu değişkenler veri ve gelecek düğümün adresidir.

Doubly Linked List(Çift Yönlü Bağlı Liste): Düğüm içerisinde üç adet değişken bulunur. Bu değişkenler veri, bir önceki düğümün adresi ve bir sonraki düğümün adresidir.

Circular Lists (Dairesel Liste): Singly ve Doubly Linked List’in son düğümleri, ilk düğüme bağlanmasıdır. Bu listenin avantajı son düğüm ve ilk düğüm arasında tek hamlede geçiş yapılmasıdır.

Circular-Singly List (Dairesel Tek Yönlü Bağlı Liste)

Neden Linked List Kullanmalıyız Peki?

• Bir sonraki verinin adresini tutmasıyla oluşan esneklik sayesinde liste içerisinde kolaylıkla ekleme ve çıkarma yapılabilir.
• Belli bir boyutlandırma tanımı yapılmaz, istenildiği kadar veri eklenebilir. Gereksiz bellek tutumu olmaz. Maliyeti açısından avantajlıdır.
• Liste arasına istenilen yere eleman eklemesi kolaylıkla gerçekleştirilebilir. Dizilerde araya eleman ekleme durumu olduğunda sonraki adreslerin hepsinin yerinin değişmesi gerekecektir.

Linked List’in dezavantajı ise liste içerisinde arama yapmaktır. Aranılan elemana düğümlere tek tek giderek ulaşılmaktadır. Bu durum da O(n) karmaşıklığına sebep olmaktadır.

Leetcode’da “Middle of the Linked List” örneğindeki Linked List’i detaylıca bir anlayalım ve kodlayalım. Burada istenilen head’ i verilmiş olan Linked List’ deki ortadaki düğümü bulmak. Eğer iki düğüm varsa ortada iki düğümden ikincisi seçilecek.

İstenilen çıktılar

Kodlar java dilinde yazılmıştır.

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) {
         this.val = val; 
         this.next = next; }
      }

Singly List’in tanımını yapıyoruz öncelikle. Burada bir düğümün verisini ve bir sonraki düğümün adresini tanımlamış oluyoruz. Daha sonra algoritmamızda bu düğüm sınıfını kullanacağız.

class Solution {
    public ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

Oluşturduğumuz ListNode ‘u kullanarak ortadaki değeri bulacağız. Head değeri verilmiş olan düğümü slow ve fast değerlerine atıyoruz. Fast düğümün boş olup olmadığını kontrol ederken kendisi iki düğüm ilerliyor ve slow bir düğüm ilerliyor. Fast düğüm sonuna ulaştığında, yani null değerine ulaştığında, slow ortada istenilen değerde kalacaktır. Ve geriye slow değerini döndürerek ortadaki değer bulunmuş olacaktır.

Teşekkürler..