Code example for Double Linked List

Dreammer's Market

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

struct List{
    char name[50];
    int qty;
    int price;
    List *next,*prev;
}*head,*tail,*curr,*temp;

List *createNode(const char name[], int qty){
    List *temp = (List*)malloc(sizeof(List));
    strcpy(temp->name,name);
    temp->qty = qty;
    temp->next = temp->prev = NULL;
    return temp;
}

void enter(){
    puts("\nPress any key to continue...");
    getchar();
}

void cls(){
    for(int i=0;i<30;i++)
        puts("");
}

void deleteList(char name[]){
    if(!head){
        puts("Your cart is empty");
        return;
    }
    curr = head;
    while(curr){
        if(strcmp(curr->name,name)==0)
            break;
        if(strcmp(curr->name,name)>0){
            puts("Not Found");
            return;
        }
        curr = curr->next;
    }
    if(!curr)
        printf("Not Found");
    else if(curr == head && !curr->next)
        head = NULL;
    else if(curr == head){
        head->next->prev = NULL;
        head = curr->next;
    }
    else if(curr == tail){
        curr->prev->next = NULL;
        tail = curr->prev;
    }  
    else{
        curr->next->prev = curr->prev;
        curr->prev->next = curr->next;
    }
    free(curr);
}

void edit(char name[], int change){
    if(!head){
        puts("Your cart is empty");
        return;
    }
    curr = head;
    while(curr){
        if(strcmp(curr->name,name)==0)
            break;
        if(strcmp(curr->name,name)>0){
            puts("Not Found");
            return;
        }
        curr = curr->next;
    }
    if(!curr)
        printf("Not found");
    else
        curr->qty = change;
}

bool search(char name[]){
    if(!head)
        return false;
    curr = head;
    while(curr){
        if(strcmp(curr->name,name)==0)
            return true;
        if(strcmp(curr->name,name)>0)
            return false;
        curr = curr->next;
    }
    return false;
}

void pushPriority(char name[], int qty){
    curr = createNode(name,qty);
    curr->price = rand() % 89999 + 10000;
    if(!head)
        head = tail = curr;
    else{
        temp = head;
        while(temp->next){
            if(strcmp(temp->next->name,curr->name)>0)
                break;
            temp = temp->next;
        }
        if(temp==tail){
            temp->next = curr;
            curr->prev = temp;
            tail = curr;
        }
        else{
            curr->prev = temp;
            curr->next = temp->next;
            temp->next->prev = curr;
            temp->next = curr;
        }
    }
    head->prev = NULL;
    tail->next = NULL;
}

void checkOut(){
    if(!head){
        puts("Your cart is empty");
        enter();
        return;
    }
    curr = head;
    int count = 0;
    int total = 0;
    puts("=====================================================================================");
    puts("=                               Dreammers Market Bill's                             =");
    puts("=====================================================================================");
    puts("= No  =             Item Name               =  Qty   =   Price    =       Total     =");
    puts("=====================================================================================");
    while(curr){
        printf("= %3d = %-35s = %6d = Rp.%7d = Rp. %11d =\n",++count,curr->name,curr->qty,curr->price, curr->qty*curr->price);
        total += curr->qty*curr->price;
        curr = curr->next;
    }
    puts("=====================================================================================");
    printf("=-----------------------------Discount----------------------------= Rp. %11d =\n", -total);
    puts("=====================================================================================");
    printf("=------------------------------Total------------------------------=       Free      =\n");
    puts("= ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~Kindness is Free ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ =        ^^       =");
    puts("=====================================================================================");
  
    enter();
}

void deleteCart(){
    char name[50];
    int quantity;
    char strquantity[50];
    do{
        printf("Input item name you want to delete>> ");
        scanf("%[^\n]", name);getchar();
    }while(strlen(name)<1);
  
    curr = head;
    while(curr){
        if(strcmp(curr->name,name)==0)
            break;
        curr = curr->next;
    }
    if(!curr){
        puts("Not Found");
        enter();
        return;
    }
  
    char confirm[10];
    printf("%-15s: %s\n", "Item Name",curr->name);
    printf("%-15s: %d\n", "Quantity",curr->qty);
    printf("%-15s: %d\n\n", "Price", curr->price);
    puts("Do you still want to delete this item from cart? [Yes|No] case sensitive");
    do{
        printf(">> ");
        scanf("%[^\n]", confirm);getchar();
    }while(!(strcmp(confirm,"Yes")==0 || strcmp(confirm,"No")==0));
    if(strcmp(confirm,"No")==0)
        return;
    deleteList(name);
    puts("Succesfully deleted");
    enter();
}

void editCart(){
    char name[50];
    int quantity;
    char strquantity[50];
    do{
        printf("Input item name you want to edit>> ");
        scanf("%[^\n]", name);getchar();
    }while(strlen(name)<1);
  
    curr = head;
    while(curr){
        if(strcmp(curr->name,name)==0)
            break;
        curr = curr->next;
    }
    if(!curr){
        puts("Not Found");
        enter();
        return;
    }
    bool error;
    printf("%-15s: %s\n", "Item Name",curr->name);
    printf("%-15s: %d\n", "Quantity",curr->qty);
    printf("%-15s: %d\n\n", "Price", curr->price);
  
    do{
        error = false;
        printf("Edit Quantity [0 to cancel] >> ");
        scanf("%[^\n]", strquantity);getchar();
        for(int i=0;strquantity[i]!='\0';i++){
            if(strquantity[i]>=48 && strquantity[i]<=57)
                continue;
            else{
                error = true;
                break;
            }
        }
    }while(error);
    if(quantity)
        return;
    quantity = atoi(strquantity);
    edit(curr->name, quantity);
    puts("Succesfully Update Your Cart");
    enter();
}

void addCart(){
    char name[50];
    int quantity;
    char strquantity[50];
    do{
        printf("Input item name >> ");
        scanf("%[^\n]", name);getchar();
    }while(strlen(name)<1);
  
    if(search(name)){
        puts("\n\nYour item already exist!");
        enter();
        return;
    }
  
    bool error;
    do{
        error = false;
        printf("Input %s quantity >> ", name);
        scanf("%[^\n]", strquantity);getchar();
        for(int i=0;strquantity[i]!='\0';i++){
            if(strquantity[i]>=48 && strquantity[i]<=57)
                continue;
            else{
                error = true;
                break;
            }
        }
    }while(error);
    quantity = atoi(strquantity);
//    printf("%d", quantity);
    pushPriority(name,quantity);
}

void viewCart(){
    if(!head){
        puts("Your cart is empty");
        enter();
        return;
    }
    curr = head;
    int count = 0;
    puts("===================================================================");
    puts("=                                Cart                             =");
    puts("===================================================================");
    puts("= No  =             Item Name               =  Qty   =   Price    =");
    puts("===================================================================");
    while(curr){
        printf("= %3d = %-35s = %6d = Rp.%7d =\n",++count,curr->name,curr->qty,curr->price);
        curr = curr->next;
    }
    puts("===================================================================");
    enter();
}

void mainMenu(){
    int input=0;
    do{
        cls();
        puts("Welcome to Dreammers Market!!");
        puts("");
        puts("Choose what to do:");
        puts("1. View Cart");
        puts("2. Add New Item to Cart");
        puts("3. Edit Quantity Item on Cart");
        puts("4. Delete Item on Cart");
        puts("5. CheckOut");
        puts("6. Exit");
        scanf("%d", &input);getchar();
        switch(input){
            case 1:
                viewCart();
                break;
            case 2:
                addCart();
                break;
            case 3:
                editCart();
                break;
            case 4:
                deleteCart();
                break;
            case 5:
                checkOut();
                break;
        }
    }while(input!=6);
    puts("\n\nThank you for coming!!");
}

int main(){
    mainMenu();
    return 0;
}

 

 

Summary

Linked List

Linked List adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan). Elemen data yang dihubungkan dengan link pada Linked List disebut Node. Biasanya didalam suatu linked list, terdapat istilah head dan tail.

• Head adalah elemen yang berada pada posisi pertama dalam suatu linked list
• Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list

Ada beberapa macam Linked List, yaitu :

1. Single Linked List
2. Double Linked List
3. Circular Linked List
4. Multiple Linked List
5. Doubly Linked List
6. Circular Doubly Linked List

Single Linked List

Linked List merupakan kumpulan dari banyak data, yang disebut sebagai nodes, dimana setiap node akan menunjuk pada node lain melalui pointer. Linked List bisa juga disebut kumpulan data linear.

Linked List yang memiliki satu penghubung dengan node lain, disebut single linked list.

Dalam Linked List pasti terdapat node yang bernama head dan tail. Head yang dimaksud disini adalah penunjuk untuk menunjukkan dimana letak data pertama dan tail menunjukkan dimana letak data terakhir. 

Sebuah linked list, dikatakan kosong jika tidak memiliki head yang menandakan bahwa node tersebut kosong.

Operasi pada single linked list:
1. Push (Memasukkan data)
2. Pop (Menghapus data dari Node)

1. Push
Push merupakan operasi pada linked list untuk menginsert suatu data pada node, push bisa saja dilakukan pada head, tail, ataupun index.

Contoh push adalah sebagai berikut:

Jika terdapat node yang berisi angka 7, 6, 9, 3, 5 , NULL

Kemudian pushHead(4) maka hasilnya akan menjadi 4, 7, 6, 9, 3, 5, NULL

Sama halnya jika melakukan pushTail(10) hasilnya akan menjadi 4, 7, 6, 9, 3, 5, 10, NULL

Untuk contoh kode pushHead bisa dilihat dibawah ini

public void pushHead(int n){ // int n ini merupakan data yang akan dimasukkan pada linked list

struct Data* curr = (struct Data*)malloc(sizeof(Data));
    curr->isi = n;
    if(head==NULL) head = tail = curr; // Jika belum terdapat head
    else{
        curr->next = head;
        head = curr;
    }
}

2. Pop

Pop merupakan kebalikan dari push, dimana fungsi pop adalah mendelete suatu data dalam linked list dan melepaskanny agar memory dapat dipakai kembali. Pop biasa digunakan untuk mendelete head, tail ataupun suatu index.

Contoh pop:
terdapat suatu data 1, 5, 6, 7, 8, 9, NULL

Kemudian popHead() maka hasilnya akan menjadi  5, 6, 7, 8, 9, NULL

Jika popTail() maka hasilnya akan menjadi  5, 6, 7, 8, NULL

Untuk contoh kode dari popHead bisa dilihat dibawah ini

 void popHead(){
    struct Data* curr = head;
    head = head->next; // merubah head ke angka selanjutnya dikarenakan angka pada head akan dilepas
    free(curr);
}

Double Linked List

Double Linked List adalah salah satu contoh lain implementasi linked list selain single linked list. Sesuai namanya, Double artinya blok data yang kita miliki akan memiliki 2 penunjuk kiri dan kanan untuk menentukan data sebelum/sesudahnya. Berbeda dengan single linked list yang hanya mempunyai satu penunjuk, double linked list mempunyai 2 penunjuk kiri dan kanan untuk menentukan urutan datanya.

Circular Linked List

Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL.
Ada 2 jenis Circular Linked List, yaitu :

1. Circular Single Linked List
2. Circular Double Linked List

Circular Single Linked List

Single Linked List Circular adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node,  maka pointer next pada node terakhir akan menunjuk ke node terdepannya.

Circular Double Linked List

Double Linked List adalah linked list dengan node yang memiliki data dan dua buah reference link (biasanya disebut next dan prev) yang menunjuk ke node sebelum dan node sesudahnya.

Hash Table and Binary Tree

Ketika kita diberikan data yang sangat banyak, kita harus membutuhkan suatu data structure yang cepat untuk melakukan banyak hal (insert, delete,dan search). Seharusnya kita mempunyai kunci(key) untuk dapat mengakses data tersebut, agar ketika kita mencari, kita hanya tinggal memakai key tersebut, sehingga waktu yang diperlukan untuk mencari data lebih efisien, karena sudah mendekati dimana lokasi data tersebut dibanginkan jika kita mencari data secara linear(satu per satu). Ada beberapa cara untuk mengimplementasi cara penggunaan key ini, contoh nya seperti, hash table, balanced binary search tree(bst) dan doubly linked list.

Hash Table

Untuk sekarang, saya akan menjelaskan tentang hash table. Hash table merupakan method tercepat yang dapat digunakan insert,delete dan search dibandingkan bst dan double linked list.

Di dalam hash table terdapat suatu function bernama hash function, hash function adalah function untuk menempatkan index dari suatu key dalam suatu array.

Ada banyak cara hash function seperti, salah satu contohnya division method, division method adalah salah satucara pada hash function dimana kita akan menaruh suatu index pada array h dimana
h(k) = k%m , k disini merupakan key dan m merupakan panjang arraynya.

dibawah ini merupakan contoh dari division method:



untuk contoh disamping, terdapat key 1276, maka index dari key tersebut akan disimpan dalam array ke - [6]




Namun, apa yang terjadi jika dalam array tersebut telah terdapat data yang telah disimpan? ini disebut hash collision. Ada banyak cara untuk mengatasi hash collisin ini, contohnya seperti open addressing dan closed addressing.

Open Addressing
suatu cara yang digunakan untuk mencari tempat kosong setelah tempat key tersebut terisi.






Contoh penggunaan open addressing pada bahasa C




Closed Addressing
cara yang digunakan untuk menempatkan suat data secara linked list.


Contoh penggunaan closed addressing

Binary Tree

Tree Concept

Tree adalah sebuah struktur data yang memiliki bentuk sebuah pohon, yang terdiri dari serangkaian node (simpul) berisi data yang saling berhubungan.

Binary tree

Binary Tree adalah sebuah pohon yang menyimpan data, keunikan binary tree adalah mensortir semua data yang dimasukkan. Sebuah binary search tree memiliki root dan cabang left serta right pada setiap nodenya.

dalam binary tree, kita dapat melakukan insert.
Contoh dari insert dalam binary tree: mencari dari parent dimana lokasi yang tepat untuk memasukkan nilai, dan jika ditemukan bahwa parentnya tersebut NULL, masukkan ke dalam parent

Berikut adalah contoh code di C jika kita ingin memasukkan data sesuai gambar diatas

Binary Search Tree

Binary Search Tree adalah tree yang terurut. Binary Search Tree sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory. Implemetasi binary search tree ini biasanya data akan dibagi menjadi dua dengan mencari titik tengah seagai patokannya. Binary tree terdiri dari anak satu pertama yang disebut dengan istilah root. Root tersebut memiliki anak(rootbaru) kiri dan anak kanan. Data disimpan setelah root disimpan berdasarkan nilai perbandingan dengan root tersebut. Pengurutan dengan metode in-order. Data yang telah tersusun dalam struktur data BST dapat dicari dengan mudah dan memiliki rata-rata kompleksitas sebesar O(log n), namun membutuhkan waktu sebesar O(n) pada worstcase dimana BST berbentuk seperti linked list.

 Contoh implementasi code C insert,delete dalam bst.
/*
#include <stdio.h>
#include <stdlib.h>

struct Node{
int value;
Node *left,*right;
}*root,*curr;

Node *createNode(int val){
curr = (Node*) malloc(sizeof(Node));
curr->value = val;
curr->left = curr->right = NULL;
return curr;
}

Node *insertNode(Node *parent,int value){
if(!parent)
 return createNode(value);
else if(parent->value == value)
 return parent;
else if(parent->value > value)
 parent->left = insertNode(parent->left,value);
else
 parent->right = insertNode(parent->right,value);
}

Node *removeNode(Node *parent,int value){
if(!parent)
 return parent;
else if(parent->value > value)
 parent->left = removeNode(parent->left,value);
else if(root->value < value)
 parent->left = removeNode(parent->left,value);
else if(parent->value == value){
if(parent->left == NULL || parent->right == NULL){
 Node *temp = parent->left != NULL ? parent->left : parent->right;
if(temp)
 *parent = *temp;
else{
temp = parent;
parent = NULL;
}
free(temp);
}
else{
Node *temp = parent->left;
while(temp->right)
 temp = temp->right;
parent->left=removeNode(parent->left,temp->value);
}
return parent;
}
}

void print(Node *parent){
if(parent){
print(parent->left);
printf("%d ",parent->value);
print(parent->right);
}
}

int main(){
root = insertNode(root,20);
root = insertNode(root,5);
root = insertNode(root,14);
root = insertNode(root,3);
root = insertNode(root,16);
root = insertNode(root,22);
root = insertNode(root,19);

root = removeNode(root,3);
//print in order
print(root);
}
*/


Dan untuk tugas membuat aplikasi dengan konsep double linked list terdapat dalam web :

https://linkedlisttugasmingguan.blogspot.com/2020/04/code-example-for-double-linked-list.html

Demikian rangkuman mengenai hal hal apa saja yang saya pelajari sampai saat ini, Terima Kasih.