(Kendime Notlar-1) Veri Yapılarına Giriş ve Linked List Mantığı

Herkese merhaba,

Bir süredir Medium’da bir yazı dizisine başlamak aklımdaydı ancak ne yapacağım konusunda çok da bir fikrim yoktu. Yazmak her şeyden önce bana iyi gelen bir şey olduğu için bir şeyler karalamayı uzun süredir oldukça istiyordum. Nihayetinde düşündüm ki Bilgisayar Mühendisliği’nin en temel alanlarından birisi olan Veri Yapıları’na dair (benim de üniversite döneminde büyük bir keyif aldığım ancak ilk başlarda bir o kadar da bana karmaşık gelen bir konu olmuştu) kendimce notlar oluşturmak ve bunları paylaşmak istedim.

Hem kendimce bir tekrar yapmış olacağım, hem de kendime ve bir şekilde bu yazılara ulaşan insanlara belki ufak da olsa bir katkı sağlayacağım motivasyonuyla “Veri Yapıları” serimi başlatmış bulunuyorum.

Unutmadan Gelebilecek Eleştirilere Karşı Ufak Bir Not: Akademisyen veya bilirkişi değilim, en büyük amacım kendime bir arşiv oluşturmak, dijital dünyada keyif aldığım bir alana dair izler bırakabilmek.

LINKED LIST (BAĞLI LİSTE) NEDİR?

İçerisinde integer veri ve bir sonraki düğümü işaret eden pointer barındıran temsili bir Linked List gösterimi

Linked List içindeki elemanların doğrusal olarak RAM’de tutulduğu özel bir veri saklama yapısıdır. Linked List node altyapısı ile çalışır. Hafızada verilerin doğrusal olarak (Linked List yapısında, dizide olduğu gibi veri sıralı bir şekilde tutulmaz burası karıştırılmamalı) tutulması yönüyle dizilere benzese de aralarında önemli performans ve işlevsellik farkları mevcuttur.

LINKED LIST vs ARRAY (DİZİ) ARASINDAKI FARKLAR

Array vs Linked List

1. Dizilerde ulaşmak istediğimiz elemana indisini girerek ulaşırız. Linked List’lerde ise ulaşmak istediğimiz elemanlara point eden pointerlar vasıtasıyla ulaşırız.
2. Dizilerde eleman ekleme, silme gibi işlemler Linked List’lere göre performans açısından daha maliyetlidir. Örneğin; 1000 elemanlı bir dizimiz tanımlı 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.
3. Linked List dinamiktir. Dizi tanımlaması yapılırken en başında veri boyutunu belirtmemiz gerekirken, Linked List’lerde ihtiyaç duyduğumuzda boyutu artırabilir, silme işlemlerimizden sonra Linked List boyutumuzu küçültebiliriz.

Bu kıyaslamada Linked List’in önemli avantajlarından bahsettik elbette hiçbir şey her şeyiyle mükemmel olmuyor. Bazı noktalarda ise Linked List’in dezavantajları bulunuyor. Array ve Linked List’lerin avantajlı ve dezavantajlı olduğu hususları göz önünde bulundurarak tasarımımızı buna göre seçmemiz çok daha yerinde bir hamle olacaktır.

LINKED LIST’LERİN DEZAVANTAJLARI

1. Linked List’lerde random bir veriye ulaşım dizilere göre maliyetlidir. Dizilerde dilediğimiz elemana indisini girerek ulaşabiliyorken, Linked List’lerde ise pointerlar aracılığı ile liste üzerinde gezinmemiz gerekir. Bu da performans kaybına yol açar. (Yani bir dizide 750. elemana ulaşmak istediğimizde indisi girerek direkt ulaşabilirken, Linked List’lerde bu elemana ulaşmak için listenin en başından 750. elemana kadar gezinmemiz gerekir.)
2. Linked List’ler, sadece veriyi değil veri ile birlikte bir sonraki düğüme işaret eden pointerları da tuttuğumuz için dizilere göre hafızada daha fazla yer kaplar.

Linked List yapısının teoriğine ufak bir giriş yaptık, bir sonraki yazıda bir Linked List yapısı oluşturup içerisine elemanlarımızı gireceğiz.

Atladığım veya yanlış yazdığım bir husus olduysa yorumlarda bunu belirtmeniz beni çok mutlu edecektir.

Kaynaklar:

1. https://www.studytonight.com/data-structures/linked-list-vs-array
2. C ve Java ile Veri Yapılarına Giriş, 2. Baskı - Olcay Taner Yıldız
3. http://www.necessaryandsufficient.net/2008/05/differences-between-arrays-and-linked-lists/
4. https://www.youtube.com/watch?v=lC-yYCOnN8Q , mycodeschool