What is a Doubly Linked List?

Bir çift yönlü bağlı liste (doubly linked list), her düğümün bir değer ve iki işaretçi taşıdığı bir düğüm dizisidir: önceki düğüme prev ve sonraki düğüme next. Listenin kendisi her iki ucu da takip eder: head (ilk düğüm) ve tail (son düğüm).

Düğüm başına iki işaretçi ve ekstra tail referansı bize çok şey kazandırır. Sona ekleme artık O(1)'dir (zinciri yürümek yerine doğrudan tail'a atlanır) ve son düğümü kaldırmak da O(1)'dir (çünkü sondan bir önceki düğüme tail.prev üzerinden ulaşabiliriz). Buradaki ödünleşim, düğüm başına daha fazla bellek kullanımı ve her ekleme ve kaldırma işleminde senkronize tutulması gereken daha fazla işaretçidir.

Çift yönlü bağlı liste üzerindeki beş ana işlem şunlardır:

1. AddFirst: Listenin başına bir değer ekler.
2. AddLast: Listenin sonuna bir değer ekler (O(1)!).
3. Get: Belirli bir indeksteki değeri döndürür.
4. RemoveLast: Son düğümü siler (O(1)!).
5. Size: Şu anda saklanan düğüm sayısını döndürür.

Önce bir Node sınıfı oluşturalım, ardından bunun üzerine DoublyLinkedList yapısını kuralım!