Introduction

Welcome to the DataStructure repository, I have added here my work that I searched in the data structure area by mdbook.

Veri Yapıları

Data-Structures

Ders Notları

Yrd.Doç.Dr.Burhan ERGEN Ders Notları || Olcay Taner Yıldız Derst Slaytları

Verinin bilgisayar belleğinde saklanma şekli ve organizasyonuna Veri Yapısı denir. Veri tipleri, verinin türüne göre farklılık gösterir. İşaretli olmayan bir pozitif sayı doğrudan ikili yapıda tutulurken , işaretli sayı ikinin tümleyeni şeklinde tutulur.

Verinin bellekte kapladığı alan, erişim şekli ve hızı kavramları organizasyonun yapısı farklılaşmasını, uygun organizasyon tasarımı yapılmasını gerekli kılar. Verilere özel olarak, belirli veriler ayrı ayrı ulaşma ihtiyacı yoksa verilerin sıralı bir biçimde tutulmasına ihtiyaç yoktur.Fakat eğer bir arama yapılacaksa bu durumda verilerin sıralı olması bir avantaj sağayacaktır. Eğer verilerin eklenmesi ve çıkarılması fazlaca yapılıyorsa ve sınır belirli değilse bu durumda ağaç yapısının kullanılması ayrıca bir kolaylık getirecektir.

Verilerin bilgisayar belliğinde tutulması için organizasyon tasarımında belirli temel düşünceler yer alır. Bellekte fazla yer kaplamayacak şeklinde en uygun yapıda tutulması gereklidir. Ayrıca verilerin oluşturulması, eklenmesi, çıkarılması ve ulaşım şekli konusunda kolay ve etkin algoritmalar sunması gereklidir.

Verilerin bilgisayar belleğinde tutulması için yapılacak tasarımda amaca göre farklılık gösterebilir.Bellek boyununun artmaması öncelik ise hızdan, hız ve esneklik söz konusu ise bellekten feragat edilebilir. **Hangi organizasyon yapısı kullanılcağı tamamen yapılacak uygulamaya bağlıdır.** Doğrudan ve kesin olarak cevap verilemez.

Veri Yapıları için Kaynaklar

Awesome DataScience ✨✨

javascript-algorithms(JavaScript Algorithms and Data Structures) ✨✨

Awesome - Computer Science

Veri Yapıları Türkçe Ders Videoları(PlayListler)

BigO CheatSheet

BigO() CheatSheet

Bu repodaki birçok kod örneği ve yazılar alıntılanmıştır. Alıntıların linkleri ilgili README.md dosyalarında bulunmaktadır.

Örnek Kodların linkleri

Genc/Data-Structures

ilhanaydintr/Data-Structures
ayyucedemirbas/Data-Structures-Java

Linked List (Linkli Liste veya Bağlı Liste)

Yazan:Şadi Evren ŞEKER

Bağlı liste herhangi bir tipten node’ların (düğümlerin) yine kendi tiplerinden düğümlere işaret etmesi (point) ile oluşan zincire verilen isimdir. Buna göre her düğümde kendi tipinden bir pointer olacak ve bu pointerlar ile düğümler birbirine aşağıdaki şekilde bağlanacaktır.

alt text

Linked List’in avantajı, hafızayı dinamik olarak kullanmasıdır. Buna göre hafızadan silinen bir bilgi için hafıza alanı boşaltılacak veya yeni eklenen bir bilgi için sadece o bilgiyi tutmaya yetecek kadar hafıza alanı ayrılacaktır.

Yukarıdaki figürde görülen bağlı listeye çok benzeyen ve yine çok kullanılan bir bağlı liste uygulaması da çift bağlı liste (doubly linked list) uygulamasıdır.

Buna göre her düğüm, hem kendinden öncekine hem de kendinden sonrakine bağlanır, bu sayede liste üzerinde ileri ve geri ilerlemek mümkündür.

Yukarıdaki şekilde, sırasıyla, Tek bağlı liste (singular linked list), çift uçlu bağlı liste (double ended linked list), çift bağlı liste (doubly linked list) ve dairesel bağlı liste (circular linked list) görülmektedir.

Listelerin üzerinde işlem yapılırken, dolaşıcı (iterator) şeklinde bir gösterici tanımlanır. Bu dolaşıcı veri aranması, ekleme veya silme gibi işlemler sırasında listenin ilgili elemanına kadar gidilmesini sağlar. Listenin ilgili elemanına gidildikten sonra silme veya ekleme gibi işlemler yapılırken göstericilerde (pointers) yapılan değişikliklerin, listeyi etkilememesini sağlar.

Örneğin bir bağlı listeye yeni bir eleman eklenmesi sırasında aşağıdaki adımlar izlenir:

Ekleme işlemini yapılacağı aralıktan önceki düğüme dolaşıcı tarafından gidilir.
Yeni düğüm oluşturularak, sonrasına, dolaşıcının sonrası atanır.
Dolaşıcının sonrasına ise yeni düğüm atanır.

Yukarıdaki şekilde bu ekleme işlemi sırasıyla gösterilmiştir. İlk şekilde dolaşıcı ilgili düğüme gelmiş, ikinci şekilde yeni bir düğüm eklenmiş ve sonrasına, dolaşıcının sonrası atanmış ve son şekilde ise dolaşıcı ile gösterilen düğümün sonrasına yeni düğüm eklenmiştir.

Aynı durumu çift bağlı listeler için ele alacak olursak:

Yukarıdaki şekilde öncelikle ekleme yapılacak aralığa dolaşıcı tarafından gidilir. İkinci adımda yeni düğüm eklenir. Arından göstericiler, yukarıdaki şekilde anlatıldığı gibi sırayla atanır.

Bağlı listeden bir düğümün silinmesi

Bağlı listeden eleman silinmesi sırasında, listede silinecek olan elemandan önceki düğüme kadar dolaşıcı ile gidilir. Dolaşıcının sonrasına, sonrasının sonrası atanır. Bu sayede ilk başta dolaşıcının sonrasında olan düğüm listeden kaldırılmış ve ulaşılamaz hale gelmiş olur. Ardından bu eleman istenirse hafızadan da kaldırılır.

Bağlı listelerin nesne yönelimli programlama dillerinde pointer tipi bulunmamasından dolayı kodlanması biraz farklıdır. Bilindiği gibi C++ gibi melez (hem C hem de nesne yönelimli programlamayı destekler) diller dışında JAVA, C# gibi dillerde gösterici (pointer) bulunmaz. Bunun yerine nesne göstericisi (object referrer) bulunur. Bu değişken tipleri esas olarak bir sınıf(Class)‘dan türetilmiş bir nesneyi(object) gösterebilen değişkenlerdir. Bu değişkenlerin aslında birer göstericiden farkı yoktur.

bagliListe.java

Düğüm

LinkedList.java

linkedList

Kod Kaynağı

DoublyLinkedList.java

doublyLinkedList

3.1 Bağlı Listeler

Bağlı listeler, bir elemanın kendinden sonra gelen verinin yerini göstermesi olarak tanımlanabilir. Dizi mantığı kullanılarak da her ne kadar bağlı liste oluşturmak mümkünse de geneld verini hücre (düğüm) yapıları şeklinde tutulduğu liste oluşumu kullanılır. Çünkü düğüm yapısının kullanan bu mantıkta kaç eleman olduğunu bilmeniz ve sunuru önceden belirlemenizin gereği yoktur. Şekil 3.1'de bağlı liste mantığı şematik olrak verilmiştir. Liste başı 'Ahmet' verisi içeren düğüm ve liste sonu 'Hasan' verisi içeren düğümdür. screenShot4 screenShot7 screenshot5 screenShot6

Yazan: Yrd.Doç.Dr. Burhan Ergen

Kaynakça

Linked List (Linkli Liste veya Bağlı Liste)

alt text

Yukarıdaki figürde görülen bağlı listeye çok benzeyen ve yine çok kullanılan bir bağlı liste uygulaması da çift bağlı liste (doubly linked list) uygulamasıdır.

Buna göre her düğüm, hem kendinden öncekine hem de kendinden sonrakine bağlanır, bu sayede liste üzerinde ileri ve geri ilerlemek mümkündür.

Örneğin bir bağlı listeye yeni bir eleman eklenmesi sırasında aşağıdaki adımlar izlenir:

Ekleme işlemini yapılacağı aralıktan önceki düğüme dolaşıcı tarafından gidilir.
Yeni düğüm oluşturularak, sonrasına, dolaşıcının sonrası atanır.
Dolaşıcının sonrasına ise yeni düğüm atanır.

Aynı durumu çift bağlı listeler için ele alacak olursak:

Bağlı listeden bir düğümün silinmesi

Örnek Bağlı liste kodları:(C++)

Yazan:Şadi Evren ŞEKER

Kaynakça

Stack.java

code1

Statik Yığıt ve Kuyruklar Nedir ?

Statik Yığılar

Burada statik yapıdan kasıt boyut değişi olmayan dizi mantığının kullanılmasıdır. Yığıtlar kullanımı en kolay liste yapılarındandır. Yığıtta ekleme ve çıkarma sadece bir uçtan yapılır ve bu yığıtın tepe kısmıdır.

Yığıt mantığı için genelde ekeleme için itme (push) ve çıkarma için çekme (pop) deyimleri kullanılır. Programlama yapılırken kullanılan alt program çağırmalarında en çok kullanılan yöntemdir. Her alt program çağırıldığında CPU içerikleri yığıta itilir ve alt program bitiminde yıpıttan çekilerek CPU'nun program koşumuna nerede kaldığı , değkenlerin ne durumda olduğu hatırlatır.En son giren ilk çıkar (LIFO:Last In Fırst OUt) mantığını gerçekleşir.

Yığıt matığının gerçekleştirilebilmesi için yığıtta saklanacak verileri tutacak bir diziye ve yığıtın en üst kısmını(son eklenene elemanı) işaret edecek bir değişkene ihtiyaç duyulur. Gerek yığıt vbe gerekse başka zaman programlama yapılırken program, anlamlı olacak şekilde metodlar halinde verilmesi hem anlaşılırlığı artırır hem de programın esnek ve yazılan metodların başka programlarda da kullanılması kolaylığını getirir. Bu mantık içerisinde yığıt mantığı kod olarak şöyle verilebilir.

screenShot

screenShot2

Statik Kuyruklar

Kuyruk mantığına gerek günlük hayatta gerekse bilgisayarda sıraya sokulması olay veya işlerde oldukça sık karşılaşırız. Kuyruk yığıttan farklı olarak iki uçludur; bir başı ve bir sonu vardır. Bu nedenle bilgiyi saklamak için bir diziye ve en az iki indekse ihtiyaç vardır.Şekil 1'de bir kuyruk mantığı şematik olarak verilmitir.

Kuyruk mantığını gerçekleşmede en uygun yaklaşım diziyi daireselmiş gibi düşünüp eleman ekleme ve çıkarmada sürekli indis artırımına gitmektir.

screenShot3

Medium Yazısı

Bilginin geliş sırasına göre, en son gelen elemana ilk erişilen liste yapısına yığın (stack) denir. Verilere yalnız bir uçtan erişim sağlanır. Bu erişimde Last-In-First-Out (LIFO) prensibi vardır. Yani son giren eleman, ilk çıkar. Örneğin üst üste dizilen kitapları, yalnızca en üsttekine erişecek şekilde düşünebiliriz. Stack tasarımı dizi üzerinde veya bağlı liste ile yapılabilir. Bağlı liste kullanarak boyutu sabit olmayan bir stack oluşturabiliriz. Dizi kullanmak için ise sabit bir boyut belirlemeliyiz. ......

Stack (Yığın) mertmekatronik.com/ Yazısı

Yığın veri yapısı en kolay veri yapısı türüdür. Çünkü yığın veri yapısı tabanca şarjörüne benzer. Biraz daha derine gidersek, kuyruk yapısına benzeyen bir yapı var ve bu yapı ile, bir algoritma da işlemin sonunda üretilen veriler yığın yapısının en üstüne eklenir.

Stack yapısı işleyişi

LIFO - LAST IN FIRST OUT - SON GİREN İLK ÇIKAR FILO - FIRST IN LAST OUT - İLK GİREN SON ÇIKAR

Tabanca şarjörü örneği çok akılda kalıcıdır. Girdiğimiz veriler üst üste yerleştiği için ilk giren son çıkan oluyor.

Push = Stack' e veri ekleme

Pop = Stack' den veri silme

Peki, bu durumun dezavantajı nedir?

Bir algoritma işlemi sırasında orta sıralarda bulunan verilerden birinin kullanılması gerekiyorsa, o zaman bu veriye kadar olan veriler yığın yapısından çıkar ve gerekli veri algoritmaya aktarılır, ardından çıkan veriler tekrar yığına aktarılır. Algoritma, veri çıkarken bekler ve bu işlem zaman alır.

Gelelim Kodlamasına

#include 
#include 
#define SIZE 10
int top = -1;
int array[SIZE];
void push(element){
 if(top == SIZE - 1){
  printf("ERR! STACK OVERFLOW\n");
  return;
 }
 top = top + 1;
 array[top] = element;
 printf("%d ADDED TO STACK\n",element);
}
void pop(){
 top = top - 1;
}
int Top(){
 return array[top];
}
int isEmpty(){
 if(top == -1)
  return 1;
 else
  return 0;
}
void print(){
 int i;
 printf("Stack: ");
 for(i=0;i<=top;i++){
  printf("%d  ",array[i]);
 }
 printf("\n");
}
int main(int argc, char *argv[]) {
 push(2);
 print();
 push(4);
 print();
 push(8);
 print();
 push(34);
 push(5);
 push(76);
 push(23);
 print();
 printf("Top element : %d\n",Top());
 pop();
 pop();
 pop();
 pop();
 print();
 printf("Top element : %d\n",Top());
 return 0;
}

Output

Stack Hakkında Yazılmış Yazıların Linkleri

kodlamamerkezi.com/ cdn-acikogretim.istanbul.edu.tr technogezgin.com/ Ders Notu http://cagataykiziltan.net/ baskent.edu.tr/

Doğrusal Veri Yapıları - Kuyruk (Queue)

Bilginin geliş sırasına göre, ilk önce gelen elemana ilk erişilen liste yapısına kuyruk (queue) denir. Bu erişimde First-In-First-Out (FIFO) prensibi vardır. Yani ilk giren eleman, ilk çıkar. Örneğin sinema bileti almak için sıraya girmiş kişileri düşünebiliriz. İlk önce gelen kişi bileti daha önce alacaktır.

.... Devamı..

Kuyruk Hakkında Yazılmış Yazılar

Kuyruk Veri Yapısı (Queue)

http://cagataykiziltan.net/

Binary Search Tree

Binary Search Tree, node’lardan oluşan ve her bir node’un en fazla 2 child node’a sahip olduğu veri yapılarından bir tanesidir. Node Nedir? .... yazının devamı...

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BST {
    constructor() {
        this.root = null;
    }

    create(value) {
        const newNode = new Node(value);

        if (!this.root) {
            this.root = newNode;
            return this;
        } else {
            this.insertNode(this.root, newNode);
        }

        return this;
    }

    insertNode(currentNode, node) {
        if (node.value < currentNode.value) {
            if (currentNode.left === null) {
                currentNode.left = node;
            } else {
                this.insertNode(currentNode.left, node);
            }
        } else {
            if (currentNode.right === null) {
                currentNode.right = node;
            }
            else {
                this.insertNode(currentNode.right, node);
            }
        }
    }

    find(val) {
        if (!this.root) {
            return "There is no Root!";
        } else {
            const found = this.findNode(this.root, val);
            if (!found) {
                return "There is no such node in this tree!";
            }

            return found;
        }
    }

    findNode(currentNode, value) {
        if (currentNode.value === value) {
            return currentNode;
        } else if (value < currentNode.value && currentNode.left != null) {
            return this.findNode(currentNode.left, value);
        } else if (value > currentNode.value && currentNode.right != null) {
            return this.findNode(currentNode.right, value);
        }

        return null;
    }

    findMinNode() {
        if (!this.root) return null;

        let current = this.root;

        while (current.left) {
            current = current.left;
        }

        return current;
    }

    findMaxNode() {
        if (!this.root) return null;

        let current = this.root;

        while (current.right) {
            current = current.right;
        }

        return current;
    }

    inOrder = function () {
        this.getInOrder(this.root);
    }

    getInOrder = function (node) {
        if (node.left != null) {
            this.getInOrder(node.left);
        }

        console.log(node.value);

        if (node.right != null) {
            this.getInOrder(node.right);
        }
    }
}

const tree = new BST();
tree.create(10)
    .create(21)
    .create(5)
    .create(32);

tree.inOrder();

İkili Arama Ağacı

Düğüm yapısı kendisinden büyük ve kendisinden küçük olan düğümler için iki farklı işaretçi (pointer) ve düğüm verisinden oluşur. Bu yapı içine veri olarak başka değişkenler de tanımlanabilir. ....yazının devamı...