2 dk, tahmini okuma süresi
Bağlantılı Listeler ve Kullanımları
En Son Güncelleme: 6 Ekim, 2022Bağlantılı listeler, iki ana bölümden oluşan basit veri yapılarıdır. Gerçek verileri içeren bir bölüm ve sonraki liste öğesi hakkında bilgi için başka bir bölüm. 3 ana bağlantılı liste türü vardır; tek bağlantılı listeler, çift bağlantılı listeler ve dairesel bağlantılı listeler. Genelde bağlantılı listelerin baş görevi gören bir bölümü vardır, bağlantılı listelerinizi bir kuyruk ile sonlandırmayı seçebilir veya boş olarak da kullanabilirsiniz. Tek başına bağlantılı bir liste için basit bir görsel temsil şuna benzer:
Farklı dillerde bağlantılı listeler oluşturmak için farklı yöntemler mevcut. Ben, Python'u öğrenmesi ve anlaması gerçekten kolay olduğu için python'da bağlantılı listeler oluşturacağım.
§Başlayalım
Her şeyden önce, gerçekte nasıl bağlantılı bir liste oluştururuz? Bağlantılı listenin her bir öğesine düğüm adı verilir. Her düğüm, yukarıda söylediğimiz gibi iki bölümden ikisinden oluşacaktır. Veriler için bir kısım ve bir sonraki düğümün adresi için başka bir kısım. Düğümü şu şekilde yarattım:
class Node:
def __init__(self, data):
self.data = data
self.next = None
Gerçek bağlantılı liste için başka bir python sınıfı oluşturacağız. Benim kodumda baş / kafa değerini kendimiz vermemiz gerekiyor. Siz verilen düğümlerden otomatik olarak baş (ve belki kuyruk düğümü de) alacak şekilde kodlayabilirsiniz.
§Ekleme
Zincire benzeyen herhangi bir yapıda olduğu gibi, sabit zamanda bir düğüm eklemek için bağlantıyı herhangi bir parçadan kırabilirsiniz. Bu davranışı bir dizide/listede oluşturmak, potansiyel olarak O(N) zaman alacaktır. Diyelim ki bu diziye sahipsiniz:
arr = [4, 5, 1, 6, 2]
Şimdi, python arr[1] = 3 ikinci konumuna 3 eklemek istiyoruz. Eklemenin sonunda dizimiz/listemiz şöyle görünecek:
arr = [4, 3, 5, 1, 6, 2]
Bunu başarmak için her öğeyi bir indeks sağa ittik ve 3 değeri için alan açtık. O(N) zaman karmaşıklığının nedeni bu.
Bağlantılı bir listede aynı şeyi elde etmek daha kolay olacaktır, çünkü sadece iki düğüm arasındaki bağlantıyı kesmemiz ve aralarına yeni bağlantılarla bir düğüm eklememiz gerekir. Bu işlemin zaman karmaşıklığı sabittir (O(N)). Bir görsel muhtemelen bunu daha iyi anlamamıza yardımcı olacaktır:
Silme, bağlantıları kaldırmak kadar kolay olacaktır. Kaldırmak istediğimiz düğümün bir önceki düğümünü seçiyoruz ve bu düğümü kaldırmak istediğimiz düğümden sonraki düğüme yönlendiriyoruz. Bu şekilde sadece zincirde atlıyoruz. Görsel bir temsil aşağıda bulunabilir:
§Silme
Bağlantılı bir listede silme sabit (O(1)) zaman alırken, bir liste/dizide doğrusal (O(N)) zaman alacaktır. Bir listede, öğeyi / değeri listeden kaldırmamız ve listedeki her öğeyi bir dizin sola taşımamız gerekirdi.
§Bağlantılı Liste Kodu
Bağlantılı liste veri yapısı için tam kod da şu şekilde. Bu kodu, bağlantılı listelerdeki eylemleri uygulamak için yazdım. Bağlantılı bir listede yapmak istediğiniz eylemlerin çoğunu kapsadığını görebilirsiniz:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = Node
def is_empty(self):
size = 0
temp = self.head
while temp:
size += 1
temp = temp.next
print("is it empty: ", bool(size == 0))
def front(self):
return self.head.data
def back(self):
temp = self.head
while temp.next is not None:
temp = temp.next
return temp.data
def get_size(self):
size = 0
temp = self.head
while temp:
size += 1
temp = temp.next
print("size is: ", size)
return size
# değerleri yazdırarak tek tek gidiyor
def print_list(self):
temp = self.head
while temp:
print(temp.data)
temp = temp.next
def value_at(self, index):
temp = self.head
nth = 0
while temp:
if index != nth:
nth += 1
temp = temp.next
else:
print(index, "- n. öğe değeri:", temp.data)
return
def push_front(self, value):
to_add = Node(value)
temp = self.head
self.head = to_add
to_add.next = temp
def pop_front(self):
self.head = self.head.next
def push_back(self, value):
to_add = Node(value)
temp = self.head
while temp.next:
temp = temp.next
temp.next = to_add
def pop_back(self):
temp = self.head
while temp.next.next is not None:
temp = temp.next
print("removed: ", temp.next.data)
temp.next = None
def insert(self, index, value):
to_insert = Node(value)
temp = self.head
nth = 0
while temp:
if nth == index:
old_temp_next = temp.next
to_insert.next = old_temp_next
temp.next = to_insert
temp = temp.next
nth += 1
# bu biraz daha cix
def erase(self, index):
if index < 0:
print('index negatif olamaz')
if index == 0:
self.pop_front()
nth = 1
prev = self.head
current = self.head.next
while current:
if index == nth:
prev.next = current.next
current.next = None
return
nth += 1
prev = current
current = current.next
print("out of bounds")
# value_n_from_end(n) - listenin sonundan itibaren n. konumdaki düğümün değerini verir
# İndekslemeye 0'dan başlamaya karar verdim, bu yüzden sıfırın sonuncusu
def value_n_from_end(self, index):
nth = 1
size = self.get_size()
wanted = size - index
current = self.head
if wanted == 0:
print("istenen data : ", current.data)
return current.data
while current:
if nth == wanted:
print("geri verilen: ", current.data)
return current.data
current = current.next
nth += 1
# Alan karmaşıklığı O(1) olduğundan bunu yapmanın yinelemeli yolu ile gitmek
# def reverse(self): # yinelemeli zaman O(n), yer O(1)
# prev = None
# current = self.head
# while(current):
# next = current.next
# current.next = prev
# prev = current
# current = next
# # print("current", current.data)
# self.head = prev
def reverse(self, node): # recursive time O(n), space O(n)
if node is None:
print("düğüm:", node.data)
return node
if node.next is None:
print("düğüm, sonraki yok:", node.data)
self.head = node
return node
node1 = self.reverse(node.next) # üsse ulaşana kadar tekrar tekrar arayın
node.next.next = node # kendine işaret eder
node.next = None
return node1
# remove_value(value) - bu değere sahip listedeki ilk öğeyi kaldırır
def remove_value(self, value):
current = self.head
prev = None
if self.head.data == value:
self.head = self.head.next
while current:
if current.data == value:
prev = current
current = current.next
prev.next = current
prev = current
current = current.next
if __name__ == '__main__':
# boş bir listeyle başlat
s_l_list = LinkedList()
# ilk düğüm, kafayı tanımlamalı
s_l_list.head = Node(1)
second = Node(2)
third = Node(3)
fourth = Node(4)
fifth = Node(3)
# chain' em up
s_l_list.head.next = second
second.next = third
third.next = fourth
fourth.next = fifth
# s_l_list.print_list()
# s_l_list.get_size()
# s_l_list.is_empty()
# s_l_list.value_at(0)
# s_l_list.value_at(2)
# s_l_list.push_back(5)
# s_l_list.print_list()
# s_l_list.push_back(6)
# s_l_list.print_list()
# s_l_list.pop_back()
# s_l_list.print_list()
# s_l_list.push_front(0)
# s_l_list.print_list()
# s_l_list.pop_front()
# s_l_list.print_list()
# print(s_l_list.front())
# print(s_l_list.back())
# s_l_list.print_list()
# s_l_list.insert(1, 77)
# s_l_list.print_list()
# s_l_list.erase(2)
# s_l_list.print_list()
# s_l_list.value_n_from_end(0)
# s_l_list.reverse() # yinelemeli yöntem için
# s_l_list.print_list()
# s_l_list.reverse(s_l_list.head) # geçerli kafa ile yöntemi çağırın
# s_l_list.print_list()
s_l_list.remove_value(1)
s_l_list.print_list()
Bağlantılı listede yapabileceğiniz eylemleri ve farklı bölümleri test etmek için yorum yapılan satırların yorumunu kaldırabilirsiniz. Gidin ve test edin!
§Sonuç ve Bağlantılı Listeler için Kullanımlar
Aşağıdaki durumlarda bağlantılı listeleri kullanmayı düşünebilirsiniz:
- Gerçekten büyük veri kümeleri üzerinde ekleme ve silme işlemlerinde sabit bir zamana ihtiyacınız var.
- Dizinizin/listenizin kaç tane öğe içereceğini gerçekten bilmiyorsunuz. Bir diziye yapılan her ekleme/silme işleminde diziniz bellekte yeniden oluşturulur. Dizi/listemizi oluştururken aslında bir boyut belirlememiz gerekmediğinden JavaScript ve python gibi dillerle çalışırken bu bir sorun gibi görünmeyebilir.
- Sıranın önemli olduğu veri yapıları gibi bir kuyruk oluşturmanız gerekir.
Elbette daha birçok faydası var ve daha derine inmek istiyorsanız bu makaleyi okumanızı öneririm. Okuması biraz zor ama buradaki yazımı okuduktan sonra onu da kolayca anlayabilmeniz gerektiğine inanıyorum.
Öğrenmeye devam edin!
Ilker AkbiyikBenzer Paylaşımlar
