Langsung ke konten utama

Struktur Data: Linked List

Struktur Data: Linked List

Apa itu linked list? Linked list atau yang dalam bahasa Indonesia disebut dengan seranai berantai adalah suatu koleksi linear dari data, yang disebut sebagai nodes, dimana setiap node akan menunjuk pada node lain melalui sebuah pointer. Linked list merupakan sebuah struktur data yang mana dapat digunakan untuk mengimplementasikan struktur data lain seperti stack, queue, dan variasi lainnya.

Linked list memiliki variabel pointer START yang menyimpan alamat dari node pertama. Node pertama tersebut juga memiliki pointer yang menyimpan alamat dari node kedua dan seterusnya sampai ketemu alamat NULL (yang mana linked list akan berakhir).

Secara umum, teknik untuk mengimplementasikan linked list terdiri dari:
  • Push (Insert/tambah)
    • PushHead — menambah data ke barisan paling awal
    • PushTail — menambah data ke barisan paling akhir
    • PushMid — menambah data ke barisan di tengah
  • Pop (Delete/hapus)
    • PopHead — menghapus data di barisan paling awal
    • PopTail — menghapus data di barisan paling akhir
    • PopMid — menghapus data di barisan tengah

Jenis-Jenis Linked List

Linked list terdiri dari beberapa jenis, antara lain:
  1. Non-circular single linked list,
  2. Circular single linked list,
  3. Non-circular double linked list,
  4. Circular double linked list
Dalam postingan ini akan saya coba bahas satu persatu secara singkat jenis-jenis linked list diatas.

 1. Non-Circular Single Linked List

Bila struktur data dalam sebuah node hanya memiliki (menunjuk) satu tautan atas node berikutnya maka struktur data tersebut dinamakan sebagai single linked list. Linked list ini hanya bisa memiliki satu arah. 
 
Gambar 1 - Non-Circular Single Linked List

2. Circular Single Linked List

Circular single linked list merupakan sebuah struktur data yang terdiri dari node-node yang dibuat menggunakan tautan diri sendiri. Node terakhir dari linked list ini akan menunjuk kembali ke node pertama.

Gambar 2 - Circular Single Linked List

3. Double Linked List

Berbeda dengan single linked list, double linked list memiliki node yang terdiri dari dua buah data dan tautan yang menunjuk pada node sebelum dan sesudahnya. Maka dari itu, struktur data ini terdiri dari 3 bagian — data, pointer ke node selanjutnya, dan pointer ke node sebelumnya.

Gambar 3 - Non-Circular Double Linked List

4. Circular Double Linked List

Mirip dengan circular single linked list, linked list ini memiliki node dengan pointer yang menunjuk ke node sebelum dan sesudahnya secara bersamaan DAN tidak adanya NULL di sebelum node pertama dan setelah node terakhir.


Gambar 4 - Circular Double Linked List

 

Referensi

  • Thareja, Reema — Data Structures using C
  • PPT Linked List I — https://binusmaya.binus.ac.id/services/ci/index.php/student/classes/downloadResource/general_course_outline...course_outline...main_material/RS1...010544/20181210154455D4730_COMP6048%20-%2002%20-%20Linked%20List%20I%20(L)%20-%20R5%20-%20ok.pptx
  • PPT Linked List II — https://binusmaya.binus.ac.id/services/ci/index.php/student/classes/downloadResource/general_course_outline...course_outline...main_material/RS1...010544/20181210154552D4730_COMP6048%20-%2003%20-%20Linked%20List%20II%20(L)%20-%20R5%20-%20ok.pptx
  • https://id.wikipedia.org/wiki/Senarai_berantai
  • https://socs.binus.ac.id/2017/03/15/single-linked-list/
  • https://medium.com/codelabs-unikom/struktur-data-single-linked-list-93bbd56b6ed1
  • https://www.tutorialspoint.com/cplusplus-program-to-implement-circular-singly-linked-list
  • https://www.mahirkoding.com/struktur-data-single-linked-list-dengan-bahasa-c/
Label:

Komentar

Posting Komentar

Postingan populer dari blog ini

Struktur Data: Hash Table dan Binary Trees

Struktur Data: Hash Table dan Binary Trees Keduanya merupakan jenis-jenis struktur data yang dapat dibuat. Lalu, apa itu hash table dan binary trees ? 1. Hashing dan Hash Table Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data ( insertions ), penghapusan data ( deletions ), dan pencarian data ( searching ) relatif sama dibanding struktur data atau algoritma yang lain. Hash table menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. Pada intinya hash table merupakan penyimpanan data menggunakan key value yang didapat dari nilai data itu sendiri. Dengan key value tersebut didapat hash value . Jadi hash function merupakan suatu fungsi sederhana untuk mendapatkan
2 komentar
Baca selengkapnya

Struktur Data: Stack dan Queue

Struktur Data: Stack dan Queue Selain linked list , di dalam struktur data juga terdapat teknik lain. Antaranya adalah stack dan queue . Lalu, apa itu sebenarnya stack dan queue ? 1. Stack Stack , atau dalam Bahasa Indonesianya disebut tumpukan , merupakan salah satu teknik struktur data yang bersifat LIFO ( last in first out ). Data yang terakhir masuk ke stack merupakan data yang akan keluar pertama (namanya juga tumpukan). Misalnya terdapat data A, B, C, D, E, dan F. Jika urutan data yang masuk adalah A-B-C-D-E-F, maka untuk mengeluarkan data C, harus dilakukan pengeluaran data F-E-D terlebih dahulu. Algoritma Stack Seperti contoh yang telah dibahas di atas, algoritma dalam stack dilakukan dengan menguji apakah stack sudah penuh jika sedang memasukkan data ( push ). Jika sudah, maka data baru tidak dapat masuk. Jika belum, maka data yang terakhir dimasukkan merupakan data paling atas dari stack tersebut. Untuk mengeluarkan data ( pop ), maka dilakukan uji apaka
2 komentar
Baca selengkapnya

Struktur Data: AVL Tree

Struktur Data: AVL Tree Apa itu AVL Tree? AVL Tree merupakan sebuah BST yang bisa menyeimbangkan dirinya sendiri antara kanan dan kiri. Seimbang di sini maksudnya perbedaan panjang antara kaki kanan dan kaki kiri tree nya tidak lebih dari 1. Contoh gambarnya seperti ini: Nah bisa diliat dari contoh gambar di atas kalo panjang kaki kiri dan kanan nya sama (sejajar). Itu yang disebut AVL Tree. Nah kalo gambar yang itu bukan AVL, kenapa? Karena kaki kiri nya kepanjangan! Terus kalo gitu gimana caranya AVL menyeimbangkan dirinya sendiri? Hayo gimana, kepo ya? Jadi gini, si AVL itu bisa nyeimbangin dirinya sendiri dengan cara melakukan perputaran node di kaki yang terpanjang. Perputarannya sendiri terdiri dari 2 jenis, yaitu single rotation dan heavy double rotation . Single Rotation Single rotation akan dilakukan ketika kaki yang terpanjangnya memiliki arah yang lurus. Maksudnya gimana tuh? Jadi gini, liat gambar di bawah ini: Bisa diliat dari gambar di atas, ka
Posting Komentar
Baca selengkapnya