Mengenal Linked List

Definisi Linked List

Linked List adalah struktur data linear yang terdiri dari elemen-elemen yang disebut node. Setiap node memiliki dua bagian utama:

1. Data – menyimpan nilai elemen.

2. Pointer/Referensi – menunjuk ke node berikutnya (atau sebelumnya pada Doubly Linked List).

Perbedaan Linked List dan Array

Aspek	Array	Linked List
Penyimpanan	Elemen disimpan secara bersebelahan dalam memori.	Node disimpan tersebar di memori dan dihubungkan oleh pointer.
Akses Elemen	Akses langsung menggunakan indeks, kompleksitas O(1).	Akses harus dilakukan dengan traversal dari awal, kompleksitas O(n).
Ukuran	Bersifat statis, ukuran ditentukan saat deklarasi.	Bersifat dinamis, dapat bertambah/berkurang sesuai kebutuhan.
Insert/Delete	Mahal karena perlu menggeser elemen, kompleksitas O(n).	Lebih efisien karena hanya mengubah pointer, kompleksitas O(1) jika posisi diketahui.

Manfaat Linked List

1. Ukuran Dinamis

   • Tidak perlu menentukan ukuran di awal seperti pada array.

   • Dapat bertambah atau berkurang sesuai kebutuhan program.

2. Efisiensi pada Operasi Insert/Delete

   • Menambahkan atau menghapus elemen tidak memerlukan pergeseran data.

   • Kompleksitas dapat menjadi O(1) jika pointer sudah diketahui.

3. Memanfaatkan Memori Secara Lebih Fleksibel

   • Node dapat disimpan di lokasi memori yang tersebar.

   • Berguna pada sistem dengan memori yang terfragmentasi.

4. Dukungan untuk Struktur Data Kompleks

   • Menjadi dasar untuk struktur data lain seperti Stack, Queue, Deque, dan Graph.

   • Memungkinkan pembuatan varian seperti Circular Linked List dan Doubly Linked List.

5. Traversal Dua Arah (pada Doubly Linked List)

   • Memudahkan navigasi ke depan maupun ke belakang dalam list.

Contoh Kode Singkat

#include <iostream>
using namespace std;

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

void pushFront(Node*& head, int value) {
    Node* newNode = new Node(); // Buat node baru
    newNode->data = value;      // Isi data
    newNode->next = head;       // Hubungkan ke head lama
    head = newNode;             // Jadikan node baru sebagai head
}

void printList(Node* head) {
    Node* current = head;
    while (current != nullptr) {
        cout << current->data << " -> ";
        current = current->next;
    }
    cout << "NULL\n";
}

int main() {
    Node* head = nullptr;  // List kosong

    pushFront(head, 10);
    pushFront(head, 20);
    pushFront(head, 30);

    printList(head); // Output: 30 -> 20 -> 10 -> NULL

    return 0;
}

Penjelasan Kode:

• Node adalah struktur dasar Linked List.

• pushFront menambahkan node baru di awal list.

• printList menelusuri list dan menampilkan semua elemen.