Veri Yapılarında Tek Bağlantılı Liste

Tek Bağlantılı Liste Nedir?

Tek yönlü bağlantılı liste, verilerin düğümlere kaydedildiği ve her düğümün bir sonraki düğüme bir bağlantı yoluyla bağlandığı doğrusal ve tek yönlü bir veri yapısıdır. Her düğüm bir veri alanı ve bir sonraki düğüme bir bağlantı içerir. Tek yönlü bağlantılı listeler yalnızca tek yönde gezilebilirken, çok yönlü bağlantılı listeler yalnızca tek yönde gezilebilir. Çift Bağlantılı Liste Her iki yönde de geçilebilir.

İşte tek yönlü bağlantılı listenin düğüm yapısı:

Bağlantılı Listedeki Düğümün Yapısı

Neden dizi yerine bağlantılı liste kullanılır?

Çeşitli senaryolarda bağlantılı liste, tek listeye göre daha avantajlıdır. Dizi:

• Bilinmeyen sayıda öğe: Derleme zamanında gerekli eleman sayısı bilinmediğinde, bağlantılı liste elemanlar eklendikçe dinamik olarak bellek tahsis eder.
• Rasgele erişim: Rastgele indeksli erişime ihtiyaç duyulmadığında, bağlantılı liste uygun bir seçimdir.
• Ortaya yerleştirme: Bir dizinin ortasına eleman eklemek, elemanların kaydırılmasını gerektirir. Bağlı liste ise yalnızca birkaç işaretçiyi yeniden yazarak herhangi bir konuma eleman eklemeye olanak tanır.

OperaTek Bağlantılı Liste'nin özellikleri

Tek yönlü bağlantılı liste, dinamik bellek tahsisi için uygundur. Ekleme, silme, arama, güncelleme, iki listeyi birleştirme ve dolaşma gibi bağlantılı listenin standart işlemlerini destekler.

Bu makalede aşağıdaki işlemler ele alınmaktadır:

• Başlığa yerleştirme
• Kuyruğa ekleme
• Bir düğümden sonra ekleme
• Bir düğümden önce ekleme
• Baş düğümü sil
• Kuyruk düğümünü sil
• Bir düğümü arayın ve silin
• Bağlantılı Listede Gezinme

İşte dört düğümlü bir bağlantılı liste örneği.

Tek Bağlantılı Liste Örneği

Tek Yönlü Bağlantılı Listenin Başına Ekleme

Bu basit bir işlemdir. Genellikle Tek Yönlü Bağlantılı Listeye eleman ekleme olarak bilinir. Yeni bir düğüm oluşturulur ve listenin başına yerleştirilir.

Bu işlemi gerçekleştirmek için iki önemli koşula uymanız gerekmektedir:

1. Liste boşsa, yeni oluşturulan düğüm baş düğüm olur ve onun sonraki İşaretçi NULL'dur.
2. Liste boş değilse, yeni düğüm baş düğüm olur ve onun sonraki İşaretçi önceki baş düğümü gösteriyor.

İşte bağlantılı listenin başına bir düğüm eklemek için kullanılan sözde kod:

function insertAtHead(head, value):
  newNode = Node(value)
  if head is NULL:
    head = newNode
    return head
  else:
    newNode.next = head
    return newNode

Kafasına yerleştirme

Tek Yönlü Bağlantılı Listenin Sonuna Ekleme

Bağlı listenin sonuna bir düğüm eklemek, başa eklemeye benzer. Son düğüme kadar ilerleyin, ardından onu işaretleyin. sonraki Yeni düğüme işaretçi. Eğer baş düğüm NULL ise, yeni düğüm baş düğüm olur.

) 1 Adım Geçene kadar sonraki Geçerli düğümün işaretçisi NULL olur.

) 2 Adım Belirtilen değere sahip yeni bir düğüm oluşturun.

) 3 Adım Yeni düğümü kuyruk düğümünün bir sonraki düğümü olarak atayın.

Tek elemanlı bir listenin sonuna eleman eklemek için kullanılan sözde kod:

function insertAtEnd(head, value):
  newNode = Node(value)
  if head is NULL:
    head = newNode
    return head
  while head.next is not NULL:
    head = head.next
  head.next = newNode
  newNode.next = NULL

Kuyruğa yerleştirme

Tek Yönlü Bağlı Listede Bir Düğümden Sonra Ekleme

Bir düğümden sonra ekleme işlemi iki aşamadan oluşur: hedef düğümü aramak ve ondan sonra yeni bir düğüm eklemek. Eşleşme bulunana kadar listeyi dolaşın, ardından yeni düğümü ekleyin.

) 1 Adım Geçerli düğümün değeri arama öğesine eşit olana kadar ilerleyin.

) 2 Adım Yeni düğümün ayarlarını yapın. sonraki mevcut düğümün işaretçisi sonraki Işaretçi.

) 3 Adım Mevcut düğümün işaretini gösterin. sonraki Yeni düğüme işaretçi.

Sözde kod:

function insertAfter(head, value, searchItem):
  newNode = Node(value)
  while head.value != searchItem:
    head = head.next
  newNode.next = head.next
  head.next = newNode

Tek Bağlantılı Listedeki bir düğümden sonra düğüm ekleme

Tek Yönlü Bağlı Listede Bir Düğümden Önce Ekleme

Bu, bir düğümden sonra eklemeye benzer. Bir sonraki düğüm arama değeriyle eşleşene kadar ilerleyin, ardından yeni düğümü ondan önce ekleyin.

) 1 Adım Sonraki düğümün değeri arama öğesine eşit olana kadar ilerleyin.

) 2 Adım Yeni bir düğüm oluşturun ve ayarlarını yapın. sonraki mevcut düğümün işaretçisi sonraki.

) 3 Adım Mevcut düğümün işaretini gösterin. sonraki yeni düğüme.

function insertBefore(head, value, searchItem):
  newNode = Node(value)
  while head.next.value != searchItem:
    head = head.next
  newNode.next = head.next
  head.next = newNode

Tek Bağlantılı Listede bir düğümden önce bir düğüm ekleme

Tek yönlü bağlantılı listenin başını sil

Baş düğüm işaretçisi parametre olarak verilir. Baş düğüm kaldırılır ve bir sonraki düğüm yeni baş düğüm olur. Bellek sızıntılarını önlemek için silinen düğümün belleği serbest bırakılmalıdır.

) 1 Adım Baş düğümün bir sonraki noktasını yeni baş düğüm olarak atayın.

) 2 Adım Önceki ana düğümün tahsis ettiği belleği serbest bırakın.

) 3 Adım Yeni baş düğümü döndürün.

function deleteHead(head):
  temp = head
  head = head.next
  free(temp)
  return head

Bağlantılı listenin başlığını silme

Tek yönlü bağlantılı listenin sonunu silin.

Kuyruk düğümünü silmek, baş düğümünü silmeye benzer. Fark, listenin sonuna kadar gidilmesinin gerekli olmasıdır. Tek yönlü bağlantılı listede, düğümün sonraki İşaretçi NULL ise, bu kuyruk düğümüdür.

) 1 Adım Kuyruk düğümünün hemen öncesine kadar ilerleyin. Mevcut düğümü kaydedin.

) 2 Adım Sonraki düğümün (kuyruğun) belleğini serbest bırakın.

) 3 Adım Mevcut düğümün bir sonraki düğümünü NULL olarak ayarlayın.

function deleteTail(head):
  while head.next.next is not NULL:
    head = head.next
  free(head.next)
  head.next = NULL

Tek Bağlantılı Listenin kuyruğunu silme

Tek yönlü bağlantılı listeden bir düğümü arama ve silme

Bu fonksiyon iki görevi yerine getirir: arama ve silme. Listenin sonuna kadar ilerler. Eşleşen bir düğüm bulunursa, onu kaldırır ve önceki düğümün bağlantısını yeniden kurar. sonraki Işaretçi.

) 1 Adım Listenin sonuna kadar ilerleyin. Geçerli düğümün arama düğümüne eşit olup olmadığını kontrol edin.

) 2 Adım Eşleşme bulunursa, geçerli düğüme işaret eden bir göstericiyi saklayın.

) 3 Adım MKS sonraki Önceki düğümün bir sonraki düğümü, mevcut düğümün bir sonraki düğümü olur.

) 4 Adım Mevcut düğümü silin ve belleğini boşaltın.

function searchAndDelete(head, searchItem):
  while head.next.next is not NULL and head.next.value != searchItem:
    head = head.next
  temp = head.next
  head.next = head.next.next
  free(temp)

Tek Bağlantılı Listeden bir düğümü arayın ve silin

Tek Yönlü Bağlantılı Listeyi Gezme

Tek yönlü bağlantılı liste yalnızca baştan sona doğru gezinmeyi destekler. Önceki düğüme işaret eden bir gösterici olmadığından, ters yönde gezinme mümkün değildir. Her düğüm sırayla ziyaret edilir ve NULL değerine ulaşılana kadar değeri yazdırılır.

) 1 Adım NULL değerine ulaşılana kadar her düğümü dolaşın.

) 2 Adım Geçerli düğümün değerini yazdırın.

function traverse(head):
  while head is not NULL:
    print head.value
    head = head.next

Tek Bağlantılı Liste Örneği C++

#include<iostream>
using namespace std;
struct Node{
  int data;
  struct Node *next;
};
void insertAtHead(Node* &head, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  if(head != NULL){
    newNode->next = head;
  }
  head = newNode;
  cout<<"Added "<<newNode->data<<" at the front"<<endl;
}
void insertEnd(Node* &head, int value){
  if(head == NULL){
    insertAtHead(head, value);
    return;
  }
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *temp = head;
  while(temp->next != NULL){
    temp = temp->next;
  }
  temp->next = newNode;
  cout<<"Added "<<newNode->data<<" at the end"<<endl;
}
void searchAndDelete(Node **headPtr, int searchItem){
  Node *temp = NULL;
  if((*headPtr)->data == searchItem){
    temp = *headPtr;
    *headPtr = (*headPtr)->next;
    free(temp);
  } else {
    Node *currentNode = *headPtr;
    while(currentNode->next != NULL){
      if(currentNode->next->data == searchItem){
        temp = currentNode->next;
        currentNode->next = currentNode->next->next;
        free(temp);
        break;
      } else {
        currentNode = currentNode->next;
      }
    }
  }
  cout<<"Deleted Node\t"<<searchItem<<endl;
}
void insertAfter(Node* &headPtr, int searchItem, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *head = headPtr;
  while(head->next != NULL && head->data != searchItem){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  cout<<"Inserted "<<value<<" after node\t"<<searchItem<<endl;
}
void insertBefore(Node* &headPtr, int searchItem, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *head = headPtr;
  while(head->next != NULL && head->next->data != searchItem){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  cout<<"Inserted "<<value<<" before node\t"<<searchItem<<endl;
}
void traverse(Node *headPointer){
  Node* tempNode = headPointer;
  cout<<"Traversal from head:\t";
  while(tempNode != NULL){
    cout<<tempNode->data;
    if(tempNode->next)
      cout<<" --> ";
    tempNode = tempNode->next;
  }
  cout<<endl;
}
int main(){
  Node *head = NULL;
  insertAtHead(head, 5);
  insertAtHead(head, 6);
  insertAtHead(head, 7);
  insertEnd(head, 9);
  traverse(head);
  searchAndDelete(&head, 6);
  traverse(head);
  insertAfter(head, 7, 10);
  insertBefore(head, 9, 11);
  traverse(head);
}

Çıktı

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Traversal from head:    7 --> 6 --> 5 --> 9
Deleted Node    6
Traversal from head:    7 --> 5 --> 9
Inserted 10 after node  7
Inserted 11 before node 9
Traversal from head:    7 --> 10 --> 5 --> 11 --> 9

Tek Bağlantılı Liste Örneği Python

class Node:
  def __init__(self, data=None, next=None):
    self.data = data
    self.next = next
class SinglyLinkedList:
  def __init__(self):
    self.head = None
  def insertAtHead(self, value):
    newNode = Node(data=value)
    if self.head is not None:
      newNode.next = self.head
    self.head = newNode
    print(f'Added {newNode.data} at the front.')
  def insertAtEnd(self, value):
    if self.head is None:
      self.insertAtHead(value)
      return
    newNode = Node(value)
    temp = self.head
    while temp.next is not None:
      temp = temp.next
    temp.next = newNode
    print(f'Added {newNode.data} at the end.')
  def searchAndDelete(self, searchItem):
    if self.head is None:
      return
    if self.head.data == searchItem:
      self.head = self.head.next
      print(f'Deleted node\t{searchItem}')
      return
    currentNode = self.head
    while currentNode.next is not None:
      if currentNode.next.data == searchItem:
        currentNode.next = currentNode.next.next
        print(f'Deleted node\t{searchItem}')
        return
      currentNode = currentNode.next
  def insertAfter(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} after node\t{searchItem}')
  def insertBefore(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.next.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} before node\t{searchItem}')
  def traverse(self):
    temp = self.head
    print("Traversing from head:\t", end="")
    while temp:
      print("{}\t".format(temp.data), end="")
      temp = temp.next
    print()
singlyLinkedList = SinglyLinkedList()
singlyLinkedList.insertAtHead(5)
singlyLinkedList.insertAtHead(6)
singlyLinkedList.insertAtHead(7)
singlyLinkedList.insertAtEnd(9)
singlyLinkedList.traverse()
singlyLinkedList.searchAndDelete(6)
singlyLinkedList.traverse()
singlyLinkedList.insertAfter(7, 10)
singlyLinkedList.insertBefore(9, 11)
singlyLinkedList.traverse()

Çıktı

Added 5 at the front.
Added 6 at the front.
Added 7 at the front.
Added 9 at the end.
Traversing from head:   7       6       5       9
Deleted node    6
Traversing from head:   7       5       9
Inserted 10 after node  7
Inserted 11 before node 9
Traversing from head:   7       10      5       11      9

Tek Bağlantılı Listenin Karmaşıklığı

İki tür karmaşıklık vardır: zaman karmaşıklığı ve alan karmaşıklığı. Tek yönlü bağlantılı liste için en kötü ve ortalama durum zaman karmaşıklığı aynıdır.

En iyi senaryo zaman karmaşıklığı:

• Listenin başına ekleme işlemi O(1) sürede yapılabilir. Liste içinde gezinme gerekmez.
• Hedef eleman baş düğümde ise arama ve silme işlemleri O(1) sürede yapılabilir.

Ortalama durum zaman karmaşıklığı:

• Bağlı listeye ekleme işlemi O(n) zaman alır, burada n Toplam eleman sayısıdır.
• Arama ve silme işlemleri de O(n) zaman alabilir, çünkü hedef öğe kuyruk düğümüne kadar herhangi bir yerde bulunabilir.

Tek yönlü bağlantılı listenin alan karmaşıklığı

Tek yönlü bağlantılı liste, belleği dinamik olarak tahsis eder. Depolamak için n unsurları tahsis eder n bellek birimleri. Dolayısıyla alan karmaşıklığı O(n)'dir.

Tek Yönlü Bağlantılı Listelerin Uygulamaları

Tek yönlü bağlantılı listeler, yalnızca ileriye doğru gezinmenin ve dinamik belleğin yararlı olduğu birçok yerde karşımıza çıkar:

• Yığınlar ve kuyruklar: Düğümlerden oluşturulan LIFO yığınları ve FIFO kuyrukları için temel depolama alanı.
• Karma tablo zincirleme: Çakışmalar, her bir bölme için girişlerin tek yönlü bağlantılı listeye zincirlenmesiyle çözülür.
• Komşuluk listeleri: Seyrek grafikler, her köşe için tek yönlü bağlantılı bir komşu listesi kullanır.
• Sembol tabloları: Derleyiciler ve yorumlayıcılar, her kapsam için tanımlayıcıları tek yönlü bağlantılı bir liste halinde birbirine bağlar.
• Bellek ayırıcılar: Serbest liste tahsis edicileri track adet boş bloğu tek yönlü bağlantılı liste olarak tanımlayın.

SSS