Bölüm 3 / 33
Veri Yapıları ve Algoritmalar
Veriyi bellekte düzenleme, arama, sıralama ve verimli işlem yapma kavramları.
3 canlı örnek — seçerek incele
İlgili kavramlar: Stack, Queue, Array
Stack vs Queue
Veriyi bellekte belirli erişim ve işlem ihtiyaçlarına göre düzenleme biçimi.
Bir problemi sonlu ve açık adımlarla çözen yöntem.
Elemanları sıralı ve indeksle erişilebilir biçimde tutan koleksiyon.
Kapasitesi ihtiyaç oldukça büyüyebilen dizi yapısı.
- ListT
Sıralı veri koleksiyonu için genel yapı.
Elemanların birbirine referanslarla bağlandığı liste.
- NodeT
Bağlı liste, ağaç veya graph içindeki veri ve bağlantı birimi.
Son giren ilk çıkar mantığıyla çalışan LIFO veri yapısı.
İlk giren ilk çıkar mantığıyla çalışan FIFO veri yapısı.
Her iki uçtan ekleme ve çıkarma yapılabilen kuyruk.
Elemanların giriş sırasından çok önceliğine göre işlendiği kuyruk.
- SetT
Tekrarsız değerler tutan koleksiyon.
Anahtar-değer çiftleriyle veri saklayan yapı.
Anahtarı hash fonksiyonuyla bir konuma eşleyerek hızlı erişim sağlayan yapı.
Veriyi sabit boyutlu sayısal veya metinsel özete dönüştüren fonksiyon.
Farklı anahtarların aynı hash konumuna düşmesi.
- TreeO
Düğümlerin ebeveyn-çocuk ilişkisiyle hiyerarşik düzenlendiği yapı.
Ağaç yapısının en üst düğümü.
Altında çocuk düğüm bulunmayan ağaç düğümü.
Her düğümün en fazla iki çocuk taşıdığı ağaç.
Solunda küçük, sağında büyük değerler tutarak aramayı hızlandıran ağaç.
Yüksekliğini dengeli tutarak işlemlerin kötüleşmesini önleyen ağaç.
- HeapO
Minimum veya maksimum elemana hızlı erişim sağlayan özel ağaç yapısı.
- Trieİ
Metin ve prefix aramalarında karakterleri ağaç biçiminde saklayan yapı.
Düğümler ve bu düğümler arasındaki kenarlardan oluşan ilişki modeli.
Graph içindeki düğüm.
- EdgeO
Graph içindeki iki düğüm arasındaki bağlantı.
Bağlantıların yön taşıdığı graph.
Kenarların mesafe, maliyet veya süre gibi ağırlık taşıdığı graph.
Bir graph düğümünün komşularını listelerle saklama yöntemi.
Verinin satır ve sütunlardan oluşan iki boyutlu yapıda tutulması.
Sabit sayıda ve sıralı değerden oluşan veri grubu.
Adlandırılmış alanlardan oluşan veri nesnesi.
Algoritmanın girdi büyüdükçe zaman veya bellek maliyetinin nasıl arttığını ifade eder.
Algoritmanın çalışma süresinin girdi büyüklüğüne bağlı maliyeti.
Algoritmanın kullandığı ek belleğin girdi büyüklüğüne bağlı maliyeti.
- O(1)O
Girdi boyutundan bağımsız sabit maliyet.
Girdi büyüdükçe yavaş artan logaritmik maliyet.
- O(n)O
Girdiyle doğru orantılı doğrusal maliyet.
Verimli genel sıralama algoritmalarında sık görülen maliyet.
İç içe karşılaştırmalar nedeniyle karesel büyüyen maliyet.
Elemanları baştan sona tek tek kontrol eden arama.
Sıralı veri üzerinde arama aralığını her adımda ikiye bölen yöntem.
Verileri belirli bir anahtara göre sıralama işlemi.
Komşu elemanları karşılaştırıp yer değiştirerek sıralayan öğretici algoritma.
Veriyi bölüp sıralı parçaları birleştirerek çalışan algoritma.
Pivot seçip veriyi küçük ve büyük gruplara ayıran sıralama algoritması.
Eşit anahtarlı elemanların önceki sırasını koruyan sıralama.
Bir veri yapısındaki elemanları belirli düzende ziyaret etme.
Bir graph veya ağacın dalında mümkün olduğunca derine ilerleyen arama.
Düğümleri seviye seviye ziyaret eden arama.
Özyinelemeli fonksiyonun sonsuza gitmesini önleyen durma koşulu.
Fonksiyon sonuçlarını saklayarak aynı hesabı tekrar yapmama tekniği.
Problemi örtüşen alt problemlere ayırıp sonuçları saklayarak çözme yöntemi.
Her adımda o an için en iyi görünen seçimi yapan yaklaşım.
Bir seçim başarısız olduğunda geri dönüp başka seçeneği deneyen yöntem.
Büyük veri kümesini sayfalara bölerek sunma mantığı.
Listeleme veya veritabanı sorgusunda mevcut konumu temsil eden işaretçi.
Bir koleksiyon içindeki elemanın konumunu veya hızlı erişim yapısını ifade eder.
Tekrarlanan kayıtları belirleyip tekilleştirme işlemi.
Veriyi karşılaştırılabilir veya standart biçime dönüştürme işlemi.
Nesneyi JSON, binary veya metin biçiminde aktarılabilir veriye dönüştürme.
Aktarılmış veriyi tekrar program nesnesine dönüştürme.
| Kavram | Seviye | Kısa açıklama |
|---|---|---|
| Data Structure | T | Veriyi bellekte belirli erişim ve işlem ihtiyaçlarına göre düzenleme biçimi. |
| Algorithm | T | Bir problemi sonlu ve açık adımlarla çözen yöntem. |
| Array | T | Elemanları sıralı ve indeksle erişilebilir biçimde tutan koleksiyon. |
| Dynamic Array | O | Kapasitesi ihtiyaç oldukça büyüyebilen dizi yapısı. |
| List | T | Sıralı veri koleksiyonu için genel yapı. |
| Linked List | O | Elemanların birbirine referanslarla bağlandığı liste. |
| Node | T | Bağlı liste, ağaç veya graph içindeki veri ve bağlantı birimi. |
| Stack | T | Son giren ilk çıkar mantığıyla çalışan LIFO veri yapısı. |
| Queue | T | İlk giren ilk çıkar mantığıyla çalışan FIFO veri yapısı. |
| Deque | O | Her iki uçtan ekleme ve çıkarma yapılabilen kuyruk. |
| Priority Queue | O | Elemanların giriş sırasından çok önceliğine göre işlendiği kuyruk. |
| Set | T | Tekrarsız değerler tutan koleksiyon. |
| Map / Dictionary | T | Anahtar-değer çiftleriyle veri saklayan yapı. |
| Hash Table | O | Anahtarı hash fonksiyonuyla bir konuma eşleyerek hızlı erişim sağlayan yapı. |
| Hash Function | O | Veriyi sabit boyutlu sayısal veya metinsel özete dönüştüren fonksiyon. |
| Collision | O | Farklı anahtarların aynı hash konumuna düşmesi. |
| Tree | O | Düğümlerin ebeveyn-çocuk ilişkisiyle hiyerarşik düzenlendiği yapı. |
| Root Node | T | Ağaç yapısının en üst düğümü. |
| Leaf Node | T | Altında çocuk düğüm bulunmayan ağaç düğümü. |
| Binary Tree | O | Her düğümün en fazla iki çocuk taşıdığı ağaç. |
| Binary Search Tree | O | Solunda küçük, sağında büyük değerler tutarak aramayı hızlandıran ağaç. |
| Balanced Tree | İ | Yüksekliğini dengeli tutarak işlemlerin kötüleşmesini önleyen ağaç. |
| Heap | O | Minimum veya maksimum elemana hızlı erişim sağlayan özel ağaç yapısı. |
| Trie | İ | Metin ve prefix aramalarında karakterleri ağaç biçiminde saklayan yapı. |
| Graph | O | Düğümler ve bu düğümler arasındaki kenarlardan oluşan ilişki modeli. |
| Vertex | O | Graph içindeki düğüm. |
| Edge | O | Graph içindeki iki düğüm arasındaki bağlantı. |
| Directed Graph | O | Bağlantıların yön taşıdığı graph. |
| Weighted Graph | O | Kenarların mesafe, maliyet veya süre gibi ağırlık taşıdığı graph. |
| Adjacency List | İ | Bir graph düğümünün komşularını listelerle saklama yöntemi. |
| Matrix | O | Verinin satır ve sütunlardan oluşan iki boyutlu yapıda tutulması. |
| Tuple | T | Sabit sayıda ve sıralı değerden oluşan veri grubu. |
| Record | T | Adlandırılmış alanlardan oluşan veri nesnesi. |
| Big O Notation | O | Algoritmanın girdi büyüdükçe zaman veya bellek maliyetinin nasıl arttığını ifade eder. |
| Time Complexity | O | Algoritmanın çalışma süresinin girdi büyüklüğüne bağlı maliyeti. |
| Space Complexity | O | Algoritmanın kullandığı ek belleğin girdi büyüklüğüne bağlı maliyeti. |
| O(1) | O | Girdi boyutundan bağımsız sabit maliyet. |
| O(log n) | O | Girdi büyüdükçe yavaş artan logaritmik maliyet. |
| O(n) | O | Girdiyle doğru orantılı doğrusal maliyet. |
| O(n log n) | O | Verimli genel sıralama algoritmalarında sık görülen maliyet. |
| O(n²) | O | İç içe karşılaştırmalar nedeniyle karesel büyüyen maliyet. |
| Linear Search | T | Elemanları baştan sona tek tek kontrol eden arama. |
| Binary Search | O | Sıralı veri üzerinde arama aralığını her adımda ikiye bölen yöntem. |
| Sorting | T | Verileri belirli bir anahtara göre sıralama işlemi. |
| Bubble Sort | T | Komşu elemanları karşılaştırıp yer değiştirerek sıralayan öğretici algoritma. |
| Merge Sort | O | Veriyi bölüp sıralı parçaları birleştirerek çalışan algoritma. |
| Quick Sort | O | Pivot seçip veriyi küçük ve büyük gruplara ayıran sıralama algoritması. |
| Stable Sort | O | Eşit anahtarlı elemanların önceki sırasını koruyan sıralama. |
| Traversal | O | Bir veri yapısındaki elemanları belirli düzende ziyaret etme. |
| Depth First Search | O | Bir graph veya ağacın dalında mümkün olduğunca derine ilerleyen arama. |
| Breadth First Search | O | Düğümleri seviye seviye ziyaret eden arama. |
| Recursion Base Case | O | Özyinelemeli fonksiyonun sonsuza gitmesini önleyen durma koşulu. |
| Memoization | O | Fonksiyon sonuçlarını saklayarak aynı hesabı tekrar yapmama tekniği. |
| Dynamic Programming | İ | Problemi örtüşen alt problemlere ayırıp sonuçları saklayarak çözme yöntemi. |
| Greedy Algorithm | İ | Her adımda o an için en iyi görünen seçimi yapan yaklaşım. |
| Backtracking | İ | Bir seçim başarısız olduğunda geri dönüp başka seçeneği deneyen yöntem. |
| Pagination Algorithm | O | Büyük veri kümesini sayfalara bölerek sunma mantığı. |
| Cursor | O | Listeleme veya veritabanı sorgusunda mevcut konumu temsil eden işaretçi. |
| Index | T | Bir koleksiyon içindeki elemanın konumunu veya hızlı erişim yapısını ifade eder. |
| Deduplication | O | Tekrarlanan kayıtları belirleyip tekilleştirme işlemi. |
| Normalization | O | Veriyi karşılaştırılabilir veya standart biçime dönüştürme işlemi. |
| Serialization | O | Nesneyi JSON, binary veya metin biçiminde aktarılabilir veriye dönüştürme. |
| Deserialization | O | Aktarılmış veriyi tekrar program nesnesine dönüştürme. |
Bölüm uygulamaları
Bu bölümü bitirmeden önce şunları deneyin veya açıklayın.
- Bir ürün listesini fiyat ve ada göre sıralayın; doğrusal arama ile binary search farkını açıklayın.
- Stack, queue, set ve map için gerçek web uygulamasından birer kullanım örneği bulun.
- Bir kategori ağacını ve bir kullanıcı-arkadaş graph yapısını şema olarak çizin.