Circular Single Linked List
- Circular Single Linked List merupakan Single Linked List dimana tail node menunjuk (menggunakan pointer) pada head node.
- Ini juga berarti tidak ada node yang menunjuk pada NULL dikarenakan tail node-nya menunjuk pada head node membentuk lingkaran.
- Karena berbentuk circular maka linked list ini dapat dimulai dari mana saja karena bentuknya.
Doubly Linked List
- Bernama lain two-way linked list.
- Tidak seperti single linked list, doubly linked list setiap nodenya memiliki 2 pointer, yang satu menunjuk pada node sebelumnya (previous node) dan lainnya menunjuk pada node setelahnya (next node).
- Dikarenakan head node adalah node pertama maka pointer yang seharusnya menujuk pada node sebelumnya menunjuk pada NULL. Begitu pula dengan tail node-nya, di mana pointer yang seharusnya menunjuk pada node setelahnya menunjuk pada NULL.
Insertion pada Doubly Linked List
- Sama seperti insertion pada Single Linked List, tetapi bedanya kali ini kita harus menghubungkan kembali bukan hanya dengan node setelahnya, tetapi juga dengan node sebelumnya karena ini adalah Doubly Linked List
Delete pada Doubly Linked List
- Jika yang di-delete adalah node satu-satunya :
free(head);
head = NULL;
tail = NULL;
- Jika yang di-delete adalah head node :
free (head -> prev );
head -> prev = NULL;
- Jika yang di-delete adalah tail node :
free (tail -> next );
tail -> next = NULL;
struct tnode *curr = head;
- Jika yang di-delete adalah bukan head node atau tail node :
while ( curr->next->value != x ) curr = curr->next;
struct tnode *a = curr;
struct tnode *del= curr->next;
struct tnode *b= curr->next->next;
a->next = b;
b->prev = a;
free(del);
Circular Doubly Linked List
- Dapat dilihat dari namanya ini merupakan Doubly Linked list yang circular.
- Perbedaan dengan Doubly Linked List ialah tidak ada yang menunjuk pada NULL karena tail node menunjuk pada head node.
- Sama seperti Circular Single Linked List, Circular Doubly Linked List dapat dimulai dari mana saja karena bentuknya yang circular.
Sumber :
- Materi dari Binusmaya
- https://www.geeksforgeeks.org/doubly-circular-linked-list-set-1-introduction-and-insertion/
- https://www.youtube.com/watch?v=BFYLS0uPnJk
- https://www.studytonight.com/data-structures/doubly-linked-list
I. Push
- Adalah metode memasukkan "gerbong" (data) baru pada linked list.
- Ada dua jenis push, yaitu :
- Push head
- Memasukkan data baru yang akan menjadi head (bagian depan) sehingga "gerbong" (data) yang di belakangnya terdorong.
- Contoh : {1,2,3} jika di-PushHead "7" menjadi {7,1,2,3} (Head berpindah dari 1 ke 7).
- Push Tail
- Memasukkan data baru yang akan menjadi tail (bagian belakang) sehingga "gerbong" (data) yang di depannya terdorong.
- Contoh : {1,2,3} jika di-PushHead(7) menjadi {1,2,3,7} (Head berpindah dari 1 ke 7).
II. Pop
- Adalah metode untuk menghapus data pada linked list
- Setelah dihapus datanya, kita harus menyambung kembali node yang terputus akibat hilangnya data yang dipop.
Hashing Table
Hash Table is a data structure which stores data in an associative manner. In a hash table, data is stored in an array format, where each data value has its own unique index value. Access of data becomes very fast if we know the index of the desired data.
Thus, it becomes a data structure in which insertion and search operations are very fast irrespective of the size of the data. Hash Table uses an array as a storage medium and uses hash technique to generate an index where an element is to be inserted or is to be located from.
Binary Search Tree
Binary tree adalah sekumpulan data digambarkan berupa sebuah tree.
Berikut merupakan Binary Search Tree :
Binary tree selalu dimulai dari root. Setiap data memiliki maksimal 2 cabang (bisa 2, 1, atau tidak ada cabang sama sekali). Angka yang lebih kecil selalu berada di cabang yang kiri dan yang besar berada di cabang yang kanan.
Dalam Binary Search Tree ada function insertion, deletion, dan print sama seperti linked list.
Deklarasi Binary Search Tree :
#include<stdio.h>
#include<stdlib.h>
struct Data
{
int nilai;
Data *left , *right;
}*root = NULL; //NULL karena belum ada data dimasukan
Insertion:
struct Data* insert(struct Data *curr,int nilai) //menggunakan struct karena akan mengreturn struct
{
if(curr == NULL)
{
struct Data *temp = (struct Data*)malloc(sizeof(struct Data));
temp->nilai = nilai;
temp->left = temp->right = NULL;
curr = temp;
}
else
{
if(curr->nilai > nilai)
{
curr->left = insertNilai(curr->left,nilai);
}
else
{
curr->right = insertNilai(curr->right,nilai);
}
}
return curr;
}
APLIKASI
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
struct node{
char name[21];
int price;
int qty;
// int howMuchDel;
node *next,*prev;
}*head,*tail,*curr;
void pushTail(char name[21],int qty,int price){
curr = (struct node *) malloc(sizeof(node));
strcpy(curr->name,name);
curr->qty=qty;
curr->price=price;
curr->next = curr -> prev =NULL;
if(head==NULL){
head=tail=curr;
}else{
curr->prev=tail;
tail->next=curr;
tail=curr;
}
}
void popHead(){
if(head==tail){
curr=head;
head=tail=NULL;
free(curr);
}else{
curr=head;
head=head->next;
head->prev=NULL;
free(curr);
}
}
void pop(){
if(curr==head && curr==tail){
head=tail=NULL;
free(curr);
}else if(curr==head){
popHead();
}else if(curr==tail){
curr=tail->prev;
free(tail);
tail=curr;
tail->next=NULL;
}
else{
curr->prev->next=curr->next;
curr->next->prev=curr->prev;
free(curr);
}
}
void buyItem(){
char name [21];
int qty;
int price;
int len;
srand(time(0));
do {
printf("Masukkan input nama (max 20 huruf): ");
scanf("%[^\n]s",name);getchar();
len=strlen(name);
printf("\n");
}while (len>20);
printf("Masukkan input quantity: ");
scanf("%d",&qty);getchar();
printf("\n");
price=(rand() % (100000 - 10000 + 1)) + 10000;
if(qty!=0){
pushTail(name,qty,price);
printf("Item has been added to cart.\n");
}else{
printf("No item has been added to cart (user quantity input = 0).\n");
}
}
void showItem(){
if(head==NULL) {
printf("No items in cart\n\n");
}else {
printf("=====================================================\n");
printf("| List of items |\n");
curr = head;
while(curr != NULL){
printf("| %s | Rp %d | %d pc(s) |\n",curr->name,curr->price,curr->qty);
curr = curr->next;
}
printf("=====================================================\n");
}
}
void editCart(){
char input [21];
int len,found=0;
do{
printf("Input item name to edit [max 20 char]: ");
scanf("%[^\n]",input);getchar();
printf("\n");
len=strlen(input);
}while(len>20);
curr=head;
while(curr!=NULL){
if(strcmp(input,curr->name)==0){
found=1;
break;
}
curr=curr->next;
}
if(found==1){
int x;
printf("\nEdit Menu: \n\n");
printf("1. Delete from cart\n");
printf("2. Change quantity\n");
printf("3. Exit\n");
printf("--> ");
scanf("%d",&x);getchar();
printf("\n");
switch(x){
case 1 :{
pop();break;
}
case 2 :{
printf("Input new quantity for item: ");
scanf("%d",&curr->qty);getchar();
printf("\n");
if(curr->qty==0){
pop();
printf("Item has been deleted\n");
}else{
printf("Item quantity has been changed.\n");
break;
}
}
}
}else{
printf("Item not found. Please try again.\n");
editCart();
}
}
int checkOut(){
int total;
if(head==NULL) {
printf("No items left in cart\n\n");
return 0;
}else {
printf("=====================================================\n");
printf("| List of items left in cart |\n");
curr =head;
while(curr != NULL){
printf("| %s | Rp %d | %d pc(s) |\n",curr->name,curr->price,curr->qty);
total+=(curr->price*curr->qty);
curr = curr->next;
}
printf("=====================================================\n");
printf("=====================================================\n");
printf("|Total: %d|\n",total);
printf("=====================================================\n");
}
printf("Pay?\n");
printf("Y=Pay N=Back to Menu\n");
char yn;
printf("--> ");scanf("%c",&yn);getchar();printf("\n");
if(yn=='Y' || yn=='y'){
printf("Kindness is free.\n");
printf("No need to pay.\n");
printf("Have a good day !!!\n");
while(head!=NULL){
popHead();
}
return 1;
}else if (yn=='N' || yn=='n'){
return 0;
}
}
int main (){
int input,flag=0;
while (flag==0){
printf("\nMenu: \n\n");
printf("1. Buy Item\n");
printf("2. View Cart\n");
printf("3. Edit Cart\n");
printf("4. Check Out\n");
printf("5. Exit\n\n");
printf("--> ");
scanf("%d",&input);getchar();
printf("\n");
switch (input) {
case 1 : buyItem();break;
case 2 : showItem();break;
case 3 : editCart();break;
case 4 : flag=checkOut();break;
case 5 : flag=1;break;
}
}
return 0;
}
Thus, it becomes a data structure in which insertion and search operations are very fast irrespective of the size of the data. Hash Table uses an array as a storage medium and uses hash technique to generate an index where an element is to be inserted or is to be located from.
Binary Search Tree
Binary tree adalah sekumpulan data digambarkan berupa sebuah tree.
Berikut merupakan Binary Search Tree :
Binary tree selalu dimulai dari root. Setiap data memiliki maksimal 2 cabang (bisa 2, 1, atau tidak ada cabang sama sekali). Angka yang lebih kecil selalu berada di cabang yang kiri dan yang besar berada di cabang yang kanan.
Dalam Binary Search Tree ada function insertion, deletion, dan print sama seperti linked list.
Deklarasi Binary Search Tree :
#include<stdio.h>
#include<stdlib.h>
struct Data
{
int nilai;
Data *left , *right;
}*root = NULL; //NULL karena belum ada data dimasukan
Insertion:
struct Data* insert(struct Data *curr,int nilai) //menggunakan struct karena akan mengreturn struct
{
if(curr == NULL)
{
struct Data *temp = (struct Data*)malloc(sizeof(struct Data));
temp->nilai = nilai;
temp->left = temp->right = NULL;
curr = temp;
}
else
{
if(curr->nilai > nilai)
{
curr->left = insertNilai(curr->left,nilai);
}
else
{
curr->right = insertNilai(curr->right,nilai);
}
}
return curr;
}
APLIKASI
#include <stdio.h>#include <stdlib.h>
#include <string.h>
#include <time.h>
struct node{
char name[21];
int price;
int qty;
// int howMuchDel;
node *next,*prev;
}*head,*tail,*curr;
void pushTail(char name[21],int qty,int price){
curr = (struct node *) malloc(sizeof(node));
strcpy(curr->name,name);
curr->qty=qty;
curr->price=price;
curr->next = curr -> prev =NULL;
if(head==NULL){
head=tail=curr;
}else{
curr->prev=tail;
tail->next=curr;
tail=curr;
}
}
void popHead(){
if(head==tail){
curr=head;
head=tail=NULL;
free(curr);
}else{
curr=head;
head=head->next;
head->prev=NULL;
free(curr);
}
}
void pop(){
if(curr==head && curr==tail){
head=tail=NULL;
free(curr);
}else if(curr==head){
popHead();
}else if(curr==tail){
curr=tail->prev;
free(tail);
tail=curr;
tail->next=NULL;
}
else{
curr->prev->next=curr->next;
curr->next->prev=curr->prev;
free(curr);
}
}
void buyItem(){
char name [21];
int qty;
int price;
int len;
srand(time(0));
do {
printf("Masukkan input nama (max 20 huruf): ");
scanf("%[^\n]s",name);getchar();
len=strlen(name);
printf("\n");
}while (len>20);
printf("Masukkan input quantity: ");
scanf("%d",&qty);getchar();
printf("\n");
price=(rand() % (100000 - 10000 + 1)) + 10000;
if(qty!=0){
pushTail(name,qty,price);
printf("Item has been added to cart.\n");
}else{
printf("No item has been added to cart (user quantity input = 0).\n");
}
}
void showItem(){
if(head==NULL) {
printf("No items in cart\n\n");
}else {
printf("=====================================================\n");
printf("| List of items |\n");
curr = head;
while(curr != NULL){
printf("| %s | Rp %d | %d pc(s) |\n",curr->name,curr->price,curr->qty);
curr = curr->next;
}
printf("=====================================================\n");
}
}
void editCart(){
char input [21];
int len,found=0;
do{
printf("Input item name to edit [max 20 char]: ");
scanf("%[^\n]",input);getchar();
printf("\n");
len=strlen(input);
}while(len>20);
curr=head;
while(curr!=NULL){
if(strcmp(input,curr->name)==0){
found=1;
break;
}
curr=curr->next;
}
if(found==1){
int x;
printf("\nEdit Menu: \n\n");
printf("1. Delete from cart\n");
printf("2. Change quantity\n");
printf("3. Exit\n");
printf("--> ");
scanf("%d",&x);getchar();
printf("\n");
switch(x){
case 1 :{
pop();break;
}
case 2 :{
printf("Input new quantity for item: ");
scanf("%d",&curr->qty);getchar();
printf("\n");
if(curr->qty==0){
pop();
printf("Item has been deleted\n");
}else{
printf("Item quantity has been changed.\n");
break;
}
}
}
}else{
printf("Item not found. Please try again.\n");
editCart();
}
}
int checkOut(){
int total;
if(head==NULL) {
printf("No items left in cart\n\n");
return 0;
}else {
printf("=====================================================\n");
printf("| List of items left in cart |\n");
curr =head;
while(curr != NULL){
printf("| %s | Rp %d | %d pc(s) |\n",curr->name,curr->price,curr->qty);
total+=(curr->price*curr->qty);
curr = curr->next;
}
printf("=====================================================\n");
printf("=====================================================\n");
printf("|Total: %d|\n",total);
printf("=====================================================\n");
}
printf("Pay?\n");
printf("Y=Pay N=Back to Menu\n");
char yn;
printf("--> ");scanf("%c",&yn);getchar();printf("\n");
if(yn=='Y' || yn=='y'){
printf("Kindness is free.\n");
printf("No need to pay.\n");
printf("Have a good day !!!\n");
while(head!=NULL){
popHead();
}
return 1;
}else if (yn=='N' || yn=='n'){
return 0;
}
}
int main (){
int input,flag=0;
while (flag==0){
printf("\nMenu: \n\n");
printf("1. Buy Item\n");
printf("2. View Cart\n");
printf("3. Edit Cart\n");
printf("4. Check Out\n");
printf("5. Exit\n\n");
printf("--> ");
scanf("%d",&input);getchar();
printf("\n");
switch (input) {
case 1 : buyItem();break;
case 2 : showItem();break;
case 3 : editCart();break;
case 4 : flag=checkOut();break;
case 5 : flag=1;break;
}
}
return 0;
}
