Definisi Struktur Data Linked List
Linked List adalah suatu cara untuk menyimpan data dengan struktur sehingga programmer/pengguna dapat secara otomatis menciptakan suatu tempat baru untuk menyimpan data kapan saja pada saat diperlukan.
Linked List dikenal juga dengan sebutan senarai berantai adalah stuktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan). Elemen data yang dihubungkan dengan link pada linked list disebut Node.
Fungsi Linked List
- Penyimpanan Data, Linked list digunakan untuk menyimpan dan mengatur data secara dinamis.
- Penambahan & Penghapusan, Linked list memungkinkan penambahan atau penghapusan elemen dengan cepat.
- Akses Berurutan, Linked list memungkinkan akses berurutan ke elemen-elemennya, sehingga mengakses elemen-elemen dalam urutan tertentu.
- Manajemen Memori Dinamis, Linked list memungkinkan alokasi dan dealokasi memori secara dinamis saat elemen ditambah atau dihapus.
Jenis Jenis Linked List
Singly Linked List
Setiap elemen (node) dalam daftar ini memiliki dua bagian, yaitu data dan tautan (link) ke node berikutnya dalam daftar.
Doubly Linked List
Setiap elemen dalam daftar ini memiliki tiga bagian, yaitu data, tautan ke node sebelumnya, dan tautan ke node berikutnya.
Circular Linked List
Pada daftar ini, node terakhir menautkan kembali ke node pertama, sehingga membentuk lingkaran.
Sorted Linked List
Elemen-elemen dalam daftar ini diatur dalam urutan tertentu, biasanya urutan naik atau turun.
Keuntungan Linked List
Dalam ilmu komputer, linked list atau daftar bertaut adalah salah satu struktur data dasar yang digunakan untuk menyimpan kumpulan elemen data dalam urutan tertentu. Berikut adalah beberapa keuntungan dari penggunaan linked list:
- Penyesuaian Ukuran Dinamis: Tidak seperti array yang memiliki ukuran tetap, linked list dapat menyesuaikan ukurannya dengan dinamis sesuai kebutuhan.
- Penyisipan dan Penghapusan Efisien: Menyisipkan atau menghapus elemen dari awal atau tengah linked list dapat dilakukan dengan efisien tanpa perlu menggeser elemen-elemen lain, seperti yang perlu dilakukan pada array.
- Penggunaan Memori Tidak Boros: Memori untuk linked list dialokasikan saat runtime (dinamis), jadi tidak ada pemborosan memori seperti yang mungkin terjadi dengan array yang telah dialokasikan lebih awal dengan ukuran maksimum.
- Tidak ada Batasan Ukuran: Karena linked list dinamis, tidak ada batasan ukuran teoretis untuk itu, kecuali memori yang tersedia di sistem.
- Fleksibilitas: Variasi dari linked list, seperti doubly linked list atau circular linked list, memberikan fleksibilitas tambahan dalam operasi tertentu.
- Tidak memerlukan Realokasi: Tidak seperti array dinamis, linked list tidak memerlukan operasi realokasi saat elemen ditambahkan atau dihapus. Hal ini bisa memberikan keuntungan performa dalam beberapa kasus.
- Implementasi Struktur Lain: Linked list sering digunakan sebagai blok pembangun untuk struktur data lainnya seperti stack dan queue.
Keterbatasan Linked List
Meskipun linked list memiliki beberapa keuntungan, ada juga keterbatasan dan kelemahan yang perlu diperhatikan:
- Akses Acak: Akses elemen dalam linked list memerlukan penelusuran dari awal hingga elemen yang diinginkan ditemukan. Hal ini berarti akses acak ke elemen dalam linked list memerlukan waktu O(n) dalam kasus terburuk.
- Penggunaan Memori Tambahan: Setiap elemen dalam linked list memerlukan memori tambahan untuk menyimpan pointer ke elemen berikutnya (dan mungkin sebelumnya, dalam kasus doubly linked list). Hal ini berarti linked list memerlukan lebih banyak memori per elemen dibandingkan dengan array.
- Kompleksitas dalam Implementasi: Operasi seperti pemasukan dan penghapusan elemen dari linked list memerlukan penanganan pointer yang lebih rumit dibandingkan dengan array.
- Cache Locality: Array memiliki keuntungan dari cache locality, yang berarti akses berurutan ke elemen dalam array sering kali lebih cepat karena cara data disimpan dalam memori. Linked list tidak memiliki sifat ini, sehingga operasi pada linked list mungkin lebih lambat karena miss cache yang lebih sering.
- Risiko Kesalahan Pointer: Karena operasi pada linked list memerlukan penanganan pointer, ada risiko kesalahan seperti “dangling pointers” atau “memory leaks”.
- Kesulitan dalam Akses Mundur: Dalam singly linked list, akses ke elemen sebelumnya memerlukan penelusuran dari awal. Sedangkan dalam array, kita bisa dengan mudah mengakses elemen sebelumnya dengan mengurangi indeks.
- Kesulitan dalam Pembalikan: Membalik urutan elemen dalam linked list memerlukan algoritma khusus dan mungkin lebih kompleks daripada operasi serupa pada array.
Contoh Penerapan Singly Linked List (SLL)
Penerapan Singly Linked List (SLL) sering digunakan dalam berbagai aplikasi karena fleksibilitas dan keefisienannya dalam operasi penyisipan dan penghapusan. Berikut adalah contoh konkret dari penerapan Singly Linked List dalam kehidupan sehari-hari atau di dalam aplikasi tertentu:
- Riwayat Browser Web: Saat Anda menjelajahi internet menggunakan browser web, setiap halaman yang Anda kunjungi dapat disimpan dalam SLL. Saat Anda mengklik tombol “kembali”, Anda bergerak mundur dalam list tersebut. Jika Anda mengunjungi halaman web baru setelah mundur beberapa langkah, bagian depan dari list (halaman yang Anda kunjungi sebelumnya) dapat dihapus dan halaman baru ditambahkan ke list.
- Pemutar Musik Sederhana: Dalam pemutar musik sederhana yang memungkinkan Anda memilih lagu berikutnya, namun tidak memungkinkan Anda untuk memilih lagu sebelumnya, SLL bisa digunakan untuk mengatur antrian lagu.
- Aplikasi Perekaman Aktivitas: Bayangkan aplikasi yang merekam setiap tindakan atau aktivitas yang Anda lakukan, tetapi hanya memungkinkan Anda untuk “membatalkan” tindakan terakhir. Dalam kasus ini, SLL bisa digunakan untuk menyimpan riwayat tindakan, dengan operasi pembatalan menghapus node terakhir dari list.
- Aplikasi Pemesanan Tiket: Saat pengguna memesan tiket untuk suatu acara, aplikasi dapat menggunakan SLL untuk menyimpan riwayat pemesanan dari pengguna, tetapi tidak memungkinkan pengguna untuk melihat riwayat pemesanan sebelumnya dengan mudah.
- Sistem Manajemen Tugas: Dalam sistem operasi atau aplikasi multitasking, tugas atau proses yang perlu dikerjakan bisa dikelola dalam bentuk SLL. Saat satu tugas selesai, tugas berikutnya diambil dari list dan diproses.
- Aplikasi Chat Sederhana: Dalam aplikasi chat sederhana, pesan yang masuk dari pengguna lain dapat dikelola dalam bentuk SLL. Saat Anda membaca pesan, Anda melihat pesan terbaru pertama dan dapat terus melanjutkan ke pesan sebelumnya dengan mengikuti pointer dalam SLL.
Singly Linked List memiliki berbagai penerapan, dan contoh-contoh di atas hanyalah sebagian kecil dari berbagai cara di mana struktur data ini dapat digunakan dalam aplikasi nyata.
Contoh Penerapan Doubly Linked List (DLL)
Doubly Linked List (DLL) adalah bentuk linked list di mana setiap node memiliki dua pointer: satu menunjuk ke node sebelumnya dan yang lainnya menunjuk ke node berikutnya. Keuntungan dari DLL dibandingkan dengan Singly Linked List (SLL) adalah kemudahan navigasi ke kedua arah, meskipun ini datang dengan cost tambahan dari memori yang digunakan untuk pointer tambahan.
Berikut adalah beberapa penerapan atau kasus penggunaan dari Doubly Linked List:
- Browser Web – Navigasi Maju dan Mundur: DLL sangat berguna untuk menyimpan riwayat halaman yang dikunjungi di browser web. Tombol ‘mundur’ membawa Anda ke node sebelumnya, sedangkan tombol ‘maju’ membawa Anda ke node berikutnya.
- Aplikasi Editor Teks: DLL dapat digunakan untuk menyimpan karakter dalam dokumen, memudahkan operasi seperti penyisipan, penghapusan, dan navigasi antar karakter.
- Daftar Putar Pemutar Musik: Dengan menggunakan DLL, pengguna dapat dengan mudah beralih ke lagu sebelumnya atau berikutnya dalam daftar putar.
- Sistem Manajemen Cache: Salah satu strategi manajemen cache populer, LRU (Least Recently Used), dapat diimplementasikan dengan efisien menggunakan DLL. Elemen yang baru saja diakses atau ditambahkan diletakkan di depan, dan elemen yang jarang diakses (yang berada di belakang) dapat dihapus ketika cache penuh.
- Navigasi pada Aplikasi dengan Riwayat Transaksi: Aplikasi yang memerlukan kemampuan untuk melihat riwayat transaksi atau aktivitas sebelumnya dan berikutnya (seperti perangkat lunak akuntansi atau database) dapat memanfaatkan DLL untuk menyimpan dan menavigasi riwayat tersebut.
- Penerapan DEQ (Double-ended Queue): DeQ adalah struktur data yang memungkinkan penambahan dan penghapusan elemen dari kedua ujung. DLL merupakan implementasi yang pas untuk dek karena memungkinkan akses, penyisipan, dan penghapusan dengan cepat dari kedua ujung.
- Aplikasi dengan Fitur Undo dan Redo: DLL dapat digunakan untuk menyimpan riwayat perubahan dalam aplikasi yang memungkinkan operasi undo dan redo. “Undo” akan bergerak ke node sebelumnya, sedangkan “redo” akan bergerak ke node berikutnya.
- Navigasi dalam Aplikasi Grafik atau 3D: DLL bisa digunakan untuk menyimpan urutan objek atau adegan yang pengguna telah lihat atau kunjungi, memungkinkan navigasi maju dan mundur melalui urutan tersebut.
Doubly Linked List memungkinkan fleksibilitas dalam berbagai penerapan karena kemampuannya untuk menavigasi ke kedua arah dengan mudah. Namun, harus diingat bahwa cost tambahan dari memori untuk pointer tambahan mungkin menjadi pertimbangan dalam beberapa aplikasi, terutama di lingkungan dengan keterbatasan memori.
Contoh Penerapan Circular Linked List (CLL)
Circular Linked List (CLL) adalah jenis linked list di mana node terakhir menunjuk kembali ke node pertama, sehingga membentuk lingkaran. Berikut adalah beberapa penerapan atau kasus penggunaan dari Circular Linked List:
- Sistem Navigasi Carousel: Dalam aplikasi web atau GUI yang menampilkan sejumlah item dalam bentuk carousel, navigasi antar item dapat diatur dengan CLL. Saat pengguna mencapai item terakhir dan melanjutkan navigasi ke “berikutnya”, dia akan kembali ke item pertama.
- Penjadwalan OS: Dalam sistem operasi yang menggunakan algoritma round-robin untuk penjadwalan tugas, CLL bisa digunakan. Setiap tugas diberi slot waktu tertentu untuk berjalan, dan setelah tugas terakhir mendapatkan slotnya, penjadwal kembali ke tugas pertama.
- Aplikasi Jam Digital: Untuk merepresentasikan menit (0-59) atau jam (1-12/0-23), kita bisa menggunakan CLL. Setelah mencapai angka terakhir, kita kembali ke angka awal.
- Pemutar Musik dengan Mode Ulang: Jika pemutar musik memiliki mode di mana setelah mencapai lagu terakhir dalam daftar putar, ia kembali ke lagu pertama dan terus berulang, CLL dapat digunakan untuk mengimplementasikan fitur ini.
- Animasi Siklus atau Looped Animation: Dalam aplikasi grafis atau game yang memiliki animasi yang perlu diulang dari awal setelah mencapai frame terakhir, CLL dapat digunakan untuk menyimpan urutan frame dan memudahkan looping animasi.
Meskipun Circular Linked List memiliki penerapan spesifik dan berguna dalam skenario tertentu, itu mungkin bukan pilihan yang baik untuk semua kasus penggunaan. Memilih struktur data yang sesuai tergantung pada kebutuhan dan kondisi aplikasi atau masalah yang dihadapi.
Contoh Penerapan Sorted Linked List
Sorted Linked List adalah jenis linked list di mana elemen-elemen dalam list disusun berdasarkan urutan tertentu (biasanya urutan meningkat, tetapi bisa juga menurun). Ini memastikan bahwa saat elemen baru dimasukkan ke dalam list, posisinya ditentukan berdasarkan nilai ordernya sehingga list tetap terurut.
Berikut adalah karakteristik dan penerapan dari Sorted Linked List:
Karakteristik:
- Penyisipan: Saat memasukkan elemen baru ke dalam list, elemen tersebut ditempatkan pada posisi yang sesuai untuk memastikan bahwa urutan list tetap terjaga.
- Penghapusan: Saat elemen dihapus, tidak perlu pengurutan ulang karena elemen lainnya sudah berada pada posisi yang benar.
- Pencarian: Dengan list yang terurut, pencarian bisa lebih cepat dengan menggunakan teknik seperti binary search. Namun, karena linked list tidak mendukung akses acak seperti array, binary search mungkin tidak seefisien jika diimplementasikan di array.
Penerapan:
- Aplikasi dengan Operasi Pencarian Frekuensi: Dalam aplikasi di mana pencarian adalah operasi yang sering dilakukan, dan data sering masuk, menjaga data dalam keadaan terurut dapat memudahkan dan mempercepat pencarian.
- Daftar Prioritas: Di beberapa sistem, tugas atau objek dapat diberikan prioritas. Dalam hal ini, list terurut bisa digunakan untuk menjaga tugas berdasarkan prioritas.
- Sistem Rekomendasi: Di platform seperti e-commerce, rekomendasi mungkin perlu diurutkan berdasarkan kriteria tertentu, seperti relevansi atau peringkat. Saat rekomendasi baru dihasilkan, mereka dapat ditempatkan dalam list terurut.
- Manajemen Data dalam Aplikasi: Aplikasi seperti buku alamat atau daftar karyawan mungkin memerlukan penyimpanan data yang terurut berdasarkan kriteria seperti nama atau ID.
Meskipun Sorted Linked List memiliki keuntungan dalam menjaga elemen dalam urutan tertentu, ada juga kekurangannya. Penyisipan mungkin memerlukan waktu lebih lama dibandingkan dengan linked list biasa karena perlu menemukan posisi yang tepat untuk penyisipan. Juga, seperti semua jenis linked list, ia tidak mendukung akses acak seefisien array.
Perbedaan Array dan Linked List
Perbedaan array dan linked list adalah sebagai berikut:
- Array merupakan struktur data berbasis indeks, setiap elemen dalam array terkait dengan indeks tersebut. Sementara itu, linked list bergantung pada referensi. Node-node dalam linked list terdiri dari data dan referensi ke elemen data yang lain.
- Array adalah kumpulan objek data yang mirip satu sama lain dan disimpan di lokasi memori secara berurutan. Sementara itu, linked list merupakan sekumpulan data yang berisi urutan elemen dalam strukturnya. Setiap elemen saling terkait dengan elemen berikutnya.
Pembahasan:
Array merupakan istilah yang akrab dengan ilmu komputer. Array dapat kita temukan dalam berbagai bahasa pemrograman mulai dari Java, C, hingga PHP. Terdapat array satu dimensi dan array dua dimensi yang memiliki fungsi berbeda.
Array adalah tipe data yang terstruktur, gunanya untuk menyimpan data-data dengan tipe serupa. Array memiliki banyak variabel dalam strukturnya, namun dengan tipe data yang sama. Masing-masing variabel dalam array memiliki nilai indeks.
Kita dapat mengakses data dalam array melalui nomor indeks tertentu. Nomor indeks ini dimulai dari 0, untuk mengaksesnya harus menggunakan proses looping.
Linked list adalah struktur data yang terdiri dari urutan record data. Setiap record dalam linked list memiliki field masing-masing untuk menyimpan alamat atau referensi dari record selanjutnya. Dalam linked list, elemen data ini disebut node. Dalam linked list ada juga istilah head dan tail. Head adalah elemen yang berada di posisi pertama linked list. Tail adalah elemen terakhir dalam sebuah linked list.
