1. Double Linked List.
Double linked list or two-way Linked List.
Double linked list is a
list linked with two pointer, One for next data and one for previous data.
Advantages
1.
· Double Linked List can traverse forward and backward.
2.
· More efficient in Delete operation.
3.
· Can quickly insert a new node.
Disadvantages
1.
· Every node needs extra space for previous pointer.
2.
· All operations require extra previous pointer to be maintained.
Operation.
Like single linked list
there are Insert and Delete operation in Double Linked List. Both have same
function with Operation in single linked list.
1.Operation: Insert
Just like in a single
linked list, first we should allocate the new node and assign the value to it,
and then we connect the node with the existing linked list.
In double linked list we
have 3 insert too
·
Insert head:
we insert new node in front of the linked list.
struct tnode* node =
(struct tnode*)malloc(sizeof(struct tnode));
node->value = x;
node->next = head;
node->prev = NULL;
if (head !=
NULL)
head->prev = node;
head = node;
·
Insert tail: we insert new node behind the linked
list.
struct tnode *node = (struct
tnode*) malloc(sizeof(struct tnode));
node->value = x;
node->next = NULL;
node->prev = tail;
tail->next = node;
tail = node;
·
Insert
middle: we insert new node at the middle of linked list.
struct tnode *a = ??;
struct tnode *b = ??;
struct tnode *node = (struct tnode*)
malloc(sizeof(struct tnode));
node->value = x;
node->next = b;
node->prev = a;
a->next = node;
b->prev = node;
2.Operation: Delete
There are 4 conditions we
should pay attention when deleting:
·
· The node to be deleted is the only node in linked list.
·
· The node to be deleted is head.
·
· The node to be deleted is tail.
·
· The node to be deleted is not head or tail
Circular doubly linked list
Circular doubly linked list
is similar as circular single linked list. but in circular doubly there are two
pointer. so the first node point to last node and last node pointing to first
node.
2. Stack And Queue
1. Stack
Stack is one of data structure concept that store data in orderly way.
For stack the data order is LIFO or Last In First Out manner. It’s
was like you see a pile of chair it’s was make with chair stacked from the
bottom one but when you need a chair you take the last (upper one) first.
There are 2 way you can make a stack. The first one is using array and
the second is using linked list. Even thought using array is easier when using
array, we need to declare a fixed size, but linked list doesn’t need to declare
size and can keep make a new space.so when we don’t know the size of stack we
make it using linked list.
a. Stack Operation
There are 3 operation for stack:
- Push(x) : push is operation to add x to top of the stack.
- Pop() :pop is operation to remove an
item from the top of the stack.
- Top() :top is operation to return the
top from the stack.
We must remember to use a same push and pop so if you push from head you
need to pop from head to because LIFO order.
b. Stack Application
Stacks are widely used to:
- Reverse the order of data
- Convert infix expression into postfix
- Convert postfix expression into infix
- Backtracking problem
- System stack is used in every recursive function
- Converting a decimal number into its binary equivalent
- Depth First Search.
2. Infix, Postfix, and Prefix Notation
Infix, Postfix, and Prefix Notation are one of stack application. For simple
they can be explained like:
-
Prefix :
operator is written before operands
- Infix : operator is written
between operands
-
Postfix :
operator is written after operands
3. Queue
Queue is like stack both are concept that store data in an order. but in
queue we use FIFO or First In First Out order. If stack was like a pile of
chair queue was like a line for restaurant if you line first, you can go in
first.
To
make queue we use the same ways with stack. We can make queue using array and
using linked list. Same with
stack, using array are easier but because the size is fixed, we need to use
linked list if we don’t know the size.
a.
Queue Operation
There are 3 operation for queue:
- Push(x) :push is operation to add x to the back of the queue.
- Pop() :pop is operation to remove an item
from the front of the stack.
- Top() :top is operation to return the front
from the stack.
If stack must use the same push and pop in queue, we must use different
push and pop so if you push the front you must pop the back. It was because the
first in will go out first (FIFO).
b. Queue Application.
- Deques
- Priority Queues
- Breadth First Search
c. Type of Queue
- Circular queue
Circular queue is queue where the first index is connected with the last
index.so first index will come after last index.
- Deques
Deques is queue where we do deletion and insertion from both side. There
are 2 type of queue, input restriction and output restriction deque. Input
restriction mean deletion can happen at both side but insertion can only happen
in one side and the output restriction is the opposite.
- Priority queue
Priority
queue is queue where we assign an priority to each element. Queue will procced
the highest priority first, if there are same priority it will procced with
First Come First Served basis.
4. Deep first search and breadth first search
a. Deep First Search
Deep first search (DFS) is
algorithm for traversing in tree or graph. DFS start at the root
of the tree and explore ass
far as possible along each branch before backtracking.
b.Breadth First
Search
Breadth first search (BFS)
like DFS is also an algorithm for traversing or searching in a tree or graph.
BFS start at the root of the tree and explore all neighboring nodes level per
level until we find the goal.
The difference between both are only in the data
structure concept that used. DFS use stack while BFS use queue.
3. Hashing And Binary Tree.
1. Hashing
Hashing are a transformation from string to a
shorter value or a value that represent that string. It used to take index or
item in database because of the shorter time for finding item using hash key.
Other than faster data take. Hashing used in
encrypt digital signature. Digital signature modified with hash function into
hash value and receipt to receiver. using the same hash function, receiver will
get the message-digest and will compare it with received
message-digest. (they must be identical.)
Hash function used for indexing value or
original key and will used every time the data will be taken. So, hashing will
always operate in one way and don’t need to “reverse engineer” hash function
with analysing hash value.
There are many ways to hash a string into a
key. The following are some of the important methods for constructing hash
functions.
• Mid-square
• Division (most common)
• Folding
• Digit Extraction
• Rotating Hash
2. Hash Table
Hashing can be used to make hash table
thought hash function. Hash table is a table where we store a data temporary
for efficiency data searching. Hash table will have index of the table in from
of hashed key while the value is the original string.
The size of hash table is usually several
orders of magnitude lower than the total number of possible string, so several
string might have a same hashed-key. If that happen that will induce a
collision because two data will have a same key.to resolve it we can use one of
this method:
A. Close Hashing
Close Hashing use empty memory without using
memory outside of array used. Close hashing search new address if the aimed
address is already filled. There are 3 way to search for another address.
a. Linear Probing,
If the array is filled, linear probing will
check next array until get empty array. Linear Probing use ((h+1) mod m)
equation.
b. Quadratic Probing
Quadratic Probing search new address using more complex
quadratic
equation. There is no fixed equation for this probing you can make
the
formula you will use.
Example:
h,(h+i2)mod m,(h-i2)mod m, … ,(h+((m-1)/2)2)mod m, (h-((m-1)/2)2)mod m
with i =
1,2,3,4, … , ((m-1)/2).
This mean
you will check (h+1)mod m, if filled then check (h-1)mod m, if
filled
check(h+1)mod m, if filled to check(h+4)mod m, and continue until
get empty array.
c. Double Hashing
Double Hashing use second hash function to save
collided key value. Second hash function used when the original hash function
is filled with hash function itself. But this method need more array address
than the data and need more memory to minimize collision.
B. Open Hashing
Basically, open hashing is making the value of hash
table into array of pointer that followed by linked list, with the head point
to the array of pointer and following data is connected to the head. The
downside is this method will make a long LinkedList if the data override each
other.
3. Binary Tree
A
tree is a non-linear data structure that represents the hierarchical
relationships among the data objects using connected node from up to down. In
tree each node will have maximum two child(node) connected with the node.
They
are named left and right. The node in the tree doesn’t have to be stored
contiguously and can be stored anywhere and linked by pointers. Binary tree is
a tree that have maximum 3 level of root (upper node). Binary tree is saved as
implicit in array, and this method will save memory if you make a full binary
tree.
In
binary tree the child node will be found at i+1, and i+2 index, even when the
father (upper node) will found at ((i-1)/2)
A. Element of
binary tree
· Node
· Root is the upper node
· Leaf is root without children
· Sibling is two node who have same parent
· Degree of node is the total sub tree of the node.
· Height/Depth is the maximum degree of nodes in a
tree.
· If there is a line that connects p to q, then p is
called the ancestor of q, and q is a descendant of p.
B. Type of Binary
tree
· PERFECT binary tree is a binary tree in which every
level are at the same depth.
· COMPLETE binary tree is a binary tree in which
every level, except possibly the last, is completely filled, and all nodes are
as far left as possible. A perfect binary tree is a complete binary tree.
· SKEWED binary tree is a binary tree in which each
node has at most one child.
· BALANCED binary tree is a binary tree in which no
leaf is much farther away from the root than any other leaf (different
balancing scheme allows different definitions of “much farther”).
4. Binary Search Tree
A. Binary Search Tree
Binary search tree (BST) are data structure with binary tree concept or
known as sorted version of binary tree are made to help fast searching, rapid
sorting and easy insertion and deletion.
There are some rules for BST:
· Every node has a value
· Left value will always smaller than the root
· Right value will always bigger than the root
· Right tree or left tree can be another root or can have child, so BST
have recursive function.
These rules are there to made searching process efficient.
B. Binary Search Tree Operation
BST have three basic operation
1. Find/Searching
Because BST is sorted searching in BST is easy. We only need to use some
rules.
1. Start searching at root.
2. If the root contains the value, then we can return the value and stop
searching process.
3. If the value is less than root key then search recursively on left sub
tree until the value is found, otherwise if the value is higher than
recursively search on right sub tree.
2. Insertion
As we know inserting is inputting new data into the tree. Insertion in
BST is done recursively.
1. We give the value we want to input.
2. We begin at root.
3. If the root value is lower then the value then goes into left sub tree
and make the value as root value, otherwise go into right sub tree.
4. Repeat until we found an empty node to put new value.
3. Remove/deletion
There are 3 cases which should be considered:
1. If the deleted node is in a leaf, just delete that node
2. If the deleted node is in a node which has one child, delete that node
and connect its child to its parent
3. If the deleted node is in a node which has two children, find the right
most child of its left sub tree (node P), replace its with P and remove P
recursively. (or alternately you can choose the left most child of its right
sub tree)
5. Assignment
Goal: To strengthen your coding skill,
create an application with minimarket concept,
Case: Minimarket Menu.
Answer:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
struct node{
int qty;
char product[100];
int price;
struct node*next;
struct node*prev;
}*head=NULL,*tail=NULL;
int jumlah=0;
void input(int data,char nama[]){
struct node*Node=(struct node*)malloc(sizeof(node));
Node->qty=data;
strcpy(Node->product,nama);
Node->price=((rand()+1)%100)*100;
Node->next=NULL;
Node->prev=NULL;
if(head==NULL){
head=tail=Node;
}else{
Node->prev=tail;
tail->next=Node;
tail=Node;
}
jumlah++;
}
void editqty(int data,char nama[]){
struct node*Node=head;
while(strcmp(Node->product,nama)!=0){
Node=Node->next;
}
Node->qty=data;
}
void deletei(char nama[]){
int i;
struct node*Node=head;
while(strcmp(Node->product,nama)!=0){
Node=Node->next;
}
if(head==tail){
head=tail=NULL;
free(Node);
}else if(Node==head){
head=Node->next;
free(Node);
head->prev=NULL;
}else if(Node==tail){
tail=Node->prev;
free(Node);
tail->next=NULL;
}else{
Node->prev->next=Node->next;
Node->next->prev=Node->prev;
free(Node);
}
}
void print(){
struct node*Node=head;
while(Node!=NULL){
printf("
%-3d | %-20s | Rp.%-9d | %-9d
|\n",Node->qty,Node->product,Node->price,Node->qty*Node->price);
Node=Node->next;
}
}
int printt(){
int temp=0;
struct node*Node=head;
while(Node!=NULL){
temp+=(Node->price*Node->qty);
Node=Node->next;
}
return temp;
}
int main(){
int menu,qty;
char Nama[100];
do{
printf(" Menu \n");
printf("========================================================\n");
printf("
Qty | Nama Barang | Harga Barang | total
|\n");
print();
printf("========================================================\n");
printf("1.Input
item\n");
printf("2.Edit qty\n");
printf("3.Delete
wrong input\n");
printf("4.Check
Out\n");
printf("Choose
: ");scanf("%d",&menu);getchar();
switch(menu){
case
1:
printf("Input
Name: ");scanf("%[^\n]",Nama);getchar();
printf("Input
qty: ");scanf("%d",&qty);getchar();
input(qty,Nama);
break;
case
2:
printf("Input
Name: ");scanf("%[^\n]",Nama);getchar();
printf("Input
qty: ");scanf("%d",&qty);getchar();
editqty(qty,Nama);
break;
case
3:
printf("Input
Name: ");scanf("%[^\n]",Nama);getchar();
deletei(Nama);
break;
}
}while(menu!=4);
printf(" Dreammers Market \n");
printf("========================================================\n");
printf(" Qty
| Nama Barang | Harga Barang | total
|\n");
print();
printf("Total:
Rp.%d\n",printt());
printf("========================================================\n");
printf(" Kindness is free \n");
getchar();
return 0;
}
