Linked List

Apa itu Linked List?

Linked list adalah struktur data yang digunakan dalam pemrograman komputer untuk menyimpan koleksi data. Dalam linked list, setiap elemen disebut node dan berisi dua bidang: bidang data dan bidang pointer yang menunjuk ke node berikutnya dalam daftar. Node pertama dalam daftar disebut head, dan node terakhir dalam daftar memiliki pointer null.

Dalam bahasa C, linked list diimplementasikan menggunakan struktur dan pointer. Setiap node dalam daftar direpresentasikan oleh sebuah struktur yang berisi data dan pointer ke node berikutnya. Daftar dijaga menggunakan pointer ke head dari daftar.

Linked list berguna ketika ukuran daftar tidak diketahui sebelumnya atau ketika elemen perlu dimasukkan atau dihapus secara sering. Namun, linked list memerlukan lebih banyak overhead memori daripada array dan dapat lebih lambat untuk dilintasi.

Notes

• Tidak seperti array, linked list tidak memiliki ukuran tetap dan dapat bertambah atau berkurang secara dinamis selama runtime.
• Setiap node dalam linked list berisi elemen data dan pointer ke node berikutnya dalam daftar. Node terakhir dalam daftar memiliki referensi null
• Linked list sering digunakan ketika ukuran data yang disimpan tidak diketahui sebelumnya, atau ketika sering terjadi penghapusan dan penambahan elemen.
• Mengakses elemen dalam linked list memerlukan penelusuran daftar dari awal hingga node yang diinginkan, yang dapat kurang efisien daripada mengakses elemen dalam array.
• Linked list dapat digunakan untuk mengimplementasikan berbagai struktur data, seperti stack, queue, dan hash table

Ilustrasi

Berikut adalah contoh visualisasi dari linked list, dimana blok pertama disebut head, dan blok terakhir menunjuk pada ketiadaan (NULL).

Jika kita melihat bagian terkecil dari sebuah linked list adalah node, berisi value dan alamat node berikutnya.

Jika kita menambahkan node sebelumnya pada ilustrasi pertama, maka linked list kita akan menjadi,

Terakhir, jika kita menghapus elemen pada linked list maka alamat selanjutnya akan menunjuk pada elemen setelah yang dihapus, ( * jika elemen terakhir yang dihapus maka tetap menunjuk ke NULL)

Implementasi

#include <stdio.h>
#include <stdlib.h>

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

void insert(struct Node** head_ref, int data) {
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

void delete(struct Node** head_ref, int key) {
    struct Node* temp = *head_ref;
    struct Node* prev = NULL;

    if (temp != NULL && temp->data == key) {
        *head_ref = temp->next;
        free(temp);
        return;
    }

    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) return;

    prev->next = temp->next;
    free(temp);
}

void search(struct Node* head, int key) {
    struct Node* temp = head;

    while (temp != NULL) {
        if (temp->data == key) {
            printf("\n%d found in the linked list.\n", key);
            return;
        }
        temp = temp->next;
    }

    printf("%d not found in the linked list.\n", key);
}

void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
}

int main() {
    struct Node* head = NULL;

    insert(&head, 3);
    insert(&head, 4);
    insert(&head, 5);
    insert(&head, 6);

    printf("Original linked list: ");
    printList(head);

    delete(&head, 5);
    printf("\nLinked list after deleting 5: ");
    printList(head);

    search(head, 4);
    search(head, 5);

    return 0;
}

Output

Original linked list: 6 5 4 3
Linked list after deleting 5: 6 4 3
4 found in the linked list.
5 not found in the linked list.