Örnek olarak, düğümü oluştururken direkt bağlantılı ve değerleri olan düğümler eklediğimi düşünelim. Bu bağlantılı liste üç düğüm içerir (node_a, node_b, node_c ). Bu listedeki her düğüm, verileri olarak bir string ifade içerir. Sıralı olarak tanımlandığında, sıra “kediler”, “köpekler” ve “kuşlar” dır.
Liste, ‘node_c’ ile son bulur çünkü bu düğüm içindeki bağlantı ‘null’ olarak ayarlamıştır. Bu listeye yeni bir baş düğüm eklemek için hangi bağlantıların kurulması gerekir? Kuyruğumuz ne olacaktır?
Bağlantılı Listelere Düğüm Ekleme ve Çıkarma
Bağlantılı listelere (linked list), düğümler yalnızca başka bir düğümden bağlandığından dolayı, birkaç değişiklik yapmadan düğümleri ekleyip kaldıramayız.
Düğüm Ekleme
Listenin başına yeni bir düğüm eklemek, yeni düğümünüzü halihazırda olan baş düğüme bağlamanızı gerektirir. Bu şekilde, listedeki düğümlerin bağlantısı sürdürülmüş olur. Aynı şekilde listenin sonuna yeni bir düğüm ekleme durumunda link olarak ‘NULL’ gösteren düğümün yeni ekleyeceğimiz düğümü göstermesini isteriz.
Bir Düğümü Kaldırma
Yanlışlıkla bir düğüme giden tek bağlantıyı kaldırırsanız, bu düğümün verileri ve yanındaki diğer düğümler uygulamanızdan kaybolabilir.
Bağlantılı bir listenin ortasında bir düğümü kaldırırken listeyi düzgün bir şekilde korumak için, önceki düğümdeki bağlantıyı bir sonraki düğümü gösterecek şekilde ayarladığınızdan emin olmanız gerekir.
Dile bağlı olarak, referans verilmeyen düğümler otomatik olarak kaldırılır. Bir düğümü kaldırmak (Removing), düğüme yapılan tüm başvuruları kaldırmaya eşdeğerdir.
Bağlantı Listelerin İncelenmesi
Bu yazıda bağlantılı listeler (linked list) ilgili ele aldıklarımızı gözden geçirelim. Bağlı listeler:
- Düğümlerden oluşur.
- Düğümler, sonraki düğüme bağlantı içerir.
- Tek yönlü veya çift yönlü olabilir.
- Temel bir veri yapısıdır ve diğer birçok veri yapısına temel oluşturur.
- Listede ilk düğüm olan bir baş (head veya root) düğüme sahiptir.
- Düğüm eklemek veya çıkarmak için bazı işlemler ele almak gerekir.
- Kullanılan yöntemler programlama dillerine bağlıdır.
Python İle Bağlı Liste Uygulaması
Öncelikle şunu hatırlayalım her bağlantılı liste (linked list) sıralı bir düğüm zinciridir. Bu yüzden bağlı listenin kendisini oluşturmaya başlamadan önce, Python’da veri konteynerleri oluşturmak için kullanabileceğimiz bir Node sınıfı oluşturmalıyız. Bir düğümün iki öğe içerdiğini hatırlayalım.
- Veri
- Sonraki düğüme bağlantı
class Node:
def __init__(self, value, next_node = None):
self.value = value
self.next_node = next_node
def get_value(self):
return self.value
def get_next_node(self):
return self.next_node
def set_next_node(self, next_node):
self.next_node = next_node
my_node = Node(44)
print(my_node.get_value)
Elimizdeki düğüm ile gerçek bağlantılı listeyi oluşturmaya başlayabiliriz. Bağlantılı listenin kullanımına göre çeşitli yöntemler tanımlanabilir.
Aşağıda belirtilenler için gerekli metotları tanımlayalım:
- Listenin baş (head veya root) düğümüne ulaşmak,
- Listenin başına yeni bir düğüm eklemek,
- Sırayla düğümlerdeki verileri yazdırmak,
- Belirli bir değere (veriye) sahip düğümü kaldırmak.
#Node (Düğüm) sınıfını tanımlayalım
class Node:
def __init__(self, value, next_node = None):
self.value = value
self.next_node = next_node
def get_value(self):
return self.value
def get_next_node(self):
return self.next_node
def set_next_node(self, next_node):
self.next_node = next_node
#Linked List (Bağlı Liste) sınıfını tanımlayalım
class LinkedList:
def __init __(self, value = None):
self.head_node = Node(value)
def get_head_node(self):
return self.head_node
Bu Kod Sayesinde Neler Yapabiliriz?
‘__init__()’ metodunu kullanarak yeni bir bağlı liste (Linked List) oluşturabiliriz. ‘get_head_node()’ metodunu kullanarak listenin baş düğümüne ulaşabiliriz. Şimdi biraz daha ayrıntıya girelim: Başa yeni bir düğüm ekleme ve bu sıralı düğümlerin tuttuğu değerleri yazdırmak gibi metotlarımızı tanıyalım bu metotların ‘LinkedList’ sınıfının içinde olması gerektiğini unutmayalım.
# Basa ekleme ve yazdırma metotlarımı tanımlayalım
def insert_begining(self, new_value):
new_node = Node(new_value)
new_node.set_next_node(self.head_node)
self.head_node = new_node
def stringify_list(self):
string_list = ""
current_node = self.get_head_node()
while current_node:
if current_node.get_value() != None:
string_list += str(current_node.get_value()) + "\n"
current_node = current_node.get_next_node()
return string_list
# Test edelim
li = LinkedList(5)
li.insert_begining(70)
li.insert_begining(1231)
li.insert_begining(87)
print(li.stringify_list())
Bir dizi yararlı linked list metodumuz oluştu. En başta bahsettiğimiz son metot ise belirli bir veriye sahip rastgele bir düğümü kaldırma yeteneği. Birkaç özel durumu göz önünde bulundurmamız gerektiği için biraz daha karmaşık gelebilir. Aşağıdaki gibi bir bağlı listemiz olduğunu düşünelim.
a -> b -> c
‘b’ düğümü listeden kaldırılırsa, yeni liste şu hale gelmelidir.
a -> c
Bağlantılı listeden kaldırılmadan önce, a düğümündeki bağlantıyı, b’nin işaret ettiği ile eşleşecek şekilde güncellememiz gerekir. Güzel olan şu ki, Python’da referans verilmeyen düğümler bizim için otomatik olarak kaldırılacaktır. Referanslara daha yakından bakacak olursak, ‘çöp toplama’ (Garbage Collection) adı verilen süreçte kaldırılmış olacaktır. Şimdi ilk düğümü kaldıran bir işlev yani metot oluşturalım.
def remove_node(self, value_to_remove):
self.value_to_remove = value_to_remove
current_node = self.get_head_node()
if current_node.get_value() == self.value_to_remove:
self.head_node = current_node.get_next_node()
else:
while current_node:
next_node = current_node.get_next_node()
if next_node.get_value() == value_to_remove:
current_node.set_next_node(next_node.get_next_node())
current_node = None
else:
current_node = next_node
Böylelikle birçok faydalı işlevi yani metodu olan bir bağlı liste (Linked List) sınıfı yazmış olduk. sonrasında düğümlerimize eleman ekleyip silme işlemlerini istediğimiz gibi yapabiliriz.
