Kısa süre önce bir kodlama eğitim kampından mezun olduktan sonra, temel bilgilerimi daha iyi hale getirmek için veri yapılarını ve algoritmaları derinlemesine inceledim. Bağlı listeler nispeten basit bir veri yapısıdır, ancak ilerleyen daha karmaşık veri yapılarının temelini oluşturur. Bu makale bağlantılı listeleri - güçlü yönleri, zayıf yönleri ve bunların nasıl uygulanacağını tartışacaktır.

Veri yapıları, basitçe ifade etmek gerekirse, verileri verimli bir şekilde düzenleme ve tutma yollarıdır

Veri Yapıları Nelerdir?

Veri yapıları, basitçe ifade etmek gerekirse, verileri verimli bir şekilde organize etme ve tutma yollarıdır. Bunlar, daha sonra erişebilmemiz için bilgileri tutmamızı sağlar - belirli bir öğeyi aramak veya belirli bir sıraya sahip olacak şekilde sıralamak ve hatta büyük veri kümelerini yönetmek. JavaScript, muhtemelen çok aşina olduğunuz veri yapılarına sahiptir - diziler ve nesneler. Bunlar, dile özgü ilkel veri yapılarıdır. İlkel olmayan veri yapıları, programcı tarafından tanımlanan veri yapılarıdır. Örnekler arasında yığınlar, kuyruklar, ağaçlar, grafikler ve karma tablolar bulunur.

Bağlı Listeler Nelerdir?

Bağlantılı bir liste, öğeleri sıralı sırada tutan doğrusal bir veri yapısıdır. Tanıdık geliyor mu? Dizilere benzerler ama tamamen aynı değiller. Diziler sıfır dizinlidir , yani her dizin bir değere eşlenir ve dizinin ilk öğesi 0 dizininde başlar. Dizini bildiğiniz sürece, öğeleri diziden kolayca çekebilirsiniz.

Öte yandan, bağlantılı bir liste diğer düğümlere işaret eden düğümlerden oluşur . Her düğüm yalnızca kendisini ve bir sonraki düğümü bilir. Doğrusal veri yapısı olarak öğeler sırayla düzenlenir. Bunu bir tren olarak düşünebilirsiniz - her vagon bir sonraki vagonla bağlantılıdır ve bu böyle devam eder. Bağlı listeler endekslenmez , bu nedenle 5. öğeye doğrudan erişemezsiniz. En baştan başlamanız, bir sonrakine gitmeniz ve 5. elementi bulana kadar bir sonrakine gitmeniz gerekir. İlk düğüme kafa, son düğüme kuyruk adı verilir. Çeşitli bağlantılı liste türleri vardır - tekil bağlantılı liste, çift bağlantılı liste ve döngüsel bağlantılı liste. Bu makalenin iyiliği için, tek bağlantılı listeye odaklanacağım.

Dizideki öğelere erişmek daha kolaydır, ancak bunun bir bedeli vardır.

Neden Diziler Üzerinde Bağlantılı Listeler Kullanılır?

Merak ediyor olabilirsiniz - ama öğelere doğrudan dizilerle erişebiliyorsam neden bunu kullanalım? Bu doğru! Dizideki öğelere erişmek daha kolaydır, ancak bunun bir bedeli vardır.

Diziler dizine eklenir - bu nedenle, bir öğeyi başından veya ortasından kaldırmanız gerektiğinde , aşağıdaki tüm dizinlerin kaydırılması gerekir. Bu, bir öğe eklemeniz gerektiğinde de geçerlidir - aşağıdaki tüm öğelerin yeniden dizine alınması gerekir. Bağlantılı bir listeden öğe eklerken veya kaldırırken, yeniden dizine eklemeniz gerekmez - tek önemli olan işaret ettiği düğümdür .

Tek Bağlantılı Liste Uygulama

Çeşitli türde bağlantılı listeler vardır - tekli, ikili ve döngüsel. Tekil bağlantılı listeler, her düğümün bir değeri ve sonraki düğüme işaretçisi (kuyruk düğümüyse boş) olduğu bir tür bağlantılı liste türüdür. Öte yandan, çift bağlantılı listelerin önceki düğüme ek bir işaretçisi vardır. Dairesel bağlantılı listeler, kuyruk düğümünün baş düğüme geri döndüğü yerdir.

Not: Görsel bir öğreniciyseniz, VisuAlgo , oyun oynamak ve veri yapısının değişikliklerden geçtiğini görmek için harika bir yerdir.

Kodun tamamı için atlamak istiyorsanız: bu GitHub özüne bakın .

Bir Düğüm Oluşturma

Kullanmak için bir düğüm oluşturarak başlayalım. Bir değeri ve sonraki komşusunu gösteren bir sonraki işaretçisi olacaktır.

class Node {    
    constructor(val) {        
        this.val = val;        
        this.next = null;    
    }
}

SinglyLinkedList adlı bir sınıf oluşturarak başlayacağız ve ona listenin başı, kuyruğu ve uzunluğu için bir temel vereceğiz.

class SinglyLinkedList {    
      constructor() {        
          this.head = null;
          this.tail = null;
          this.length = 0;
      }
}

Sona bir düğüm eklemek için, listede önceden bildirilmiş bir kafa olup olmadığını kontrol edeceğiz. Değilse, baş ve kuyruğu yeni oluşturulan düğüm olacak şekilde ayarlayın. Zaten bir head özelliği varsa, kuyruktaki sonraki özelliği yeni düğüme ve kuyruk özelliğini yeni düğüm olacak şekilde ayarlayın. Uzunluğu 1 artıracağız.

push(val) {
        var newNode = new Node(val)
        if (!this.head) {
            this.head = newNode
            this.tail = newNode
        } else {
            this.tail.next = newNode
            this.tail = newNode
        }
        this.length++;
        return this;
}

Sonunda bir düğümü kaldırmak için önce listede düğüm olup olmadığını kontrol etmeliyiz. Düğümler varsa, kuyruğa ulaşana kadar listeden geçmemiz gerekir. İkinci ve son düğümün sonraki özelliğini null olarak ayarlayacağız, tail özelliğini bu düğüme ayarlayacağız, uzunluğu 1 azaltacağız ve çıkarılan düğümün değerini döndüreceğiz.

pop() {
        if (!this.head) return undefined;
        var current = this.head
        var newTail = current
        while (current.next) {
            newTail = current
            current = current.next;
        }
        this.tail = newTail;
        this.tail.next = null;
        this.length--;
        if (this.length === 0) {
            this.head = null;
            this.tail = null;
        }
        return current;
}

Düğümü baştan kaldırmak için listede düğüm olup olmadığını kontrol ederiz. Mevcut head özelliğini bir değişkende saklayacağız ve head'i geçerli kafanın bir sonraki düğümü olacak şekilde ayarlayacağız. Uzunluğu 1 azaltın ve çıkarılan düğümün değerini döndürün.

shift() {
        if (!this.head) return undefined
        var oldHead = this.head;
        this.head = oldHead.next;
        this.length--
        if (this.length===0) {
            this.head = null;
            this.tail = null;
        }
        return oldHead
}

Başlangıca bir düğüm eklemek için önce düğümü oluşturuyoruz ve listede bir head özelliği olup olmadığını kontrol ediyoruz. Öyleyse, yeni oluşturulan düğümün bir sonraki özelliğini geçerli başlığa ayarlayın, baş'ı yeni düğüme ayarlayın ve uzunluğu artırın.

unshift(val) {
        var newNode = new Node(val)
        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++
        return this
}

Listedeki konumuna göre bir düğüme erişmek için, önce dizinin geçerli bir dizin olup olmadığını kontrol edeceğiz. Ardından, bir sayaç değişkeni tutarken listeyi gözden geçireceğiz. Sayaç değişkeni indeksle eşleştiğinde, bulunan düğümü döndürürüz

get(idx) {
        if (idx < 0 || idx >= this.length) return null
        var counter = 0;
        var current = this.head
        while (counter !== idx) {
            current = current.next;
            counter++;
        }
        return current;
}

Bir düğümün konumuna göre değiştirmek için, önce get yöntemini kullanarak düğümü buluruz ve değeri yeni değere ayarlarız.

set(idx, val) {
        var foundNode = this.get(idx)
        if (foundNode) {
            foundNode.val = val
            return true;
        }
        return false;
}

Bir düğüm eklemek için önce dizini kontrol ederiz. 0'a eşitse, kaydırmayı kaldırma yöntemimizi kullanırız. Uzunluğa eşitse, listeye iteriz. Aksi takdirde, get yöntemini indeksten bir eksikte kullanarak önceki düğümü elde ederiz. Esasen, işaretçilerimizin doğru düğüme yönlendirildiğinden emin olmak için seçilen dizinden önce ve sonra düğümü takip etmemiz gerekir.

insert(idx, val) {
        if (idx < 0 || idx > this.length) return false;
        if (idx === 0) {
            this.unshift(val)
            return true;
        };
        if (idx === this.length) {
            this.push(val);
            return true;
        };
        var newNode = new Node(val);
        var beforeNode = this.get(idx-1);
        var afterNode = beforeNode.next;
        beforeNode.next = newNode;
        newNode.next = afterNode;
        this.length++;
        return true;
}

Bir düğümü konuma göre kaldırmak için, get yöntemimizi tekrar kullanacağız ve bir düğüm eklemek için kullandığımız ilkeyi kullanacağız. Seçilen dizinden önceki düğümü takip ederek, işaretçilerimizi hareket ettirebiliriz.

remove(idx) {
        if (idx < 0 || idx > this.length) return undefined;
        if (idx === this.length-1) {
            this.pop()
        }
        if (idx === 0) {
            this.shift()
        }
        var prevNode = this.get(idx-1)
        var removeNode = prevNode.next
        prevNode.next = removeNode.next
        this.length--;
        return removeNode;
}

Bağlı Listelerin Güçlü Yönleri

Bağlantılı bir liste kullanmanın yararı, öğeleri hızlı bir şekilde ekleme ve kaldırma yeteneğidir. Bağlantılı listeler dizine eklenmediğinden, öğe eklemek nispeten hızlı ve kolaydır.

Bağlı listenin sonuna eklemek , eski kuyruğun yeni düğüme işaret etmesini ve kuyruk özelliğinin yeni düğüme ayarlanmasını gerektirir. Bağlantılı listenin başına ekleme yapmak aynı öncüldür, ancak yeni düğüm eski kafayı işaret eder ve head özelliği yeni düğüme ayarlanır. Temelde aynı eylemler, dolayısıyla ekleme O (1) 'dir.

Not: Bağlantılı bir listenin ortasına ekleme, düğümünüzü (O (N)) bulmak için arama yapmayı ve ardından düğümü (O (1)) eklemeyi gerektirir.

Bağlantılı listeden bir düğümü kaldırmak kolay olabilir… ama aynı zamanda değil. Bu nereye bağlıdır. Listenin başından bir düğümü kaldırmak basittir - ikinci düğüm yeni başlık olur ve eski kafanın bir sonraki göstericisini boş olarak ayarlarız. Sondan kaldırmak daha zordur çünkü bu, tüm listeyi gözden geçirmeyi ve ikinci ile son düğüm arasında durmayı gerektirir. En kötü durum O (N) ve en iyi durum O (1).

Bağlı Listelerin Zayıf Yönleri

Bağlantılı bir listenin zayıf yönleri, yeniden dizinleme eksikliğinden kaynaklanır. Öğelere doğrudan erişemeyeceğiniz için, öğeleri aramayı ve bunlara erişmeyi zorlaştırır.

Bağlantılı bir listedeki bir düğümü aramak ve erişmek , listenin başlangıcından başlamayı ve listedeki içerik haritalarının izini takip etmeyi gerektirir. Listenin sonunda düğümü arıyorsak, tüm bağlantılı listeyi gözden geçirmek zorunda kalacağız, bu da zaman karmaşıklığını etkili bir şekilde O (N) yapmalıyız. Liste büyüdükçe işlem sayısı da artıyor. Rastgele erişime sahip bir diziyle karşılaştırıldığında - bir öğeye erişmek sabit zaman alır.

Bu kadar!

Bağlantılı listeler, başlangıçta ekleme ve silme anahtar eylemler olduğunda dizilere harika alternatiflerdir. Diziler indekslenir, bağlantılı listeler ise değildir. Bağlantılı listeler ayrıca yığınların ve kuyrukların üzerine inşa edildiği temel veri yapısıdır ve bunu daha sonraki bir makalede ele alacağım. Buraya kadar geldiyseniz, tebrikler ve umarım programlama yolculuğunuzla birlikte küçük bir külçe öğrenmişsinizdir!

Referanslar