Doğrusal yapılar ve hashing · 09 / 53
Tek, çift ve dairesel bağlı listeler
Anla → iz sür → uygula → gerekçelendir
2 dk okuma · uygulama için ayrıca zaman ayırBağlı listede her düğüm değer ve bağlantı tutar. Tek yönlü listede next, çift yönlü listede prev ve next bulunur. Dairesel listede son düğüm başa bağlanır; sonlanma kontrolü None yerine tekrar başlangıca dönmektir. Sentinel düğüm sınır durumlarını azaltır ama gerçek veriyle karıştırılmamalıdır.
Bilinen bir tek yönlü düğümden sonra ekleme iki bağlantı değişimiyle yapılır: yeni.next=eski.next, eski.next=yeni. Düğümü silmek için önceki düğüme ihtiyaç vardır; yalnız silinecek düğüm referansı her durumda yeterli değildir. Çift yönlü listede komşular biliniyorsa silme O(1)'dir. Baş ve kuyruk güncellemeleri bütün işlemlerin invariant'ına dahildir.
Bellek yükü yalnız değerlerden oluşmaz: pointer alanları, allocator metadata ve parçalanma da vardır. Cache locality çoğunlukla diziden kötüdür. Floyd cycle detection iki farklı hızda işaretçiyle döngü saptar. “Listeyi ters çevir” probleminde next'i değiştirmeden önce eski next'i sakla; aksi halde zincirin devamını kaybedersin.
Adım adım iz sürme
A→B→C ters çevirilirken prev=None, cur=A, nxt=B; A.next=None yap, prev=A ve cur=B. Her tur işlenmiş prefix ters, kalan suffix sağlamdır.
Maliyet ve varsayımlar
Arama/indeks Θ(n); bilinen komşuyla bağlantı düzenleme O(1); reverse Θ(n) zaman O(1) ek alan.
Çalıştırılabilir örnek
Python 3 ile çalıştır. Assert küçük bir örneği denetler; genel doğruluk ispatı değildir. Bazı ileri örnekler özellikle küçük model veya referans oracle'dır; tam üretim uygulaması değildir.
class Node:
def __init__(self, value, next=None):
self.value, self.next = value, next
def reverse(head):
prev = None
while head is not None:
nxt = head.next
head.next = prev
prev, head = head, nxt
return prev
head = reverse(Node(1, Node(2, Node(3))))
assert (head.value, head.next.value) == (3, 2)KAVRADIĞINI KONTROL ET
Sıra sende
Dairesel listede while node is not None neden yanlış?
Çözümün mantığını göster
Bağlantılar hiçbir zaman None olmaz; döngü sonsuz sürer. Başlangıç düğümünü kimlikle kontrol et veya bilinen uzunluk kadar gez.
Bir adım ileri
- Örneği değiştirmeden önce girdi sözleşmesini ve invariantı yaz.
- Uygun olan boş, sınır, tekrar ve adversarial girdileri ekle. Basit bir oracle ile karşılaştır.
- Belirtilen modelde maliyeti çıkar; farklı girdi büyüklüklerini ölç ve farkları gerekçelendir.
Temel kaynaklar ve ders notları
Bu eğitimde özgün anlatım kullanıldı; aşağıdaki kaynaklar ispatlar ve ileri okumalar sunar. Bağlantılar daha geniş ders modülünü kapsayabilir.
Pat Morin · Open Data Structures ↗