Çift Bağlantılı Liste: C++, Python (Code Örnek)

Çift yönlü bağlantılı liste nedir?

Çift yönlü bağlantılı listede, her düğümün hem önceki hem de sonraki düğüme bağlantıları vardır. Her düğüm üç elemandan oluşur: biri veriyi tutar, diğer ikisi ise sonraki ve önceki düğüme işaretçilerdir. Bu iki işaretçi, belirli bir düğümden ileri veya geri hareket etmeye yardımcı olur.

İşte çift yönlü bağlantılı listenin temel yapısı.

Çift Bağlantılı Listenin Yapısı

Her bağlantılı listenin bir baş ve bir kuyruk düğümü vardır. Baş düğümün hiçbir işlevi yoktur. prev (önceki işaretçi) düğümü ve kuyruk düğümünün hiçbir özelliği yok. sonraki düğümü.

İşte çift yönlü bağlantılı liste için bazı önemli terimler:

• Önceki: Her düğüm bir önceki düğüme bağlıdır. İşaretçi veya bağlantı olarak kullanılır.
• Sonraki: Her düğüm bir sonraki düğüme bağlanır. İşaretçi veya bağlantı olarak kullanılır.
• Veri: Bu, bir düğümde veri depolamak için kullanılır. Veriler başka bilgiler de içerebilir. Veri Yapıları İçine örneğin, dize, sözlük, küme, hashmap ve diğer yapılar kaydedilebilir.

İşte çift yönlü bağlantılı listedeki tek bir düğümün temel yapısı:

Çift Bağlantılı Listedeki bir düğümün yapısı

OperaÇifte Bağlantılı Liste'nin özellikleri

Çift yönlü bağlantılı listenin işlemleri arasında düğüm ekleme, silme, ekleme ve kaldırma işlemlerinin yanı sıra listede yukarıdan aşağıya veya aşağıdan yukarıya doğru gezinme de yer alır.

İşte çift yönlü bağlantılı liste üzerinde uygulanabilecek işlemlerin listesi:

• Ön tarafa yerleştirme
• Kuyruk veya son düğüme ekleme
• Bir düğümden sonra ekleme
• Bir düğümden önce ekleme
• Önden silme
• Kuyruktan silme
• Bir düğümü arayın ve silin
• Baştan sona geç
• Kuyruktan başa doğru geç

Bu işlemlerin her birinin uygulaması ve sözde kodu aşağıda verilmiştir.

Çift Yönlü Bağlantılı Listede Başa Ekleme

Öne ekleme, bağlantılı listede bir düğüm oluşturup onu listenin başına yerleştirmek anlamına gelir.

Örneğin, belirli bir düğüm vardır. 15Bu, baş düğüm olarak eklenmelidir.

Bu işlemi gerçekleştirirken iki önemli koşul geçerlidir:

1. Çift yönlü bağlantılı liste boşsa, yeni düğüm baş düğüm olur.
2. Eğer halihazırda bir baş düğüm varsa, önceki baş düğüm yeni düğümle değiştirilir.

İşte bu işlemin sözde kodu:

function insertAtFront(ListHead, value):
  newNode = Node()
  newNode.value = value
  ListHead.prev = newNode
  newNode.next = ListHead
  newNode.prev = NULL
  return ListHead

Ön düğüme ekleme

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

Sona ekleme, bağlantılı listede bir düğüm oluşturup onu listenin sonuna yerleştirmek anlamına gelir.

Bu işlemi gerçekleştirmek için iki yöntem vardır:

• Yöntem 1: Çift yönlü bağlantılı listenin başından başlayarak sırayla ilerleyin. sonraki null olur. Ardından yeni düğümü ile bağlayın. sonraki Işaretçi.
• Yöntem 2: Çift yönlü bağlantılı listenin son düğümünü alın. Ardından, sonraki Son düğümün işaretçisi yeni düğümü gösterir. Yeni düğüm kuyruk düğümü olur.

Kuyruk düğümüne ekleme için sözde kod aşağıdadır:

function insertAtTail(ListHead, value):
  newNode = Node()
  newNode.value = value
  newNode.next = NULL
  while ListHead.next is not NULL:
    ListHead = ListHead.next
  newNode.prev = ListHead
  ListHead.next = newNode
  return ListHead

Bağlantılı listenin sonuna ekleme

Bir Düğümden Sonra Ekleme

Aşağıdaki gibi mevcut bir Çift Yönlü Bağlantılı Listeyi ele alalım:

Amaç, belirli bir değere sahip düğümden sonra bağlanacak olan belirli bir düğümü eklemektir. 12.

) 1 Adım Baş düğümden son düğüme kadar ilerleyin. Hangi düğümün değere sahip olduğunu kontrol edin. 12.

) 2 Adım Yeni bir düğüm oluşturun ve onu düğümün bir sonraki işaretçisi olarak atayın. 12. sonraki Yeni düğümün düğüm sayısı 15 olacaktır.

İşte çift yönlü bağlantılı listede bir düğümden sonra bir düğüm eklemek için kullanılan sözde kod:

function insertAfter(ListHead, searchItem, value):
  List = ListHead
  newNode = Node()
  newNode.value = value
  while List.value is not equal searchItem:
    List = List.next
  newNode.next = List.next
  newNode.prev = List
  List.next = newNode

Bir Düğümden Sonra Ekleme

Düğümden Önce Ekleme

Bu işlem, bir düğümden sonra ekleme işlemine benzer. Belirli bir düğüm değeri aranır, ardından yeni bir düğüm oluşturulur ve aranan düğümden önce eklenir.

Belirli bir düğümü eklemek için 15 düğümden önce 12, bu adımları takip et:

) 1 Adım Bağlantılı listeyi baş düğümden kuyruk düğümüne taşıyın.

) 2 Adım Geçerli düğümün bir sonraki işaretçisinin değerinin olup olmadığını kontrol edin. 12.

) 3 Adım Yeni düğümü şu şekilde ekleyin: sonraki Mevcut düğümün düğümü.

İşte çift yönlü bağlantılı listede bir düğümden önce başka bir düğüm eklemek için kullanılan sözde kod:

function insertBefore(ListHead, searchItem, value):
  List = ListHead
  newNode = Node()
  newNode.value = value
  while List.next.value is not equal searchItem:
    List = List.next
  newNode.next = List.next
  newNode.prev = List
  List.next = newNode

Düğümden Önce Düğüm Ekleme

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

Çift yönlü bağlantılı listedeki baş düğümün kendisinden önce gelen bir düğümü yoktur. Dolayısıyla sonraki Mevcut baş düğüm kaldırıldığında, işaretçi yeni baş düğüm olur. Silinen düğümün kapladığı belleğin serbest bırakılması da gereklidir.

İşte ana düğümü silme adımları:

) 1 Adım Geçerli baş düğüme bir değişken atayın.

) 2 Adım Airdrop formunu doldurun : sonraki mevcut baş düğümün düğümünü oluşturun ve prev İşaretçi NULL. Bu, ikinci düğümü birinci düğümden ayırır.

) 3 Adım Önceki ana düğümün kullandığı belleği boşaltın.

İşte çift yönlü bağlantılı listeden baş elemanı silmek için kullanılan sözde kod:

function deleteHead(ListHead):
  PrevHead = ListHead
  ListHead = ListHead.next
  ListHead.prev = NULL
  PrevHead.next = NULL
  free memory(PrevHead)
  return ListHead

Baş düğümün silinmesi

Herhangi bir silme işleminden sonra ayrılan belleğin serbest bırakılması gereklidir. Aksi takdirde, silinen bloğa ait bellek programın tüm çalışma süresi boyunca işgal altında kalır ve başka hiçbir uygulama bu bellek bölümünü kullanamaz.

Çift yönlü bağlantılı listenin kuyruğunu silin.

Bu işlem, baş düğümün silinmesine benzer. Baş düğüm yerine, kuyruk düğümü silinir. Bir düğümü kuyruk düğümü olarak tanımlamak için, next işaretçisinin null olup olmadığı kontrol edilir. Kuyruk düğümü silindikten sonra, bellek serbest bırakılmalıdır.

Bu işlem aynı zamanda şu şekilde de bilinir: arkadan silme.

Bunu yapmak için adımlar şunlardır:

) 1 Adım Çift yönlü bağlantılı listenin son düğümüne kadar ilerleyin.

) 2 Adım Kuyruk düğümüne bir değişken veya işaretçi atayın.

) 3 Adım Yı kur sonraki İşaretçiyi NULL'a ayarlayın ve kuyruk düğümünün belleğini serbest bırakın.

Kuyruk düğümünü silmek için kullanılan sözde kod aşağıdadır:

function deleteTail(ListHead):
  head = ListHead
  while ListHead.next is not NULL:
    ListHead = ListHead.next
  Tail = ListHead
  ListHead.prev.next = NULL
  free memory(Tail)
  return head

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

Bu işlem, belirli bir düğüm değerini arar ve o düğümü siler. Bağlı liste doğrusal bir veri yapısı olduğundan doğrusal arama gereklidir. Silme işleminden sonra bellek serbest bırakılmalıdır.

Çift yönlü bağlantılı listede bir düğümü arama ve silme adımları şunlardır:

) 1 Adım Bağlantılı listeyi baştan başlayarak, düğüm değeri arama öğesine eşit olana kadar dolaşın.

) 2 Adım Bir değişkene atama yapın Düğümü sil Eşleşen düğüme.

) 3 Adım Önceki düğümü bağlayın. Düğümü sil bir sonraki düğüme gidin ve bir sonraki düğümün ayarlarını yapın. prev Önceki düğüme işaretçi.

) 4 Adım Anıları özgür bırak Düğümü sil.

İşte bağlantılı listeden bir düğümü arama ve silme işlemi için sözde kod:

function searchAndDelete(ListHead, searchItem):
  head = ListHead
  while head.value not equals searchItem:
    head = head.next
  deleteNode = head
  head.prev.next = head.next
  if head.next is not NULL:
    head.next.prev = head.prev
  free memory(deleteNode)
  return ListHead

Arama ve silme işlemi

İleri Yönden Çift Yönlü Bağlantılı Listeyi Gezme

Başlangıç ​​düğümünden başlayarak, NULL bulunana kadar bir sonraki düğüme geçilir. Her düğüme geçilirken, değer yazdırılabilir. İleri yönde ilerleme adımları şunlardır:

) 1 Adım Geçerli baş düğüme bir işaretçi veya değişken atayın.

) 2 Adım Baş düğümün bir sonraki düğümüne, NULL değeri elde edilene kadar ilerleyin.

) 3 Adım Her yinelemede düğüm verilerini yazdırın.

) 4 Adım Baş düğümü döndürün.

İşte çift yönlü bağlantılı bir listeyi önden dolaşmak için kullanılan sözde kod:

function traverseFromFront(ListHead):
  head = ListHead
  while head not equals NULL:
    print head.data
    head = head.next
  return ListHead

Geri dönüş zorunlu değildir. Ancak, işlemlerden sonra ana düğümü geri döndürmek iyi bir uygulamadır.

Çift Yönlü Bağlantılı Listeyi Geriden Dolaşarak Gezme

Bu işlem, önden yapılan geçişin tersidir. Yaklaşım aynıdır, ancak küçük bir fark vardır: önce bitiş noktasına ulaşın, ardından geriye doğru yürüyerek başa ulaşın. prev Işaretçi.

İşte çift yönlü bağlantılı bir listede arkadan başlayarak gezinme adımları:

) 1 Adım Kuyruk düğümüne ulaşılana kadar ilerleyin.

) 2 Adım Kuyruk düğümünden başlayarak, aşağıdaki komutu kullanarak ilerleyin. prev Önceki düğüm NULL olana kadar. prev Baş düğüm için işaretçi null'dur.

) 3 Adım Her yinelemede, düğüm verilerini yazdırın.

İşte geriye doğru gezinmek için kullanılan sözde kod:

function traverseFromBack(ListHead):
  head = ListHead
  while head.next is not NULL:
    head = head.next
  tail = head
  while tail is not NULL:
    print tail.value
    tail = tail.prev
  return ListHead

Tek Yönlü ve Çift Yönlü Bağlantılı Listeler Arasındaki Fark

Tek yönlü bağlantılı liste ile çift yönlü bağlantılı liste arasındaki temel fark, her düğümün sahip olduğu bağlantı sayısıdır.

Tek yönlü bağlantılı liste ve çift yönlü bağlantılı listenin düğümleri arasındaki fark şöyledir:

Çift Bağlantılı Liste C++

Aşağıda eksiksiz bir liste bulunmaktadır. C++ Ekleme, silme, arama ve dolaşma işlemlerini içeren çift yönlü bağlantılı listenin uygulanması.

#include<iostream>
using namespace std;
struct node{
  int data;
  struct node *next;
  struct node *prev;
};
void insertFront(node* &listHead, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  if(listHead != NULL){
    listHead->prev = newNode;
    newNode->next = listHead;
  }
  listHead = newNode;
  cout<<"Added "<<value<<" at the front"<<endl;
}
void insertEnd(node* &listHead, int value){
  if(listHead == NULL){
    insertFront(listHead, value);
    return;
  }
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next != NULL){
    head = head->next;
  }
  head->next = newNode;
  newNode->prev = head;
  cout<<"Added "<<value<<" at the end"<<endl;
}
void insertAfter(node* &listHead, int searchValue, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next != NULL && head->data != searchValue){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  newNode->prev = head;
  if(newNode->next != NULL){
    newNode->next->prev = newNode;
  }
  cout<<"Inserted "<<value<<" after node "<<searchValue<<endl;
}
void insertBefore(node* &listHead, int searchValue, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next != NULL && head->next->data != searchValue){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  newNode->prev = head;
  if(newNode->next != NULL){
    newNode->next->prev = newNode;
  }
  cout<<"Inserted "<<value<<" before node "<<searchValue<<endl;
}
void traverseFromFront(node *listHead){
  node* head = listHead;
  cout<<"Traversal from head:\t";
  while(head != NULL){
    cout<<head->data<<"\t";
    head = head->next;
  }
  cout<<endl;
}
void traverseFromEnd(node *listHead){
  node* head = listHead;
  cout<<"Traversal from tail:\t";
  while(head->next != NULL){
    head = head->next;
  }
  node *tail = head;
  while(tail != NULL){
    cout<<tail->data<<"\t";
    tail = tail->prev;
  }
  cout<<endl;
}
void searchAndDelete(node **listHead, int searchItem){
  node* head = (*listHead);
  while(head != NULL && head->data != searchItem){
    head = head->next;
  }
  if(*listHead == NULL || head == NULL) return;
  if((*listHead)->data == head->data){
    *listHead = head->next;
  }
  if(head->next != NULL){
    head->next->prev = head->prev;
  }
  if(head->prev != NULL){
    head->prev->next = head->next;
  }
  free(head);
  cout<<"Deleted Node\t"<<searchItem<<endl;
}
int main(){
  node *head = NULL;
  insertFront(head, 5);
  insertFront(head, 6);
  insertFront(head, 7);
  insertEnd(head, 9);
  insertEnd(head, 10);
  insertAfter(head, 5, 11);
  insertBefore(head, 5, 20);
  traverseFromFront(head);
  traverseFromEnd(head);
  searchAndDelete(&head, 7);
  traverseFromFront(head);
  traverseFromEnd(head);
}

Çıktı

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

Çift Bağlantılı Liste Python

Aşağıda eksiksiz bir liste bulunmaktadır. Python Düğümler ve listenin kendisi için sınıflar kullanarak çift yönlü bağlantılı listenin uygulanması.

class Node:
  def __init__(self, data=None, prev=None, next=None):
    self.data = data
    self.next = next
    self.prev = prev
class DoublyLinkedList:
  def __init__(self):
    self.head = None
  def insertFront(self, val):
    newNode = Node(data=val)
    newNode.next = self.head
    if self.head is not None:
      self.head.prev = newNode
    self.head = newNode
    print("Added {} at the front".format(val))
  def insertEnd(self, val):
    newNode = Node(data=val)
    if self.head is None:
      self.head = newNode
      print("Added {} at the end".format(val))
      return
    temp = self.head
    while temp.next is not None:
      temp = temp.next
    temp.next = newNode
    newNode.prev = temp
    print("Added {} at the end".format(val))
  def traverseFromFront(self):
    temp = self.head
    print("Traversing from head:\t", end="")
    while temp is not None:
      print("{}\t".format(temp.data), end="")
      temp = temp.next
    print()
  def traverseFromEnd(self):
    temp = self.head
    print("Traversing from tail:\t", end="")
    while temp.next is not None:
      temp = temp.next
    tail = temp
    while tail is not None:
      print("{}\t".format(tail.data), end="")
      tail = tail.prev
    print()
  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
    newNode.prev = temp
    if newNode.next is not None:
      newNode.next.prev = newNode
    print("Inserted {} after node {}".format(value, 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
    newNode.prev = temp
    if newNode.next is not None:
      newNode.next.prev = newNode
    print("Inserted {} before node {}".format(value, searchItem))
  def searchAndDelete(self, searchItem):
    temp = self.head
    while temp is not None and temp.data != searchItem:
      temp = temp.next
    if self.head is None or temp is None:
      return
    if self.head.data == temp.data:
      self.head = temp.next
    if temp.next is not None:
      temp.next.prev = temp.prev
    if temp.prev is not None:
      temp.prev.next = temp.next
    print("Deleted Node\t{}".format(searchItem))
doublyLinkedList = DoublyLinkedList()
doublyLinkedList.insertFront(5)
doublyLinkedList.insertFront(6)
doublyLinkedList.insertFront(7)
doublyLinkedList.insertEnd(9)
doublyLinkedList.insertEnd(10)
doublyLinkedList.insertAfter(5, 11)
doublyLinkedList.insertBefore(5, 20)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()
doublyLinkedList.searchAndDelete(7)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()

Çıktı

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

Çift Bağlantılı Listenin Karmaşıklığı

Zaman karmaşıklığı genel olarak üç türe ayrılır: en iyi durum, ortalama durum ve en kötü durum.

Çift Bağlantılı Liste için en iyi durumda zaman karmaşıklığı:

1. Baş veya son düğüme ekleme işlemi O(1) maliyetlidir çünkü bağlantılı liste içinde herhangi bir dolaşım gerekmez. Baş ve son işaretçileri, baş ve son düğümlere doğrudan erişim sağlar.
2. Baş veya kuyruktan silme işlemi O(1) maliyetindedir.
3. Hedef düğüm baş düğüm olduğunda bir düğümü aramanın maliyeti O(1)'dir.

Çift Bağlantılı Liste için ortalama durumda zaman karmaşıklığı:

1. Baş veya kuyruk kısmına eklemenin maliyeti O(1)'dir.
2. Baş veya kuyruktan silme işlemi O(1) maliyetindedir.
3. Bir düğümü aramak O(n) maliyetindedir, çünkü hedef listede herhangi bir yerde bulunabilir. Burada, n Toplam düğüm sayısıdır.

Çift yönlü bağlantılı listenin en kötü durum zaman karmaşıklığı, ortalama durumla aynıdır.

Çift Bağlantılı Listenin Bellek Karmaşıklığı

Bellek karmaşıklığı O(n)'dir, burada n , toplam düğüm sayısıdır. Bağlı liste oluşturulurken bellek serbest bırakılmalıdır. Aksi takdirde, daha büyük bağlı listeler bellek sızıntılarına neden olur.

Çift Yönlü Bağlantılı Listelerin Uygulamaları

Çift yönlü bağlantılı listeler, çift yönlü geçişin birçok yaygın işlemi basitleştirmesi nedeniyle gerçek dünyadaki birçok veri yapısını destekler.

• LRU önbelleği: En az kullanılan önbellekler, O(1) öne taşıma ve çıkarma için karma haritalı çift yönlü bağlantılı liste kullanır.
• Tarayıcı geçmişi: Geri ve ileri gezinme, bağlantılı listede her iki yönde de gezinmeyi sağlar.
• Geri alma ve yineleme yığınları: Editörler ve IDE'ler tracÖnceki ve sonraki işaretçilere sahip k belge sürümü.
• Deque: DoubleUçtan uca kuyruklar, her iki uçtan da O(1) sürede push ve pop yapar.
• Müzik çalma listeleri: Önceki ve sonraki tracK tuşları geri ve ileri işaretçilere bağlıdır.

SSS