Single Linked List

Motivasi: Array vs Linked List

Bayangkan Anda sedang menyusun kursi untuk tamu. Menggunakan Array ibarat menyewa bus: jumlah kursinya sudah tetap. Jika tamu yang datang lebih banyak, Anda harus menyewa bus baru yang lebih besar dan memindahkan semua orang — ini repot dan memakan waktu.

Dalam kenyataannya, jumlah data seringkali tidak pasti. Di sinilah Linked List hadir sebagai solusi.

Linked List ibarat rangkaian gerbong kereta api. Jika ada tamu tambahan, Anda cukup menambah gerbong baru di belakang. Jika ada yang turun, Anda tinggal melepas gerbongnya. Proses ini jauh lebih cepat dan efisien. Dua alasan utama memakai Linked List adalah ukurannya yang fleksibel dan kemudahan dalam menambah atau menghapus data.

Konsep Inti & Anatomi Node

Single Linked List adalah rangkaian elemen yang disebut Node. Setiap Node menyimpan dua hal:

1. Info: Berisi nilai atau data aslinya.
2. Next: Berisi alamat (pointer) ke elemen berikutnya.

Sebuah list harus punya "kepala" (First) agar kita tahu di mana mulainya. Jika First bernilai NULL, berarti list kosong. Elemen terakhir ditandai dengan Next yang menunjuk ke NULL.

Perhatikan gambaran berikut:

Hands-On: Menambah Data di Awal (Insert First)

Operasi InsertFirst bertujuan untuk memasukkan node baru langsung di posisi pertama.

void InsertFirst(List *L, int x) {
  // 1. Buat gerbong baru
  Node *NewElmt = Allocation(x);

  // 2. Sambungkan gerbong baru ke gerbong pertama yang lama
  NewElmt->next = L->first;

  // 3. Jadikan gerbong baru sebagai yang pertama
  L->first = NewElmt;
}

Mengakses data (Traversal)

Karena memori Linked List tersebar, kita tidak bisa langsung loncat ke urutan tertentu. Kita harus menelusurinya dari First satu per satu menggunakan bantuan pointer sementara (temp).

void PrintInfo(List L) {
  Node *temp = L.first;         // Mulai dari awal (First)

  while (temp != NULL) {        // Selama belum sampai ujung
    cout << temp->info << " ";  // Cetak isinya
    temp = temp->next;          // Pindah ke gerbong berikutnya
  }
}

Ringkasan

• Linked List adalah kumpulan node yang saling terhubung memakai pointer.
• Node terdiri dari data (info) dan alamat node berikutnya (next).
• Sangat efisien untuk data yang sering ditambah atau dihapus secara dinamis.
• Penelusuran data dilakukan dari awal hingga menemukan NULL.

Latihan

Silakan coba buat fungsi untuk menambah data di akhir list atau menghapus data tertentu untuk memperdalam pemahaman Anda.