JavaScript ile Singly LinkedList-1
Bu yazımda Üniversitede kendi dersim olan Veri Yapıları(DataStructure) konusuna çalışırken not almaya karar verdim ve tüm öğrendiklerimi bu şekilde yazıp benden sonra gelecek arkadaşlara yardımcı olmak amacı ile başladım. Umarım faydalı bir yazı olmuştur. Konuya geçmeden önce şunu söylemek istiyorum. Okulda Veri Yapıları öğrenirken kullandığımız programlama dilleri C# ve Java peki neden JavaScript ile yazıyorum derseniz JavaScript🐱👤 ile oluşturulmuş türkçe kaynak pek bulamadığımdan ve JavaScript hayranlığımdan olsa gerek JS ile yazmaya karar verdim. Lafı Fazla Uzatmadan hadi başlayalım.🚦
Peki nedir bu bağlı liste ?(linked list). Aynı kümeye ait verilerin bellek üzerinde bir gösterici (pointer) yardımı ile birbirine bağlanması sonucu oluşturulan veri yapısıdır. Bu veri yapısındaki bütün elemanların ortak noktası kendi içlerinde bağlantı bilgisi içeren kendi türünden bir ya da daha fazla göstericiye sahip olmasıdır. Veri yapısı, kümedeki herhangi bir elemanın, kendisinden önce ve kendisinden sonra hangi elemanın bulunduğu bilgisi bu göstericilere değer vererek kurulur.
“ Neden Array varken Linked List tercih edelim ? dediğinizi duyar gibiyim “🙉
Aslında linked list kullanımı hem avantaj hem de dezavantaj içerir , önce bunları inceleyelim :
dezavantaj: Bağlı listedeki öğelerin sıralı dizinlere sahip olmaması ve bu da rastgele erişime izin vermemesi anlamına geliyor , yani biz bir ekleme , silme gibi işlemler yapmaya kalkar isek tüm bağlı listeyi tamamen dolaşmamız (sequential) gerekir ama Array kullanımında ise index numarasına (random) göre arama yapıp daha hızlı işlemleri gerçekleştirebiliriz.
avantaj: Arrayler’de veri ekleme ve silme işlemleri pahalı olabilir. Bağlantılı liste ise dinamik boyuta sahiptir ve ekleme ve silme işlemini çok kolaylaştırır. Mesela; 2000 elemanlı bir dizimiz olsun. Bu dizinin 500.cü elemanını silmek istediğimizde, bu elemandan sonra gelen her eleman bir sıra geri kaydırılacak bu da performans kaybına yol açacaktır. Linked List’te ise bu işlem sadece basit [pointer] operasyonlarıyla gerçekleştirilir ve kaydırma işlemlerine gerek kalmaz. Bu sayede performanstan kazanç sağlanmaktadır.
Bağlantılı liste türleri : Tek bağlantılı liste (singly linked list), çift bağlantılı (doubly linked list) liste ve döngüsel bağlantılı liste ( circular linked list)gibi farklı bağlantılı liste türleri vardır. Bu yazımda (singly linked list)ile başlayıp daha sonra diğer listeleri anlatmayı düşünüyorum., Hadi gelin JavaScript’teki tek bağlantılı listeden (singly linked list) başlayalım.
Singly Linkedlistin her düğümü’nün(node) özellikleri şöyle : değer(value) sonraki referans(next) .
Singly LinkedList’in özellikleri şöyle : bağlantılı listenin baş(head), kuyruk(tail) ve uzunluk (length) özniteliği olacaktır.
Linked List Create :
Push (Sona Eleman Ekleme) :
Yeni bir düğüm (node) nesnesini oluşturduk. Eğer herhangi bir değer ataması olmamış ise, baş(head) ve kuyruk(tail) kısmı aynı değeri işaret etmiş olacaklar. Eğer başlangıçta baş (head) varsa kuyruk(tail) değerimize sonraki (node)’u atadık. Artık yeni kuyruk (tail) değerimiz yeni oluşan düğüm(node) olmuş oldu.
Pop (Sondan Eleman Silme) :
Burada dikkat edilecek yer başlangıçta dezavantaj olarak bahsettiğimiz Array(dizi) olmadığı için son elemana kadar tüm düğümlerin(node) üzerinden geçmesidir. Diğer önemli nokta son düğüm yapımız kuyruk(tail) olduğu için (tail) değerini referans alabiliriz.
Eğer listemiz boş ise null veya undefined (size kalmış) dönüyoruz. Eğer listemizde tek değer varsa (head) ve (tail) ikisi aynı düğüm olacağı için her ikisini de null yapmalıyız.
Eğer listemizden birden fazla düğüm varsa tüm düğümleri next değeri null olana kadar döngüde aram işlemi yapmalıyız. null düğünümden bir önceki elemanı döner while döngüsü , onu referans olarak alıp tail’e atadığımız zaman son düğümü silmiş oluruz.
Unshift (Listenin Başına Eleman Ekleme) :
Yeni bir değişken ekleneceği zaman düğümü (linked list) oluşturuyoruz. Eğer başta listemiz boş ise oluşturulan düğümü (linked list) (head), ve ( tail) ’e atıyoruz.
Başlangıç değişkenimiz’ i (this.head) yeni oluşan düğümün(node.next) değerine atıyoruz. Ardından yeni başlangıç değerine ise oluşan yani node değerini entegre ediyoruz.
Shift (Listenin Başından Eleman Silmek) :
Eğer liste boş ise (null) veya (undefined) dönecek. Silinecek eleman baş(head) kısmı burada dikkat edilmesi gereken önemli nokta eğer head kısmını kestiğimiz zaman head kısmına next ile bağlı olan tüm elemanlar uzayda kaybolmaması için (:D) , this.head.next değerlerini this.head ‘e atamamız şart , daha sonra liste uzunluğunu bir azaltıyoruz.
Get (Listenin Seçilmiş Değerini Dönmek) :
Bağlı listenin(linked list)dizinleri olmasa da, yine de verilen dizine göre düğümü(node) bulabiliriz. Öncelikle, verilen dizinin sıfırdan büyük ve listenin uzunluğundan küçük veya ona eşit olduğundan emin olun. Daha sonra dizine ulaşana kadar listeyi gözden geçiririz.
Set (Listenin Seçilmiş Değerine Değişken Atamak) :
Listemizdeki bir düğümü(node) değiştirmek istersek ne olur? Düğümü Get() ile buluyoruz ve düğümü(node) verilen verilerle ayarlıyoruz.
Insert (Listenin Seçilmiş Indexin Değişken Atamak) :
Listeye yeni bir düğüm(node) eklemek istediğimizde, önce indeksin 0'dan büyük ve uzunluktan küçük olup olmadığını kontrol edin. İndeks uzunluksa, sadece push() kullanıyoruz, indeks 0 ise, unshift() kullanıyoruz.
İnsert()’te indeksler için, indeks-1'deki düğümü almalıyız(previous) ve bu düğümün bir sonraki özelliğini (next) yeni düğüm(new node) olacak şekilde ayarlamalıyız ve yeni düğümün sonraki özelliğini(new node.next) önceki sonraki özellik olacak şekilde ayarlamalıyız, sonra uzunluğu artırmalıyız .
Aslında karışık geldiğinin farkındayım 😁 bende ilk başta anlamamıştım. Bunun için sizlere video anlatımlı bir site önereceğim biraz kurcaladıktan sonra kapmış olursunuz 👍🎉. [LINK]
Remove (Listenin Seçilmiş Değerini Kaldırıyoruz) :
Pop() ve Unshift() ’in aksine, remove() işlevi düğümü verilen index değerine göre kaldırma işlemi yapar. Burada belli bir index değerini kaldırdığımız zaman eğer ardından gelen düğümler (node) varsa , düğümlerin uzay boşluğunda kaybolmaması için previous ve next işlemleri uygulanacak.
Reverse (Listenin Seçilmiş Değerini Kaldırıyoruz) :
Burada ise en çok kafamın karıştığı nokta oldu.😪 Bunun için en iyi açıklama yönteminin biraz görsel ile aklınızda harika bir şekilde kalacağını düşündüm(video). Reverse metodu’nun iki çözüm yolu bulunmakta ,( Iteravtive ve Recursive) çözüm.
Bu 📺videoda aşağıda yaptığımız Iterative yöntemi kullanıyorlar. Reverse yapısında düğümlerin(node) bulundukları yer önemli değil. Önemli olan işaret ettikleridir.🚀
GetLast (Listenin Son Eleman Alma) :
GetFirst — Clear — Size ( Listenin Ilk Eleman ı— Temizleme — Boyutu Dönmek)
Bu içeriklerin devamı gelecek… JavaScript ile mutlu günler.
twitter :https://twitter.com/M_ckymn
github :https://www.github.com/ckymn
linkedin :https://www.linkedin.com/in/ckymn/
Referances :
