Memahami Linked List: Struktur Data yang Efisien dan Fleksibel

Sebagai seorang mahasiswa yang gemar belajar tentang struktur data, saya sering kali menemukan istilah "Linked List". Bagi kalian yang mungkin belum begitu familiar, Linked List adalah salah satu struktur data yang sangat penting dalam dunia pemrograman. Mari kita bahas lebih dalam!

Linked List adalah struktur data linear yang terdiri dari sekumpulan node. Setiap node menyimpan data dan referensi (pointer) ke node berikutnya dalam urutan 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. 

Struktur Node

1. Data = Jika ada informasi atau nilai akan disimpan dalam node
2. Pointer = Menyimpan alamat memori node berikutnya (atau node sebelumnya untuk double linked list).

Linked List digunakan untuk strukturisasi data, fungsinya hampir sama dengan ArrayList. Akan tetapi Linked List tidak sama seperti ArrayList, Linked List tidak menggunakan lokasi memori yang bersebelahan untuk penyimpanannya, melainkan node-node yang terhubung melalui pointer.

Perbedaan Linked List dengan Array List

Fungsi Linked List 

Adapun fungsi dan kegunaan linked list adalah sebagai berikut:

➤Linked list dapat digunakan untuk mengimplementasikan struktur data lain seperti stack, queue, graf, dll.
➤Digunakan untuk melakukan operasi aritmatika pada bilangan long integer.
➤Dipakai untuk representasi matriks rongga.
➤Digunakan dalam alokasi file yang ditautkan.
➤Membantu dalam manajemen memori.

Kelebihan dan Kekurangan

Kelebihan :

  • Struktur Data Dinamis: Linked list dapat bertambah dan menyusut selama runtime tanpa memerlukan ukuran awal.
  • Efisien dalam Memori: Linked list memanfaatkan memori secara efisien karena ukurannya dapat berubah sesuai kebutuhan selama runtime.
  • Implementasi Mudah: Struktur data linier seperti stack dan queue sering diimplementasikan menggunakan linked list.
  • Operasi Penyisipan dan Penghapusan: Operasi penyisipan dan penghapusan pada linked list mudah dilakukan tanpa perlu menggeser elemen, hanya perlu memperbarui alamat di pointer berikutnya.

    • Kekurangan :

  • Penggunaan Memori: Linked list memerlukan lebih banyak memori dibandingkan array karena adanya pointer.
  • Traversal: Traversal pada linked list lebih lambat karena tidak ada akses langsung ke elemen.
  • Reverse Traversing: Reverse traversing tidak dimungkinkan pada single linked list, tetapi bisa dilakukan pada double-linked list dengan memori tambahan, menyebabkan pemborosan memori.

    • 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.

    Ilustrasi Linked List

    LinkList 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 55, 20, 99 dan 23 dalam Array, contoh gambar konsep dari Single LinkedList seperti berikut ini:

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

    Jenis-jenis Linked List

    1. Single Linked List

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

    Di dalam sebuah linked list, ada 1 pointer yang menjadi gambaran besar, yakni pointer HEAD yang menunjuk pada node pertama di dalam linked list itu sendiri. Sebuah linked list dikatakan kosong apabila isi pointer head adalah NULL.

    2. Double Linked List

    Double Linked List merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.

    3. Circular Linked List

    Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL. Ada 2 jenis Circular Linked List, yaitu :

    Operasi dalam Linked List

    ✿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.

    # contoh penerapannya 

    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

    ✿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).

    #contoh penerapannya

    popDepan: 5, 3, 7, 9 maka hasilnya adalah: 3 →7→9→ NULL
    popBelakang: 5, 3, 7, 9 maka hasilnya adalah: 5 →3→7→ NULL

    Contoh Program C++

    Menghasilkan Output