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 C Code for Collision Resolution in Hash Table is below

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

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

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 ***********
 Insert value
 Print Circular List
 Print Length of list
 Insert at Beginning
 Delete front node
 Delete rear node
 Exit
*/

Doubly Linked List in C

Doubly Linked List in C

Structure for doubly linked list

struct dnode{
int val;
struct dnode *next,*prev;
};