Linked List

Linked List

• Pengertian Linked List

Senarai berantai (bahasa Inggris: linked list) atau kadang-kadang disebut dengan senarai bertaut atau daftar bertaut dalam ilmu komputer merupakan sebuah struktur data yang digunakan untuk menyimpan sejumlah objek data biasanya secara terurut sehingga memungkinkan penambahan, pengurangan, dan pencarian atas elemen data yang tersimpan dalam senarai dilakukan secara lebih efektif. Pada praktiknya sebuah struktur data memiliki elemen yang digunakan untuk saling menyimpan rujukan antara satu dengan lainnya sehingga membentuk sebuah senarai abstrak, tiap-tiap elemen yang terdapat pada senarai abstrak ini seringkali disebut sebagai node. karena mekanisme rujukan yang saling terkait inilah disebut sebagai senarai berantai.

Sebuah senarai berantai dengan tiap-tiap node yang terdiri atas dua elemen, data integer, dan elemen rujukan ke node berikutnya

Senarai berantai merupakan bentuk struktur data paling umum dan sederhana yang banyak digunakan untuk mengimplementasikan model struktur data lainnya, termasuk antrian, stack, ataupun larik assosiatif.

• Keuntungan dan Kerugian Linked List

Keuntungan utama pemanfaatan senarai berantai dibandingkan larik, ataupun senarai biasa adalah kemudahan dan efektifitas kerja yang lebih baik dalam hal menambah, mengurangi, serta mencari suatu elemen/node yang terdapat dalam senarai. Hal tersebut dimungkinkan karena elemen-elemen yang terdapat pada sebuah senarai berantai tidak ditempatkan pada sebuah blok memori komputer seperti halnya larik ataupun senarai biasa, melainkan tiap-tiap elemen/node tersebut tersimpan dalam blok memori terpisah, penambahan, pengurangan, ataupun penggantian node dapat dilakukan dengan mengubah elemen rujukan atas tiap-tiap node yang terkait. Kerugiannya, sebuah senarai berantai tidak memungkinkan pengaksesan elemen secara acak, dalam artian untuk dapat mengakses node ke tiga pada contoh di atas harus dilakukan dengan cara mengunjungi elemen-elemen sebelumnya, dimulai dari elemen pertama, ke dua, seterusnya hingga pada lokasi elemen yang dimaksudkan.

• Jenis-Jenis Linked List

1. Senarai tunggal

Bila struktur data sebuah node hanya memiliki satu tautan atas node berikutnya dalam sebuah senarai, maka senarai tersebut dinamakan sebagai senarai tunggal.

Senarai tunggal dengan tiap-tiap node yang terdiri atas dua elemen, data integer, dan elemen rujukan ke node berikutnya.

2. Senarai ganda

Berbeda halnya dengan senarai tunggal, pada senarai ganda, struktur data atas tiap-tiap node memiliki rujukan pada node sebelum dan berikutnya. Sebagian algoritme membutuhkan taut ganda, contohnya sorting dan reverse traversing.

Senarai ganda dengan tiap-tiap node yang terdiri atas tiga elemen, data integer, dan dua elemen rujukan ke node sebelum serta berikutnya.

3. Senarai sirkuler

Pada dua jenis senarai sebelumnya, node terakhir dalam senarai tersebut merujuk pada null yang artinya akhir dari sebuah senarai, begitu pula null sebagai rujukan node sebelumnya pada node pertama bila senarai yang dimaksudkan adalah senarai ganda. Pada senarai sirkuler, informasi rujukan pada node terakhir akan merujuk pada node pertama, dan rujukan pada node pertama akan merujuk pada node terakhir bila yang digunakan sebagai dasar implementasi adalah senarai ganda.

Senarai sirkuler dengan menggunakan model implementasi senarai tungal. Node terakhir menyimpan rujukan pada node pertama

Konstruktor untuk Java LinkedList:

LinkedList ()                      : Digunakan untuk membuat daftar tertaut yang kosong.
LinkedList (Collection C): Digunakan untuk membuat daftar pesanan yang berisi semua elemen koleksi tertentu, sebagaimana dikembalikan oleh iterator koleksi.

// Java code for Linked List implementation

import java.util.*;

public class Test
{
public static void main(String args[])
{
// Creating object of class linked list
LinkedList<String> object = new LinkedList<String>();

// Adding elements to the linked list
object.add("A");
object.add("B");
object.addLast("C");
object.addFirst("D");
object.add(2, "E");
object.add("F");
object.add("G");
System.out.println("Linked list : " + object);

// Removing elements from the linked list
object.remove("B");
object.remove(3);
object.removeFirst();
object.removeLast();
System.out.println("Linked list after deletion: " + object);

// Finding elements in the linked list
boolean status = object.contains("E");

if(status)
System.out.println("List contains the element 'E' ");
else
System.out.println("List doesn't contain the element 'E'");

// Number of elements in the linked list
int size = object.size();
System.out.println("Size of linked list = " + size);

// Get and set elements from linked list
Object element = object.get(2);
System.out.println("Element returned by get() : " + element);
object.set(2, "Y");
System.out.println("Linked list after change : " + object);
}
}

Output:

Linked list : [D, A, E, B, C, F, G]
Linked list after deletion: [A, E, F]
List contains the element 'E' 
Size of linked list = 3
Element returned by get() : F
Linked list after change : [A, E, Y]

Method untuk Java LinkedList:

1. add (int index, E element): Metode ini Menyisipkan elemen yang ditentukan pada posisi yang ditentukan dalam daftar ini.
2. add (E): Metode ini Menambahkan elemen yang ditentukan ke akhir daftar ini.
3. addAll (int index, Collection c): Metode ini Menyisipkan semua elemen dalam koleksi yang ditentukan ke dalam daftar ini, mulai dari posisi yang ditentukan.
4. addAll (Collection c): Metode ini Menambahkan semua elemen dalam koleksi yang ditentukan ke bagian akhir daftar ini, dalam urutan yang dikembalikan oleh iterator koleksi yang ditentukan.
5. addFirst (E e): Metode ini Menyisipkan elemen yang ditentukan di awal daftar ini.
6. addLast (E e): Metode ini Menambahkan elemen yang ditentukan ke akhir daftar ini.
7. clear (): Metode ini menghapus semua elemen dari daftar ini.
8. clone (): Metode ini mengembalikan salinan dangkal LinkedList ini.
9. contains (Object o): Metode ini mengembalikan true jika daftar ini mengandung elemen yang ditentukan.
10. descendingIterator (): Metode ini mengembalikan iterator atas elemen-elemen dalam deque ini dalam urutan berurutan terbalik.
11. element (): Metode ini mengambil, tetapi tidak menghapus, kepala (elemen pertama) dari daftar ini.
12. get (int index): Metode ini mengembalikan elemen pada posisi yang ditentukan dalam daftar ini.
13. getFirst (): Metode ini mengembalikan elemen pertama dalam daftar ini.
14. getLast (): Metode ini mengembalikan elemen terakhir dalam daftar ini.
15. indexOf (Object o): Metode ini mengembalikan indeks dari kemunculan pertama dari elemen yang ditentukan dalam daftar ini, atau -1 jika daftar ini tidak mengandung elemen.
16. lastIndexOf (Object o): Metode ini mengembalikan indeks kejadian terakhir dari elemen yang ditentukan dalam daftar ini, atau -1 jika daftar ini tidak mengandung elemen.
17. listIterator (int index): Metode ini mengembalikan daftar-iterator dari elemen dalam daftar ini (dalam urutan yang benar), mulai dari posisi yang ditentukan dalam daftar.
18. offer (E): Metode ini Menambahkan elemen yang ditentukan sebagai ekor (elemen terakhir) dari daftar ini.
19. offerFirst (E e): Metode ini Menyisipkan elemen yang ditentukan di bagian depan daftar ini.
20. offerLast (E e): Metode ini Menyisipkan elemen yang ditentukan di akhir daftar ini.
21. peek (): Metode ini mengambil, tetapi tidak menghapus, kepala (elemen pertama) dari daftar ini.
22. peekFirst (): Metode ini mengambil, tetapi tidak menghapus, elemen pertama dari daftar ini, atau mengembalikan null jika daftar ini kosong.
23. peekLast (): Metode ini mengambil, tetapi tidak menghapus, elemen terakhir dari daftar ini, atau mengembalikan null jika daftar ini kosong.
24. jajak pendapat (): Metode ini mengambil dan menghapus kepala (elemen pertama) dari daftar ini.
25. pollFirst (): Metode ini mengambil dan menghapus elemen pertama dari daftar ini, atau mengembalikan null jika daftar ini kosong.
26. pollLast (): Metode ini mengambil dan menghapus elemen terakhir dari daftar ini, atau mengembalikan null jika daftar ini kosong.
27. pop (): Metode ini Muncul elemen dari tumpukan diwakili oleh daftar ini.
28. push (E): Metode ini Mendorong elemen ke tumpukan yang diwakili oleh daftar ini.
29. remove (): Metode ini mengambil dan menghapus head (elemen pertama) dari daftar ini.
30. remove (int index): Metode ini menghilangkan elemen pada posisi yang ditentukan dalam daftar ini.
31. remove (Object o): Metode ini menghilangkan kemunculan pertama dari elemen yang ditentukan dari daftar ini, jika ada.
32. removeFirst (): Metode ini menghapus dan mengembalikan elemen pertama dari daftar ini.
33. removeFirstOccurrence (Object o): Metode ini menghilangkan kemunculan pertama dari elemen yang ditentukan dalam daftar ini (ketika melintasi daftar dari kepala ke ekor).
34. removeLast (): Metode ini menghapus dan mengembalikan elemen terakhir dari daftar ini.
35. removeLastOccurrence (Object o): Metode ini menghilangkan kemunculan terakhir dari elemen yang ditentukan dalam daftar ini (ketika melintasi daftar dari kepala ke ekor).
36. set (int index, E element): Metode ini menggantikan elemen pada posisi yang ditentukan dalam daftar ini dengan elemen yang ditentukan.
37. size (): Metode ini mengembalikan jumlah elemen dalam daftar ini.
38. spliterator (): Metode ini Membuat Spliterator yang mengikat dan gagal-cepat atas elemen-elemen dalam daftar ini.
39. toArray (): Metode ini mengembalikan array yang berisi semua elemen dalam daftar ini dalam urutan yang tepat (dari elemen pertama hingga terakhir).
40. toArray (T [] a): Metode ini mengembalikan array yang berisi semua elemen dalam daftar ini dalam urutan yang tepat (dari elemen pertama hingga terakhir); jenis runtime dari array yang dikembalikan adalah array yang ditentukan.

Nah untuk mengetahui secara lengkap bagaimana kerja Linked list dapat dilihat di video bawah ini:

setelah mengetahui cara kerja pada linked list ada contoh program yang dapat di download di link: https://ideone.com/m6cNvn
dan penjelasan mengenai linked list dari Blog lain dapat di akses di:
1. http://arliansyahazhary.blogspot.com/2015/06/struktur-data-singly-linked-list.html
2. https://study.cs50.net/linked_lists

Daftar Isi:
Parlante, Nick (2001). "Linked list basics" (PDF). Stanford University. Diakses tanggal 2009-09-21.
https://www.geeksforgeeks.org/data-structures/linked-list/ 
https://www.geeksforgeeks.org/linked-list-in-java/
https://medium.com/codelabs-unikom/struktur-data-single-linked-list-93bbd56b6ed1