Implementasi Daftar Tertaut Tunggal Python

Pelajari cara mengimplementasikan daftar tertaut tunggal dengan Python. Jelajahi alokasi memori dinamis, operasi node, penyisipan, traversal, dan penghapusan.

Coba di Editor

Ikhtisar

Daftar tertaut adalah struktur data linier di mana elemen tidak disimpan di lokasi memori yang berdekatan. Sebaliknya, setiap elemen (disebut node) adalah objek terpisah yang berisi referensi ke node berikutnya dalam urutan tersebut.

Manfaat utama daftar tertaut dibandingkan array tradisional adalah ukurannya yang dinamis dan kemampuan untuk menyisipkan atau menghapus elemen dalam waktu O(1) yang konstan di awal. Namun, mengakses elemen berdasarkan indeks memerlukan traversal linier, yang memerlukan waktu O(n).

Dengan Python, kami mengimplementasikan daftar tertaut dengan mendefinisikan kelas Node untuk menyimpan data dan penunjuk referensi, dan kelas LinkedList untuk mengelola node kepala, penyisipan di kepala atau ekor, dan penghapusan.

Kode & Output Eksekusi

Implementasi daftar tertaut tunggal dengan Python, menampilkan pembuatan node, penambahan, dan traversal daftar.

linked_list.py

Coba di Editor

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()

Keluaran Terminal

Initial Linked List:
Node A -> Node B -> Node C -> None
Deleting 'Node B':
Node A -> Node C -> None

Implementasi Langkah demi Langkah

Menerapkan fungsi undo-redo di editor teks
Membangun struktur data yang kompleks seperti grafik, tumpukan, dan antrian
Mengelola daftar di mana frekuensi penyisipan dan penghapusan melebihi jumlah tindakan pencarian

Pertanyaan yang Sering Diajukan

Apa perbedaan antara Daftar Tertaut Tunggal dan Ganda?

Dalam Daftar Tertaut Tunggal, setiap node menunjuk hanya ke node berikutnya. Dalam Daftar Tertaut Ganda, setiap node berisi referensi ke node berikutnya dan sebelumnya, memungkinkan traversal dua arah dengan mengorbankan memori tambahan.

Mengapa Python tidak memiliki kelas LinkedList bawaan?

Array Python (daftar) diimplementasikan sebagai array dinamis. Karena manajemen memori Python dan optimasiCPython, daftar standar menjadi sangat cepat dan efisien untuk sebagian besar tugas, sehingga mengurangi kebutuhan praktis akan daftar tertaut bawaan.

Topik Terkait

Tutorial Struktur Data Tumpukan Python

Menerapkan tumpukan LIFO dengan Python. Jalankan contoh kode tumpukan interaktif kami untuk menguasai batas push, pop, peek, dan kapasitas.

Tutorial Struktur Data Antrian Python

Kuasai operasi antrian FIFO dengan Python. Jalankan dan jalankan contoh antrian interaktif kami yang menampilkan metode enqueue dan dequeue.