Struktur Data - Singly Linked List

Linked List adalah struktur data yang ukurannya dinamis, sedangkan Array adalah struktur data yang ukurannya statis(ukuran Array harus ditentukan). Pada Linked List tidak hanya terdapat data yang ingin kita simpan, tapi juga pointer untuk ke elemen selanjutnya. Karena itu, Linked List lebih banyak memakan memori dibandingkan dengan Array.

Bedanya dengan Array, kita tidak dapat mengambil data secara langsung, karena pada Linked List kita hanya mengetahui elemen pertama yang disebut dengan head, sedangkan pada Array kita dapat mengetahui semua elemen dengan menentukan indeksnya.

Cara mendefinisikan elemen pada Linked List yang menyimpan data berupa integer

typedef struct node
{
    // field untuk menyimpan integer
    int n;
    
    // pointer ke elemen selanjutnya
    struct node* next;
} node;

// elemen pertama pada linked list
node* head = NULL;

Tiap-tiap elemen pada Linked List disebut dengan Node. Program tidak akan mengenal definisi Node sampai baris node; tereksekusi dan itu menyebabkan program tidak mengenal pointer ke elemen selanjutnya karena bertipe Node. Untuk itu, perlu diberi nama Node juga pada baris typedef struct.

Untuk mencari sebuah elemen pada Linked List, terlebih dahulu deklarasi pointer pembantu untuk mengecek elemen satu per satu(yang ditandai dengan panah kuning pada gambar di bawah)

Misalnya kita ingin mencari angka 3, pointer pembantu akan mengecek satu per satu nilai-nilai pada elemen yang dilaluinya. Jika angka yang dicari sama dengan angka pada elemen yang ditunjuk pointer pembantu, maka ketemu(return true).

Fungsi pencarian pada Linked List

bool search(node* list, int value)
{
    // pointer pembantu start dari elemen pertama(list)
    node* current = list;
    
    // pointer pembantu akan melewati elemen pada linked list sampai ujung(NULL)
    while (current != NULL)
    {
        // nilai pada elemen yang ditunjuk pointer pembantu sama dengan nilai yang dicari
        if (current->n == value)
        {
            // ketemu
            return true;
        }
        else
        {
            // pergi ke elemen selanjutnya
            current = current->next;
        }
    }
    
    // pointer pembantu telah sampai di ujung list, berarti tidak ketemu
    return false;
}

Perlu diingat bahwa kita hanya mengetahui elemen pertama pada Linked List, karena itu kita hanya dapat mengetahui jumlah elemen pada Linked List ketika telah di-cek sampai ke ujung list. Hal ini menyebabkan kita tidak dapat menerapkan algoritma Binary Search pada Linked List. Algoritma yang dipakai adalah Linear Search.

Terdapat tiga skenario ketika ingin memasukkan angka pada Linked List, yaitu ingin memasukkan di awal, di ujung, maupun di antara elemen-elemen yang ada pada list.

Ketika ingin memasukkan elemen baru pada list, terlebih dahulu alokasikan memori untuk membuat Node baru yang ingin dimasukkan. Jika ingin memasukkan Node baru pada list, pertama-tama pointer pada Node baru tersebut harus menunjuk ke elemen selanjutnya, setelah itu kita ubah pointer pada elemen sebelumnya untuk menunjuk ke Node baru. Perlu kehati-hatian ketika mengubah pointer. Jika kita mengubah pointer pada elemen sebelumnya terlebih dahulu baru pointer pada Node baru, maka hal tersebut akan membuat elemen-elemen yang ditunjuk pointer sebelumnya akan menghilang. Misalnya ingin memasukkan angka 1, jika pointer head di ubah terlebih dahulu, maka angka 2, 3, dan 9 akan hilang.

Cara yang tidak benar dalam mengubah pointer

Untuk itu terlebih dahulu ubah pointer pada Node baru setelah itu pointer pada elemen sebelumnya.

Pertama-tama ubah dulu pointer pada Node baru untuk menunjuk ke elemen selanjutnya

Setelah itu ubah pointer pada head untuk menunjuk ke Node baru. Dengan cara ini kita tidak akan kehilangan satu elemen pun

Cara pointer pembantu berpindah dari satu elemen ke elemen selanjutnya

// pointer pembantu
previous = current;
// pointer pembantu pergi ke elemen selanjutnya
current = current->next;

Ketika elemen yang ingin dimasukkan telah ada sebelumnya serta tidak ingin terdapat dua elemen yang sama, maka Node baru yang diinisialisasi menggunakan malloc harus dibebaskan dengan fungsi free agar Node tersebut terhapus.

if (current->n == value)
{
   free(new_node);
   return false;
}

Fungsi insert pada Linked List(memasukkan elemen baru)

bool insert(node* list, int value)
{
    // inisialisasi node baru
    node* new_node = malloc(sizeof(node));
    
    if (new_node == NULL)
    {
        // alokasi memori gagal
        return false;
    }
    
    // inisialisasi nilai pada node yang baru
    new_node->n = value;
    new_node->next = NULL;
    
    // deklarasi node pembantu
    node* current = list;
    node* previous = NULL;
    
    // jika list kosong
    if (current == NULL)
    {
        head = new_node;
        new_node->next = NULL;
        return true;
    }
    
    // pointer pembantu akan mengecek elemen satu per satu sampai ujung list
    while (current != NULL)
    {
        // memasukkan elemen baru pada awal atau tengah list
        if (current->n > value)
        {
            // pointer node baru menunjuk pada elemen selanjutnya(elemen yang ditunjuk pointer pembantu)
            new_node->next = current;
            
            // jika hanya ada satu elemen pada list
            if (previous == NULL)
            {
                head = new_node;
            }
            // jika ingin memasukkan elemen baru di tengah list
            else
            {
                // ubah pointer pada elemen sebelumnya untuk menunjuk node baru
                previous->next = new_node;
            }
            
            // node baru berhasil dimasukkan
            return true;
        }
        // memasukkan elemen baru pada ujung list
        else if (current->n < value)
        {
            // pointer pembantu
            previous = current;
            // pointer pembantu pergi ke elemen selanjutnya
            current = current->next;
            
            // jika pointer pembantu sampai di ujung list
            if (current == NULL)
            {
                // pointer sebelumnya menunjuk ke node baru
                previous->next = new_node;
                return true;
            }
        }
        // jika elemen yang ingin dimasukkan telah ada sebelumnya, maka Node baru di-delete
        else if (current->n == value)
        {
            free(new_node);
            return false;
        }
    }
    
    // gagal memasukkan elemen baru
    return false;
}

Ketika ingin menghapus sebuah elemen, terlebih dahulu cari elemen yang ingin dihapus menggunakan algoritma pencarian, lalu jika ketemu maka hapus elemen tersebut. Jika elemen yang ingin dihapus berada di tengah list, jangan lupa untuk mengubah pointernya agar elemen yang lain tidak hilang.

Fungsi delete pada Linked List

bool delete(node* list, int value)
{
    // deklarasi pointer pembantu
    node* current = list;
    node* previous = NULL;
    
    // pointer pembantu akan mengecek elemen satu per satu sampai ujung list
    while (current != NULL)
    {
        // jika elemen yang ingin dihapus ditemukan
        if (current->n == value)
        {
            // jika hanya terdapat satu elemen pada list
            if (previous == NULL)
            {
                // hapus, membebaskan memorinya dengan free
                free(head);
                
                // list kosong
                head = current->next;
            }
            // jika elemen yang ingin dihapus terdapat di tengah list
            else
            {
                // pointer sebelumnya menunjuk ke elemen yang ditunjuk oleh elemen setelahnya
                previous->next = current->next;
                
                // hapus, membebaskan memorinya dengan free
                free(current);          
            }
            
            // elemen berhasil dihapus
            return true;
        }
        else
        {
            // pointer pembantu pergi ke elemen selanjutnya
            previous = current;
            current = current->next;
        }
    }
    
    // elemen gagal dhapus
    return false;
}

Fungsi untuk menampilkan elemen-elemen pada Linked List

void print(node* list)
{
    node* current = list;
    while (current != NULL)
    {
        printf("%d -> ", current->n);
        current = current->next;
    }
    printf("NULL\n");
}

Fungsi untuk menghapus semua elemen pada Linked List

void free_node(node* list)
{
    node* current = list;
    while (current != NULL)
    {
        free(current);
        current = current->next;   
    }
}

Program linked list yang saya buat bisa dilihat disini: http://ideone.com/m6cNvn

Output program ketika di-run menggunakan valgrind(tool untuk mengecek memory leak)

root@kali (~): valgrind --leak-check=full ./linked_list
==7071== Memcheck, a memory error detector
==7071== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==7071== Using Valgrind-3.10.0.SVN and LibVEX; rerun with -h for copyright info
==7071== Command: ./linked_list
==7071==
1. Insert
2. Display
3. Search
4. Delete
0. Quit
(~): 1
Insert value: 1
Insertion berhasil
1. Insert
2. Display
3. Search
4. Delete
0. Quit
(~): 1
Insert value: 5
Insertion berhasil
1. Insert
2. Display
3. Search
4. Delete
0. Quit
(~): 1
Insert value: 3
Insertion berhasil
1. Insert
2. Display
3. Search
4. Delete
0. Quit
(~): 2
1 -> 3 -> 5 -> NULL
1. Insert
2. Display
3. Search
4. Delete
0. Quit
(~): 3
Angka yang dicari: 3
Elemen yang dicari ketemu
1. Insert
2. Display
3. Search
4. Delete
0. Quit
(~): 4
Angka yang ingin dihapus: 3
Deletion berhasil
1. Insert
2. Display
3. Search
4. Delete
0. Quit
(~): 2
1 -> 5 -> NULL
1. Insert
2. Display
3. Search
4. Delete
0. Quit
(~): 0
==7071== Invalid read of size 4
==7071==    at 0x804885D: free_node (linked_list.c:184)
==7071==    by 0x8048A1D: main (linked_list.c:219)
==7071==  Address 0x423c02c is 4 bytes inside a block of size 8 free'd
==7071==    at 0x402B3D8: free (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==7071==    by 0x8048859: free_node (linked_list.c:183)
==7071==    by 0x8048A1D: main (linked_list.c:219)
==7071==
==7071==
==7071== HEAP SUMMARY:
==7071==     in use at exit: 0 bytes in 0 blocks
==7071==   total heap usage: 3 allocs, 3 frees, 24 bytes allocated
==7071==
==7071== All heap blocks were freed -- no leaks are possible
==7071==
==7071== For counts of detected and suppressed errors, rerun with: -v
==7071== ERROR SUMMARY: 2 errors from 1 contexts (suppressed: 0 from 0)