Pointer dalam Bahasa Pemrograman C

Pointer merupakan salah satu fitur yang terdapat dalam bahasa pemrograman C. Fitur ini bisa dibilang powerful karena dapat membuat kita mengakses dan memanipulasi alamat memori(address) pada suatu variabel.

Dalam menggunakan pointer, kita menggunakan operator reference(& dan *).  Misalkan suatu variabel bernama x, maka &x adalah address dari variabel x.

#include <stdio.h>

int main()
{
    int x = 7;

    printf("Nilai x: %d\n", x);
    
    // gunakan %p agar address yang ditampilkan dalam angka heksadesimal
    printf("Alamat x: %p\n", &x); // lambang ampersand(&) sebelum variabel x
    return 0;
}

Output:
Nilai x: 7
Alamat x: 0029ff0c

*kamu mungkin menghasilkan alamat yang berbeda tergantung sistem operasi memakai alamat mana saat kode tersebut dieksekusi

Pada program tersebut, nilai 7 disimpan di lokasi memori 0029ff0c. x hanyalah sebuah nama yang diberikan ke lokasi memori tersebut.

 Variabel hanyalah lokasi memori yang diberi nama

Variabel pointer adalah suatu variabel yang dapat menyimpan address, sedangkan variabel biasa menyimpan nilai. Ketika suatu pointer sedang memegang suatu address variabel lain, kita juga dapat mengubah nilai yang ada pada variabel yang address-nya sedang dipegang oleh pointer tersebut.

Cara mendeklarasikan suatu variabel pointer menggunakan operator * , dan untuk mengambil address suatu variabel menggunakan operator & .

#include <stdio.h>

int main()
{
    int y;
    int *x = &y; // pointer x menyimpan alamat y
    printf("yang disimpan x = %p\n", x);
    printf("alamat y = %p\n", &y);
    return 0;
}

Output:
yang disimpan x: 0029ff08
alamat y: 0029ff08

*kamu mungkin menghasilkan alamat yang berbeda tergantung sistem operasi memakai alamat mana saat kode tersebut dieksekusi

Jika ingin menampilkan nilai dari address yang sedang dipegang oleh variabel pointer, kita menggunakan operator * pada saat menggunakan printf()

#include <stdio.h>

int main()
{
    int y = 5;
    int *x = &y; // pointer x menyimpan alamat y

    printf("nilai dari address yang dipegang oleh x = %d\n", *x);
    printf("nilai variabel y = %d\n", y);
    return 0;
}

Output:
nilai dari address yang dipegang oleh x = 5
nilai variabel y = 5

Cara untuk mengubah nilai dari address yang dipegang oleh variabel pointer

#include <stdio.h>

int main()
{
    int y = 5;
    int *x = &y; // pointer x menyimpan alamat y

    printf("Nilai y sebelum diubah dari pointer x = %d\n", y);

    *x = 10; // mengubah nilai dari address yg dipegang pointer x

    printf("Nilai y setelah diubah dari pointer x = %d\n", y);

    return 0;
}

Output:
Nilai y sebelum diubah dari pointer x = 5
Nilai y setelah diubah dari pointer x =10

Namun, jika kita mengubah nilai dari address yang dipegang tanpa operator * , maka pointer tersebut berarti menyimpan alamat 10 atau dalam heksadesimal 0000000a

#include <stdio.h>

int main()
{
    int y = 5;
    int *x = &y; // pointer x menyimpan alamat y

    x = 10; // tanpa * , maka x menyimpan alamat 10
    // 10 dalam heksadesimal adalah 0000000a

    printf("address yang dipegang x = %p\n", x);

    return 0;
}

Output:
address yang dipegang x = 0000000a

 

Read more

C - Struktur Pembangun Algoritma

Read more

Struktur Data - Binary Tree dan Huffman Coding

Tree adalah struktur data dimana tiap-tiap titik(node)-nya memiliki nilai serta pointer ke titik di bawahnya(child node).

Terdapat istilah-istilah yang perlu diketahui pada struktur data Tree ini. Perhatikan gambar di samping. Node yang memiliki angka 1 disebut sebagai root node, dan node yang berangka 5, 6, 7, 8, dan 9 disebut sebagai leaves. Node 2 dan node 3 merupakan siblings karena kedua node tersebut berasal dari parent node yang sama, yaitu 1. Sedangkan 5, 6, 7 adalah child node dari 3. Lalu 2 merupakan parent node dari 4.

Struktur data tree terdapat beberapa jenis, salah satunya adalah Binary Tree. Binary Tree merupakan struktur data tree yang tiap-tiap parent node-nya hanya memiliki dua child node. Tiap-tiap node pada binary tree tersusun oleh dua pointer dan data yang disimpan. Misalnya binary tree yang menyimpan integer, maka tiap-tiap node pada binary tree tersusun dari variabel bertipe integer, pointer ke child node kanan, dan pointer ke child node kiri.

Cara mendefinisikan node pada Binary Tree

typedef struct node
{
    // data yang disimpan
    int value;

    // pointer ke child node kiri
    struct node* left;

    // pointer ke child node kanan
    struct node* right;
} node;

// deklarasi root node sebagai variabel global
node* root = NULL;

Ketika ingin mencari suatu data pada Binary Tree, pastikan terlebih dahulu bahwa data pada Binary Tree tersebut dalam keadaan terurut. Maksudnya adalah nilai child node sebelah kanan harus lebih besar dari nilai parent node, sedangkan nilai child node sebelah kiri harus lebih kecil dari nilai parent node-nya, atau sebaliknya.

Pada setiap parent node yang memiliki child node, nilai child node sebelah kanan lebih besar sedangkan nilai child node sebelah kiri lebih kecil

Setelah dipastikan terurut, pencarian data dimulai dari root node. Kita dapat menggunakan algoritma Binary Search untuk mencari data pada Binary Tree. Misalkan nilai yang kita cari lebih besar dari nilai node yang kita cek, maka pencarian akan bergerak ke child node sebelah kanan, lalu kemudian ketika nilai pada child node itu di cek lagi dan ternyata lebih besar dari nilai yang kita cari, maka pencarian akan bergerak ke child node sebelah kiri. Jika nilai pada node sama dengan nilai yang kita cari maka ketemu, namun ketika kita sampai pada node yang tidak ada nilai(NULL), berarti tidak ketemu.

Fungsi pencarian pada Binary Tree dengan nilai kembalian berupa boolean

/**
 * @param value: nilai yang ingin dicari
 * @param tree: tree yang salah satu nilainya sedang dicari
 */
bool contains(int value, node* tree)
{
    // pencarian dimulai dari root node
    node* current = tree;
    
    // pencarian terus berlanjut selama tidak ketemu NULL
    while (current != NULL)
    {
        if (current->value == value)
        {
            // jika nilai yang dicek sama dengan nilai yang dicari, berarti ketemu
            return true;
        }
        else if (current->value < value)
        {
            // jika nilai yang dicek lebih kecil dari yang dicari, 
            // maka pencarian bergerak ke child node kanan
            current = current->right;
        }
        else
        {
            // jika nilai yang dicek lebih besar dari yang dicari, 
            // maka pencarian bergerak ke child node kiri
            current = current->left;
        }
    }

    // tidak ketemu karena bertemu NULL
    return false;
}

Ketika ingin menyisipkan nilai pada Binary Tree, berarti kita akan menambahkan child node baru. Child node tersebut akan ditambah pada lokasi NULL tadi lalu dihubungkan dengan parent node. Jadi kita melakukan pencarian lokasi yang cocok untuk dimasukkan nilai tersebut. Jika bertemu NULL, maka masukkan nilai tersebut.

Fungsi memasukkan nilai pada Binary Tree dengan nilai kembalian berupa boolean

/**
 * @param value: nilai yang ingin dicari
 * @param tree: tree yang salah satu nilainya sedang dicari
 */
bool insert(int value, node* tree)
{
    // alokasi memori untuk membuat node baru
    node* new_node = malloc(sizeof(node));
    if (new_node == NULL)
    {
        // alokasi memori gagal
        return false;
    }
    
    // inisialisasi nilai tersebut ke node baru
    new_node->value = value;
    new_node->right = NULL;
    new_node->left = NULL;

    // pointer pembantu untuk mencari lokasi penyisipan
    node* current = tree;
    node* previous = NULL;

    // jika tree kosong
    if (current == NULL)
    {
        // berarti root node diinisialisasi oleh node baru tadi
        root = new_node;
        return true;
    }

    // lakukan pencarian lokasi selama belum ketemu NULL
    while (current != NULL)
    {
        // jika nilai yang ingin dimasukkan telah ada sebelumnya
        if (current->value == value)
        {
            // release memori dari nilai tersebut
            free(new_node);
            return false;
        }

        if (current->value < value)
        {
            // jika nilai yang dicek lebih kecil dari yang dicari, 
            // maka pencarian bergerak ke child node kanan
            previous = current;
            current = current->right;
        }
        else
        {
            // jika nilai yang dicek lebih besar dari yang dicari, 
            // maka pencarian bergerak ke child node kiri
            previous = current;
            current = current->left;
        }
    }

    // jika ketemu null
    if (current == NULL)
    {
        // maka sisipkan node baru pada lokasi tersebut
        current = new_node;

        if (previous->value < value)
        {
            // jika nilai yang disisipkan lebih besar dari parent node-nya,
            // berarti node baru dihubungkan oleh pointer sebelah kanan dari parent node-nya
            previous->right = current;
        }
        else
        {
            // jika nilai yang disisipkan lebih kecil dari parent node-nya,
            // berarti node baru dihubungkan oleh pointer sebelah kiri dari parent node-nya
            previous->left = current;
        }

        // penyisipan berhasil
        return true;
    }

    // penyisipan gagal
    return false;
}

Struktur data Binary Tree ini digunakan sebagai model untuk mengkompres(mengecilkan ukuran memori) dari suatu file. Suatu file yang berukuran besar perlu dikompres ketika ingin mengirimkannya melalui internet. Pengkompresan file ini menggunakan jumlah bits memori yang lebih kecil dari jumlah bits yang biasanya dipakai untuk merepresentasikan sebuah data. Metode ini dinamakan Huffman Coding.

Biasanya kita menggunakan ASCII untuk merepresentasikan data. ASCII adalah skema encoding yang berukuran tetap(biasanya 8 bit). Di sisi lain, huffman encoding adalah skema encoding yang ukurannya berbeda-beda tergantung pada banyaknya frekuensi suatu data yang ingin di-encoding.

Misalnya ketika kita ingin mengkompres sebuah string seperti pada gambar di samping. Kita akan menggunakan binary tree untuk menyusun skema encoding pada tiap karakter. Pertama-tama kita harus mencari tahu frekuensi kemunculan dari masing-masing karakter tersebut, nilainya dapat dilihat pada gambar di samping. Lalu susun nilai-nilai frekuensi tersebut sebagai leaves dari tree yang akan kita buat.

Kemudian, gabungkan dua node menjadi satu node dan tambahkan nilai frekuensi keduanya. Lakukan terus menerus hingga terbentuknya suatu tree seperti gambar di bawah

Lalu kita buat skema bahwa setiap child node sebelah kanan direpresentasikan oleh 1 sedangkan yang sebelah kiri direpresentasikan oleh 0. Jadi kita dapat merepresentasikan tiap huruf dengan jumlah bit yang berbeda. Misalnya huruf E yang frekuensi kemunculannya paling besar, kita hanya perlu merepresentasikannya dengan bit 1 dengan ukuran 1 bit dan itu akan menghemat memori dari pada kita merepresentasikannya dengan jumlah 8 bit. Lalu misalnya untuk merepresentasikan huruf C kita menggunakan 0001 dengan ukuran 4 bit.

--------------------------------------------------------------------------------------------------
https://study.cs50.net/

Read more

Kriptografi - Program Bahasa C untuk Menyembunyikan Pesan Menggunakan Teknik Caesar Cipher dan Vigenere Cipher

Kriptografi adalah seni menyembunyikan/menyamarkan pesan seolah-olah pesan tersebut tidak memiliki makna yang bertujuan untuk keamanan informasi dari pihak-pihak yang tidak diinginkan.

Istilah-istilah umum dalam kriptografi

Plaintext    : pesan yang ingin dirahasiakan.

Ciphertext : pesan yang telah disamarkan.

Encryption: proses penyamaran dari plaintext ke ciphertext.

Decryption: proses pembalikan dari ciphertext ke plaintext.

Contoh

Kriptografi sudah lama digunakan oleh tentara Sparta di Yunani pada permulaan 400 SM. Mereka menggunakan alat yang disebut scytale. Alat ini terdiri dari sebuah pita panjang dari daun papyrus yang dililitkan pada sebatang silinder. Pesan yang akan dikirim ditulis horizontal (baris per baris). Bila pita dilepaskan, maka huruf-huruf di dalamnya telah tersusun membentuk pesan rahasia.

Untuk membaca pesan, penerima melilitkan kembali silinder yang diameternya sama dengan diameter silinder pengirim. Teknik kriptografi seperti ini dikenal dengan nama transposition cipher, yang merupakan metode enkripsi tertua.

Transposition Cipher

Algoritma Kriptografi(cipher) adalah fungsi matematika yang digunakan untuk enkripsi dan dekripsi. Kekuatan suatu algoritma kriptografi diukur dari banyaknya kerja yang dibutuhkan untuk memecahkan data ciphertext menjadi plaintext.

Kriptografi modern tidak lagi mendasarkan kekuatan pada algoritmanya. Jadi algoritma tidak dirahasiakan. Kekuatan kriptografinya terletak pada kunci, yang berupa deretan karakter atau bilangan bulat yang dijaga kerahasiannya.

Misalnya dengan menggunakan teknik Caesar Cipher, yaitu teknik menyembunyikan pesan dengan menggeser susunan alphabet sejauh k huruf. Jika kunci(k) bernilai 3, maka huruf-huruf pada plaintext digeser sejauh 3 huruf.

Dengan kata lain, misalkan p adalah plaintext, pi adalah huruf ke-i pada plaintext, dan k adalah kunci rahasianya, maka pergeseran tiap huruf plaintext menjadi ciphertext(c), yaitu ci, adalah sebagai berikut: 

ci = (pi + k) % 26

Komputer hanya mengerti angka, jadi angka-angka itu harus direpresentasikan menjadi karakter agar dapat dipahami oleh manusia. Daftar representasi angka-angka tersebut dapat kita lihat pada tabel ASCII berikut ini

Perhatikan pada angka 65 - 90 dan 97 - 122 pada kolom dec(desimal). Huruf-huruf pada abjad direpresentasikan oleh angka-angka pada range tersebut. 65 - 90 merepresentasikan huruf kapital, sedangkan 97 - 122 merepresentasikan huruf kecil. Jadi perhitungan yang dilakukan di komputer akan menjadi seperti ini

if (plain[i] >= 'A' && plain[i] <= 'Z')
{
   // pada ASCII, huruf A dimulai dari 65, maka kurangi sejauh A yaitu 65 ketika di-modulo
   // lalu ditambah sejauh A yaitu 65 agar yang tampil adalah huruf 
   // karena pada ASCII huruf kapital dimulai dari 65
   cipher = ((plain[i] + key - 'A') % 26) + 'A';
}
else if (plain[i] >= 'a' && plain[i] <= 'z')
{
   // pada ASCII, huruf a dimulai dari 97, maka kurangi sejauh a yaitu 97 ketika di-modulo
   // lalu ditambah sejauh a yaitu 97 agar yang tampil adalah huruf 
   // karena pada ASCII huruf kecil dimulai dari 97
   cipher = ((plain[i] + key - 'a') % 26) + 'a';
}

Perhatikan rumus yang dilabeli dengan warna kuning, kita dapat melakukan perhitungan menggunakan huruf karena sejatinya huruf merupakan representasi dari angka. Mengapa perlu dikurang A dan ditambah lagi dengan A pada perhitungan diatas? Misalnya plaintext-nya adalah A, dan key-nya 3, maka ketika dihitung cipher = (65 + 3) % 26 = 16. Maka menurut tabel ASCII yang tampil bukan huruf D melainkan DLE(Data Link Escape) yang direpresentasikan oleh angka 16. Maka dari itu perlu dikurang A dan ditambah lagi dengan A, perhitungannya akan menjadi cipher = ((65 + 3 - 65) % 26) + 65 = 68, sehingga yang tampil menurut tabel ASCII adalah huruf D. Begitu juga pada perkondisian yang mengenkripsi huruf kecil.

Program yang menggunakan teknik Caesar Cipher dengan nama caesar.c

#include <stdio.h>
#include <string.h> // agar dapat menggunakan strlen()

int main()
{
    // input kunci
    int key;
    printf("Key: ");
    scanf("%d", &key);

    // input plaintext
    char plain[77];
    printf("Plaintext: ");
    gets(plain); // get string, untuk menginput string

    // angka pada ciphertext di-inisialisasi 0
    int cipher = 0;

    // strlen(), fungsi yang menghitung panjang string
    // pengulangan untuk mengenkripsi huruf per huruf
    for (int i = 0; i < strlen(plain); i++)
    {
        cipher = plain[i];

        // jangan di-enkripsi jika huruf pada plaintext berupa spasi
        if (plain[i] == ' ')
        {
            cipher = ' ';
        }

        // perkondisian supaya hanya huruf-huruf pada alphabet yang terenkripsi
        // sesuai dengan kode pada tabel ASCII
        else if (plain[i] >= 'A' && plain[i] <= 'Z')
        {
            // pada ASCII, huruf A dimulai dari 65, maka kurangi sejauh A yaitu 65 ketika di-modulo
            // lalu ditambah sejauh A yaitu 65 agar yang tampil adalah huruf 
            // karena pada ASCII huruf kapital dimulai dari 65
            cipher = ((plain[i] + key - 'A') % 26) + 'A';
        }
        else if (plain[i] >= 'a' && plain[i] <= 'z')
        {
            // pada ASCII, huruf a dimulai dari 97, maka kurangi sejauh a yaitu 97 ketika di-modulo
            // lalu ditambah sejauh a yaitu 97 agar yang tampil adalah huruf 
            // karena pada ASCII huruf kecil dimulai dari 97
            cipher = ((plain[i] + key - 'a') % 26) + 'a';
        }

        // tampilkan huruf yang telah digeser(di-enkripsi)
        // nilai bertipe data integer dapat ditampilkan menggunakan %c 
        // agar yang tampil adalah karakter sesuai tabel ASCII
        printf("%c", cipher);
    }

    printf("\n");

    return 0;
}

Output program ketika di-run

root@kali: ./caesar
Key: 3
Plaintext: awasi asterix dan temannya obelix
Ciphertext: dzdvl dvwhula gdq whpdqqbd rehola
root@kali: ./caesar
Key: 14
Plaintext: Temui aku di kolong jembatan pukul sembilan malam
Ciphertext: Hsaiw oyi rw yczcbu xsapohob diyiz gsapwzob aozoa
root@kali:

Teknik lain yang lebih kuat adalah Vigenere Cipher. Teknik ini kurang lebih sama dari Caesar Cipher namun yang menjadi kunci adalah string.

Misalnya kita memiliki plaintext "I like you" dan kunci "panda", ketika di-enkripsi huruf per huruf, maka huruf I pada plaintext akan di-enkripsi oleh huruf p pada kunci. Lalu huruf l pada plaintext akan di-enkripsi dengan huruf a pada kunci, dan seterusnya. Jika kunci telah sampai ke huruf terakhir, maka kembali ke awal.

Perlu diingat kembali bahwa huruf direpresentasikan oleh angka. Jadi, misalkan kita ingin menggeser huruf sebanyak B maka akan tergeser sejauh 66, karena kunci yang kita gunakan adalah huruf. Maka dari itu kurangi sebesar A, yaitu 65, sehingga akan bergeser sejauh 1.

Program yang menggunakan teknik Vigenere Cipher dengan nama vigenere.c

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

int main()
{
    // input kunci
    char key_str[25];
    printf("Enter key: ");
    gets(key_str);

    // input plaintext
    char plain[77];
    printf("Enter plain text: ");
    gets(plain);

    // inisialisasi cipher sama dengan 0
    int cipher = 0;
    
    // variabel untuk menandakan indeks pada kunci
    int j = 0;

    printf("Cipher text: ");
    for (int i = 0; i < strlen(plain); i++)
    {
        // indeks (huruf ke-i) pada kunci yang digunakan untuk mengenkripsi plainteks
        int index = j % strlen(key_str);
        int key = key_str[index];

        // karena huruf alphabet berjumlah 26, maka kunci dikurangi dengan 65(huruf kapital)
        if (key_str[index] >= 'A' && key_str[index] <= 'Z')
        {
            key = key - 'A';
        }
        
        // karena huruf alphabet berjumlah 26, maka kunci dikurangi dengan 97(huruf kecil)
        else if (key_str[index] >= 'a' && key_str[index] <= 'z')
        {
            key = key - 'a';
        }

        // jangan pindah ke huruf selanjutnya pada key jika huruf pada plaintext adalah selain alphabet
        if ((plain[i] >= 'A' && plain[i] <= 'Z') || (plain[i] >= 'a' && plain[i] <= 'z'))
        {
            j++;
        }

        cipher = plain[i];
        
        // jangan di-enkripsi jika huruf pada plaintext adalah spasi
        if (plain[i] == ' ')
        {
            cipher = ' ';
        }
        
        // jangan di-enkripsi jika huruf pada plaintext adalah selain huruf alphabet
        else if (plain[i] < 'A' || (plain[i] > 'Z' && plain[i] < 'a') || plain[i] > 'z')
        {
            cipher = plain[i];
        }
        
        // perkondisian untuk mengenkripsi huruf alphabet
        else if (plain[i] >= 'A' && plain[i] <= 'Z')
        {
            cipher = ((plain[i] + key - 'A') % 26) + 'A';
        }
        else if (plain[i] >= 'a' && plain[i] <= 'z')
        {
            cipher = ((plain[i] + key - 'a') % 26) + 'a';
        }

        printf("%c", cipher);
    }

    printf("\n");

    return 0;
}

Output program ketika di-run

root@kali: ./vigenere
Enter key: panda
Enter plain text: I like you
Cipher text: X lvne noh
root@kali: ./vigenere
Enter key: senpai
Enter plain text: notice me, senpai!
Cipher text: fsgxcm ei, ftnxsm!
root@kali:

Read more

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)

Reference: https://study.cs50.net/linked_lists

Read more