Memahami Linked List

Salah satu hal yang perlu dipahami oleh seorang software engineer adalah struktur data. Pada dasarnya, topik struktur data mempelajari teknik pengorganisasian data sehingga cepat, mudah dan efisien untuk digunakan untuk menyelesaikan problem tertentu. Bayangkan kamu memiliki banyak buku, ada buku catatan kuliah, ada buku diary, buku resep, buku teks perkuliahan (dengan berbagai macam topik, tentunya), novel, buku sejarah, ensiklopedia, dan masih banyak lagi. Tidak akan ada masalah jika kamu hanya punya 5 atau 10 buku. Masalah baru muncul ketika kamu punya lebih dari 300 buku. Jika tidak disusun, disimpan, dan ditempatkan dengan benar, buku yang kamu punya akan sangat sulit untuk dicari kemudian hari dan menyusunnya kembali setelah dibaca. Salah satu hal yang mungkin kamu lakukan untuk mengatasi hal ini adalah menyusun buku sesuai huruf abjad, sesuai kategori, atau kedua-duanya. Masing-masing cara penyusunan ini punya kelebihan dan kekurangannya masing-masing.

Hal yang sama berlaku pada data. Data perlu disusun dan diorganisir supaya dapat dicari, diambil, dan diproses dengan cepat, efektif, dan efisien. Cara untuk mengorganisir data inilah yang disebut sebagai struktur data. Pada program komputer, struktur data yang kita gunakan setidaknya harus memperhatikan 2 aspek, yaitu kecepatan pemrosesan dan alokasi memori. Beberapa struktur data tertentu dapat digunakan sehingga dapat digunakan dengan cepat, akan tetapi memakan memori cukup banyak. Beberapa struktur data lainnya hemat memori, tapi memiliki waktu pemrosesan yang lebih lama. Selalu ada trade-off untuk masalah ini.

Mungkin cukup banyak yang mengenal struktur data array, yang biasanya direpresentasikan sebagai kumpulan data yang diapit oleh tanda kurung, misalnya [2, 5, 8, 1]. Selain array, sebenarnya ada struktur data lainnya yang dapat digunakan, dan pada use case tertentu, jauh lebih cepat dibandingkan array, yaitu Linked List. Linked list direpresentasikan sebagai kumpulan node (titik) yang dihubungkan oleh link (penghubung), seperti pada gambar di bawah:

Secara prinsip, masing-masing node terdiri dari 2 properti, yaitu nilai yang disimpan oleh node itu sendiri dan node berikutnya. Sebagai contoh, node pertama pada gambar di atas bernilai 2, dan node berikutnya dari node ini adalah node dengan nilai 5.

Untuk membuatnya lebih presisi, kita dapat mendefinisikan 2 properti untuk masing-masing node, yaitu value dan next. Properti value menunjukkan nilai yang disimpan oleh sebuah node, dan properti next menyatakan “node berikutnya yang mana?”. Properti next ini disebut juga sebagai pointer. Bayangkan struktur berikut:

Jika kita mempunyai linked list dengan struktur seperti ini, kita dapat mengamati hal berikut:

1. Pada node1, value nya adalah 1, dan next nya adalah node2. Artinya, node1 bernilai 1, dan setelah node1 ada node2.
2. Pada node2, value nya adalah 5, dan next nya adalah node3. Artinya, node2 bernilai 5, dan setelah node2 ada node3.
3. dst.

Cukup masuk akal? intinya, setiap node punya 2 properti, yaitu value (nilai yang disimpan) dan next (siapa node berikutnya). Coba tebak, berapa value dari node4?

Kenapa Linked List Diperlukan?

Linked list diperlukan pada saat kita memerlukan struktur data yang fleksibel dan kecepatan proses data insertion dan data deletion. Berbeda dengan array yang ukurannya tetap, linked list sangat fleksibel, sehingga cocok digunakan jika modifikasi konten pada struktur data sering dilakukan. Selain itu, jika kita ingin menambah / menghapus data pada struktur data array, kita perlu menggeser semua data yang sudah ada sebelumnya, sehingga proses nya lebih lama, dengan time complexity $O(n)$. Pada linked list, untuk melakukan hal yang sama kita hanya perlu mengganti pointer pada node yang bersesuaian. Oleh karena itu, jika node target sudah diketahui, proses ini akan sangat cepat, dengan time complexity $O(1)$.

Implementasi Linked List Menggunakan Python

Implementasi minimum dari Linked List pada bahasa Python dapat kita lakukan dengan membuat class untuk node yang akan kita gunakan, dengan properti data (value) dan next. Berikut adalah implementasinya:

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

sebagai contoh, untuk membuat sebuah linked list dengan struktur dan data seperti pada gambar sebelumnya, kita dapat melakukannya sebagai berikut:

class Node:
	def __init__(self, data):
		self.data = data
		self.next = None
 
node1 = Node(2)
node2 = Node(5)
node3 = Node(8)
node4 = Node(1)
 
node1.next = node2
node2.next = node3
node3.next = node4

Ini merupakan implementasi paling dasar dari linked list menggunakan Python. Dengan struktur data ini, ada banyak hal yang bisa kita lakukan, seperti searching, insertion, dan deletion yang akan kita bahas pada artikel berikutnya.