Skip to main content

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.

  1. Dynamic Memory Allocation

    • Used to keep track of free and allocated memory blocks.

  2. Undo/Redo Operations in Text Editors

    • Linked lists are used to store changes and navigate through editing history.

  3. Graph Representation

    • Implement adjacency lists efficiently in graph data structures.

  4. Implementation of Other Data Structures

    • Used as a base for stacks, queues, and deques.

Advantages of Linked List

  • Inserting and deleting nodes is efficient since no shifting of elements is required as in arrays.

  • Dynamic size allows growth or shrinkage at runtime.

  • Memory utilization is efficient; no pre-allocation means less wasted space.

  • Suitable for applications requiring large or frequently changing datasets.

  • Uses non-contiguous memory blocks, making it useful in memory-limited systems.

Disadvantages of Linked List

  • Direct access to an element is not possible; traversal is required from the start.

  • Each node requires extra memory to store a pointer.

  • More complex to implement and manage compared to arrays.

  • Pointer mismanagement can lead to bugs, memory leaks, or segmentation faults.

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.

Back to top