Penggunaan Linked List di C++

Linked List adalah salah satu struktur data yang sering digunakan dalam pemrograman untuk menyimpan data secara dinamis. Di C++, Linked List biasanya digunakan untuk membuat koleksi data yang ukurannya tidak diketahui pada saat kompilasi dan memungkinkan penyisipan serta penghapusan elemen dengan efisiensi tinggi.

Berikut penjelasan tentang Linked List dan contoh penggunaannya di C++.

Apa itu Linked List?

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

1. Data: Menyimpan nilai dari node.
2. Pointer (next): Menunjuk ke node berikutnya dalam daftar.

Linked List bisa terdiri dari beberapa jenis:

• Singly Linked List: Node hanya menunjuk ke node berikutnya.
• Doubly Linked List: Node memiliki pointer ke node sebelumnya dan berikutnya.
• Circular Linked List: Node terakhir menunjuk kembali ke node pertama.

Kelebihan Linked List

1. Dinamis: Ukurannya bisa bertambah atau berkurang secara dinamis tanpa perlu memesan memori sebelumnya.
2. Efisiensi dalam Penyisipan/Penghapusan: Operasi ini dapat dilakukan dengan efisiensi O(1) jika kita memiliki pointer ke node yang relevan.
3. Tidak Ada Pemborosan Memori: Tidak ada alokasi memori yang tidak digunakan seperti dalam array.

Kekurangan Linked List

1. Akses Acak Tidak Dimungkinkan: Untuk mengakses elemen tertentu, traversal dari awal diperlukan (O(n)).
2. Overhead Memori: Setiap node membutuhkan memori tambahan untuk pointer.
3. Kompleksitas Implementasi: Lebih sulit diimplementasikan dibanding array.

Contoh Implementasi Singly Linked List di C++

Berikut adalah contoh implementasi Singly Linked List sederhana:

#include <iostream>
using namespace std;

// Node structure
struct Node {
    int data;
    Node* next;

    Node(int value) {
        data = value;
        next = nullptr;
    }
};

// Linked List class
class LinkedList {
private:
    Node* head;

public:
    LinkedList() {
        head = nullptr;
    }

    // Add a node at the end
    void append(int value) {
        Node* newNode = new Node(value);
        if (head == nullptr) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
    }

    // Display the linked list
    void display() {
        Node* temp = head;
        while (temp != nullptr) {
            cout << temp->data << " -> ";
            temp = temp->next;
        }
        cout << "NULL" << endl;
    }

    // Delete a node by value
    void deleteByValue(int value) {
        if (head == nullptr) return;

        // If the head node is to be deleted
        if (head->data == value) {
            Node* temp = head;
            head = head->next;
            delete temp;
            return;
        }

        Node* temp = head;
        while (temp->next != nullptr && temp->next->data != value) {
            temp = temp->next;
        }

        if (temp->next == nullptr) return;

        Node* nodeToDelete = temp->next;
        temp->next = temp->next->next;
        delete nodeToDelete;
    }
};

int main() {
    LinkedList list;

    list.append(10);
    list.append(20);
    list.append(30);

    cout << "Linked List: ";
    list.display();

    list.deleteByValue(20);
    cout << "After deleting 20: ";
    list.display();

    return 0;
}

Penjelasan Kode

1. Node Structure: Struktur dasar node berisi data dan pointer next.
2. LinkedList Class: Mengelola operasi pada Linked List seperti menambahkan node (append), menampilkan elemen (display), dan menghapus elemen berdasarkan nilai (deleteByValue).
3. Main Function: Membuat instance LinkedList, menambahkan elemen, menampilkan elemen, dan menghapus elemen.

Variasi dan Pengembangan

• Implementasi Doubly Linked List untuk operasi dua arah.
• Membuat Linked List generik menggunakan template C++.
• Mengubah Linked List menjadi circular dengan menghubungkan node terakhir ke node pertama.

Jika Anda memiliki pertanyaan tambahan atau membutuhkan kode variasi lainnya, silakan beri tahu saya! 😊