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

Tek Bağlantılı Liste Nedir?

Tek Bağlantılı Liste, verilerin düğümlere kaydedildiği ve her düğümün bir sonraki düğüme bir bağlantı aracılığıyla 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 Bağlantılı Listelerde yalnızca bir yönde geçiş yapılabilirken Çift Bağlantılı Listelerde her iki yönde geçiş yapılabilir.

Tek Bağlantılı Listenin düğüm yapısı şöyledir:

Neden dizi üzerinde bağlantılı liste kullanılmalı?

Bağlantılı Listeyi kullanmanın daha iyi olduğu birkaç durum vardır. Dizi. İşte bazı senaryolar:

• Bilinmeyen sayıda öğe: Programın çalışma süresi boyunca kaç öğeyi saklamanız gerektiğini bilmiyorsanız Bağlantılı Listeyi kullanabilirsiniz. Bağlantılı listelere öğe ekledikçe bellek dinamik olarak tahsis edilir.
• Rasgele erişim: Öğelerin rastgele erişimini kullanmanıza gerek olmayan bir senaryoda Bağlantılı Liste'yi kullanabilirsiniz.
• Ortaya yerleştirme: Bir dizinin ortasına ekleme yapmak karmaşık bir iştir. Çünkü diğer elemanları sağa itmeniz gerekir. Ancak, bir bağlantılı liste istediğiniz herhangi bir konuma bir eleman eklemenize olanak tanır.

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

Tek Bağlantılı Liste, belleği dinamik olarak ayırmak için iyidir. Bağlantılı listenin tüm temel işlemlerini sağlar, yani ekleme, silme, arama, güncelleme, iki bağlantılı listeyi birleştirme, gezinme vb.

Burada bağlı listenin aşağıdaki işlemini ele alacağız:

• 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

Burada dört düğümden oluşan bağlantılı bir liste örneği verilmiştir.

Tek Bağlantılı Listenin başına ekleme

Bu basit bir işlemdir. Genellikle tek bağlantılı bir listenin itilmesi olarak bilinir. Yeni bir düğüm oluşturmanız ve bunu bağlantılı listenin başına yerleştirmeniz gerekir.

Bu operasyonu gerçekleştirmek için iki önemli şartı yerine getirmemiz gerekiyor. Onlar

1. Liste boşsa yeni oluşturulan düğüm baş düğüm olacak ve başın bir sonraki düğümü “NULL” olacaktır.
2. Liste boş değilse, yeni düğüm baş düğüm olacak ve bir sonraki, önceki baş düğüme işaret edecektir.

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

Tek Bağlantılı Listenin sonuna ekleme

Bağlantılı bir listenin sonuna bir düğüm eklemek, başa eklemekle bazı benzerliklere sahiptir. Tek yapmanız gereken son düğüme veya kuyruk düğümüne geçmek. Daha sonra uç düğümün “sonraki” düğümünü yeni oluşturulan düğüme yönlendirin. Baş düğüm boşsa, yeni düğüm baş düğüm olacaktır.

İşte adımlar:

) 1 Adım Geçerli düğümün "sonraki" düğümü null olana kadar ilerleyin.

) 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.

Tekli bir listenin kuyruğuna bir düğüm eklemek için sözde kod:

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

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

Bir düğümden sonra ekleme iki bölümden oluşur: Düğümü arayın ve aranan düğümden sonra ekleyin. Tüm düğümleri geçmemiz gerekiyor. Her düğüm için arama elemanıyla eşleşmemiz gerekiyor. Bir eşleşme varsa, yeni düğümü aranan düğümden sonra ekleyeceğiz.

İşte adımlar:

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

) 2 Adım Yeni düğümün bir sonraki işaretçisi mevcut düğümün bir sonraki işaretçisi olacaktır.

) 3 Adım Mevcut düğümün bir sonraki düğümü yeni düğüm olacaktır.

Bir düğümden sonra düğüm eklemek için kullanılan sözde kod aşağıda verilmiştir:

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

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

Bu işlev, bir düğümden sonra ekleme işlemine çok benzer. Yeni bir düğüm oluşturmalı ve mevcut düğüm arama düğümüyle eşleşene kadar bağlantılı listede dolaşmalıyız. Bundan sonra yeni düğümü mevcut düğümün bir önceki düğümü olarak ekleyeceğiz.

İşte adımlar:

) 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 düğümün “sonraki”ni mevcut düğümün bir sonraki düğümüne atayın.

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

İşte sözde kod:

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

Tek bağlantılı listenin başlığını silin

Bağlantılı listenin her fonksiyonunda, parametre olarak baş işaretçisi sağlanır. Baş düğümü silmeniz ve baş düğümün bir sonraki düğümünü bağlantılı listenin yeni başı yapmanız gerekir. Ayrıca silinen düğümün belleğini boşaltmamız gerekir. Aksi takdirde, başka bir program erişmeye çalıştığında bellek işgal edilmiş olarak işaretlenir.

Tek bağlantılı listenin başlığını silme adımları şunlardır:

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

) 2 Adım Ayrılan belleği önceki baş düğüm tarafından boşaltın.

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

Baş düğümü silmek için kullanılan sözde kod:

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

Tek bağlantılı listenin kuyruğunu silin

Kuyruk düğümünün silinmesi, baş düğümün silinmesine daha aşinadır. Aradaki fark, bağlantılı listenin sonuna gidip onu silmemiz gerektiğidir. Tek bağlantılı listede, bir sonraki düğümün “NULL” olduğu düğüm kuyruk düğümüdür.

Bağlantılı listenin kuyruk düğümünü silme adımları şunlardır:

) 1 Adım Kuyruk düğümünün önünden geçin. Geçerli düğümü kaydedin.

) 2 Adım Geçerli düğümün bir sonraki düğümünün belleğini boşaltın.

) 3 Adım Geçerli düğümün bir sonraki düğümünü NULL olarak ayarlayın.

İşte kuyruk düğümünü silmek için kullanılan sözde kod:

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

Tek bağlı listeden bir düğümü arayın ve silin

Bu fonksiyonun iki görevi vardır; arama ve silme. Tek bağlantılı listelerin sonuna kadar arama yapmamız gerekiyor. Benzer bir düğüm bulursak onu sileriz. Bundan sonra silinen düğümün sol ve sağ düğümlerini birleştirmemiz veya bağlamamız gerekir. Bunu yapmanın adımları şunlardır:

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

) 2 Adım Herhangi bir düğüm eşleşirse düğüm işaretçisini geçerli düğüme kaydedin.

) 3 Adım Önceki düğümün “sonraki”, mevcut düğümün bir sonraki düğümü olacaktır.

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

Tek bağlantılı bir listeden bir düğümü aramak ve silmek için sözde kod:

function searchAndDelete( head, searchItem ):
	while head.next.next is not NULL  and head.next.value is not equals searchItem :
		head = head.next
	head.next = head.next.next
	delete(head.next)

Tek bağlantılı bir listede gezinme

Tek bağlantılı liste yalnızca baştan sona geçiş yapma işlevine sahiptir. Önceki düğüme işaret eden hiçbir işaretçi noktası yoktur; bu yüzden Tek Bağlantılı Listeyi ters sırada geçemiyoruz. Her düğümden geçeceğiz ve geçerli düğümün değerini null elde edene kadar yazdıracağız.

İşte adımlar:

) 1 Adım Bir sonraki düğüm olarak null olana kadar her düğümü geçin.

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

Tek bağlantılı bir listede gezinmek için sözde kod:

function traverse( head ):
		while head.next is not NULL:
			print the value of the head
			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);
  }
  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 = new Node();
  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);
      }else{
        currentNode = currentNode->next;
      }
    }
  }
  cout<<"Deleted Node\t"<<searchItem<<endl;
  return;
}
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 = new 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 Programı

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.')
    return  
  def insertAtEnd(self,value):
    if self.head is None:
      self.insertAtHead(value)
    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):
    temp = Node()
    if self.head is searchItem:
      temp = self.head
      self.head = self.head.next
    else:
      currentNode = self.head
      while currentNode.next is not None:
        if currentNode.next.data is searchItem:
          temp = currentNode.next
          currentNode.next = currentNode.next.next
        else:
          currentNode = currentNode.next
    print(f'Deleted node\t{searchItem}')
    return
  def insertAfter(self,searchItem,value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.data is not searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} after node\t{searchItem}')
    return 
  def insertbefore(self,searchItem,value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.next.data is not searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} before node\t{searchItem}')
    return
  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 uzay karmaşıklığı. En kötü ve ortalama durum zaman karmaşıklığı Tek Bağlantılı Liste için aynıdır.

En iyi durum için zaman karmaşıklığı:

• Kafaya yerleştirme O(1)'de yapılabilir. Bağlantılı listenin içinde gezinmemize gerek olmadığı için.
• Eğer arama elemanı baş düğümde mevcutsa O(1)’de arama ve silme işlemi yapılabilir.

Ortalama bir vaka için zaman karmaşıklığı:

• Tek Bağlantılı Listede “n” öğe mevcutsa bağlantılı listenin içine ekleme işlemi O(n) alacaktır.
• Arama elemanı kuyruk düğümünde mevcut olabileceğinden, arama ve silme işlemi de O(n) alabilir. Bu durumda tüm listeyi geçmelisiniz.

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

Tek Bağlantılı Liste dinamik olarak bellek ayırır. n eleman depolamak istiyorsak, n bellek birimi ayırır. Bu nedenle, alan karmaşıklığı O(n)'dir.