Veri Yapıları #1 – Linked List Mantığı ve Array ile Arasındaki Farklar

Herkese Merhaba,

Bilgisayar Mühendisliği disiplininin mihenk taşları arasında yer alan bir alandır “Veri Yapıları“. Veri Yapıları serisine Linked List ile başlamak istedim. Veri Yapıları, fakülte yıllarımda başlarda karışık gelse de öğrendikçe keyif aldığım bir alan olmuştu. Şimdi hem bu temelleri tekrar etmek hem de birilerine fayda sağlayabilmek adına sözü fazla uzatmadan Linked List’i incelemeye başlayalım.

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. Herkese mutlu günler, keyifli kodlamalar :)!

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