/*
Azhary Arliansyah
Teknik Informatika 
Universitas Sriwijaya
arliansyahazhary.blogspot.com
*/

#include <stdio.h>
#include <stdlib.h> // agar dapat menggunakan malloc() dan free()
#include <stdbool.h> // agar dapat menggunakan tipe data boolean

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;

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;
}

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;
}

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;
}

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

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

int main()
{
    int value;
    int option;
    
    while (true)
    {
        printf("1. Insert\n2. Display\n3. Search\n4. Delete\n0. Quit\n(~): ");
        scanf("%d", &option);
        switch (option)
        {
            case 1:
                printf("Insert value: ");
                scanf("%d", &value);
                printf("Insertion %s\n", (insert(head, value)) ? 
                "berhasil" : "tidak berhasil");
                break;
            case 2: print(head); break;
            case 3:
                printf("Angka yang dicari: ");
                scanf("%d", &value); 
                printf("Elemen yang dicari %s\n", (search(head, value)) ? 
                "ketemu" : "tidak ketemu"); 
                break;
            case 4:
                printf("Angka yang ingin dihapus: ");
                scanf("%d", &value);
                printf("Deletion %s\n", (delete(head, value)) ? 
                "berhasil" : "tidak berhasil");
                break;
            case 0:
                free_node(head);
                return 0;
                break;
        }
    }
}