Python Tek Bağlantılı Liste Uygulaması

Python'da tek bağlantılı listenin nasıl uygulanacağını öğrenin. Dinamik bellek ayırmayı, düğüm işlemlerini, eklemeyi, geçişi ve silmeyi keşfedin.

Editör'de deneyin

Genel Bakış

Bağlantılı liste, öğelerin bitişik bellek konumlarında saklanmadığı doğrusal bir veri yapısıdır. Bunun yerine, her öğe (düğüm olarak adlandırılır), dizideki bir sonraki düğüme referans içeren ayrı bir nesnedir.

Bağlantılı listenin geleneksel diziye göre birincil avantajı, dinamik boyutlandırması ve öğeleri başlangıçta sabit O(1) sürede ekleme veya silme yeteneğidir. Ancak öğelere dizine göre erişim, O(n) zaman alan doğrusal geçiş gerektirir.

Python'da, verileri ve referans işaretçisini depolamak için bir Node sınıfı ve baş düğümü, baş veya kuyruktaki eklemeleri ve silmeleri yönetmek için bir LinkedList sınıfı tanımlayarak bağlantılı bir liste uygularız.

Kod ve Yürütme Çıkışı

Python'da düğüm oluşturma, ekleme ve liste geçişini gösteren tek bağlantılı liste uygulaması.

linked_list.py
Editör'de deneyin
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
        
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        
    def delete(self, key):
        curr = self.head
        if curr and curr.data == key:
            self.head = curr.next
            curr = None
            return
        prev = None
        while curr and curr.data != key:
            prev = curr
            curr = curr.next
        if not curr:
            return
        prev.next = curr.next
        curr = None
        
    def display(self):
        elements = []
        curr = self.head
        while curr:
            elements.append(str(curr.data))
            curr = curr.next
        print(" -> ".join(elements) + " -> None")

# Instantiate and build the linked list
llist = LinkedList()
llist.append("Node A")
llist.append("Node B")
llist.append("Node C")
print("Initial Linked List:")
llist.display()

print("Deleting 'Node B':")
llist.delete("Node B")
llist.display()
Terminal Çıkışı
Initial Linked List:
Node A -> Node B -> Node C -> None
Deleting 'Node B':
Node A -> Node C -> None

Adım Adım Uygulama

  • Metin editörlerinde geri alma-yeniden yapma işlevini uygulama
  • Grafikler, yığınlar ve kuyruklar gibi karmaşık veri yapıları oluşturma
  • Ekleme ve silme sıklıklarının arama eylemlerinden daha fazla olduğu listeleri yönetme

Sıkça Sorulan Sorular

Tekli ve Çift Bağlantılı Listeler arasındaki fark nedir?

Tek Bağlantılı Listede her düğüm yalnızca bir sonraki düğüme işaret eder. Çift Bağlantılı Listede, her düğüm hem sonraki hem de önceki düğüme referanslar içerir ve ekstra bellek pahasına çift yönlü geçişe izin verir.

Python'un neden yerleşik bir LinkedList sınıfı yok?

Python dizileri (listeleri) dinamik diziler olarak uygulanır. Python'un bellek yönetimi veCPythonoptimizasyonları nedeniyle, standart listeler çoğu görev için son derece hızlı ve etkilidir ve yerleşik bağlantılı listeye olan pratik ihtiyacı azaltır.

İlgili Konular