Data Structure — Linked List

Diharapkan setidaknya pernah mengimplementasikan array, linked list adalah struktur data linear. Bedanya dengan array, element dari linked list tidak di-store di lokasi yang berdekatan, sebaliknya, setiap elementnya dihubungkan menggunakan pointer.

Lalu, kenapa harus menggunakan linked list? Sebenarnya array dapat digunakan, tetapi ada limit-limit tertentu:

• Ukuran array statis, dalam artian kita harus mengetahui batas dari jumlah elemennya dulu sewaktu kita mengalokasikannya.
• Memasukkan elemen baru ke dalam array juga membutuhkan tenaga lagi, karena harus mmebuat ruangan baru. Maka ketika mmebuat ruangan ini, berarti elemen yang sudah ada terpaksa harus digeser.

Beda halnya dengan linked list, kalau kita punya simpul kepala (head node), maka kita dapat jalan ke elemen mana saja yang ada di dalam linked list itu, dan kita bisa memasukkan elemen baru di posisi yang kita perlukan.

Asumsikan kita punya array berikut :

array[] = [1,3,5,7]

Kalau kita ingin memasukkan list baru (katakanlah angka 2)dan dengan mempertahankan urutan yang ada, kita harus memindahkan semua elemen yang ada setelah angka 1.

Nah kali ini kita akan melihat sisi keuntungan dari penggunaan linked-list :

• Ukuran yang dinamis (Paling kritikal)
• Mudah untuk diedit, dalam artian untuk memasukkan data baru ataupun menghapus data baru.

Kekurangannya ada beberapa, mari kita ulik lagi :

• Akses secara random tidak bisa, karena sejak awal linked list dibuat adalah model terurut dari head node-nya. Pastinya tidak bisa melakukan pencarian secara biner.
• Penggunaan space memori ekstra, ini diperlukan untuk setiap elemen, karena kita memerlukan space untuk element, dan juga untuk si pointer.

Perlu diingat, setiap node dari linked-list terdiri minimal dari 2 bagian, yakni si data sendiri (sudah tidak perlu dijelaskan, isinya tergantung developer) dan pointer(referensi ke node berikutnya). Saya akan membawa bahasa C untuk merepresentasikannya menggunakan bahasa C.

Berikut adalah representasi dari node.

struct Node {
  int data;
  struct Node* next;
};

Node ini begitu sederhana (bahkan bukan program), mari kita coba program lengkap dari sebuah linked list yang berisi 3 node.

#include <stdio.h>
#include <stdlib.h>
  
struct Node {
  int data;
  struct Node* next;
};
int main(){
  struct Node* head = NULL;
  struct Node* second = NULL;
  struct Node* third = NULL;
  
  //  Di sini, kita mengalokasikan node sebanyak 3
  head = (struct Node*)malloc(sizeof(struct Node));
  second = (struct Node*)malloc(sizeof(struct Node));
  third = (struct Node*)malloc(sizeof(struct Node));
  
  
  head->data = 1; // Masukkan datanya (kebetulan berupa int)
  head->next = second; // Sambungkan dengan node ke dua
  
  second->data = 2; // Hal yang sama terjadi dengan node pertama
  second->next = third;
  
  third->data = 3;
  third->next = NULL;
  
  return 0;
}
// Prosedur yang dibuat untuk mencetak semua elemen dari linked list
void printList(struct Node* n){
  while (n != NULL) {
    printf(" %d ", n->data);
    n = n->next;
  }
}

Sekian, semoga ilmu simpelnya bermanfaat

Cheers :) !