Bağlı liste, bilgisayar bilimlerinde temel bir veri yapısıdır. Esas olarak dizilere kıyasla verimli ekleme ve silme işlemlerine izin verir. Diziler gibi, stack, queue ve deque gibi diğer veri yapılarını uygulamak için de kullanılır.

Veri Yapısı: Bitişik Olmayan

Bellek Tahsisi: Tipik olarak tek tek elemanlara tek tek tahsis edilir

Ekleme/Silme: Verimli

Erişim: Sıralı

Tek Bağlantılı Liste

Tekli bağlı liste temel bir veri yapısıdır, her düğümün bir veri alanı ve bağlı listedeki bir sonraki düğüme bir referans içerdiği düğümlerden oluşur. Son düğümün bir sonraki düğümü null'dur ve listenin sonunu gösterir. Bağlı Listeler etkin ekleme ve silme işlemlerini destekler.

Düğüm (Node) Yapısı

Tekli bağlı listede her düğüm iki parçadan oluşur: veri ve bir sonraki düğüme bir işaretçi. Bu yapı, düğümlerin dinamik olarak birbirine bağlanmasına ve zincir benzeri bir dizi oluşturmasına olanak tanır.

^{Tekli Bağlı Liste Yapısı (Kaynak:}^{geeksforgeeks.com}⁾

Tek Bağlantılı Liste İşlemleri

Dolaşma - Listeleme
Arama
Uzunluk Hesaplama
Ekleme
Başa ekleme
Sona ekleme
Belirli bir konuma ekleme
Silme
Baştan silme
Sondan silme
Belirli bir düğümü silme

Java ile Listeleme İşlemi:

public static void traverseLinkedList(Node head)
{
    // bağlı listenin başı (düğüm - node) belirtilir
    Node current = head;

    // listenin sonuna ulaşana kadar dolaşılır
    while (current != null) {

        // mevcut düğüm yazdırılır
        System.out.print(current.data + " ");

        // bir sonraki düğüme geçilir
        current = current.next;
    }

    System.out.println();
}

Java ile Arama İşlemi:

public boolean searchLinkedList(Node head, int target)
{
    // liste dolaşılır
    while (head != null) {
        // hedef ile mevcut düğüm karşılaştırılır
        if (head.data == target) {
            // bulunduysan true döndürülür
            return true;
        }
        // bulunmadıysa bir sonraki düğüme geçilir
        head = head.next;
    }
    // bulunmadıysa false döndürülür
    return false;
}

Java ile Uzunluk Bulma İşlemi:

public int findLength(Node head) {
  
    // başlangıç için bir değer verilir
    int length = 0;

    // baş düğümden başlanır
    Node current = head;

    // her düğümden sonra uzunluk (length) değeri 1 arttırılır.
    while (current != null) {
        length++;
        current = current.next;
    }
    // bulunan değer döndürülür
    return length;
}

Java ile Ekleme İşlemi:

// Başa Eleman Ekleme
public Node insertAtBeginning(Node head, int value) {
    // yeni bir düğüm eklenir
    Node newNode = new Node(value);

    // sonraki düğüm baş düğüm olarak işaretlenir
    newNode.next = head;

    // baş düğüm, yeni eklenen düğüm olacak şekilde güncellenir.
    head = newNode;

    // baş düğüm güncellenir.
    return head;
}

// Sona Eleman Ekleme
public static Node insertAtEnd(Node head, int value)
{
    // yeni düğüm oluşturulur
    Node newNode = new Node(value);

    // eğer liste boşsa, yeni eklenen düğüm baş düğüm olur
    if (head == null)
        return newNode;

    // son düğüme kadar liste dolaşılır
    Node curr = head;
    while (curr.next != null) {
        curr = curr.next;
    }

    // sondan bir sonraki yeni son düğüm olur
    curr.next = newNode;

    return head;
}

// Belirli Bir Konuma Eleman Ekleme
public static Node insertPos(Node head, int pos, int data)
{
    if (pos < 1) {
        System.out.println("Invalid position!");
        return head;
    }

    // Başa yerleştirmek için özel durum koşulu
    if (pos == 1) {
        Node temp = new Node(data);
        temp.next = head;
        return temp;
    }

    // Eklenecek yerden bir önceki düğümün yeri bulunur
    Node prev = head;
    int count = 1;
    while (count < pos - 1 && prev != null) {
        prev = prev.next;
        count++;
    }

    // eğer konum düğüm sayısından büyükse
    if (prev == null) {
        System.out.println("Invalid position!");
        return head;
    }

    // yeni düğüm belirtilen konuma eklenir
    Node temp = new Node(data);
    temp.next = prev.next;
    prev.next = temp;

    return head;
}

Java ile Silme İşlemi:

// Baştan Silme
static Node removeFirstNode(Node head)
{
    if (head == null)
        return null;

    Node temp = head;
    head = head.next;

    return head;
}

// Sondan Silme
Node removeLastNode(Node head)
{
    if (head == null)
        return null;

    if (head.next == null) {
        head = null;
        return null;
    }

    Node second_last = head;
    while (second_last.next.next != null)
        second_last = second_last.next;

    second_last.next = null;

    return head;
}

// Belirli Bir Konumdan Silme
public void deleteAtPosition(Node head, int position)
{
    if (head == null || position < 1) {
        return;
    }

    if (position == 1) {
        Node temp = head;
        head = head.next;
        temp = null;
        return;
    }

    Node current = head;
    for (int i = 1; i < position - 1 && current != null;
         i++) {
        current = current.next;
    }

    if (current == null || current.next == null) {
        return;
    }

    Node temp = current.next;

    current.next = current.next.next;

    temp = null;
}

Çift Bağlantılı Liste

Çift bağlı liste, her biri bir değer ve biri listedeki bir önceki düğüme, diğeri de listedeki bir sonraki düğüme işaret eden iki işaretçi içeren bir dizi düğümden oluşan bir veri yapısıdır. Bu, listenin her iki yönde de verimli bir şekilde geçilmesine olanak tanıyarak, sık ekleme ve silme işlemlerinin gerekli olduğu uygulamalar için uygun hale getirir.

^{Çift Bağlantılı Liste Yapısı (Kredi:}^{geeksforgeeks.com}⁾

Bir veri yapısında, çift bağlantılı bir liste üç alana sahip düğümler kullanılarak temsil edilir:

Veri
Bir sonraki düğümü işaretleyen işaretçi (next)
Bir önceki düğümü işaretleyen işaretçi (prev)

// Düğüm (Node) Tanımlama
class Node {
    int data;

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

// Liste Sıralama ve Dolaşma
class GfG {
    static void forwardTraversal(Node head) {    
        Node curr = head;

        while (curr != null) {       
            System.out.print(curr.data + " ");

            curr = curr.next;
        }

        System.out.println();
    }

    static void backwardTraversal(Node tail) {

        Node curr = tail;
        while (curr != null) {
            System.out.print(curr.data + " ");
            curr = curr.prev;
        }

        System.out.println();
    }

    public static void main(String[] args) {

        Node head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);

        head.next = second;
        second.prev = head;
        second.next = third;
        third.prev = second;

        System.out.println("Baştan Dolaşma:");
        forwardTraversal(head);

        System.out.println("Sondan Dolaşma:");
        backwardTraversal(third);
    }
}

// Baştan Dolaşma: 1 2 3
// Sondan Dolaşma: 3 2 1

Java ile Listenin Uzunluğunu Bulma:

//Listenin Uzunluğunu Bulma
class Node {
    int data; 
    Node prev; 
    Node next;

    public Node(int val) { 
        data = val; 
        prev = null; 
        next = null; 
    }
}


class GfG {
    static int FindLength(Node head) {
        int count = 0;
        for (Node cur = head; cur != null; cur = cur.next)
            count++;
        return count;
    }
    public static void main(String[] args) {

        Node head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);
        
        head.next = second; 
        second.prev = head;
        second.next = third; 
        third.prev = second;

        System.out.println("Listenin uzunluğu: " + FindLength(head));
    }
}

// Listenin uzunluğu: 3

Java ile Eleman Ekleme İşlemi:

//Listenin Başına Eleman Ekleme
class Node {
    int data;
    Node prev, next;

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

class GfG {
    static Node insertBegin(Node head, int data) {

        Node new_node = new Node(data);      
        new_node.next = head;

        if (head != null) {
            head.prev = new_node;
        }

        return new_node;
    }

    static void printList(Node head) {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data + " ");
            curr = curr.next;
        }
      	System.out.println();
    }

    public static void main(String[] args) {

        Node head = new Node(2);
        head.next = new Node(3);
        head.next.prev = head;
        head.next.next = new Node(4);
        head.next.next.prev = head.next;

        System.out.print("Orijinal Liste: ");
        printList(head);

        head = insertBegin(head, 1);

      	System.out.print("Eklendikten sonra: ");
        printList(head);
    }
}

// Listenin Sonuna Eleman Ekleme
class Node {
    int data;
    Node next, prev;

    Node(int newData) {
        data = newData;
        next = prev = null;
    }
}

class GFG {
    public static Node insertEnd(Node head, int newData) {

        Node newNode = new Node(newData);

        if (head == null) {
            head = newNode;
        }
        else {
            Node curr = head;
            while (curr.next != null) {
                curr = curr.next;
            }
            curr.next = newNode;
            newNode.prev = curr;
        }
        return head;
    }
    public static void printList(Node head) {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data + " ");
            curr = curr.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.prev = head;
        head.next.next = new Node(3);
        head.next.next.prev = head.next;

        System.out.println("Orijinal Bağlı Liste: ");
        printList(head);

        System.out.println("Ekledikten sonra: ");
        int data = 4;
        head = insertEnd(head, data);

        printList(head);
    }
}

// Belirli Bir Konuma Eleman Ekleme
class Node {
    int data;
    Node next;
    Node prev;

    Node(int new_data) {
        data = new_data;
        next = prev = null;
    }
}

class GFG {
    public static Node insertAtPosition(Node head, int pos, int new_data) {
        Node new_node = new Node(new_data);
        if (pos == 1) {
            new_node.next = head;
            if (head != null) {
                head.prev = new_node;
            }
            head = new_node;
            return head;
        }

        Node curr = head;
        for (int i = 1; i < pos - 1 && curr != null; ++i) {
            curr = curr.next;
        }

        if (curr == null) {
            System.out.println("Pozisyon sınırların dışında.");
            return head;
        }

        new_node.prev = curr;
        new_node.next = curr.next;
        curr.next = new_node;

        if (new_node.next != null) {
            new_node.next.prev = new_node;
        }
        return head;
    }

    public static void printList(Node head) {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data + " ");
            curr = curr.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.prev = head;
        head.next.next = new Node(4);
        head.next.next.prev = head.next;

        System.out.print("Orijinal Bağlı Liste: ");
        printList(head);

        System.out.print("Belirli konuma düğüm ekle: ");
        int data = 3;
        int pos = 3;
        head = insertAtPosition(head, pos, data);
        printList(head);
    }
}

Java ile Eleman Silme İşlemi:

// Baştan Eleman Silme
class Node {
    int data;
    Node prev;
    Node next;

    Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

class GFG {
    public static Node delHead(Node head) {
        if (head == null) {
            return null;
        }

        Node temp = head;
        head = head.next;

        if (head != null) {
            head.prev = null;
        }

        return head;
    }

    public static void printList(Node head) {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data + " ");
            curr = curr.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {   
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.prev = head;
        head.next.next = new Node(3);
        head.next.next.prev = head.next;

        System.out.print("Orijinal Bağlı Liste: ");
        printList(head);

        System.out.print("Silindikten sonra: ");
        head = delHead(head);

        printList(head);
    }
}

// Sondan Eleman Silme
class Node {
    int data;
    Node prev;
    Node next;

    Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

class GFG {
    public static Node delLast(Node head) {
         if (head == null) {
            return null;
        }
        if (head.next == null) {
            return null;
        }

        Node curr = head;
        while (curr.next != null) {
            curr = curr.next;
        }

        if (curr.prev != null) {
            curr.prev.next = null;
        }

        return head;
    }

    public static void printList(Node head) {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data + " ");
            curr = curr.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.prev = head;
        head.next.next = new Node(3);
        head.next.next.prev = head.next;

        System.out.print("Orijinal Bağlı Liste: ");
        printList(head);

        System.out.print("Silindikten sonra: ");
        head = delLast(head);

        printList(head);
    }
}

// Belirli Bir Konumu Silme İşlemi
class Node {
    int data;
    Node prev;
    Node next;

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

class GFG {
    public static Node delPos(Node head, int pos) {
        if (head == null) {
            return head;
        }

        Node curr = head;

        for (int i = 1; curr != null && i < pos; ++i) {
            curr = curr.next;
        }

        if (curr == null) {
            return head;
        }

        if (curr.prev != null) {
            curr.prev.next = curr.next;
        }

        if (curr.next != null) {
            curr.next.prev = curr.prev;
        }

        if (head == curr) {
            head = curr.next;
        }

        return head;
    }

    public static void printList(Node head) {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data + " ");
            curr = curr.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.prev = head;
        head.next.next = new Node(3);
        head.next.next.prev = head.next;

        System.out.print("Orijinal Bağlı Liste: ");
        printList(head);

        System.out.print("Silindikten Sonra: ");
        head = delPos(head, 2);

        printList(head);
    }
}

Bağlı Liste Veri Yapısı

Tek Bağlantılı Liste

Düğüm (Node) Yapısı

Tek Bağlantılı Liste İşlemleri

Çift Bağlantılı Liste

Kaynakça

Yazar Bilgileri

Etiketler