Çift Bağlantılı Liste: C++, Python (Kod Örneği)
Çift bağlantılı liste nedir?
Çift bağlantılı listede her düğümün hem önceki hem de sonraki düğüme bağlantıları vardır. Her düğüm üç öğeden oluşur: biri verileri tutar, diğer ikisi ise sonraki ve önceki düğümün işaretçileridir. Bu iki işaretçi belirli bir düğümden ileri veya geri gitmemize yardımcı olur.
İşte çift bağlantılı listenin temel yapısı.

Her bağlantılı listenin bir baş ve kuyruk düğümü vardır. Baş düğümün "önceki" (önceki işaretçi) düğümü yoktur ve kuyruk düğümünün "sonraki" düğümü yoktur.
Çift bağlantılı bir liste için bazı önemli terimler şunlardır:
- Ö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, verileri bir düğümde depolamak için kullanılır. “Veri” diğerlerini tutabilir Veri Yapıları içinde. Örneğin string, sözlük, set, hashmap vb. “Veri” içerisinde saklanabilir.
Çift bağlantılı listedeki tek bir düğümün temel yapısı şöyledir:

OperaÇifte Bağlantılı Liste'nin özellikleri
Çift bağlantılı bir listenin işlemleri arasında düğüm ekleme ve silme, düğüm ekleme ve çıkarma ve bağlantılı listede yukarıdan aşağıya doğru geçiş yapma yer alır.
Çift bağlantılı listeyi kullanarak uygulayabileceğimiz işlemlerin listesi:
- Ön tarafa yerleştirme
- Kuyruğa 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ç
Yukarıdaki tüm işlemler için uygulamayı ve sözde kodu göreceğiz.
Çifte Bağlantılı Listenin önüne ekleme
Öne ekleme, bağlantılı listede bir düğüm oluşturmamız ve onu bağlantılı listenin başına yerleştirmemiz gerektiği anlamına gelir.
Örneğin, belirli bir “15” düğümü var. Bunu baş düğüme eklememiz gerekiyor.
Bu işlemi yaparken iki önemli koşul vardır:
- Çift Bağlantılı Listede hiçbir düğüm yoksa yeni düğüm baş düğüm olacaktır.
- Zaten bir baş düğüm varsa, önceki başın yerini yeni düğüm alacaktır.
İş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
Çift Bağlantılı Listenin sonuna ekleme
“Sona ekleme”, bağlantılı listede bir düğüm oluşturup onu en sona yerleştireceğimiz anlamına gelir.
Bunu gerçekleştirmek için iki yöntem kullanabiliriz:
- Yöntem 1: “Sonraki” boş hale gelene kadar Çift Bağlantılı Listenin başından geçmeye başlayın. Ardından yeni düğümü “sonraki” ile bağlayın.
- Yöntem 2: Çift Bağlantılı Listenin son düğümünü alın. Daha sonra son düğümün “sonraki” düğümü yeni düğüme bağlanacaktır. Artık yeni düğüm kuyruk düğümü olacak.
İşte kuyruk düğümüne eklenecek sözde kod:
function insertAtTail(ListHead, value): newNode = Node() newNode.value = value newNode.next = NULL while ListHead.next is not NULL: then ListHead = ListHead.next newNode.prev = ListHead ListHead.next = newNode return ListHead
Bir düğümden sonra ekleme
Aşağıdaki gibi çift yönlü bağlı bir listemiz olduğunu varsayalım:
“12” değerine sahip düğümden sonra bağlanacak belirli bir düğümü eklemek istiyoruz.
İşte bunun için adımlar:
) 1 Adım Baştan son düğüme kadar ilerleyin. Hangi düğümün “12” değerine sahip olduğunu kontrol edin.
) 2 Adım Yeni bir düğüm oluşturun ve onu “12” düğümünün bir sonraki işaretçisi olarak atayın. Yeni düğümün “sonraki” düğümü 15 olacaktır.
Çift bağlantılı listede bir düğümden sonra bir düğüm eklemek için sözde kod:
function insertAfter(ListHead, searchItem, value): List = ListHead NewNode = Node() NewNode.value = value while List.value is not equal searchItem then List = ListHead.next List = List.next NewNode.next = List.next NewNode.prev = List List.next = NewNode
Bir düğümden önce ekleme
Bu işlem daha çok "düğümden sonra ekleme" işlemine benzer. Bunu gerçekleştirmek için belirli bir düğümün değerini aramamız gerekir. Daha sonra yeni bir düğüm oluşturup onu aranan düğümün önüne ekleyeceğiz.
Diyelim ki belirli bir “15” düğümünü “12” düğümünün önüne eklemek istiyoruz. O zaman işte bunu yapmanın adımları:
) 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 “12” değerine sahip olup olmadığını kontrol edin.
) 3 Adım Yeni düğümü mevcut düğümün "sonraki" düğümü olarak ekleyin.
Çift Bağlantılı Listede bir düğümün önüne bir düğüm eklemek için sözde kod:
function insertBefore(ListHead, searchItem, value): List = ListHead NewNode = Node() NewNode.value = value while List.next.value is not equal searchItem then List = ListHead.next NewNode.next = List.next NewNode.prev = List List.next = NewNode
Çift bağlantılı listenin başını silin
Çift bağlantılı listede daha önce herhangi bir düğümü olmayan baş düğüm. Yani eğer baş düğümü silmek istersek bir sonraki işaretçi yeni baş düğüm olacaktır. Bir düğümü silerken aynı zamanda düğümün kapladığı hafızayı da boşaltmamız gerekir.
Baş düğümü silme adımları şunlardır:
) 1 Adım Geçerli baş düğüme bir değişken atayın.
) 2 Adım Mevcut baş düğümün “sonraki” düğümünü ziyaret edin ve “önceki” (önceki işaretçi) düğümünü ''NULL'' yapın. Bu, ikinci düğümün birinci düğümle olan bağlantısını kestiğimiz anlamına gelir.
) 3 Adım Önceki baş düğümün işgal ettiği belleği boşaltın.
Çift bağlantılı bir listeden başlığı 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
Herhangi bir silme işlemi gerçekleştirildikten sonra tahsis edilen belleğin silinmesi gerekir. Aksi takdirde, programın tüm çalışma zamanı boyunca, silinen blok için bellek meşgul kalacaktır. Başka hiçbir uygulama bu bellek segmentini kullanamaz.
Çift bağlantılı listenin kuyruğunu silin.
Bu operasyon bir nevi kafanın silinmesiyle aynıdır. Burada kafa yerine kuyruğu silmemiz gerekiyor. Bir düğümü kuyruk düğümü olarak tanımlamak için sonraki işaretçinin veya sonraki düğümün boş olup olmadığını kontrol etmeliyiz. Kuyruğu sildikten sonra hafızayı boşaltmamız gerekiyor.
Bu operasyona “arkadan silme” adı da verilmektedir.
Bunu yapmanın adımları şunlardır:
) 1 Adım Çift bağlantılı listenin kuyruk 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 “Sonraki” düğümü NULL yapın ve kuyruk düğümünün hafızasını boşaltın.
İşte kuyruk düğümünü silmek için kullanılan sözde kod:
function DeleteTail( ListHead ): head = ListHead while ListHead.next is not NULL: ListHead = ListHead.next Tail = ListHead.next ListHead.next = NULL free memory( Tail ) return head
Çift Bağlantılı Listeden bir düğümü arayın ve silin
Bu işlem, belirli bir düğüm verisini aramamıza ve o düğümü silmemize olanak tanır. Bağlantılı liste doğrusal bir veri yapısı olduğundan doğrusal bir arama yapmamız gerekir. Sildikten sonra hafızayı da boşaltmamız gerekiyor.
Çift bağlantılı listede bir düğümü arama ve silme adımları şunlardır:
) 1 Adım Düğümün değeri arama öğesine eşit olana kadar bağlantılı listeyi baştan sona dolaşın.
) 2 Adım Eşleşen düğüme bir "deleteNode" değişkeni atayın.
) 3 Adım “DeleteNode”un önceki düğümünü bir sonraki düğüme atayın.
) 4 Adım “DeleteNode”un hafızasını boşaltın
İşte bağlı listeden bir düğümü aramak ve silmek için kullanılan sözde kod:
function SearchAndDelete(ListHead, searchItem): head = ListHead while ListHead.next.value not equals searchItem: head = head.next deleteNode = head.next head.next = head.next.next head.next.prev = head deleteNode.next, deleteNode.next = NULL free memory(deleteNode) return ListHead
Çift bağlantılı bir listede ileriden geçiş yapma
Baş düğümden geçmek ve “NULL”u bulana kadar bir sonraki düğümü yinelemek. Her düğümü geçerken düğümün değerini yazdırabiliriz. Önden (ileri yönde) geçiş 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 “NULL” elde edene kadar kafanın bir sonraki düğümüne yineleyin
) 3 Adım Her yinelemede düğümün verilerini yazdırın.
) 4 Adım Baş düğümü döndürün.
Çifte Bağlantılı Listeyi önden gezmek için kullanılan sözde kod:
function traverseFromFront(ListHead): head = ListHead while head not equals to NULL: print head.data head = head.next return ListHead
Burada iade zorunlu değildir. Ancak operasyonlardan sonra baş düğümü geri döndürmek iyi bir uygulamadır.
Çift bağlantılı bir listede geriye doğru geçiş yapma
Bu işlem önden traversin tersidir. Yaklaşım küçük bir farkla aynı. Son düğüme gitmeli ve ardından uç düğümden ön düğüme geçmeliyiz.
Çift bağlantılı bir listenin arkadan geçişine ilişkin adımlar şunlardır:
) 1 Adım Kuyruk düğümüne ulaşana kadar ilerleyin.
) 2 Adım Kuyruk düğümünden bir önceki düğümü “NULL” olarak elde edene kadar geçeceğiz. “Önceki” (önceki işaretçi) baş düğüm için boş olacaktır
) 3 Adım Her yinelemede düğüm verilerini yazdıracağız.
İşte arkadan geçiş için sözde kod:
function traverseFromBack(ListHead): head = ListHead while head not equals NULL: head = head.next tail = head while tail not equal to NULL: print tail.value tail = tail.prev return ListHead
Tekli ve Çift bağlantılı liste arasındaki fark
Tekli ve Çift Bağlantılı liste arasındaki temel fark, bağlantıların sayısıdır.
Tek Bağlantılı listenin düğümleri ile Çift Bağlantılı Listenin düğüm yapısı arasındaki fark şu şekildedir:
Alan | Tek Bağlantılı Liste | Çift Bağlantılı Liste |
---|---|---|
Structure | Tek Bağlantılı Liste bir veri alanına ve bir sonraki düğüme bir bağlantıya sahiptir. | Çift Bağlantılı Listede bir veri alanı ve iki bağlantı bulunur. Biri önceki düğüm için, diğeri sonraki düğüm için. |
Geçişi | Yalnızca baştan kuyruğa doğru hareket edebilir. | Hem ileri hem de geri hareket edebilir. |
Bellek | Daha az hafıza kaplar. | Tek bağlantılı listeden daha fazla hafıza kaplar. |
Engellilerin kullanımları için uygunluk | Tek Bağlantılı Listeler, sonraki düğüme yalnızca bir bağlantı kullandıklarından daha az verimlidir. Önceki düğüm için bağlantı yok. | Çift Bağlantılı Listeler Tek Bağlantılı Listelerden daha verimlidir. |
Çift Bağlantılı Liste C++
#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); } 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 = new 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 = new node(); head = listHead; cout<<"Traversal from head:\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 = new node(); head = (*listHead); while(head->next!=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; return; } 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 Aded 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 head: 10 9 11 5 20 6 7 Deleted Node 7 Traversal from head: 6 20 5 11 9 10 Traversal from head: 10 9 11 5 20 6
Çift Bağlantılı Liste Python
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.insertFront(val) 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: 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 is not 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 is not 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.next is not None and temp.data is not searchItem: temp = temp.next if self.head is None or temp is None: return if self.head.data is 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)) return 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.
Bunlar:
- En iyi senaryo
- Ortalama Vaka
- En kötü durumda
Çift Bağlantılı Liste için en iyi durumda zaman karmaşıklığı:
- Baş veya kuyrukta ekleme O(1)'e mal olacak. Çünkü bağlantılı listenin içinde dolaşmamıza gerek yok. Baş ve kuyruk işaretçisi bize baş ve kuyruk düğümüne O(1) zaman karmaşıklığıyla erişim sağlayabilir.
- Baştan veya kuyruktan silme işlemi O(1)'e mal olacaktır.
- Bir düğümü aramanın zaman karmaşıklığı O(1) olacaktır. Çünkü hedef düğüm baş düğüm olabilir.
Çift Bağlantılı Liste için ortalama durumda zaman karmaşıklığı:
- Baş veya kuyruk kısmına yerleştirmenin zaman karmaşıklığı O(1) maliyetinde olacaktır.
- Baş veya kuyruktan silmenin zaman karmaşıklığı O(1) maliyetinde olacaktır.
- Bir düğümü aramanın zaman karmaşıklığı O(n) olacaktır. Çünkü arama öğesi bağlantılı liste arasında herhangi bir yerde bulunabilir. Burada, "n" bağlantılı listede bulunan toplam düğümdür.
Çift yönlü bağlı listenin en kötü durumdaki zaman karmaşıklığı, ortalama durumla aynı olacaktı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ğlantılı listeyi uygularken kullandığımız belleği serbest bırakmalıyız. Aksi takdirde, daha büyük bir bağlantılı liste için bellek sızıntılarına neden olur.
ÖZET
- Bağlantılı liste, bir tür doğrusal veri yapısıdır; doğrusal bir şekilde temsil edilen bir veri koleksiyonudur.
- Çift bağlantılı liste, bir düğümün hem önceki hem de sonraki düğümle bağlantılara sahip olduğu bir bağlantılı liste türüdür.
- Çift bağlantılı liste, bir düğüm eklemek, bir düğümü silmek, başka bir düğümün arkasına veya önüne bir düğüm eklemek ve bağlı listeyi baştan sona dolaşmak gibi tüm işlemleri içerir.
- Çift Bağlantılı Listede bir veri alanı ve iki bağlantı bulunur. Biri önceki düğüm için, diğeri sonraki düğüm için.
- Çift Bağlantılı Listelerin Karmaşıklığı En İyi Durum, Ortalama Durum
- Ve En Kötü Durum.