Veri Yapıları ve Algoritmalar

5 min readOct 12, 2021

Veri yapıları nedir? Neden kullanılır? Algoritmalar ile bağlantısı nedir? Veri yapıları ve algoritmalar hangi konularda işimize yarar?

Bu yazıda veri yapıları ile ilgili aldığım notlar ve edindiğim bilgiler bulunuyor.

Veri yapısı, bilgisayarın belleğindeki verilerin düzenlenmesidir. Algoritmalara, bu yapılardaki verileri, belirli bir veri öğesini aramak ve verileri sıralamak gibi çeşitli şekillerde yönledirir.

Peki hangi konularda bize yardımcı olurlar?

Veri depolama
Modelleme
Programcı araçları

Veri Depolama

İşimizi gerçek dünyada yaparken gerekli bilgileri kağıtlarda tutarız. Mesal bir beyaz eşya; ismini, fiyatını, markasını, modelini, özelliklerini … bir kağıtta tutarız. Bilgisayar ortamına taşıdığımıya karar verirsek veri yapıları işin içine girmiş olur. Burada da aşağıdaki sorular çıkar:

Verileri bilgisayarda nasıl saklarız?
Saklayacağımız verileri, bilgisayara geçirme yöntemimiz bin, yüz bin, milyon veri için işe yarar mı? (Scability)
Yöntemimiz, verileri ne kadar hızda siliyor, ekliyor veya belirli bir veriyi arıyor?
Sıralama işlemini nasıl yaparız?

Programcı Araçları

Tüm veri depolama yapıları, veri depolama için kullanılmaz. Bazı verileri direkt program kullanabilir. Programıcı da bu verilere ulaşımı kolaylaştırmak için veri yapılarını araç olarak kullanır.

Modelleme

Bazı veri yapıları, gerçek dünya durumlarını doğrudan modeller. Mesela havayolu rotalarını temsil etmek için grafikleri kullanabilirsiniz.

Algoritma, belirli bir görevi yerine getirmek için oluşturulan prosedürdür. Programcının aracıdır. Big O notasyonu da algoritmanın karmaşıklığını ve performansını anlamamızı sağlayan yapı.

Algoritma Oluşturmak

Bilgisayara, sorunun çözümünü adım adım anlattırız.

Verilen sayılar arasında kaç tane çift sayı olduğunu anlatan algoritma:

Burada dizi boyutu ne kadar olursa for o kadar çalışacak (1000 elemansa 1000kez dönecek …, lineer yapı).

Birde quadratic fonksiyon vardır. Bu da iç içe döngülerin oluşturduğu algoritmalardır.

Lineer → O(n)
Quadratic → O(nⁿ)
Constant → O(1)

Algoritma oluştururken en başta senaryolar kurmak gerekiyor ve bu senaryoların da bir sınıflandırmasını yapmamız lazım(kötü, orta, iyi senaryolar). Burada en kötü (Big O notasyonu) ve en iyi (Omega) algoritmaları hesaplanır. Bizim için en önemlisi tabi ki en kötü senaryodur. Bu değeri olabildiğince en hızlıya getirmemiz gerekir.

Heap Space ve Stack Memory

Heap space, nesnelere ve JRE classlarına hafıza da yer tahsis etmek için kullandığımız bir alan. Bize programda belirli bir alan verilir ve bu hafızayı aştığımızda hataya düşeriz.

Ne zaman bir nesne oluştursak her zaman heap spacede oluşur.
Gabrage Collection, bir nesnenin artık referansı olmadığında onu hafızadan silen ve yer açan bir yapıdır.
New ile açılan nesneler globalden ulaşılabilecek şekilde açılır.

Stack Memory, threadleri çalıştırırken oluşan hafızadır. Burada metoda özgü değerler bulunur, yani kısa süreli hafızalardır.

Stack Memory de LIFO (Last in First out) mantığı, son giren ilk çıkar, mantığı vardır.
Metod ne zaman çağırılırsa stackte yeri açılır. Metod biter bitmez blok kapanır.
Heape göre çok daha küçük alanı kapsar.

ABSTRACT DATA TYPE ve DATA STRUCTURES

Abstract Data Type, Data structerin bir modeli diyebiliyoruz. İnterfacelerin gövdesi boş oluyordu ve interfaceyi buna örnek verebiliriz benzer metodları vardır. ADTler implemantasyonu olmayan yapılardır. Son kullanıcı sadece fonksoyenilliği bilir, içerşdeki algoritmaz bize bağlıdır(APİ işlemleri içerisini bilmeyiz neye yaradığını biliriz).

Data Structures, Asıl implemantasyonlardır. Datayı hangi yolla etkin biçimde kullanırız(ARRAYS, LİİNKEDLİST, MAPS ….).

Stack — ADT → DS — Array, Linked list
QUEUE-ADT → DS — Array, Linked list
Priority Queues - ADT → DS — HEAP
Dictionary/Hashmap -ADT → DS-ARRAY

Veri Yapılarının Çeşitleri

Şimdi veri yapılarının çeşitlerine ve özelliklerine bakacağız. Bakacağımız veriler aşağıdaki gibi:

Arrays

Diziler, aynı tipteki verileri tuttuğumuz bir veri yapısıdır. Diziler birer nesnedir.

Dizilerde herhangi bir indexe ulaşmak çok kolaydır (ör. dizi[3]). Yani bu durumun big o notasyonu O(1)’dir.

Dizide herhangi bir değeri aramamız ise bulana kadar elemanları gezeceğimizden O(n)’dir.

Dizide ekleme yapmak istersek, 0. indexe eleman eklersek(en kötü senaryo) elemanları birer index kaydıracağımızdan O(n)’dir.

Dizide silme işlemi de ekleme ile aynı şekildedir. Big O notasyonu O(n)’dir.

Dizilerin dezavantajları:
Boyut belirtmek zorundayız.(Dinamik diziler farklı yapılardır.)
Tüm veriler aynı veri yapısında olmalıdır.

Dizilerde tek boyutlu, iki boyutlu ve çok boyutlu diziler diye ayrılıyor. İki boyutlu dizilerde koordinat sistemi mantığı vardır. Yani yatay düzlemin yanında dikey düzlem değeri de verilir.

Dinamik diziler: Bu dizilerde bir boyut vermemize gerek kalmıyor. Bu dizi türünde ekleme işlemlerinde bir farklılık oluşuyor. Bu farklılık, diziye bir eleman eklediğimizde önceki diziyi kopyalayıp boş indexler ortaya çıkartmış oluyor. Yani 16 elemanlı diziye eleman eklersek 16lık bir alan daha açılacak ve toplam 32 indexli bir dizi oluşacak. Bu durumda hafıza yönetiminde bir dezavantaj ortaya çıkartacak. Arraylistler bu mantıkla çalışırlar, artma miktarı değişebilir(iki kat yerine (n + n/2 + 1) olabilir).

Linked List (Bağlı Liste)

Lineer yapıdadırlar. Dizilerden farklı olarak art arda sıralanmayabilirler. Çünkü listede ki elemanlar birbirlerine pointer ile bağlanırlar.

Dizilere göre bir avantajı;

Listelerde boyut belirlememize gerek yoktur böylece kullanmadığımız yer için hafızada yer ayırmamıza gerek kalmayacak.
Linked listte elemanlar birbirlerine pointerler ile bağlı olduğundan araya istediğimiz elemanı daha kolay sokabiliriz. Tabi elemanı koyarken tekrar elemanları bir birine bağlamamız için eleman pointer adreslerini ayrı olarak tutmamız gerekecek.

Dizilere göre dezavantajı ise;

Rastgele elemana ulaşmak için elemanların adreslerini tek tek dolaşmamız gerekiyor.
Pointerler için ayrıca hafıza ayırmamızdır.

Arama → O(n)
Ekleme→ O(n)
İndexe ulaşma→ O(n)
Silme→ O(n)

Circular Linked List (Dairesel Bağlı Liste)

Tek yönlüde bağlı listede ilk elemanı belirleyemeyiorduk ama dairesel bağlı liste ile bunu yapabilioruz.

Double Linked List (Çift Yönlü Bağlı Liste)

Bu bağlı liste çeşidi ile hem ileri hem geriye gitme şansımız oluyor ve böylece liste aralarına eleman ekleme ve silme işlemlerimiz hız kazanıyor.

DezAvantajı ise, fazladan önceki adres pointeri ile hafıza kaybı, aynı zamanda herhangi işlemde iki pointeri birden değiştirmemiz gerekecek.

Çift yönlü bağlı listede yukarıda linked listte ayrı olaran önceki elemanın referansını tutan bir veri daha işin içine girdiğinden işlemlerde buna göre değişir. Yani ilk elemanın, previ null olur. Sonraki elemanlarda previ önceki elemanın referansı bulunur.

Queue (Kuyruk Veri Yapısı)

FIFO (First in First Out), ilk gelen ilk çıkar, mantığı vardır.

Ekleme işleminde kuyruk doluysa farklı dönüşler olur(overflow condection) Kuyrukta eleman silececeğimiz zaman eleman yoksa (sunderflow condition).

Hashtable

Bu veri yapısı içerisine key ve value bulunur. Her key tekil bir değere sahiptir. Hashtable, hashing şifreleme tekniğini kullanır ve elde edilen hasncode’u keyin indexi olarak kullanır.

Bu yapının altında diziler yatar. Aynı değerler geldiğinde aynı dizi indexi gelir ve alta linked list ile bağlanır. Böylece index numarasıyla beraber linkedlistlere ulaşbilme imkanımız oluyor.

Hashtable<Integer, String> names= new Hashtable<Integer, String>();
name.put(1,”Hasan”);