Veri yapısı
,
bilgisayar
ortamında verilerin etkin olarak saklanması ve i?lenmesi icin kullanılan yapı.
Veri yapıları, verilerin duzenlenme bicimini 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?aclar
ve
cizgeler
gibi veri modellerine uydurularak duzenlenmesi gerekebilir. Veri, yapı ve algoritma bir yazılımın birbirinden ayrılmaz bile?enleridir. Algoritması hazırlanmı? her yapı icin verilerin duzenli bir ?ekilde kullanımı onemlidir. Cunku yapı iyi kuruldu?unda, etkin, do?ru, anla?ılır ve hızlı calı?ıp az kaynak kullanan algoritma geli?tirmek kolayla?ır.
Bilgisayar biliminde veri yapısı, genellikle verilere verimli eri?im icin secilen bir veri organizasyonu ve depolama bicimidir. 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.
Veri yapıları soyut veri turlerinin (ADT (abstract data types)) temelini olu?turur. ADT, veri tipinin mantıksal formunu tanımlar. Veri yapısı veri tipinin fiziksel formunu uygular.
Farklı turdeki veri yapıları, farklı turdeki uygulamalara uygundur ve bazıları belirli gorevlere oldukca uzmanla?mı?tır. Orne?in, ili?kisel veritabanları genellikle veri alımı icin B-a?acı dizinlerini kullanırken, derleyici uygulamaları genellikle tanımlayıcıları aramak icin karma tabloları kullanır.
Veri yapıları, buyuk veritabanları ve internet indeksleme hizmetleri gibi kullanımlar icin buyuk miktarlardaki verileri verimli bir ?ekilde yonetmeye yonelik bir arac sa?lar. Genellikle verimli veri yapıları, verimli algoritmalar tasarlamanın anahtarıdır. Bazı resmi tasarım yontemleri ve programlama dilleri, yazılım tasarımında anahtar duzenleme faktoru 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ı duzenlemek icin kullanılabilir.
Veri yapıları, ce?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?aretci 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 o?elerinin adreslerinin aritmetik i?lemlerle hesaplanmasına dayanırken, ba?lantılı veri yapıları, veri o?elerinin adreslerinin yapının kendisi icinde saklanmasına dayanır. Veri yapılandırmasına yonelik bu yakla?ımın, algoritmaların verimlili?i ve olceklenebilirli?i uzerinde derin etkileri vardır. Orne?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 orneklerini yaratan ve i?leyen bir dizi prosedur yazmayı gerektirir. Bir veri yapısının verimlili?i bu i?lemlerden ayrı olarak analiz edilemez. Bu gozlem, soyut bir veri turu, uzerinde gercekle?tirilebilecek i?lemlerle dolaylı olarak tanımlanan bir veri yapısı ve bu i?lemlerin matematiksel ozellikleri (yer ve zaman maliyetleri dahil) ?eklindeki teorik kavramı motive eder.
Genellikle daha basit ilkel veri turleri uzerine in?a edilen cok sayıda veri yapısı turu vardır. ?yi bilinen ornekler ?unlardır:
- Dizi, belirli bir sıradaki, genellikle hepsi aynı turde olan bir dizi o?edir (dile ba?lı olarak, tek tek o?elerin tumu aynı turde olmaya zorlanabilir veya hemen hemen her turde olabilir). Hangi o?enin gerekli oldu?unu belirtmek icin o?elere bir tam sayı dizini kullanılarak eri?ilir. Tipik uygulamalar dizilerin elemanları icin 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 du?umun kendine ait bir de?ere sahip oldu?u ve ba?lantılı listedeki bir sonraki du?ume i?aret etti?i, du?um adı verilen herhangi bir turdeki veri o?elerinin do?rusal bir koleksiyonudur. Ba?lantılı listenin diziye gore temel avantajı, listenin geri kalanının yeri de?i?tirilmeden de?erlerin her zaman verimli bir ?ekilde eklenip cıkarılabilmesidir. Ancak belirli bir o?eye rastgele eri?im gibi di?er bazı i?lemler, listelerde dizilere gore 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 iceren ve genellikle adlara gore dizine eklenen bir de?erdir. Kayıtların o?elerine genellikle alanlar veya uyeler denir. Nesne yonelimli programlama ba?lamında kayıtlar, onları nesnelerden ayıran duz 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 icin bir karma i?levi kullanırlar ve ortalama durumda sabit zamanlı eri?ime izin verirler. Hash tabloları sozluklerde, onbelleklerde ve veritabanı indekslemede yaygın olarak kullanılır. Ancak performanslarını etkileyebilecek karma carpı?malar meydana gelebilir. Carpı?maların ustesinden gelmek icin zincirleme ve acık adresleme gibi teknikler kullanılır.
- Grafikler, varlıklar arasındaki ili?kileri temsil eden, kenarlarla birbirine ba?lanan du?umlerin koleksiyonlarıdır. Grafikler, di?er ?eylerin yanı sıra sosyal a?ları, bilgisayar a?larını ve ula?ım a?larını modellemek icin kullanılabilir. Ko?elerden (du?umler) ve kenarlardan (du?umler arasındaki ba?lantılar) olu?urlar. Grafikler yonlu veya yonsuz olabilir, dongulere sahip olabilir veya dongusel olmayabilir. Grafik geci? algoritmaları, geni?lik oncelikli aramayı ve derinlik oncelikli aramayı icerir.
- Yı?ınlar ve kuyruklar, diziler veya ba?lantılı listeler kullanılarak uygulanabilen soyut veri turleridir. Bir yı?ının iki temel i?lemi vardır: Son Giren ?lk Cıkar (LIFO) prensibini takip eden push (yı?ının en ustune bir o?e ekler) ve pop (yı?ından en ustteki o?eyi kaldırır). Kuyrukların iki ana i?lemi vardır: Enqueue (sıranın arkasına bir o?e ekler) ve dequeue (sıranın onunden bir o?eyi kaldırır), ?lk Giren ?lk Cıkar (FIFO) ilkesini izler.
- A?aclar o?elerin hiyerar?ik organizasyonunu temsil eder. Bir a?ac, kenarlarla birbirine ba?lanan du?umlerden olu?ur; bir du?um koktur ve di?er tum du?umler alt a?acları olu?turur. A?aclar ce?itli algoritmalarda ve veri depolama senaryolarında yaygın olarak kullanılmaktadır. ?kili a?aclar (ozellikle yı?ınlar), AVL a?acları ve B a?acları bazı populer a?ac turleridir. Verilerin verimli ve optimum ?ekilde aranmasını, sıralanmasını ve hiyerar?ik temsilini sa?larlar.
- Onek a?acı olarak da bilinen bir trie, dizelerin verimli bir ?ekilde alınması icin kullanılan ozel bir a?ac veri yapısıdır. Her kenar bir karakteri temsil edecek ?ekilde bir dizenin karakterlerini du?umler halinde depolamaya calı?ır. Otomatik tamamlama, yazım denetimi ve sozluk uygulamaları gibi metin i?leme senaryolarında ozellikle kullanı?lıdırlar. Denemeler, dizelerde hızlı arama ve onek tabanlı i?lemleri mumkun kılar.
Co?u montaj dili ve BCPL (Temel Kombine Programlama Dili) gibi bazı du?uk seviyeli diller, veri yapıları icin yerle?ik destekten yoksundur. Ote yandan, bircok ust duzey programlama dili ve MASM gibi bazı ust duzey montaj dilleri, kayıtlar ve diziler gibi belirli veri yapıları icin ozel sozdizimine veya di?er yerle?ik deste?e sahiptir. Orne?in, C (BCPL'nin do?rudan soyundan gelen) ve Pascal dilleri, vektorlere (tek boyutlu diziler) ve cok boyutlu dizilere ek olarak sırasıyla yapıları ve kayıtları destekler.
Co?u programlama dili, veri yapısı uygulamalarının farklı programlar tarafından yeniden kullanılmasına izin veren bir tur kutuphane mekanizmasına sahiptir. Modern diller genellikle en yaygın veri yapılarını uygulayan standart kutuphanelerle birlikte gelir. Ornekler C++ Standart ?ablon Kitaplı?ı, Java Koleksiyon Cercevesi ve Microsoft .NET Cercevesidir.
Modern diller ayrıca genellikle moduler programlamayı, yani bir kutuphane modulunun arayuzu ile bunun uygulanması arasındaki ayrımı destekler. Bazıları, istemcilerin uygulama ayrıntılarını gizlemesine olanak tanıyan opak veri turleri sa?lar. C++, Java ve Smalltalk gibi nesne yonelimli programlama dilleri genellikle bu amac icin sınıfları kullanır.
Bilinen bircok veri yapısının, birden fazla bilgi i?lem i? parcacı?ının bir veri yapısının tek bir somut orne?ine aynı anda eri?mesine izin veren e?zamanlı versiyonları vardır.
- Soyut veri turu
- E?zamanlı veri yapısı
- Veri orne?i
- Dinamizasyon
- Ba?lantılı veri yapısı
- Veri yapılarının listesi
- Kalıcı veri yapısı
- Duz eski veri yapısı
- Queap
- Kısa ve oz veri yapısı
- A?ac (veri yapısı)
- 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.
- Peter Brass,
Advanced Data Structures
, Cambridge University Press, 2008, ISBN 978-0521880374
- Alfred Aho, John Hopcroft, and Jeffrey Ullman,
Data Structures and Algorithms
, Addison-Wesley, 1983, ISBN 0-201-00023-7
- Descriptions from the Dictionary of Algorithms and Data Structures