Pertemuan 5 - Variasi linked list

 Pertemuan 5 - Variasi linked list

Linked List adalah salah satu struktur data linear yang terdiri dari sekumpulan node yang terhubung satu sama lain secara dinamis. Setiap node dalam linked list memiliki dua bagian utama:

  • Data: Menyimpan nilai atau informasi.

  • Pointer (Next): Menunjuk ke node berikutnya dalam list.

Tidak seperti array yang menggunakan indeks untuk mengakses elemen, linked list menggunakan pointer untuk menghubungkan elemen-elemen yang tersebar di memori.

2. Jenis-jenis Linked List

  1. Singly Linked List: Setiap node memiliki satu pointer yang menunjuk ke node berikutnya.

  2. Doubly Linked List: Setiap node memiliki dua pointer, satu menunjuk ke node sebelumnya dan satu ke node berikutnya.

  3. Circular Linked List: Node terakhir terhubung kembali ke node pertama, membentuk siklus.

  4. Multi-Level Linked List: Setiap node dapat memiliki lebih dari satu pointer ke node lain, sering digunakan dalam struktur seperti skip list.

  5. Skip List: Sebuah variasi dari linked list yang memiliki beberapa tingkat referensi untuk mempercepat pencarian.

  6. Self-Organizing Linked List: Linked list yang mengatur ulang dirinya sendiri berdasarkan frekuensi akses untuk meningkatkan efisiensi pencarian.

3. Struktur Node dalam Linked List (C++)

Berikut adalah contoh struktur dasar dari sebuah node dalam singly linked list:

#include <iostream>
using namespace std;

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

4. Operasi Dasar pada Linked List

a. Menambahkan Node di Awal

void insertAtHead(Node*& head, int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = head;
    head = newNode;
}

b. Menambahkan Node di Akhir

void insertAtTail(Node*& head, int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = nullptr;
    
    if (head == nullptr) {
        head = newNode;
        return;
    }
    
    Node* temp = head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }
    temp->next = newNode;
}

c. Menghapus Node

void deleteNode(Node*& head, int key) {
    Node* temp = head;
    Node* prev = nullptr;
    
    if (temp != nullptr && temp->data == key) {
        head = temp->next;
        delete temp;
        return;
    }
    
    while (temp != nullptr && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    
    if (temp == nullptr) return;
    prev->next = temp->next;
    delete temp;
}

d. Menampilkan Isi Linked List

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

5. Kelebihan dan Kekurangan Linked List

Kelebihan:

  • Ukuran Dinamis: Tidak perlu menentukan ukuran tetap saat deklarasi.

  • Efisien dalam Penyisipan dan Penghapusan: Tidak perlu menggeser elemen seperti pada array.

Kekurangan:

  • Akses Tidak Langsung: Harus menelusuri dari awal untuk mengakses elemen tertentu.

  • Memerlukan Memori Tambahan: Setiap node menyimpan pointer tambahan.

6. Kesimpulan

Linked List adalah struktur data fleksibel yang memungkinkan penyisipan dan penghapusan elemen dengan efisien. Namun, penggunaan memori tambahan untuk pointer serta akses yang tidak langsung menjadi tantangan dalam implementasi. Pemahaman tentang operasi dasar dan variasi linked list akan membantu dalam pemecahan masalah berbasis struktur data secara lebih optimal.