Linked List Python: Tutorial dengan Contoh

Linked list adalah struktur data yang berperan penting dalam pengorganisasian dan pengelolaan data. Struktur ini berisi serangkaian node yang disimpan pada lokasi acak di memori, sehingga memungkinkan pengelolaan memori yang efisien. Setiap node dalam linked list memiliki dua komponen utama: bagian data dan referensi ke node berikutnya dalam urutan.

Jika konsep ini terdengar rumit sekilas, jangan khawatir!

Kita akan menguraikannya ke dasar-dasarnya untuk menjelaskan apa itu linked list, mengapa kita menggunakannya, dan keunggulan unik yang ditawarkannya.

Mengapa Linked List?

Linked list diciptakan untuk mengatasi berbagai kekurangan yang terkait dengan penyimpanan data pada list dan array biasa, seperti yang diuraikan di bawah ini:

Kemudahan penyisipan dan penghapusan

Dalam list, menyisipkan atau menghapus elemen pada posisi selain di akhir mengharuskan pergeseran semua item setelahnya ke posisi berbeda. Proses ini memiliki kompleksitas waktu O(n) dan dapat menurunkan kinerja secara signifikan, terutama saat ukuran list membesar. Jika Anda belum familiar dengan cara kerja list atau implementasinya, Anda dapat membaca tutorial tentang list di Python kami.

Linked list, bagaimanapun, bekerja secara berbeda. Elemen-elemennya disimpan di berbagai lokasi memori yang tidak bersebelahan dan dihubungkan melalui pointer ke node berikutnya. Struktur ini memungkinkan linked list menambah atau menghapus elemen di posisi mana pun hanya dengan memodifikasi tautan untuk memasukkan elemen baru atau melewati elemen yang dihapus.

Setelah Anda memiliki referensi langsung ke node pada titik penyisipan atau penghapusan, operasinya sendiri adalah O(1). Namun, menemukan posisi tersebut tetap memerlukan penelusuran O(n), jadi manfaat O(1) hanya berlaku ketika Anda sudah memegang pointer ke node terkait (misalnya saat bekerja di head dari list).

Ukuran dinamis

List Python adalah array dinamis, yang berarti memberikan fleksibilitas untuk mengubah ukuran.

Namun, proses ini melibatkan serangkaian operasi kompleks, termasuk mengalokasikan ulang array ke blok memori baru yang lebih besar. Realokasi semacam ini tidak efisien karena elemen-elemen disalin ke blok baru, berpotensi mengalokasikan ruang lebih banyak daripada yang langsung diperlukan.

Sebaliknya, linked list dapat bertambah dan menyusut secara dinamis tanpa perlu realokasi atau pengubahan ukuran. Ini menjadikannya opsi yang lebih disukai untuk tugas yang memerlukan fleksibilitas tinggi.

Efisiensi memori

List mengalokasikan memori untuk semua elemennya dalam satu blok bersebelahan. Jika sebuah list perlu tumbuh melampaui ukuran awalnya, list harus mengalokasikan blok memori bersebelahan baru yang lebih besar dan kemudian menyalin semua elemen yang ada ke blok baru ini. Proses ini memakan waktu dan tidak efisien, terutama untuk list besar. Di sisi lain, jika ukuran awal list terlalu besar, memori yang tidak terpakai menjadi terbuang.

Sebaliknya, linked list mengalokasikan memori untuk setiap elemen secara terpisah. Struktur ini menghasilkan pemanfaatan memori yang lebih baik karena memori untuk elemen baru dapat dialokasikan saat elemen tersebut ditambahkan.

Kapan Sebaiknya Menggunakan Linked List?

Walaupun linked list memberikan beberapa keuntungan dibanding list dan array biasa, seperti ukuran dinamis dan efisiensi memori, struktur ini juga memiliki keterbatasan. Karena pointer untuk setiap elemen harus disimpan untuk mereferensikan node berikutnya, penggunaan memori per elemen lebih tinggi saat menggunakan linked list. Selain itu, struktur data ini tidak memungkinkan akses langsung ke data. Mengakses suatu elemen memerlukan penelusuran berurutan dari awal list, menghasilkan kompleksitas waktu pencarian O(n).

Pilihan antara menggunakan linked list atau array bergantung pada kebutuhan spesifik aplikasi. Linked list paling berguna ketika:

• Anda sering perlu menyisipkan dan menghapus banyak elemen
• Ukuran data tidak dapat diprediksi atau kemungkinan sering berubah
• Akses langsung ke elemen bukan persyaratan
• Dataset berisi elemen atau struktur yang besar

Jenis-jenis linked list

Ada tiga jenis linked list, masing-masing menawarkan keunggulan unik untuk skenario berbeda. Jenis-jenis tersebut adalah:

Singly-linked list

Singly-linked list

Singly-linked list adalah jenis linked list yang paling sederhana, di mana setiap node berisi beberapa data dan referensi ke node berikutnya dalam urutan. Penelusuran hanya dapat dilakukan ke satu arah — dari head (node pertama) ke tail (node terakhir).

Setiap node dalam singly-linked list umumnya terdiri dari dua bagian:

• Data: Informasi aktual yang disimpan dalam node.
• Next Pointer: Referensi ke node berikutnya. Pointer next pada node terakhir biasanya diatur ke null.

Karena struktur data ini hanya dapat ditelusuri ke satu arah, mengakses elemen tertentu berdasarkan nilai atau indeks mengharuskan mulai dari head dan bergerak secara berurutan melalui node hingga node yang diinginkan ditemukan. Operasi ini memiliki kompleksitas waktu O(n), sehingga kurang efisien untuk list besar.

Menyisipkan dan menghapus node di awal singly-linked list sangat efisien dengan kompleksitas waktu O(1). Namun, penyisipan dan penghapusan di tengah atau di akhir memerlukan penelusuran list hingga titik tersebut, sehingga kompleksitas waktunya O(n).

Desain singly-linked list menjadikannya struktur data yang berguna ketika melakukan operasi yang terjadi di awal list.

Doubly-linked list

Doubly-linked list

Salah satu kelemahan singly-linked list adalah kita hanya dapat menelusurinya ke satu arah dan tidak dapat kembali ke node sebelumnya jika diperlukan. Batasan ini mengurangi kemampuan kita untuk melakukan operasi yang memerlukan navigasi dua arah.

Doubly-linked list mengatasi masalah ini dengan menambahkan pointer tambahan pada setiap node, sehingga list dapat ditelusuri ke dua arah. Setiap node dalam doubly-linked list berisi tiga elemen: data, pointer ke node berikutnya, dan pointer ke node sebelumnya.

Circular linked list

Circular linked list

Circular linked list adalah bentuk khusus dari linked list di mana node terakhir menunjuk kembali ke node pertama, membentuk struktur melingkar. Ini berarti, tidak seperti singly dan doubly linked list yang telah kita lihat, circular linked list tidak berakhir; alih-alih, ia berputar kembali.

Sifat siklis pada circular linked list menjadikannya ideal untuk skenario yang perlu dilalui secara terus-menerus, seperti permainan papan yang kembali dari pemain terakhir ke pemain pertama, atau dalam algoritma komputasi seperti penjadwalan round-robin.

Ringkasan kompleksitas waktu

Berguna untuk melihat sekilas bagaimana linked list dibandingkan dengan list Python:

Inti utamanya: linked list unggul pada penyisipan dan penghapusan di head (O(1)), tetapi kalah pada hal lainnya. Jika Anda tidak sering menambah atau menghapus elemen di awal struktur data Anda, list Python biasa kemungkinan adalah pilihan yang lebih baik.

Cara Membuat Linked List di Python

Sekarang kita memahami apa itu linked list, mengapa kita menggunakannya, dan variasinya, mari lanjut mengimplementasikan struktur data ini di Python. Notebook untuk tutorial ini juga tersedia di DataLab workbook ini; jika Anda membuat salinan, Anda dapat mengedit dan menjalankan kodenya. Ini pilihan yang bagus jika Anda mengalami kendala saat menjalankan kode sendiri!

Inisialisasi node

Seperti yang telah kita pelajari, node adalah elemen dalam linked list yang menyimpan data dan referensi ke node berikutnya dalam urutan. Berikut cara Anda mendefinisikan node di Python:

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

    def __repr__(self):
        return f"Node({self.data})"

Kode di atas menginisialisasi sebuah node dengan melakukan dua aksi utama: Atribut "data" pada node diberi nilai yang merepresentasikan informasi aktual yang dimaksudkan untuk dikandung node. Atribut "next" merepresentasikan alamat node berikutnya. Saat ini diatur ke None, menandakan bahwa ia belum terhubung ke node lain dalam list. Saat kita terus menambahkan node baru ke linked list, atribut ini akan diperbarui untuk menunjuk ke node selanjutnya.

Membuat kelas linked list

Selanjutnya, kita perlu membuat kelas linked list. Ini akan membungkus semua operasi untuk mengelola node, seperti penyisipan dan penghapusan. Kita akan mulai dengan menginisialisasi linked list:

class LinkedList:
    def __init__(self):
        self.head = None  # Initialize head as None

Dengan menetapkan self.head ke None, kita menyatakan bahwa linked list pada awalnya kosong dan tidak ada node dalam list yang dapat ditunjuk. Sekarang kita akan melanjutkan untuk mengisi list dengan menyisipkan node baru.

Menyisipkan node baru di awal linked list

Di dalam kelas LinkedList, kita akan menambahkan metode untuk membuat node baru dan menempatkannya di awal list:

    def insertAtBeginning(self, new_data):
        new_node = Node(new_data)  # Create a new node 
        new_node.next = self.head  # Next for new node becomes the   current head
        self.head = new_node  # Head now points to the new node

Setiap kali Anda memanggil metode di atas, sebuah node baru dibuat dengan data yang Anda tentukan. Pointer next dari node baru ini diatur ke head saat ini dari list, yang akan menempatkan node ini di depan node yang sudah ada. Terakhir, node yang baru dibuat dijadikan head dari list.

Sekarang kita akan mengisi linked list ini dengan serangkaian kata untuk memahami lebih baik bagaimana operasi penyisipan bekerja. Untuk melakukannya, mari terlebih dahulu membuat metode yang dirancang untuk menelusuri dan mencetak konten list:

    def printList(self):
        temp = self.head # Start from the head of the list
        while temp:
            print(temp.data,end=' ') # Print the data in the current node
            temp = temp.next # Move to the next node
        print()  # Ensures the output is followed by a new line

Metode di atas akan mencetak isi linked list kita. Sekarang mari kita gunakan metode yang telah kita definisikan untuk mengisi list dengan serangkaian kata: “the quick brown fox.”

if __name__ == '__main__':
    # Create a new LinkedList instance
    llist = LinkedList()

    # Insert each letter at the beginning using the method we created
    llist.insertAtBeginning('fox') 
    llist.insertAtBeginning('brown') 
    llist.insertAtBeginning('quick')  
    llist.insertAtBeginning('the')  

    # Now 'the' is the head of the list, followed by 'quick', then 'brown' and 'fox'

    # Print the list
    llist.printList()

Baris-baris kode di atas akan menghasilkan keluaran berikut:

"the quick brown fox"

Menyisipkan node baru di akhir linked list

Sekarang kita akan membuat metode bernama insertAtEnd di dalam kelas LinkedList, untuk membuat node baru di akhir list. Jika list kosong, node baru akan menjadi head dari list. Jika tidak, node baru akan ditambahkan ke node terakhir saat ini di list. Mari kita lihat cara kerjanya:

    def insertAtEnd(self, new_data):
        new_node = Node(new_data)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

Metode di atas dimulai dengan membuat node baru. Kemudian memeriksa apakah list kosong, dan jika ya, node baru ditetapkan sebagai head dari list tersebut. Jika tidak, metode menelusuri list untuk menemukan node terakhir dan mengatur pointer node tersebut ke node baru.

Sekarang kita perlu memasukkan metode ini ke dalam kelas LinkedList dan menggunakannya untuk menambahkan sebuah kata di akhir list kita. Untuk melakukannya, ubah fungsi utama Anda agar seperti ini:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

    # Print the list
    llist.printList()

Perhatikan bahwa kita cukup memanggil metode insertAtEnd untuk mencetak kata “jumps” di akhir list. Kode di atas akan menghasilkan keluaran berikut:

"the quick brown fox jumps"

Menghapus node dari awal linked list

Menghapus node pertama dari linked list mudah karena hanya melibatkan pengalihan head list ini ke node kedua. Dengan cara ini, node pertama tidak lagi menjadi bagian dari list. Untuk melakukannya, sertakan metode berikut dalam kelas LinkedList:

def deleteFromBeginning(self):
    if self.head is None:
        return "The list is empty" # If the list is empty, return this string
    self.head = self.head.next  # Otherwise, remove the head by making the next node the new head

Menghapus node dari akhir linked list

Untuk menghapus node terakhir dari linked list, kita harus menelusuri list untuk menemukan node kedua dari terakhir dan mengubah pointer next-nya menjadi None. Dengan cara ini, node terakhir tidak lagi menjadi bagian dari list. Salin dan tempel metode berikut ke dalam kelas LinkedList Anda untuk melakukannya:

def deleteFromEnd(self):
    if self.head is None:
        return "The list is empty" 
    if self.head.next is None:
        self.head = None  # If there's only one node, remove the head by making it None
        return
    temp = self.head
    while temp.next.next:  # Otherwise, go to the second-last node
        temp = temp.next
    temp.next = None  # Remove the last node by setting the next pointer of the second-last node to None

Metode di atas pertama-tama memeriksa apakah linked list kosong, dan jika ya, mengembalikan pesan kepada pengguna. Jika tidak, jika list berisi satu node, node tersebut dihapus. Untuk list dengan banyak node, metode mencari node kedua dari terakhir, dan referensi node berikutnya diperbarui menjadi None.

Sekarang mari kita perbarui fungsi utama untuk menghapus elemen dari awal dan akhir linked list:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

    # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from the beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()

Kode di atas akan mencetak list sebelum dan sesudah penghapusan, menampilkan cara kerja operasi sisip dan hapus pada linked list. Anda akan melihat keluaran berikut setelah menjalankan kode ini:

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox

Mencari nilai tertentu dalam linked list

Operasi terakhir yang akan kita pelajari dalam bab ini adalah pengambilan nilai tertentu dalam linked list. Untuk melakukannya, metode harus mulai dari head list dan mengiterasi setiap node, memeriksa apakah data node cocok dengan nilai pencarian. Berikut implementasi praktis operasi ini:

def search(self, value):
    current = self.head  # Start with the head of the list
    position = 0  # Counter to keep track of the position
    while current: # Traverse the list
        if current.data == value: # Compare the list's data to the search value
            return f"Value '{value}' found at position {position}" # Print the value if a match is found
        current = current.next
        position += 1
    return f"Value '{value}' not found in the list" 

Untuk menemukan nilai tertentu dalam linked list yang telah kita buat, perbarui fungsi utama Anda untuk menyertakan metode pencarian yang baru saja kita buat:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

   # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()
    
        # Search for 'quick' and 'lazy' in the list
    print(llist.search('quick'))  # Expected to find
    print(llist.search('lazy'))   # Expected not to find

Kode di atas akan menghasilkan keluaran berikut:

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox 
Value 'quick' found at position 0
Value 'lazy' not found in the list

Kata “quick” berhasil ditemukan dalam linked list karena ada pada posisi pertama list. Namun, kata “lazy” bukan bagian dari list, itulah sebabnya tidak ditemukan.

Penutup

Jika Anda sudah sampai di sini, selamat! Anda kini memiliki pemahaman yang solid tentang prinsip dasar linked list, termasuk strukturnya, jenis-jenisnya, cara menambah dan menghapus elemen, serta cara menelusurinya.

Namun perjalanan tidak berhenti di sini. Linked list hanyalah awal dari dunia struktur data dan algoritma. Berikut beberapa langkah lanjutan yang dapat Anda ambil untuk memperdalam pemahaman Anda tentang topik ini:

Buat proyek Anda sendiri

Dalami aplikasi praktis linked list dengan mengintegrasikannya ke dalam proyek coding atau data science. Linked list digunakan untuk mengembangkan sistem berkas, membangun hash table, dan bahkan membuat sistem navigasi GPS serta permainan papan. Untuk memulai proyek Anda sendiri, lihat proyek data science gratis kami yang memandu Anda memecahkan masalah dunia nyata di Python, R, dan SQL.

Pelajari struktur data dan algoritma

Mempelajari struktur data lain, seperti tree, stack, dan queue, adalah kelanjutan alami dari memahami linked list. Struktur-struktur ini dibangun di atas prinsip linked list, membantu Anda menyelesaikan beragam masalah komputasional secara efisien. Tree dan binary search tree, misalnya, memperluas konsep linked list menjadi bentuk hierarkis, memungkinkan setiap node terhubung ke banyak elemen dalam struktur data.

Jika konsep-konsep ini terdengar asing bagi Anda, jangan khawatir! Datacamp memiliki satu kursus lengkap tentang struktur data dan algoritma di Python yang akan membahas konsep-konsep ini secara lebih mendalam. Anda akan terlebih dahulu mempelajari struktur data seperti stack, tree, hash table, queue, dan graph. Seiring kemajuan Anda dalam kursus, Anda akan memahami algoritma pencarian dan pengurutan, yang akan membantu Anda menjadi programmer dan pemecah masalah yang lebih efisien.

Mengeksplorasi konsep lanjutan linked list

Kita telah mengimplementasikan singly-linked list dalam tutorial ini, mencakup operasi seperti penyisipan, penghapusan, dan penelusuran.

Anda dapat melangkah lebih jauh dengan mempelajari implementasi doubly dan circular linked list. Skip list adalah perpanjangan lain dari linked list yang memungkinkan operasi pencarian lebih cepat dengan memfasilitasi akses yang lebih cepat ke elemen.

Mempelajari struktur data lanjutan ini akan meningkatkan keterampilan teknis Anda ke tingkat berikutnya dan secara dramatis meningkatkan kemampuan pemrograman Anda, mempersiapkan Anda untuk tantangan yang lebih kompleks di bidang seperti data science, pengembangan perangkat lunak, dan rekayasa machine learning.

Jika Anda menginginkan pengantar pemrograman yang lebih ramah pemula sebelum membahas topik-topik lanjutan ini, jelajahi jalur keterampilan Python Programming kami. Jalur ini menawarkan serangkaian kursus yang akan mengajarkan Anda dasar-dasar bahasa tersebut.