Düğüm Sınıfı ve Liste Oluşturma
Bir Node veri sınıfı tanımlayın, düğümleri elle bağlayarak listeler oluşturun ve işaretçi değişikliklerini görselleştirmek için ekleme/silme/yazdırma yardımcılarını yazın.
Düğüm Sınıfı ve Liste Oluşturma, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 1. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Bağlantılı Liste Nedir
Bağlantılı liste, her düğümün bir değer ve sonraki düğümü gösteren bir işaretçi tuttuğu düğüm dizisidir. Dizilerin aksine düğümler belleğe dağınık şekilde yerleştirilir; dizin tabanlı O(1) erişim yoktur. Bunun karşılığında, bilinen herhangi bir konumda öğeleri kaydırmadan O(1) ekleme ve silme işlemi yapabilirsiniz.
Python'da her düğümü val ve next alanlarını tutan küçük bir sınıfla temsil ederiz. Düğümleri birbirine bağlamak listeyi oluşturur; son düğümün next değeri, listenin sonunu belirtmek için None olur.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Build: 1 -> 2 -> 3 -> None
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
# Traverse and print
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None')Dizilerden Liste Oluşturma
Mülakatlarda sık sık size bir liste verilir ve bunun bağlantılı liste karşılığını oluşturmanız ya da tersini yapmanız istenir. build ve to_list yardımcı işlevlerini ezberlemeye değer: build bir dizideki düğümleri birbirine bağlar, to_list ise değerleri kolayca doğrulamak için listede ilerleyerek toplar.
n öğeden bağlantılı liste oluşturmak O(n) zaman ve O(n) alan alır. Sahte baş düğümü kullanmak, ilk düğümün değişebileceği sınır durumlarını ele almayı kolaylaştırır.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def build(arr):
dummy = ListNode(0)
curr = dummy
for val in arr:
curr.next = ListNode(val)
curr = curr.next
return dummy.next
def to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
head = build([1, 2, 3, 4, 5])
print(to_list(head)) # [1, 2, 3, 4, 5]Başa ve Sona Ekleme
head konumuna yeni bir düğüm eklemek O(1) sürer: düğümü oluşturun, next değerini eski head'e yönlendirin ve yeni düğümü head olarak döndürün. tail konumuna eklemek ise son düğüme kadar ilerlemeyi (O(n)) ve ardından yeni düğümü bağlamayı gerektirir.
Sahte baş düğümü kullanmak, her iki ekleme için de boş listeye ilişkin özel durumu ortadan kaldırır; çünkü dummy.next her zaman gerçek head'dir.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insert_head(head, val):
return ListNode(val, head) # O(1)
def insert_tail(head, val):
new_node = ListNode(val)
if not head:
return new_node
curr = head
while curr.next:
curr = curr.next
curr.next = new_node
return head
head = None
for v in [1, 2, 3]:
head = insert_tail(head, v)
head = insert_head(head, 0)
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None') # 0 -> 1 -> 2 -> 3 -> NoneBir Düğümü Değerine Göre Silme
Belirli bir değere sahip ilk düğümü silmek için curr'ın bir adım gerisinde bulunan bir prev işaretçisi tutun. curr.val == target olduğunda, düğümü aradan çıkarmak için prev.next = curr.next atamasını yapın. Sahte baş düğümü burada özellikle yararlıdır, çünkü gerçek head düğümünü silmeye ilişkin özel durumu ortadan kaldırır; prev her zaman sahte düğümden başlayabilir.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def delete_val(head, target):
dummy = ListNode(0)
dummy.next = head
prev, curr = dummy, head
while curr:
if curr.val == target:
prev.next = curr.next
break
prev, curr = curr, curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
head = None
for v in [1, 2, 3, 2, 4]:
dummy2 = ListNode(v)
dummy2.next = head
head = dummy2 # build in reverse for speed
head = delete_val(head, 2)
print(to_list(head))İşaretçi Değişikliklerini Görselleştirme
Yaygın bir hata, işaretçileri güncellerken bir düğümün izini kaybetmektir. Üzerine yazmadan önce next'i her zaman kaydedin: saved = curr.next, ardından yeniden atama yapın. Listeyi oklarla birbirine bağlanmış kutular olarak çizin ve kodlamadan önce her işaretçi güncellemesini kâğıt üzerinde uygulayın. Bu görsel yaklaşım, mülakatlar sırasında yanlışlıkla oluşan boş işaretçi hatalarını önler.
Unutmayın: Python'da curr.next'i yeniden atamak curr'nin kendisini etkilemez; ancak kaydetmeden önce curr.next başvurusunu kaybederseniz artık ileriye doğru ilerleyemezsiniz.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Demonstrate safe pointer update
def swap_first_two(head):
if not head or not head.next:
return head
first = head
second = head.next
# Save third before losing the reference
third = second.next
# Rewire
second.next = first
first.next = third
return second
from functools import reduce
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = swap_first_two(nodes[0])
curr = head
while curr:
print(curr.val, end=' ')
curr = curr.next
# 2 1 3 4Tek Yönlü ve Çift Yönlü Bağlantılı Listeler
Tek yönlü bağlantılı liste yalnızca bir next işaretçisi tutar; gezinme tek yönlüdür. Çift yönlü bağlantılı liste hem prev hem de next işaretçilerini tutar; bu sayede geriye doğru O(1) gezinme ve doğrudan bir düğüm başvurusu verildiğinde O(1) silme mümkün olur (prev izleme döngüsüne gerek kalmaz).
Python'daki collections.deque, çift yönlü bağlantılı liste olarak uygulanmıştır; bu nedenle O(1) appendleft ve popleft işlemlerini destekler. Mülakatlarda tek yönlü bağlantılı listeleri uygulayacaksınız; çift yönlü bağlantılı listeler LRU önbellek tasarımında karşınıza çıkar.
class DLNode:
def __init__(self, val=0):
self.val = val
self.prev = None
self.next = None
# Build doubly linked: 1 <-> 2 <-> 3
a, b, c = DLNode(1), DLNode(2), DLNode(3)
a.next = b; b.prev = a
b.next = c; c.prev = b
# Traverse forward
curr = a
while curr:
print(curr.val, end=' <-> ')
curr = curr.next
print('None')
# Traverse backward from c
curr = c
while curr:
print(curr.val, end=' <-> ')
curr = curr.prev
print('None')Uzunluk, tail ve Yazdırma Yardımcıları
Her bağlantılı liste mülakatında elinizin altında bulundurmanız gereken üç yardımcı işlev vardır: length(head) O(n) zamanda düğümleri sayar, tail(head) O(n) zamanda son düğümü döndürür ve print_list(head) hata ayıklama için listeyi biçimlendirir. Bu işlevleri hazır bulundurmak, yardımcı mantığı yeniden uygulamak yerine temel algoritmaya odaklanmanızı sağlar.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def length(head):
count = 0
while head:
count += 1
head = head.next
return count
def tail(head):
while head and head.next:
head = head.next
return head
def print_list(head):
parts = []
while head:
parts.append(str(head.val))
head = head.next
print(' -> '.join(parts) + ' -> None')
# Build and test
nodes = [ListNode(i) for i in [10, 20, 30, 40]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = nodes[0]
print('Length:', length(head))
print('Tail:', tail(head).val)
print_list(head)Bağlantılı Listelerde İki İşaretçi Kurulumu
İki işaretçi tekniği, bağlantılı listeler için dizilerdeki kadar önemlidir; ancak işaretçiler dizinler yerine bağlantılı liste düğümleridir. Yaygın kurulumlar arasında orta noktaları bulmak ve döngüleri tespit etmek için kullanılan yavaş ve hızlı işaretçi (hızlı işaretçi 2 kat daha hızlı hareket eder) ile silme ve ters çevirme için kullanılan öncül ve mevcut işaretçi çifti bulunur.
Her iki işaretçiyi de her zaman açıkça başlatın ve boş sonlandırma kontrolünü dikkatle yapın — fast and fast.next, fast sona yaklaştığında boş işaretçi hatalarını önler.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Find middle node using slow-fast pointers
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # for even length, returns second of two middle nodes
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
print(find_middle(nodes[0]).val) # 3 (middle of 1->2->3->4->5)Sahte Baş Düğüm Kalıbı
Sahte baş düğüm (nöbetçi düğüm) kalıbı, bağlantılı liste problemlerindeki en yararlı yöntemlerden biridir. Değeri 0 olan bir sahte düğümü listenin başına ekleyerek boş liste veya gerçek head'de değişiklik olması durumlarına özel işlem yapmanız gerekmez. Sonucunuz her zaman dummy.next olur. Bu kalıp sıralı listeleri birleştirme, sondan n'inci öğeyi kaldırma, listeyi bölümlere ayırma ve daha birçok işlemde karşınıza çıkar.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Remove all nodes with val == target (may include head)
def remove_all(head, target):
dummy = ListNode(0)
dummy.next = head
curr = dummy
while curr.next:
if curr.next.val == target:
curr.next = curr.next.next # skip the node
else:
curr = curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
nodes = [ListNode(v) for v in [1, 2, 6, 3, 4, 5, 6]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = remove_all(nodes[0], 6)
print(to_list(head)) # [1, 2, 3, 4, 5]Zaman ve Alan Karmaşıklığı
Çoğu bağlantılı liste işlemi şu karmaşıklıklara sahiptir. Dizine göre erişim: O(n) — head'den başlayarak ilerlemek gerekir. Bilinen düğümde ekleme/silme: O(1) — yalnızca işaretçileri yeniden bağlamak yeterlidir. k konumunda ekleme/silme: O(k) — önce ilerlemek gerekir. Arama: O(n) — en kötü durumda listenin tamamı taranır. Ek veri yapıları hariç, yerinde yapılan tüm işlemlerde alan O(1)'dir.
Bunu dizilerle karşılaştırın: diziler O(1) erişim sunar, ancak öğeleri kaydırmak gerektiği için ekleme/silme O(n) sürer. Bağlantılı listeler, rastgele konumlarda ekleme ve silme işlemlerinin sık yapıldığı durumlarda daha iyidir.
Mülakatlarda Bağlantılı Listeler İçin İpuçları
Bağlantılı liste kodu yazmadan önce listeyi kutular ve oklarla görsel olarak çizin. Sınır durumlarını sesli olarak doğrulayın: boş liste, tek düğüm, çift ve tek uzunluk. Sınır koşullarını basitleştirmek için sahte baş düğümü kullanın. if not head kontrolünü her zaman erkenden yapın. Kodlamadan sonra, mülakatçı fark etmeden önce işaretçi hatalarını yakalamak için çözümünüzü üç düğümlü bir listede adım adım izleyin.
Bağlantılı liste hatalarının çoğu üç kaynaktan gelir: üzerine yazmadan önce next'i kaydetmeyi unutmak, sonlandırma koşulunda bir eksik veya fazla adım yapmak ya da head değişikliği sınır durumunu ele almamak — sahte düğüm üçüncü durumu tamamen ortadan kaldırır.
Hızlı Kontrol
Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını anlayıp anlamadığınızı test edin.
Ders Özeti
Bu derste şunları öğrendiniz: bağlantılı liste, val ve next alanlarına sahip Node nesnelerinden oluşturulur, sahte baş düğüm kalıbı, head değişikliği sınır durumlarını ortadan kaldırır ve yavaş-hızlı iki işaretçi kurulumu, orta nokta bulma ve döngü tespitinin temelidir. Sıradaki konuda bağlantılı listeyi ters çevirmeyi ele alacağız; bu, en sık sorulan işaretçi problemlerinden biridir.
Sıkça Sorulan Sorular
“Düğüm Sınıfı ve Liste Oluşturma” dersi ücretsiz mi?
Evet — “Düğüm Sınıfı ve Liste Oluşturma” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Düğüm Sınıfı ve Liste Oluşturma” dersinde ne öğreneceğim?
Bir Node veri sınıfı tanımlayın, düğümleri elle bağlayarak listeler oluşturun ve işaretçi değişikliklerini görselleştirmek için ekleme/silme/yazdırma yardımcılarını yazın. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 1. dersidir.
“Düğüm Sınıfı ve Liste Oluşturma” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Düğüm Sınıfı ve Liste Oluşturma
- Bağlı Listeyi Ters Çevirme
- Floyd Algoritmasıyla Döngü Algılama
- Birleştirme, Bölme ve Sondan N’inciyi Bulma