Veri yapısı

Veri yapısı, bilgisayar ortamında verilerin etkin olarak saklanması ve işlenmesi için kullanılan yapı.

Veri yapıları, verilerin düzenlenme biçimini belirleyen yapıtaşlarıdır. Bir yazılım değişkeni bile basit bir veri yapısı olarak kabul edilebilir. Değişik algoritmalarda verilerin diziler, listeler, yığıtlar, kuyruklar, ağaçlar ve çizgeler gibi veri modellerine uydurularak düzenlenmesi gerekebilir. Veri, yapı ve algoritma bir yazılımın birbirinden ayrılmaz bileşenleridir. Algoritması hazırlanmış her yapı için verilerin düzenli bir şekilde kullanımı önemlidir. Çünkü yapı iyi kurulduğunda, etkin, doğru, anlaşılır ve hızlı çalışıp az kaynak kullanan algoritma geliştirmek kolaylaşır.

Bilgisayar biliminde veri yapısı, genellikle verilere verimli erişim için seçilen bir veri organizasyonu ve depolama biçimidir. Daha doğrusu veri yapısı, veri değerlerinin, bunlar arasındaki ilişkilerin ve verilere uygulanabilecek işlevlerin veya işlemlerin bir koleksiyonudur; yani verilere ilişkin cebirsel bir yapıdır.

Kullanım

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.

Uygulama

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.

Örnekler

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 tamsayı 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.
• Grafikler, varlıklar arasındaki ilişkileri temsil eden, kenarlarla birbirine bağlanan düğümlerin koleksiyonlarıdır. Grafikler, 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. Grafikler yönlü veya yönsüz olabilir, döngülere sahip olabilir veya döngüsel olmayabilir. Grafik geçiş algoritmaları, genişlik öncelikli aramayı ve derinlik öncelikli aramayı içerir.
• 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 push (yığının en üstüne bir öğe ekler) ve pop (yığından en üstteki öğeyi kaldırır). Kuyrukların iki ana işlemi vardır: Enqueue (sıranın arkasına bir öğe ekler) ve dequeue (sıranın önünden bir öğeyi kaldırır), İlk Giren İlk Çıkar (FIFO) ilkesini izler.
• Ağaçlar öğelerin hiyerarşik organizasyonunu temsil eder. Bir ağaç, 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.
• Önek ağacı olarak da bilinen bir trie, dizelerin 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ırlar. Denemeler, dizelerde hızlı arama ve önek tabanlı işlemleri mümkün kılar.

Dil desteği

Çoğu montaj dili ve BCPL (Temel Kombine 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 montaj 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ı uygulayan 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.

Ayrıca bakınız

• 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ı)

Kaynakça

1. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms, Third Edition (3rd ed.). The MIT Press. ISBN 978-0262033848.

Kaynakça

• Peter Brass, Advanced Data Structures, Cambridge University Press, 2008, ISBN 978-0521880374

Daha fazla okuma

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

Dış bağlantılar

• Descriptions from the Dictionary of Algorithms and Data Structures