Data Structures — 1

Data Structure ve Algoritma ,yazılım geliştirme sürecinde en önemli yapı taşıdır. Çoğu zaman unuttuğumuz bu yapılar aslında çoğu kez karşımıza çıkıyor.

Data Structures (veri yapıları) veriyi Memory’de nasıl tuttuğumuzun(sakladığımızın) yöntemidir.Array , Linked List, Stack, Queue, Hash Table, Binary Tree, Binary Heap vb gibi yapıları içeririr.

Bu yazımda Arrays ve LinkedList diziye eleman ekleme,silme,değiştirme fonksiyonlarının Time Complexity göre inceleyeceğiz.

Time complexity bir algoritmanın çalışması için gerekli olan süredir. Ancak buradaki süre, saniyeleri hesaplayarak değil, kaç tane işlem gerçekleştirdiğine göre hesaplanmaktadır.

1.ArrayList

• Diziye elemanlar ekleme sırasına göre sıralı bir şekilde eklenir.Her eklenen elemanın dizide bir index vardır.Herhangi bir elemana index ile erişilir.

public String get(int index) {
    return (String) data[index];
}

public void set(int index, String value) {
    data[index] = value;
}

• Tekrardan boyutlanabilir.(Re-sizeable) .Dizi ilk tanımlandığında statik bir boyuta sahiptir.Dizi boyutu dolduktan sonra yeni bir eleman ekleneceği zaman yeni bir dizi oluşur. Eski dizideki elemanlar yeni diziye kopyalanır.Yeni diziye bu eleman eklenir.

private void resize() {
    Object[] newData = new Object[initialCapacity * 2];
    for (int i = 0; i < initialCapacity; i++) {
        newData[i] = data[i];
    }
    data = newData;
    initialCapacity = initialCapacity * 2;
}

• Herhangi bir öğe silindiğinde tüm elemanların index kaydırılır.Dizide n kadar kaydırma işlemi yapmaktadır.Size aşılırsa tekrardan resize edilmesi gerekir.

public void insert(int index, String value) {
    //Check Size
    if (size == initialCapacity) {
        resize();
    }
    // Copy up
    for (int j = size; j > index; j--) {
        data[j] = data[j - 1];
    }
    // Insert
    data[index] = value;
    size++;
}

• Aynı şekilde delete işleminde dizinin size elemanı çıkarılarak başka bir diziye kopyalanır

public void delete(int index) {
    for (int j = index; j < size - 1; j++) {
        data[j] = data[j + 1];
    }
    size--;
}

2. LinkedList

Temel mantık olarak, her bir eleman(node) tutması gereken dataya ilaveten kendinden bir sonra gelecek olan node’un adresini tutar. Dolayısıyla her linked list node’u kendisinden bir sonraki node’un yerini bilir. Bu da linked listlerin bellekte sıralanış şekli açısından bize esneklik sağlar.ArrayList gibi ilk zamandan bellekte boyut açmak gerekmez.

Get ÖMER FARUK İÇEN’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Tutulacak olan veri -> Data
Kendinden bir sonraki node’ın adresi -> Next

public class CustomLinkedList {
    private static class Node {

        public int data;
        public Node next;
        private Node head;
}
}

• İlk Eleman getirme

public int getFirstElement() {
    return head.data;
}

• Son Elemanı bulmak için dizinin sonuna kadar gidiyoruz. Yada Node<E> last ile eleman diziye her eklendiğinde tutulursa O(1) olur.

public int getLastElement() {
    Node current = head;
    while (current.next != null) {
        current = current.next;//O(n)
    }
    return current.data;
}

• Diziye eleman eklenmesi (Dizinin ilk elemanına) O(1)

public void addFront(int data) {
    Node newNode = new Node(data);
    // if head..
    if (head == null) {
        head = newNode;
        return;
    }
    //Set its nexto current head
    newNode.next = head;
    head = newNode;
    size++;
}

• Dizi sonuna eleman eklenmesi

public void addBack(int data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = newNode;
        return;
    }
    Node current = head;
    while (current.next != null) {
        current = current.next;//O(n)
    }
    current.next = newNode;
}

• Dizide bir eleman silme işleminde O(n) şeklinde olmaktadır.

public void deleteValue(int data) {
    if(head.data==data){
        head=head.next;
        return;
    }
    Node current = head;
    while (current.next != null) {
        if(current.next.data==data){
            current.next=current.next.next;
            return;
        }
        current = current.next;//O(n)
    }
}

LinkedList ile ArrayList farkı nedir?

Data Structures animasyon olarak anlatan kaynaktan çok daha rahat öğreneceğinizi düşünüyorum.

Data Structure Animations using Processing.js by cathyatseneca