Daftar Tertaut dengan Python

Pengantar

Daftar Tertaut adalah struktur data yang terdiri dari rangkaian node, masing-masing berisi nilai dan referensi ke node berikutnya dalam urutan tersebut. Berbeda dengan array, Daftar Tertaut tidak memerlukan alokasi memori yang berdekatan, menjadikannya lebih fleksibel dan efisien untuk operasi tertentu. Pada artikel ini, kita akan membahas kelebihan dan kekurangan Daftar Tertaut dan cara mengimplementasikannya dengan Python.

Keuntungan dan Kerugian Daftar Tertaut

Daftar Tertaut menawarkan beberapa keunggulan dibandingkan struktur data lainnya. Pertama, mereka memungkinkan penyisipan dan penghapusan elemen secara efisien, karena mereka hanya memerlukan pembaruan referensi dari node tetangga. Hal ini menjadikan LinkedLists ideal untuk skenario yang memerlukan seringnya modifikasi. Selain itu, LinkedLists dapat bertambah atau menyusut ukurannya secara dinamis, tidak seperti array, yang memiliki ukuran tetap.

Namun, Linked List juga memiliki beberapa kelemahan. Tidak seperti array, Daftar Tertaut tidak mendukung akses acak ke elemen, yang berarti bahwa mengakses elemen pada indeks tertentu memerlukan penelusuran daftar dari awal. Hal ini dapat mengakibatkan kinerja lebih lambat untuk operasi tertentu. Selain itu, Daftar Tertaut memerlukan memori ekstra untuk menyimpan referensi ke node berikutnya, yang mungkin tidak efisien untuk kumpulan data kecil.

Menerapkan Daftar Tertaut dengan Python

Python menyediakan cara yang fleksibel dan intuitif untuk mengimplementasikan Daftar Tertaut. Ada tiga jenis utama Daftar Tertaut: Daftar Tertaut Tunggal, Daftar Tertaut Ganda, dan Daftar Tertaut Melingkar. Mari kita jelajahi masing-masing secara mendetail.

Daftar Tertaut Tunggal

Daftar Tertaut Tunggal terdiri dari simpul-simpul yang setiap simpulnya berisi nilai dan referensi ke simpul berikutnya dalam urutan. Inilah cara Anda membuat Daftar Tertaut Tunggal dengan Python:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class Linked List:
    def __init__(self):
        self.head = None

Membuat Daftar Tertaut Tunggal

Untuk membuat Daftar Tertaut Tunggal, kita perlu mendefinisikan kelas Node yang mewakili setiap node dalam daftar. Setiap node berisi nilai dan referensi ke node berikutnya. Kelas Daftar Tertaut berfungsi sebagai wadah untuk node, dengan atribut head menunjuk ke node pertama dalam daftar.

Memasukkan Node dalam Daftar Tertaut Tunggal

Memasukkan node ke dalam Daftar Tertaut Tunggal melibatkan pembaruan referensi dari node tetangga. Berikut ini contoh menyisipkan node di awal daftar:

def insert_at_beginning(self, value):
    new_node = Node(value)
    new_node.next = self.head
    self.head = new_node

Menghapus Node dari Daftar Tertaut Tunggal

Menghapus node dari Daftar Tertaut Tunggal memerlukan pembaruan referensi dari node tetangga. Berikut contoh penghapusan node dengan nilai tertentu:

def delete_node(self, value):
    current = self.head
    if current.value == value:
        self.head = current.next
    else:
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                break
            current = current.next

Mencari dalam Daftar Tertaut Tunggal

Pencarian nilai tertentu dalam Daftar Tertaut Tunggal melibatkan penelusuran daftar hingga nilai ditemukan atau akhir daftar tercapai. Berikut ini contoh pencarian nilai:

def search(self, value):
    current = self.head
    while current:
        if current.value == value:
            return True
        current = current.next
    return False

Membalikkan Daftar Tertaut Tunggal

Membalikkan Daftar Tertaut Tunggal memerlukan pembaruan referensi setiap node agar menunjuk ke node sebelumnya. Berikut ini contoh membalikkan Daftar Tertaut Tunggal:

def reverse(self):
    previous = None
    current = self.head
    while current:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node
    self.head = previous

Daftar Tertaut Ganda

Daftar Tertaut Ganda mirip dengan Daftar Tertaut Tunggal, tetapi setiap simpul berisi referensi ke simpul berikutnya dan simpul sebelumnya dalam urutan tersebut. Hal ini memungkinkan traversal yang efisien di kedua arah. Inilah cara Anda membuat Daftar Tertaut Ganda dengan Python:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.previous = None

class DoublyLinked List:
    def __init__(self):
        self.head = None

Membuat Daftar Tertaut Ganda

Untuk membuat Daftar Tertaut Ganda, kita mendefinisikan kelas Node yang berisi nilai, referensi ke node berikutnya, dan referensi ke node sebelumnya. Kelas DoublyLinked List berfungsi sebagai wadah untuk node, dengan atribut head menunjuk ke node pertama dalam daftar.

Memasukkan Node dalam Daftar Tertaut Ganda

Memasukkan node ke dalam Daftar Tertaut Ganda melibatkan pembaruan referensi dari node tetangga. Berikut ini contoh menyisipkan node di awal daftar:

def insert_at_beginning(self, value):
    new_node = Node(value)
    if self.head:
        self.head.previous = new_node
    new_node.next = self.head
    self.head = new_node

Menghapus Node dari Daftar Tertaut Ganda

Menghapus node dari Daftar Tertaut Ganda memerlukan pembaruan referensi dari node tetangga. Berikut contoh penghapusan node dengan nilai tertentu:

def delete_node(self, value):
    current = self.head
    if current.value == value:
        self.head = current.next
        if self.head:
            self.head.previous = None
    else:
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                if current.next:
                    current.next.previous = current
                break
            current = current.next

Mencari dalam Daftar Tertaut Ganda

Pencarian nilai tertentu dalam Daftar Tertaut Ganda melibatkan penelusuran daftar ke salah satu arah hingga nilai ditemukan atau akhir daftar tercapai. Berikut ini contoh pencarian nilai:

def search(self, value):
    current = self.head
    while current:
        if current.value == value:
            return True
        current = current.next
    return False

Membalikkan Daftar Tertaut Ganda

Membalikkan Daftar Tertaut Ganda memerlukan pembaruan referensi setiap node untuk menukar pointer berikutnya dan sebelumnya. Berikut ini contoh membalikkan Daftar Tertaut Ganda:

def reverse(self):
    current = self.head
    while current:
        next_node = current.next
        current.next = current.previous
        current.previous = next_node
        if not next_node:
            self.head = current
        current = next_node

Daftar Tautan Edaran

Daftar Tertaut Melingkar adalah variasi dari Daftar Tertaut Tunggal di mana simpul terakhir menunjuk kembali ke simpul pertama, sehingga menciptakan struktur melingkar. Hal ini memungkinkan traversal yang efisien dari node mana pun dalam daftar. Inilah cara Anda membuat Daftar Tertaut Melingkar dengan Python:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class CircularLinked List:
    def __init__(self):
        self.head = None

Membuat Daftar Tertaut Melingkar

Untuk membuat Circular Linked List, kita mendefinisikan kelas Node yang berisi nilai dan referensi ke node berikutnya. Kelas CircularLinked List berfungsi sebagai wadah untuk node, dengan atribut head menunjuk ke node pertama dalam daftar. Selain itu, referensi berikutnya dari simpul terakhir diatur ke kepala, sehingga menciptakan struktur melingkar.

Memasukkan Node dalam Daftar Tertaut Melingkar

Memasukkan node ke dalam Daftar Tertaut Melingkar melibatkan pembaruan referensi dari node tetangga. Berikut ini contoh menyisipkan node di awal daftar:

def insert_at_beginning(self, value):
    new_node = Node(value)
    if not self.head:
        self.head = new_node
        new_node.next = self.head
    else:
        current = self.head
        while current.next != self.head:
            current = current.next
        current.next = new_node
        new_node.next = self.head
        self.head = new_node

Menghapus Node dari Daftar Tertaut Melingkar

Menghapus node dari Circular Linked List memerlukan pembaruan referensi dari node tetangga. Berikut contoh penghapusan node dengan nilai tertentu:

def delete_node(self, value):
    if not self.head:
        return
    current = self.head
    if current.value == value:
        while current.next != self.head:
            current = current.next
        if current == self.head:
            self.head = None
        else:
            current.next = self.head.next
            self.head = self.head.next
    else:
        previous = None
        while current.next != self.head:
            previous = current
            current = current.next
            if current.value == value:
                previous.next = current.next
                break

Mencari dalam Daftar Tertaut Melingkar

Pencarian nilai tertentu dalam Daftar Tertaut Melingkar melibatkan penelusuran daftar hingga nilai ditemukan atau seluruh daftar dilintasi. Berikut ini contoh pencarian nilai:

def search(self, value):
    if not self.head:
        return False
    current = self.head
    while True:
        if current.value == value:
            return True
        current = current.next
        if current == self.head:
            break
    return False

Membalikkan Daftar Tertaut Melingkar

Membalikkan Daftar Tertaut Melingkar memerlukan pembaruan referensi setiap node untuk membalikkan struktur melingkar. Berikut ini contoh membalikkan Circular Linked List:

def reverse(self):
    if not self.head:
        return
    previous = None
    current = self.head
    next_node = current.next
    while True:
        current.next = previous
        previous = current
        current = next_node
        next_node = next_node.next
        if current == self.head:
            break
    self.head = previous

Operasi Umum pada Daftar Tertaut

Daftar Tertaut mendukung berbagai operasi umum yang dapat dilakukan pada elemen. Mari kita jelajahi beberapa operasi berikut:

Mengakses Elemen dalam Daftar Tertaut

Untuk mengakses elemen dalam Linked List, kita dapat melintasi list mulai dari node kepala dan berpindah ke node berikutnya hingga mencapai posisi yang diinginkan. Berikut ini contoh mengakses elemen pada indeks tertentu:

def get_element(self, index):
    current = self.head
    count = 0
    while current:
        if count == index:
            return current.value
        count += 1
        current = current.next
    raise IndexError("Index out of range")

Memodifikasi Elemen dalam Daftar Tertaut

Memodifikasi elemen dalam Daftar Tertaut melibatkan penelusuran daftar untuk menemukan elemen yang diinginkan dan memperbarui nilainya. Berikut ini contoh memodifikasi elemen pada indeks tertentu:

def modify_element(self, index, new_value):
    current = self.head
    count = 0
    while current:
        if count == index:
            current.value = new_value
            return
        count += 1
        current = current.next
    raise IndexError("Index out of range")

Menemukan Panjang Daftar Tertaut

Untuk mengetahui panjang Linked List, kita dapat menelusuri daftar tersebut dan menghitung jumlah node. Berikut ini contoh mencari panjang Linked List:

def get_length(self):
    current = self.head
    count = 0
    while current:
        count += 1
        current = current.next
    return count

Memeriksa apakah Daftar Tertaut Kosong

Untuk memeriksa apakah Daftar Tertaut kosong, kita cukup memeriksa apakah simpul kepala adalah Tidak Ada. Berikut ini contoh pengecekan apakah Daftar Tertaut kosong:

def is_empty(self):
    return self.head is None

Menggabungkan Daftar Tertaut

Untuk menggabungkan dua Daftar Tertaut, kita dapat melintasi daftar pertama untuk menemukan simpul terakhir dan memperbarui referensi berikutnya ke kepala daftar kedua. Berikut ini contoh penggabungan dua Daftar Tertaut:

def concatenate(self, other_list):
    if not self.head:
        self.head = other_list.head
    else:
        current = self.head
        while current.next:
            current = current.next
        current.next = other_list.head

Daftar Tertaut vs. Array

Daftar Tertaut dan array keduanya merupakan struktur data yang umum digunakan, namun keduanya memiliki karakteristik berbeda sehingga cocok untuk skenario berbeda. Mari kita bandingkan Daftar Tertaut dan array dalam hal efisiensi memori, efisiensi penyisipan dan penghapusan, dan efisiensi akses acak.

Efisiensi Memori

Daftar Tertaut lebih hemat memori dibandingkan array karena tidak memerlukan alokasi memori yang berdekatan. Setiap node dalam Daftar Tertaut hanya perlu menyimpan nilai dan referensi ke node berikutnya, sedangkan array perlu mengalokasikan memori untuk semua elemen, meskipun elemen tersebut tidak digunakan.

Efisiensi Penyisipan dan Penghapusan

Daftar Tertaut unggul dalam operasi penyisipan dan penghapusan, terutama ketika elemen sering ditambahkan atau dihapus dari tengah daftar. Memasukkan atau menghapus elemen dalam Daftar Tertaut hanya memerlukan pembaruan referensi dari node tetangga, sedangkan array mungkin memerlukan perpindahan elemen untuk mengakomodasi perubahan tersebut.

Efisiensi Akses Acak

Array menyediakan akses acak yang efisien ke elemen berdasarkan indeksnya, karena memungkinkan pengalamatan memori langsung. Sebaliknya, Daftar Tertaut memerlukan penelusuran daftar dari awal untuk mengakses elemen pada indeks tertentu, sehingga mengakibatkan kinerja lebih lambat untuk operasi akses acak.

Memilih Struktur Data yang Tepat

Pilihan antara Daftar Tertaut dan array bergantung pada kebutuhan spesifik aplikasi. Jika diharapkan sering terjadi modifikasi dan perubahan ukuran dinamis, Daftar Tertaut adalah pilihan yang lebih baik. Di sisi lain, jika akses acak dan efisiensi memori sangat penting, array lebih cocok.

Aplikasi Daftar Tertaut

Sekarang setelah kita memiliki pemahaman yang baik tentang daftar tertaut dan cara kerjanya, mari kita jelajahi beberapa aplikasi praktis di mana daftar tertaut dapat digunakan secara efektif.

Anda juga dapat mendaftar di kami Kursus Gratis Hari ini!

Menerapkan Tumpukan dan Antrian

Salah satu penerapan daftar tertaut yang paling umum adalah penerapan tumpukan dan antrian. Tumpukan dan antrian adalah tipe data abstrak yang dapat dengan mudah diimplementasikan menggunakan daftar tertaut.

Tumpukan adalah struktur data yang mengikuti prinsip Last-In-First-Out (LIFO). Elemen ditambahkan dan dihapus dari ujung yang sama, yang dikenal sebagai bagian atas tumpukan. Daftar tertaut menyediakan cara yang efisien untuk mengimplementasikan tumpukan karena kita dapat dengan mudah menambahkan atau menghapus elemen dari bagian atas daftar.

Berikut ini contoh penerapan tumpukan menggunakan daftar tertaut dengan Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.head = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def pop(self):
        if self.head is None:
            return None
        popped = self.head.data
        self.head = self.head.next
        return popped

Sebaliknya, antrian mengikuti prinsip First-In-First-Out (FIFO). Elemen ditambahkan di satu ujung, yang disebut bagian belakang, dan dihilangkan dari ujung lainnya, yang disebut bagian depan. Daftar tertaut juga dapat digunakan untuk mengimplementasikan antrean secara efisien.

Berikut ini contoh penerapan antrian menggunakan daftar tertaut dengan Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, data):
        new_node = Node(data)
        if self.rear is None:
            self.front = new_node
            self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node

    def dequeue(self):
        if self.front is None:
            return None
        dequeued = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        return dequeued

Menangani Kumpulan Data Besar

Daftar tertaut juga berguna saat menangani kumpulan data besar. Tidak seperti array, daftar tertaut tidak memerlukan alokasi memori yang berdekatan. Artinya, daftar tertaut dapat secara efisien menangani kumpulan data dengan berbagai ukuran tanpa perlu mengubah ukuran atau mengalokasikan ulang.

Misalnya, kita memiliki kumpulan data yang terdiri dari jutaan catatan, dan kita perlu melakukan operasi seperti penyisipan, penghapusan, atau traversal. Menggunakan array untuk tugas ini bisa jadi tidak efisien karena memerlukan perpindahan elemen saat menyisipkan atau menghapus. Namun, dengan daftar tertaut, kita dapat dengan mudah menyisipkan atau menghapus elemen dengan memperbarui pointer, sehingga menghasilkan pengoperasian yang lebih cepat.

Algoritma Traversal Grafik

Algoritme traversal grafik, seperti pencarian luas pertama (BFS) dan pencarian mendalam pertama (DFS), juga dapat diimplementasikan menggunakan daftar tertaut. Dalam penjelajahan graf, kita mengunjungi setiap simpul atau simpul dalam graf dalam urutan tertentu.

Daftar tertaut dapat digunakan untuk mewakili daftar ketetanggaan suatu graf, di mana setiap simpul dalam daftar tertaut mewakili sebuah simpul dan simpul-simpul yang berdekatan disimpan sebagai simpul-simpul daftar tertaut. Representasi ini memungkinkan traversal dan eksplorasi grafik yang efisien.

Representasi Polinomial

Daftar tertaut dapat digunakan untuk merepresentasikan polinomial secara efisien. Dalam matematika, polinomial adalah ekspresi yang terdiri dari variabel dan koefisien. Setiap suku dalam polinomial dapat direpresentasikan sebagai simpul dalam daftar tertaut, dimana koefisien dan eksponennya disimpan sebagai data.

Dengan menggunakan linked list, kita dapat dengan mudah melakukan operasi pada polinomial seperti penjumlahan, pengurangan, dan perkalian. Node dapat dimanipulasi untuk melakukan operasi ini, sehingga menghasilkan representasi polinomial yang ringkas dan efisien.

Daftar Putar Musik dan Video

Daftar tertaut biasanya digunakan untuk mengimplementasikan daftar putar di pemutar musik dan video. Setiap lagu atau video dapat direpresentasikan sebagai node dalam daftar tertaut, yang datanya berisi informasi tentang file media dan penunjuk menunjuk ke lagu atau video berikutnya dalam daftar putar.

Menggunakan daftar tertaut untuk daftar putar memungkinkan navigasi yang mudah antara lagu atau video. Kami dapat dengan mudah menambah atau menghapus lagu dari playlist dengan memperbarui petunjuknya, memberikan pengalaman pengguna yang lancar.

Kesimpulan

Kesimpulannya, daftar tertaut adalah struktur data serbaguna yang dapat diterapkan di berbagai domain. Mereka dapat digunakan untuk mengimplementasikan tumpukan dan antrean, menangani kumpulan data besar, melakukan traversal grafik, merepresentasikan polinomial, dan membuat daftar putar. Daftar tertaut memberikan solusi efisien untuk masalah ini dengan memanfaatkan alokasi memori dinamis dan manipulasi node yang mudah.

Dengan memahami penerapan daftar tertaut, kita dapat membuat keputusan yang tepat ketika memilih struktur data untuk program kita. Baik itu mengelola data, mengimplementasikan algoritme, atau membuat antarmuka yang ramah pengguna, daftar tertaut menawarkan alat yang berharga dalam perangkat pemrogram.

Jadi, jika nanti Anda menghadapi masalah yang memerlukan penyisipan, penghapusan, atau traversal yang efisien, pertimbangkan untuk menggunakan daftar tertaut untuk menyederhanakan solusi dan mengoptimalkan kode Anda.

Anda juga dapat membaca lebih banyak artikel terkait Daftar Python di sini:

Tanya Jawab Umum (FAQ)

terkait

• Konten Bertenaga SEO & Distribusi PR. Dapatkan Amplifikasi Hari Ini.
• PlatoData.Jaringan Vertikal Generatif Ai. Berdayakan Diri Anda. Akses Di Sini.
• PlatoAiStream. Intelijen Web3. Pengetahuan Diperkuat. Akses Di Sini.
• PlatoESG. Karbon, teknologi bersih, energi, Lingkungan Hidup, Tenaga surya, Penanganan limbah. Akses Di Sini.
• PlatoHealth. Kecerdasan Uji Coba Biotek dan Klinis. Akses Di Sini.
• Sumber: https://www.analyticsvidhya.com/blog/2024/02/linked-lists-in-python/