Collision Resolution in Hash Table (by linked list)

Colision Resolution ( By separate chaining using linked list )

We have seen hash implementation in Array , where we can fill only one value in one slot. If new value comes it overwrites previous value. But using collision resolution by linked list we can resolve this problem and preserve the values. Whenever new value comes to the slot which is already filled then we can put new value in linked list associated with that slot.

In this method performance degrades when more values are matching with same slot.

The below picture is for hash table with collision resolution using channed linked list.

Hash function is key % 5

 

Collision Resolution in Hashtable in C

 

C Code for Collision Resolution in Hash Table is below

 

Hash implementation in Array (Direct Addressing)

C code to implement hash using array.

Description :

Hash can store only integer value. One slot can store only one value. Hash function is mod ( value % slots) .

 

Queue implementation in C using linked list

 

Queue implementation in C using linked list

Queue structure :

 

C progam to Queue implementation using linked list , Queue implementation in C using linked list

stack implementation using linked list in c

 

C program to implement stack using linked list.

 

 

 

 

Memory Efficient doubly linked list in C

So far we have seen doubly linked list which have two pointers next and previous. but in efficient doubly linked list we will use only one pointer to move at next and previous nodes.

We know XOR  is used for bit recovery the same concept we will use here to store both the ptr (next and previous) information in single variable.

structure for efficient doubly linked list :

struct ednode{
int val;
struct ednode *ptr;
}

Suppose we have linked list of 4 nodes [ W | X | Y | Z ]

W->ptr= NULL ^ X

X->ptr= W ^ Y

Y->ptr= X ^ Z

Z->ptr= Y->NULL

To move at W from X 

(W^Y)^Y ==> which is (X->ptr^Y) ==> which is W

similar way to move at Y from X

(W^Y)^W ==> which is (X->ptr^W) ==> which is Y

 

 

Stack implementation using array in C

Stack implementation using array in C

Stack has following operations :

push // To add value at top of stack

pop // To remove value from top of stack

isstack_empty // To check whether stack is empty or not

isstack_full // To check whether stack is full or not

 

Stack implementation using array in C

count perfect numbers c program

Counting perfect numbers c program in array :

A perfect number is a positive integer that is equal to the sum of its integer positive divisors(excluding itself).

To know list of perfect nos click here 

 

 

Binary Search Tree in C

Binary search tree in c

Binary Search Tree , 8 is root node ,left branch has nodes whose value are less than 8 and right branch has nodes whose values are greater than 8
Binary Search Tree , 8 is root node ,left branch has nodes whose value are less than 8 and right branch has nodes whose values are greater than 8

To read about binary search tree click here 

/*
*********** Binary Search Tree Menu ***********
[1] Insert value
[2] Print Tree (Preorder)  
[3] Print Tree (inorder)  
[4] Print Tree (postorder)  
[5] Exit
*/

 

Binary search tree in c.

Circular Linked List in C

Circular Linked List in C.

Circular linked list is a linked list whose last node points to the head of list.

Structure of Circular linked list

struct clnode{
int val;
struct clnode *next;
};

/*
*********** Circular List Menu ***********
[1] Insert value
[2] Print Circular List
[3] Print Length of list
[4] Insert at Beginning
[5] Delete front node
[6] Delete rear node
[7] Exit
*/