Tag Archives: Linked List

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

 

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 ***********
[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
*/

 

Doubly Linked List in C

Doubly Linked List in C

Structure for doubly linked list

struct dnode{
int val;
struct dnode *next,*prev;
};
/* Doubly linked list Menu
[1] Insert Node:
[2] Delete Node:
[3] Print List:
[4] Print List Reverse :
[5] Find Node :
[6] Exit:
*/