Linked list

PENGERTIAN   

    Linked List atau Single Linked List merupakan suatu bentuk struktur data yang berisi kumpulan data yang disebut sebagai node yang tersusun secara sekuensial, saling sambung menyambung, dinamis, dan terbatas. Linked List adalah struktur berupa rangkaian elemen saling berkait dimana tiap elemen dihubungkan ke elemen yang lain melalui pointer. Pointer adalah alamat elemen. Penggunaan pointer untuk mengacu elemen berakibat elemen-elemen bersebelahan secara logika walaupun tidak bersebelahan secara fisik di memori. Linked List digunakan untuk strukturisasi data, fungsinya hampir sama dengan ArrayList.

FUNGSI-FUNGSI LINKED-LIST

Berikut adalah beberapa fungsi dasar yang biasanya diimplementasikan dalam linked list pada C++:

1. Menambahkan Elemen (Insertion):

• Di awal (push_front): Menambahkan elemen baru di awal linked list.
• Di akhir (push_back): Menambahkan elemen baru di akhir linked list.
• Di posisi tertentu: Menambahkan elemen baru di posisi tertentu dalam linked list.

2. Menghapus Elemen (Deletion):

• Di awal (pop_front): Menghapus elemen pertama dari linked list.
• Di akhir (pop_back): Menghapus elemen terakhir dari linked list.
• Di posisi tertentu: Menghapus elemen di posisi tertentu dalam linked list.

3. Pencarian (Search):

• Mencari elemen dalam linked list dan mengembalikan apakah elemen tersebut ditemukan atau tidak.

4. Traversing (Traversal):

• Mengunjungi setiap elemen dalam linked list untuk tujuan tertentu, misalnya mencetak nilai setiap elemen.

5. Mendapatkan Panjang (Size):

• Menghitung jumlah elemen dalam linked list.

PENERAPAN LINKED LIST

Penerapan linked list banyak ditemui dalam beberapa kasus berikut:

• Linked list digunakan dalam penjadwalan Round-Robin untuk melacak giliran dalam permainan multi-pemain.

• Digunakan dalam aplikasi penampil gambar. Gambar sebelumnya dan berikutnya ditautkan, sehingga dapat diakses oleh tombol prev dan next.

• Dalam playlist musik, lagu yang sedang diputar ditautkan ke lagu sebelumnya dan berikutnya.

KELEBIHAN LINKED LIST

• Struktur data dinamis: Linked list adalah himpunan dinamis sehingga dapat bertambah dan menyusut saat runtime dengan mengalokasikan dan membatalkan alokasi memori. Jadi kita tidak perlu memberikan ukuran awal dari linked list.

• Tidak boros memori: Dalam linked list, pemanfaatan memori yang efisien dapat dicapai karena ukuran linked list bertambah atau berkurang pada runtime sehingga tidak ada pemborosan memori dan tidak perlu mengalokasikan memori sebelumnya.

• Implementasi: Struktur data linier seperti stack dan queue seringkali mudah diimplementasikan menggunakan linked list.

• Operasi penyisipan dan penghapusan: Operasi penyisipan dan penghapusan cukup mudah dalam linked list. Kita tidak perlu menggeser elemen setelah operasi penyisipan atau penghapusan elemen, hanya alamat yang ada di pointer berikutnya saja yang perlu diperbarui.

KELEMAHAN LINKED LIST

• Penggunaan memori: Linked list memerlukan lebih banyak memori dibandingkan dengan array. Karena dalam linked list, pointer juga perlu menyimpan alamat elemen berikutnya dan membutuhkan memori tambahan untuk dirinya sendiri.

• Traversal: Dalam traversal, linked list lebih banyak memakan waktu dibandingkan dengan array. Akses langsung ke elemen tidak bisa dilakukan pada linked list seperti array yang dapat akses elemen berdasarkan indeks. Untuk mengakses sebuah simpul pada posisi n dari linked list, kita harus melintasi semua simpul sebelumnya.

• Reverse Traversing: Dalam single linked list, reverse traversing tidak dimungkinkan, tetapi dalam kasus double-linked list, ini dapat dimungkinkan karena berisi pointer ke node yang terhubung sebelumnya dengan setiap node. Untuk melakukannya, diperlukan memori tambahan untuk pointer sebelumnya sehingga ada pemborosan memori.

    

    Linked-List dapat diilustrasikan seperti kereta api, dimana kereta api terdiri dari gerbong-gerbong yang saling terhubung yang dapat mengangkut penumpang (Data). Gerbong (Node/Simpul) disini berfungsi untuk menyimpan data. Misalnya jika kita menyimpan data 89, 12, 40 dan 24 dalam Array, contoh gambar konsep dari Single LinkedList seperti berikut ini:

    Setiap Node pada LinkedList mempunyai field yang berisi Pointer yang menghubungkan kenode berikutnya dan juga memiliki field yang berisi Data. Akhir dari LinkedList ditandai dengan Node terakhir akan menunjuk ke Null yang akan digunakan sebagai kondisi berhenti pada LingkedList.

JENIS LINKED LIST

1. Single Linked List:

Sebuah linked list yang hanya memiliki 1 penghubung ke node lain disebut sebagai single linked list.

2. Doubly Linked List (Linked List Ganda)

Dalam doubly linked list, setiap node memiliki dua pointer: satu menunjuk ke node berikutnya dan satu lagi menunjuk ke node sebelumnya. Ini memungkinkan traversal di kedua arah (ke depan dan ke belakang).

3. Circular Linked List (Linked List Sirkuler)

Circular linked list adalah varian di mana node terakhir menunjuk kembali ke node pertama, membentuk lingkaran. Ini dapat diterapkan pada singly atau doubly linked list.

OPERASI DALAM LINKED LIST

1. PUSH

    Push merupakan sebuah operasi insert dimana di dalam linked list terdapat 2 kemungkinan insert, yaitu insert melalui depan (pushDepan) ataupun belakang (pushBelakang). Operasi pushDepan berarti data yang paling baru dimasukkan akan berada di depan data lainnya, dan sebaliknya pushBelakang berarti data yang paling baru akan berada di belakang data lainnya.

Representasinya adalah sebagai berikut:

• pushDepan: 5, 3, 7, 9 maka hasilnya adalah: 9 ->7 ->3 -> 5 -> NULL
• pushBelakang: 5, 3, 7, 9 maka hasilnya adalah: 5 ->3 ->7 ->9 -> NULL

2. POP

    Pop, kebalikan dari push, merupakan operasi delete, dimana di dalam linked list memiliki 2

kemungkinan delete, yaitu melalui depan (popDepan) dan melalui belakang (popBelakang). PopDepan berarti data yang akan dihapus adalah data paling depan, dan popBelakang berarti data yang akan dihapus adalah data paling belakang (akhir).

Representasinya adalah sebagai berikut:

• popDepan: 5, 3, 7, 9 maka hasilnya adalah: 3, 7, 9 , NULL
• popBelakang: 5, 3, 7, 9 maka hasilnya adalah: 5 ->3 ->7 -> NULL

Pergi ke materi  Stack C++ >>