Veri yapısı

Veri yapıları soyut veri türlerinin (ADT (abstract data types)) temelini oluşturur. ADT, veri tipinin mantıksal formunu tanımlar. Veri yapısı veri tipinin fiziksel formunu uygular.

Farklı türdeki veri yapıları, farklı türdeki uygulamalara uygundur ve bazıları belirli görevlere oldukça uzmanlaşmıştır. Örneğin, ilişkisel veritabanları genellikle veri alımı için B-ağacı dizinlerini kullanırken, derleyici uygulamaları genellikle tanımlayıcıları aramak için karma tabloları kullanır.

Veri yapıları, büyük veritabanları ve internet indeksleme hizmetleri gibi kullanımlar için büyük miktarlardaki verileri verimli bir şekilde yönetmeye yönelik bir araç sağlar. Genellikle verimli veri yapıları, verimli algoritmalar tasarlamanın anahtarıdır. Bazı resmi tasarım yöntemleri ve programlama dilleri, yazılım tasarımında anahtar düzenleme faktörü olarak algoritmalardan ziyade veri yapılarını vurgular. Veri yapıları, hem ana bellekte hem de ikincil bellekte saklanan bilgilerin depolanmasını ve alınmasını düzenlemek için kullanılabilir.

Veri yapıları, çeşitli programlama dilleri ve teknikleri kullanılarak uygulanabilir, ancak hepsi, verileri verimli bir şekilde organize etmek ve depolamak gibi ortak bir hedefi paylaşır. Veri yapıları genellikle bir bilgisayarın, kendisi de bellekte saklanabilen ve program tarafından değiştirilebilen, bir bellek adresini temsil eden bir bit dizisi olan bir işaretçi tarafından belirtilen, belleğindeki herhangi bir yere veri getirme ve saklama becerisine dayanır. Dolayısıyla dizi ve kayıt veri yapıları, veri öğelerinin adreslerinin aritmetik işlemlerle hesaplanmasına dayanırken, bağlantılı veri yapıları, veri öğelerinin adreslerinin yapının kendisi içinde saklanmasına dayanır. Veri yapılandırmasına yönelik bu yaklaşımın, algoritmaların verimliliği ve ölçeklenebilirliği üzerinde derin etkileri vardır. Örneğin, dizilerdeki bitişik bellek tahsisi, hızlı erişim ve değişiklik işlemlerini kolaylaştırarak sıralı veri işleme senaryolarında performansın optimize edilmesini sağlar.

Bir veri yapısının uygulanması genellikle o yapının örneklerini yaratan ve işleyen bir dizi prosedür yazmayı gerektirir. Bir veri yapısının verimliliği bu işlemlerden ayrı olarak analiz edilemez. Bu gözlem, soyut bir veri türü, üzerinde gerçekleştirilebilecek işlemlerle dolaylı olarak tanımlanan bir veri yapısı ve bu işlemlerin matematiksel özellikleri (yer ve zaman maliyetleri dahil) şeklindeki teorik kavramı motive eder.

Genellikle daha basit ilkel veri türleri üzerine inşa edilen çok sayıda veri yapısı türü vardır. İyi bilinen örnekler şunlardır:

• Dizi, belirli bir sıradaki, genellikle hepsi aynı türde olan bir dizi öğedir (dile bağlı olarak, tek tek öğelerin tümü aynı türde olmaya zorlanabilir veya hemen hemen her türde olabilir). Hangi öğenin gerekli olduğunu belirtmek için öğelere bir tam sayı dizini kullanılarak erişilir. Tipik uygulamalar dizilerin elemanları için bitişik hafıza kelimeleri tahsis eder (ancak bu her zaman bir zorunluluk değildir). Diziler sabit uzunlukta veya yeniden boyutlandırılabilir olabilir.
• Bağlantılı liste (aynı zamanda liste olarak da adlandırılır), her düğümün kendine ait bir değere sahip olduğu ve bağlantılı listedeki bir sonraki düğüme işaret ettiği, düğüm adı verilen herhangi bir türdeki veri öğelerinin doğrusal bir koleksiyonudur. Bağlantılı listenin diziye göre temel avantajı, listenin geri kalanının yeri değiştirilmeden değerlerin her zaman verimli bir şekilde eklenip çıkarılabilmesidir. Ancak belirli bir öğeye rastgele erişim gibi diğer bazı işlemler, listelerde dizilere göre daha yavaştır.
• Bir kayıt (aynı zamanda tuple veya yapı olarak da adlandırılır), toplu bir veri yapısıdır. Kayıt, genellikle sabit sayı ve sırayla diğer değerleri içeren ve genellikle adlara göre dizine eklenen bir değerdir. Kayıtların öğelerine genellikle alanlar veya üyeler denir. Nesne yönelimli programlama bağlamında kayıtlar, onları nesnelerden ayıran düz eski veri yapıları olarak bilinir.
• Hash haritaları olarak da bilinen hash tabloları, anahtarlara dayalı olarak değerlerin hızlı bir şekilde alınmasını sağlayan veri yapılarıdır. Anahtarları bir dizideki indekslere eşlemek için bir karma işlevi kullanırlar ve ortalama durumda sabit zamanlı erişime izin verirler. Hash tabloları sözlüklerde, önbelleklerde ve veritabanı indekslemede yaygın olarak kullanılır. Ancak performanslarını etkileyebilecek karma çarpışmalar meydana gelebilir. Çarpışmaların üstesinden gelmek için zincirleme ve açık adresleme gibi teknikler kullanılır.
• Çizgeler, varlıklar arasındaki ilişkileri temsil eden, kenarlarla birbirine bağlanan düğümlerin koleksiyonlarıdır. Çizgeler, diğer şeylerin yanı sıra sosyal ağları, bilgisayar ağlarını ve ulaşım ağlarını modellemek için kullanılabilir. Köşelerden (düğümler) ve kenarlardan (düğümler arasındaki bağlantılar) oluşurlar. Çizgeler yönlü veya yönsüz olabilir, döngülere sahip olabilir veya döngüsel olmayabilir. Çizge geçiş algoritmaları, genişlik öncelikli aramayı ve derinlik öncelikli aramayı içerir.
• Ağaçlar öğelerin hiyerarşik organizasyonunu temsil eder. Ağaç, döngü içermeyen bir çizgedir ve kenarlarla birbirine bağlanan düğümlerden oluşur; bir düğüm köktür ve diğer tüm düğümler alt ağaçları oluşturur. Ağaçlar çeşitli algoritmalarda ve veri depolama senaryolarında yaygın olarak kullanılmaktadır. İkili ağaçlar (özellikle yığınlar), AVL ağaçları ve B ağaçları bazı popüler ağaç türleridir. Verilerin verimli ve optimum şekilde aranmasını, sıralanmasını ve hiyerarşik temsilini sağlarlar.
• Yığınlar ve kuyruklar, diziler veya bağlantılı listeler kullanılarak uygulanabilen soyut veri türleridir. Bir yığının iki temel işlemi vardır: Son Giren İlk Çıkar (LIFO) prensibini takip eden yığının en üstüne bir öğe ekleme (push) ve yığından en üstteki öğeyi kaldırma (pop). Kuyrukların iki ana işlemi vardır: İlk Giren İlk Çıkar (FIFO), kuyruğun arkasına bir öğe ekleme (enqueue) ve kuyruğun en önündeki öğeyı kaldırma (dequeue).
• Önek ağacı olarak da bilinen bir trie, karakter dizelerinin verimli bir şekilde alınması için kullanılan özel bir ağaç veri yapısıdır. Her kenar bir karakteri temsil edecek şekilde bir dizenin karakterlerini düğümler halinde depolamaya çalışır. Otomatik tamamlama, yazım denetimi ve sözlük uygulamaları gibi metin işleme senaryolarında özellikle kullanışlıdır. Denemeler, dizelerde hızlı arama ve önek tabanlı işlemleri mümkün kılar.

Çoğu assembly dili ve BCPL (Basic Combined Programming Language, Temel Birleştirilmiş Programlama Dili) gibi bazı düşük seviyeli diller, veri yapıları için yerleşik destekten yoksundur. Öte yandan, birçok üst düzey programlama dili ve MASM gibi bazı üst düzey assembly dilleri, kayıtlar ve diziler gibi belirli veri yapıları için özel sözdizimine veya diğer yerleşik desteğe sahiptir. Örneğin, C (BCPL'nin doğrudan soyundan gelen) ve Pascal dilleri, vektörlere (tek boyutlu diziler) ve çok boyutlu dizilere ek olarak sırasıyla yapıları ve kayıtları destekler.

Çoğu programlama dili, veri yapısı uygulamalarının farklı programlar tarafından yeniden kullanılmasına izin veren bir tür kütüphane mekanizmasına sahiptir. Modern diller genellikle en yaygın veri yapılarını gerçekleyen standart kütüphanelerle birlikte gelir. Örnekler C++ Standart Şablon Kitaplığı, Java Koleksiyon Çerçevesi ve Microsoft .NET Çerçevesidir.

Modern diller ayrıca genellikle modüler programlamayı, yani bir kütüphane modülünün arayüzü ile bunun uygulanması arasındaki ayrımı destekler. Bazıları, istemcilerin uygulama ayrıntılarını gizlemesine olanak tanıyan opak veri türleri sağlar. C++, Java ve Smalltalk gibi nesne yönelimli programlama dilleri genellikle bu amaç için sınıfları kullanır.

Bilinen birçok veri yapısının, birden fazla bilgi işlem iş parçacığının bir veri yapısının tek bir somut örneğine aynı anda erişmesine izin veren eşzamanlı versiyonları vardır.

• Soyut veri türü
• Eşzamanlı veri yapısı
• Veri örneği
• Dinamizasyon
• Bağlantılı veri yapısı
• Veri yapılarının listesi
• Kalıcı veri yapısı
• Düz eski veri yapısı
• Queap
• Kısa ve öz veri yapısı
• Ağaç (veri yapısı)

• Alfred Aho, John Hopcroft, and Jeffrey Ullman, Data Structures and Algorithms, Addison-Wesley, 1983, ISBN 0-201-00023-7

• Dictionary of Algorithms and Data Structures1 Temmuz 2024 tarihinde Wayback Machine sitesinde arşivlendi.

• The Python Tutorial 5. Data Structures1 Temmuz 2024 tarihinde Wayback Machine sitesinde arşivlendi.

• Rust Module std::collections1 Temmuz 2024 tarihinde Wayback Machine sitesinde arşivlendi.

• C++ reference Containers library1 Temmuz 2024 tarihinde Wayback Machine sitesinde arşivlendi.