CP #29: Linked List Problemleri
Array gibi, elemanlari devamli bir sekilde (continous) hafizada tutulmayan, elemanlarin birbirine pointerlar ile baglandigi bir veri saklama yapisidir.
- Arary sabit olup eleman sayisi bir kere tanimlandiktan sonra artirilama/azaltilamaz. Bu anlamda LL daha esnektir. Gercekten kullanilan eleman sayisi mertebesinde hafiza kullanir.
- Array'a bir eleman eklemen maliyetli bir islemdir. Ornegin ortaya ekelenecekse eleman, oncelikle sag tarafta kalan tum elemanlar saga kaydirilmalidir. Bu O(n) bir islem olamktadir. LL'te ise O(1) seklinde istenilen noktaya eleman eklenebilir. Eleman silme icin de bu durum gecerlidir.
- Array'a bir eleman eklemen maliyetli bir islemdir. Ornegin ortaya ekelenecekse eleman, oncelikle sag tarafta kalan tum elemanlar saga kaydirilmalidir. Bu O(n) bir islem olamktadir. LL'te ise O(1) seklinde istenilen noktaya eleman eklenebilir. Eleman silme icin de bu durum gecerlidir.
Dezavantajlari:
- Random access mumkun degildir. Yani direk ben 12. elemana ulasayim diyemiyoruz. O elemana kadar LL uzerinde traverse etmemiz gerekiyor.
- Random access mumkun degildir. Yani direk ben 12. elemana ulasayim diyemiyoruz. O elemana kadar LL uzerinde traverse etmemiz gerekiyor.
Cok basit bir implementasyon:
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
class LinkedList:
def __init__(self):
self.head = None
Insertion
Uc farkli nokta icin insertion'a gozatalim. En basa, en sona ve verilen bir node'dan sonrasina.
def push(self, data):
# en basa verilen datayi insert ediyoruz
# en basa verilen datayi insert ediyoruz
new_node = Node(data, next = self.head)
self.head = new_node
def insert_after(self, node, data):
# verilen bir node'un sonrasina ekleme
tmp_next = node.next
new_node = Node(data)
node.next = new_node
new_node.next = tmp_next
Bu iki islem de O(1) zaman almaktadir. Ne de olsa hicbir iterasyon yapmaya gerek kalmiyor. Son olarak ise LL'in en sonune eleman eklemeye bakalim:
def append(self, data):
new_node = Node(data)
# eger LL bos ise, head olarak ata
if not self.head:
self.head = new_node
# en sondaki elemani bulalim
cur = self.head
while cur.next:
cur = cur.next
# bu noktada cur, en sondaki eleman oluyor
cur.next = new_node
Bu islem ise O(n) zaman almaktadir. LL'de tail icin (en sondaki eleman) ekstra bir pointer tutularak, O(1)'e indirgenebilir.
Deletion
Birkac kucuk noktaya dikkat edersek bu da cok straightforward bir islem:
Birkac kucuk noktaya dikkat edersek bu da cok straightforward bir islem:
def delete(self, key):
# eger hic eleman yoksa direk silemedik mesaji dondur
if not self.head:
return False
# verilen key head'e ait olabilir
if self.head.data == key:
self.head = self.head.next
# basarili bir sekilde silince True dondurelim
return True
# silme islemi icin mevcut Node'u ve de bir onceki nodu tutmak gerekir
cur = self.head.next
prev = self.head
while cur:
if cur.data == key:
# burada cur node'u, "unlik" ediyoruz
prev.next = cur.next
return True
cur = cur.next
prev = cur
# buraya kadar gelebilydisek, LL icerisinde bu key
# yok demektir.
return False
Gordulecegi gibi silme islemi lineer bir arama gerektirdigi icin O(n) zaman gereksinimine sahiptir. Simdi bazi klasik LL problemlerine gozatalim.
1. Nth node from the end of a Linked List
Sondan n.ci elemani bulmamiz isteniyor. Ilk akla gelen yontem, sona kadar gidip (O(n)), n adim geriye dogru gelmek olabilir. Toplamda O(n) bir cozum ede ederiz. Ancak eldeki LL, sadece ileriye dogru referans barindiriyorsa (singly linked list), geriye gelebilmek icin ekstra bir hafiza harcamamiz gerekir. Bu durumda ilk once LL'nin uzunlugunu bulup daha sonra en bastan len - n adim ileriye gitmek de O(n) cozum olacaktir.
Sondan n.ci elemani bulmamiz isteniyor. Ilk akla gelen yontem, sona kadar gidip (O(n)), n adim geriye dogru gelmek olabilir. Toplamda O(n) bir cozum ede ederiz. Ancak eldeki LL, sadece ileriye dogru referans barindiriyorsa (singly linked list), geriye gelebilmek icin ekstra bir hafiza harcamamiz gerekir. Bu durumda ilk once LL'nin uzunlugunu bulup daha sonra en bastan len - n adim ileriye gitmek de O(n) cozum olacaktir.
def nth_elm_from_end(self, n):
# uzunlugu bulalim
len_ll = 0
cur = self.head
while cur:
len_ll += 1
cur = cur.next
# en bastan len_ll - n adim gidelim
cur = self.head
for _ in range(len_ll - n):
cur = cur.next
return cur
2. Remove Nth Node from End of List
Problem surada.
Problem surada.
Ilk akla gelen naive yontem yine yukaridakine benzer olarak, once linked list uzunlugunu bulup sonra da head'den len_ll - n adim ilerleyerek silme islemini yapmak. Burada silinecek node'un linked list icerisindeki konumuna gore 2 farkli durum ortaya cikiyor: en bastan silme (head) ve baska herhangi bir yerden silme.
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
# bizi bu sekilde tirt inputlar ile ugrastirma
if not head:
return None
# liste uzunlugu
len_ll = 0
cur = head
while cur:
len_ll += 1
cur = cur.next
# uc duruma bakalim
# 1. head silme
if n = len_ll:
return head.next
# 2. diger
else:
# burada silinecek node'a giderken
# bir onceki node'un da referansini tutmak gerekiyor
# ki, node'u "unlink" edebilelim
prev = head
cur = head.next
# head.next'ten basladigimiz icin, len_ll-n-1 adim gitmek gerekiyor
for _ in range(len_ll - n - 1):
prev = cur
cur = cur.next
# silecegimiz node'a vardik
prev.next = cur.next
return head
Analiz
En kotu ihtimalle verilen linked listi 2 kere traverse ediyoruz. Sonucta lineer, O(n) bir cozum.
Follow-up: Bunu one-pass ile yapip yapamayacagimiz soruluyor. Tabi yapariz, ama bu sefer list uzunlugunu bulurken node referanslarini da tutmamiz gerekecek. Bastan oynatalim Ugurcum:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
if not head:
return None
# hem say, hem de ref'e kaydet ki ileride
# random access yapabilelim yigenim
refs = []
cur = head
while cur:
refs.append(cur)
cur = cur.next
# sadece head konusunda bir kontrol
if n == len(refs):
return head.next
else:
# silinecek node, sondan n.inci eleman
del_node = refs[-n]
# silinecek elemandan bir onceki eleman
prev = del_node[-n-1]
prev.next = del_node.next
return head
Iste bu kadar. Python gonderilerinin arasinda %93'unden daha hizli sonuc veriyor. Time comp. yine O(n) ama bu sefer space compl. de O(n) oldu cunku herbir linked list node'une referans tutar olduk.
3. Linked List Cycle II Problemi
Problem surada. Linked list'i bastan basa traverse ettigimizi dusunelim. Cycle olmasi icin, bir node'un daha onceden ziyaret edilmis olmasi gerekiyor. Oyleyse plan basit, LLi traverse ederken ayni zamanda ziyaret edilen node'lari sorgulamak icin tutacagiz. Her bir node daha onceden ziyaret edilmis mi diye kontrol edilecek. Soruda, cycle'in basladigi node'u geri dondurmemiz istendigi icin, eger daha once gorulmus bir node var ise direk onu dondurebiliriz.
def detectCycle(self, head: ListNode) -> ListNode:
if not head:
return None
# ziyaret edilenleri set icerisinde tutalim ki
# sorgulamasi ucuz olsun
visited = set()
cur = head
while cur:
# daha once ziyaret ettik mi? O(1)
if cur in visited:
return cur
visited.add(cur)
cur = cur.next
Analiz
Ben ilk basta soruda, cycle'in basladigi indexi dondurmek gerektigini sanip, visited icin set yerine array kullandim. Leet'te gecti gecmesine ama %5 bir performans gosterdi. Daha sonra set de kullanilabilecegini farkettim ve set ile %82'ye cikmis oldu. Demem o ki, cok farkettiriyor gercekten. Burada sadece LLi traverse ediyoruz, O(n) bir cozum var. Ama space olarak da O(n) cunku visited seti var.
Follow-up: O(1) memory ile cozebilir misiniz? Memory kullanimi azalacaksa eger, time compl. artacaktir seklinde bir suphe duyabiliriz. Cunku bu bir trade-off. O zaman biz de ziyaret edilen node'lari visited setinde tutmayiz da, her bir node traversinde tekrar en bastan traverse edip bakariz, daha once bununla karsilasmis miyiz diye? Bence olur.
def detectCycle(self, head: ListNode) -> ListNode:
if not head:
return None
ind = 0
cur = head
while cur:
# bu cur'u daha once gorduk mu?
# tekrar en bastan, ind adim kadarlik kismi tariyoruz
cur2 = head
while cur2:
# eger cur'e esit ise demek ki cycle var
if cur2 == cur:
return cur2
cur = cur.next
ind += 1
Bekledigimiz gibi runtime performansi kotu, %5. Ama memory analizi yapacak olursak, hic ekstra memory kullanmadigimizi goruyoruz. (Bu ifade yanlis, ekstra memory var ama sabit). Sonuc olarak O(1) space compl. sahip bir cozum.
4. Flatten a Multi Level Doubly Linked List
Problem surada. Problemi ilk okudugumda, sirasiyla value'lari array olarak dondurecegiz diye dusundum. Iste biz biz olalim soruyu tam anlamadan cozmeye baslamayalim. Neyse, hal boyle olunce, recusive olarak biz linked liste'yi doneriz, value'lari toplayarak gideriz diye dusundum. Yani verilen bir linked list head node'u icin, listeyi traverse edip her bir node'un value'sunu bir array'de biriktirecegiz. Eger bir node'un child linked listi varsa, recursive olarak yine ayni fonksoyonu cagirip oradaki listeyi collect edip, mevcut liste ile birlestirip yolumuza devam edecegiz. Bu sayede tum value'lari toplayabiliriz. Ancak soruda, value'lari degil de listenin kendisini istiyor, geri donus olarak. Bu durumda biz de value'lari topladiktan sonra, bunlardan yeni bir flat linked list olusturup geri dondurebiliriz.
def flatten(self, head: 'Node') -> 'Node':
if not head:
return None
# verilen head node'dan ilerleyerek
# bir linked listin elemanlarinin value'larini
# toplayan recursive fonksiyonumuz
def collect_list(node):
ret = []
cur = node
while cur:
ret.append(cur.val)
# eger child varsa
# burada mevcut listeyi traverse etmeyi pause edip
# child'a geciyoruz
if cur.child:
ret += collect_list(cur.child)
return ret
# simdi elimizde flat bir value listesi var
# bundan bir linked list olusturacagiz
def vals_to_list(vals):
head = None
cur = None
# her bir val degeri icin yeni bir Node olusturup
# uc uca eklememiz gerek
for v in vals:
# listenin en basindayiz:
if head is None:
head = Node(val=v, prev=None, next=None, child=None)
cur = head
else:
cur.next = Node(val=v, prev=cur, next=None, child=None)
cur = cur.next
return head
# verilen node'dan flatten vals arrayi olusturalim
flat_vals = collect_list(head)
flat_list = vals_to_list(flat_vals)
return flat_list
Analiz
Performans olarak gayet basarili, python gonerileri arasinda %96'sindan daha iyi. Once tum linked list elemanlarini gezdik, O(n). Daha sonra toparladigimiz value'lardan bir linked list olusturduk ki bu da O(n). Sonucta toplamda lineer bir cozum elde etmis olduk. Ilk vals arrayini olustururken yine lineer bir hafiza kullanimi var. Linked list olustururken de yine her bir value icin yeni Node olusturdugumuz icin O(n) bir space compl. elde etmis oluyoruz ki toplamda space compl. de lineerdir diyebiliriz.
Performans olarak gayet basarili, python gonerileri arasinda %96'sindan daha iyi. Once tum linked list elemanlarini gezdik, O(n). Daha sonra toparladigimiz value'lardan bir linked list olusturduk ki bu da O(n). Sonucta toplamda lineer bir cozum elde etmis olduk. Ilk vals arrayini olustururken yine lineer bir hafiza kullanimi var. Linked list olustururken de yine her bir value icin yeni Node olusturdugumuz icin O(n) bir space compl. elde etmis oluyoruz ki toplamda space compl. de lineerdir diyebiliriz.
Follow-up: Aslinda soruda sormamis ama benim aklima gelen su ki, ekstra memory kullanmadan, O(1) space compl. ile yapabilir miyiz? Bu durumda vals arrayi olusturmak yok, sadece mevcut linked listin elemanlarinin prev ve next'leri ile oynayarak flat bir hale getirmemiz gerekiyor.
Linked listle alakali sorular burada bitmiyor elbette. Ikinci bir soru setinde gorusmek uzere.
Stay hungry :)
Yorumlar
Yorum Gönder