Pertemuan 4 - Pengenalan Linked list

 Pertemuan 4 - Pengenalan 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.

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 linked list akan membantu dalam pemecahan masalah berbasis struktur data secara lebih optimal.