Veri Yapıları ve Algoritmalar

Veri Yapıları ve Algoritmalar: Bilgisayar Biliminin Temel Taşları

Veri yapıları ve algoritmalar, bilgisayar biliminin en temel ve en kalıcı konularındandır. Bir yazılım geliştiricisi olarak, doğru veri yapısını seçmek ve verimli algoritmalar tasarlamak, uygulamanızın performansını, ölçeklenebilirliğini ve bakım kolaylığını doğrudan etkiler. Bu yazıda, en yaygın veri yapılarını, temel algoritmaları, zaman ve uzay karmaşıklığı kavramlarını ve bu bilgilerin .NET ekosistemindeki pratik karşılıklarını ele alacağız.

1. Zaman ve Uzay Karmaşıklığı (Big-O Gösterimi)

Bir algoritmanın verimliliği, iki temel faktörle ölçülür:

Zaman Karmaşıklığı (Time Complexity): Algoritmanın çalışması için gereken süre (girdi büyüklüğüne bağlı olarak).
Uzay Karmaşıklığı (Space Complexity): Algoritmanın çalışması için gereken bellek miktarı.

Big-O Gösterimi (En Kötü Durum Analizi):

O(1) - Sabit Zaman: Girdi boyutundan bağımsızdır (ör. diziye indeksle erişim).
O(log n) - Logaritmik Zaman: Her adımda veri kümesini yarıya indirir (ör. Binary Search).
O(n) - Doğrusal Zaman: Girdi boyutuyla doğru orantılıdır (ör. dizi üzerinde dolaşma).
O(n log n) - Doğrusal-logaritmik Zaman: Etkili sıralama algoritmaları (ör. Merge Sort, Quick Sort).
O(n²) - Karesel Zaman: İç içe döngüler (ör. Bubble Sort, Selection Sort).
O(2^n) - Üstel Zaman: Girdi büyüdükçe çok hızlı artar (ör. Fibonacci'nin özyinelemeli hesaplanması).

2. Temel Veri Yapıları

A. Array (Dizi)

Tanım: Aynı türden verilerin, bellekte ardışık (contiguous) olarak saklandığı koleksiyondur.
Özellikler: Boyut sabittir (fixed-size). İndeksle erişim O(1), arama O(n), ekleme/silme (sona) O(1) (başa/ortaya) O(n).
Kullanım: Sabit boyutlu, hızlı indeks erişimi gerektiren durumlar.
.NET: T[], System.Array.

B. Linked List (Bağlı Liste)

Tanım: Her elemanın (node), kendisinden sonraki elemana işaret ettiği (pointer) doğrusal veri yapısıdır.
Türleri: Tek yönlü (singly), çift yönlü (doubly), dairesel (circular).
Özellikler: Ekleme/silme (başa/ortaya) O(1), arama O(n), indeksle erişim yok.
Kullanım: Sık ekleme/silme yapılan, ancak aramanın az olduğu durumlar.
.NET: LinkedList<T> (çift yönlü).

C. Stack (Yığın)

Tanım: LIFO (Last-In-First-Out) prensibiyle çalışan doğrusal veri yapısıdır.
Temel İşlemler: Push (ekle), Pop (çıkar), Peek (üstteki elemanı gör).
Karmaşıklık: Tüm işlemler O(1).
Kullanım: Geri alma (Undo/Redo), fonksiyon çağrı yığını, parantez kontrolü, derleyici tasarımı.
.NET: Stack<T>.

D. Queue (Kuyruk)

Tanım: FIFO (First-In-First-Out) prensibiyle çalışan doğrusal veri yapısıdır.
Temel İşlemler: Enqueue (ekle), Dequeue (çıkar), Peek.
Karmaşıklık: Tüm işlemler O(1).
Kullanım: İş kuyrukları, mesaj kuyrukları, BFS algoritması, yazıcı kuyrukları.
.NET: Queue<T>.

E. Hash Table (Hash Tablosu) / Dictionary

Tanım: Anahtar-değer (key-value) çiftlerini, hash fonksiyonu kullanarak depolayan veri yapısıdır.
Özellikler: Ekleme, silme, arama O(1) (ortalama). Çakışma (collision) durumunda O(n)'e düşebilir.
Kullanım: Hızlı arama, önbellekleme, veritabanı indeksleme, eşsizlik kontrolü.
.NET: Dictionary<TKey, TValue>, HashSet<T>.

F. Tree (Ağaç)

Tanım: Hiyerarşik, döngüsel olmayan bir veri yapısıdır. Kök (root), düğümler (nodes) ve yapraklardan (leaves) oluşur.
Binary Search Tree (BST): Her düğümün solunda küçük, sağında büyük değerler bulunur.
AVL / Red-Black Tree: Dengeleyici ağaçlardır. Arama, ekleme, silme O(log n).
Heap (Yığın): Maksimum veya minimum değeri hızlı bulmak için kullanılır. Priority Queue'lerin temelidir.
Kullanım: Hiyerarşik veriler (dosya sistemi, organizasyon şeması), sıralama, öncelik kuyrukları, veritabanı indeksleri (B-Tree).
.NET: SortedSet<T>, SortedDictionary<TKey, TValue> (Red-Black Tree tabanlı), PriorityQueue<TElement, TPriority> (Heap tabanlı).

G. Graph (Grafik)

Tanım: Düğümler (vertices) ve bu düğümleri birbirine bağlayan kenarlardan (edges) oluşan veri yapısıdır.
Türleri: Yönlü (directed), yönsüz (undirected), ağırlıklı (weighted), ağırlıksız (unweighted).
Temsil Yöntemleri: Komşuluk matrisi (Adjacency Matrix) O(V²) bellek, Komşuluk listesi (Adjacency List) O(V+E) bellek.
Kullanım: Sosyal ağlar, harita/rota planlama (GPS), ağ topolojisi, bağımlılık çözümleme.
.NET: Yerleşik bir Graph sınıfı yoktur; özel implementasyon veya üçüncü parti kütüphaneler (QuickGraph) kullanılır.

3. Temel Algoritmalar

A. Sıralama Algoritmaları (Sorting Algorithms)

Algoritma	En İyi	Ortalama	En Kötü	Bellek	Açıklama
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Basit, eğitim amaçlı, verimsiz.
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	Her seferinde en küçüğü seçer.
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Küçük veriler için etkili (n<50).
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Böl-ve-yönet, kararlı (stable).
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	Böl-ve-yönet, ortalama en hızlı.
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	Heap kullanır, kararsız (unstable).
Counting Sort	O(n+k)	O(n+k)	O(n+k)	O(k)	Tam sayılar için (range biliniyorsa).
Radix Sort	O(d*(n+k))	O(d*(n+k))	O(d*(n+k))	O(n+k)	Basamaklara göre sıralar.

.NET'te: Array.Sort(), List.Sort(), OrderBy()/OrderByDescending() (LINQ) kullanılır.

B. Arama Algoritmaları (Search Algorithms)

Algoritma	Zaman Karmaşıklığı	Açıklama
Linear Search (Doğrusal Arama)	O(n)	Sırasız dizide arar.
Binary Search (İkili Arama)	O(log n)	Sıralı dizide arar (diziyi ikiye bölerek).
Interpolation Search	O(log log n)	Düzgün dağılmış sıralı dizilerde.
Hash Table Search	O(1) ortalama	Hash tablosunda anahtara göre arama.

.NET'te: Array.BinarySearch(), List<T>.BinarySearch(), Dictionary<TKey, TValue>.TryGetValue().

C. Grafik Algoritmaları (Graph Algorithms)

Algoritma	Kullanım Alanı	Zaman Karmaşıklığı	Açıklama
BFS (Breadth-First Search)	En kısa yol (unweighted), bağlantı kontrolü	O(V+E)	Kuyruk (Queue) kullanır, seviye seviye ilerler.
DFS (Depth-First Search)	Döngü tespiti, topolojik sıralama	O(V+E)	Yığın (Stack) veya özyineleme kullanır.
Dijkstra	En kısa yol (weighted, pozitif)	O((V+E) log V)	Öncelik kuyruğu (Priority Queue) kullanır.
Bellman-Ford	En kısa yol (negative ağırlıklara izin verir)	O(VE)	Negatif döngü tespiti yapar.
Floyd-Warshall	Tüm çiftler arası en kısa yol	O(V³)	Dinamik programlama tabanlı.
Kruskal / Prim	Minimum Spanning Tree (MST)	O(E log V)	Bağlı ağaçlar için minimum maliyet.
Topological Sort	Bağımlılık sıralaması (DAG)	O(V+E)	Derleme sıralaması, görev planlama.

4. Algoritma Tasarım Teknikleri

Divide and Conquer (Böl ve Yönet): Problemi daha küçük alt problemlere böler, çözer ve birleştirir. (Merge Sort, Quick Sort, Binary Search).
Dynamic Programming (Dinamik Programlama): Alt problemleri çözer ve sonuçları cache'ler (memoization) veya tablo doldurur (tabulation). (Fibonacci, Knapsack, Longest Common Subsequence).
Greedy Algorithm (Açgözlü Algoritma): Her adımda yerel olarak en iyi seçimi yapar. (Dijkstra, Kruskal, Activity Selection).
Backtracking (Geri İzleme): Tüm olasılıkları dener, geçersiz yolda geri döner. (N-Queens, Sudoku çözücü).

5. Veri Yapıları ve Algoritmalar Arası İlişki

Doğru veri yapısı, doğru algoritmayı mümkün kılar. Örneğin:

Dijkstra algoritması, verimli çalışmak için bir Priority Queue (Heap) gerektirir.
Binary Search, sıralı bir dizi gerektirir.
BFS, bir Queue kullanır; DFS ise bir Stack veya özyineleme (recursion) kullanır.

6. .NET'te Kullanımlar

List<T>: Dinamik dizi (Array + List).
Dictionary<TKey, TValue>: Hash Table (O(1)).
HashSet<T>: Benzersiz eleman kümesi (Hash Table).
SortedSet<T>: Red-Black Tree (O(log n)).
Queue<T> / Stack<T>: FIFO / LIFO.
PriorityQueue<TElement, TPriority>: Heap tabanlı (Öncelik kuyruğu).

Sonuç:

Veri yapıları ve algoritmalar, yazılım geliştirmede sadece akademik bir ilgi alanı değil, günlük işlerimizin ayrılmaz bir parçasıdır. Doğru veri yapısını seçmek ve uygun algoritmayı uygulamak, uygulamanızın performansını, ölçeklenebilirliğini ve bakım kolaylığını doğrudan etkiler. Bir geliştirici olarak, bu temel bilgileri derinlemesine anlamak, sizi sadece "kod yazan" değil, "sorun çözen" bir mühendis haline getirir.

Unutmayın:

En iyi çözüm, en az kod değil, en verimli çözümdür.
Veri yapısı seçimi, mimari kararlar kadar önemlidir.
Teoriyi pratiğe dökmek, gerçek ustalığın anahtarıdır.