Veri Yapıları - LinkedList

Published in

Yetkin Yayın

4 min readDec 8, 2023

Herkese Merhabalarr! Bu yazıda Veri yapılarına (Data Structures) giriş yapacağız. Veri yapıları bilgisayar bilimlerinde ve programlamada temel bir kavramdır ve bellek yönetimi, algoritma tasarımı vb. konularda önemli avantajlar sunar. Zaman kaybetmeden önemli bir veri yapısı olan LinkedList ile başlayalım.

LinkedList

LinkedList, linear bir veri yapısıdır.

Linear Veri Yapısı: Elemanların birbirine sıralı bir şekilde bağlandığı ve her eleman bir önceki ve bir sonraki eleman ile ilişkilidir. Linear Veri yapılarına Arrays, Stacks, Queues ve LinkedListler örnek gösterilebilir.

Fotoğrafta görüldüğü üzere LinkedList elemanları birbiriyle bağlantılıdır. Her bir elemana Node(düğüm) ismi verilir ve her bir node, data( kendisine ait değer) ve bir sonraki düğümün referansını içerir (next).

Head Node: LinkedList içerisindeki en baştaki düğümdür.

Tail Node: LinkedList içerisindeki en son düğümdür. En son düğümün referans değeri başka düğümü gösteremeyeceğinden null olacaktır.

LinkedList türlerine geçmeden önce LinkedList avantajlarına ve dezavantajlarına bakalım.

Avantajları

LinkedList dinamiktir. Eleman ekleme veya çıkarma işlemleri arraylere kıyasla daha efektif olabilir.
LinkedList içinde eleman ekleme veya çıkarma işlemleri daha hızlıdır çünkü bunu yapmak için sadece ilgili düğümün referansları üzerinde işlem yapmak yeterli olacaktır.
LinkedList ile birçok veri yapısını farklı dillerde implement edebiliriz (Stack, Queue, Graph, Hash Maps).

Dezavantajları

LinkedList, bir diziden farklı olarak rastgele erişime izin vermez. Belirli konumdaki ögeye ilerlemek için tek tek düğümleri dolaşmak gerekebilir. Küçük boyutlu listelerde bu durum çok göze batmasa bile boyut büyüdükçe performans sorununa yol açabilir.

Genellikle Array veri yapısı yerine LinkedList veri yapısı kullanılır ama bu durum array veri yapısının verimsiz olduğu anlamına gelmez. Projeye veya o anki şartlara göre programcı array mi linkedList mi kullanacağına kendi karar vermelidir.

LinkedList Türleri

Single-Linked List

En başta bahsettiğimiz LinkedList tanımı Single-LinkedList içinde geçerlidir. LinkedList implementasyonunda genellikle Single-LinkedList kullanılır.

Double-LinkedList

Double-LinkedListte her bir düğüm bir sonraki ve bir önceki düğümün referansını içerir. Bu sayede Double-LinkedList üzerinde hem ileri hem de geri yönlü hareket edebilirsiniz.

Prev: Önceki düğümün referansını işaret eder. En baştaki düğümde null olacaktır.

Next: Bir sonraki düğümün referansını işaret eder. En sondaki düğümde null olacaktır.

Circular LinkedList

Burada son düğümün referansı en baştaki düğümün datasını (veri) işaret eder.

Kod üzerinde LinkedList veri yapısına göz atalım.

class LinkedList { 
    Node head; 
  
    class Node { 
        int data; 
        Node next; 
  
       
        Node(int d) 
        { 
            data = d; 
            next = null; 
        } 
    } 
}

LinkedList classının içine nested bir Node classı oluşturduk ve içinde gerekli işlemleri yaptık.

LinkedList’de en başa yeni bir node (düğüm) eklemek için aşağıdaki kodu yazmanız gerekiyor.

class LinkedList{
   class Node{
    int data;
    Node next;
    Node(int d){
    data=d;
    next=null;  
    }
  }

 Node head;
  public void push(int newData){
  Node newNode= new Node(newData);
  newNode.next=head;
  head=newNode;
  }
}

Peki en sona eklemek için neler yapmalıyız?

class LinkedList{
   class Node{
    int data;
    Node next;
    Node(int d){
    data=d;
    next=null;  
    }
  }
  Node head;
  public void pushLast(int newData){
  //Eklemek için yeni bir node oluşturuyoruz.
  Node newNode=new Node(newData);
  
  //Eğer linkedList boşsa yeni oluşturduğumuz node head olarak atıyoruz 
  //return ile işlemimiz bitiyor.
  if(head==null){
  head=new Node(newData);
  return;
  }
  //En sona ekleyeceğimiz için newNodeun referansını null olarak atıyoruz.
  newNode.next=null;
  
 
  //Son düğümün referansı null olacağı için onu bulana kadar düğümleri geziyoruz.
  Node last=head;
  while(last.next !=null){
  last=last.next;
  }
  //En son düğümü newNode olarak değiştiriyoruz.
  last.next=newNode;
  return;
  }
}

En başa ve en sona eklemeyi gördük peki başa ve sona değil, istediğimiz bir düğümden sonra eklemek istersek neler yapmamız gerekiyor?

public void insertAfter(Node prev_node, int new_data)
{
    //Parametre olarak verilen düğümün null olup olmadığını kontrol ediyoruz.
    if (prev_node == null) {
        System.out.println(
            "The given previous node cannot be null");
        return;
    }
 
    //Yeni bir node oluşturuyoruz.
    Node new_node = new Node(new_data);
 
    //Verilen düğümün referansını yeni oluşturduğumuz düğümün referansına atıyoruz
    //çünkü parametre olarak verilen düğümün sonrasına ekleme yapacağız.
    new_node.next = prev_node.next;
 
    //yeni oluşturduğumuz düğümü verilen düğümün referansına atayarak düğümü eklemiş oluyoruz.
    prev_node.next = new_node;
}