Category Archives: Linked List

Under this section you will learn linked list operations.

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

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

 

 

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

 

Singly Linked List in C

Data Structure Problems :

Singly Linked List :

Singly linked list has following features .

It contains int data value and next pointer which points to same kind of linked list node.

It is an extensive use of Dynamic Memory Allocation & structure.

 

Structure defined in following way :

struct snode{

int val;

struct snode *next;

};

Declaring a snode variable

struct snode node;

node has following variable to access

val and ptr

A C program on singly linked list.

functions used :

int create_snode(int val,struct snode **node); // To create node

int insert_snode(struct snode **head,struct snode **node );// To insert node

struct snode *find_snode(struct snode **head,int val); // To find node

int delete_snode(struct snode **head,struct snode **node); // To delete node from list

void print_sll(struct snode **head); // To print list

void reverse_sll(struct snode **head); // To reverse list

struct snode* findnthnode(struct snode **head,int lpo);// To find nth node from last in list

 

Code :

/* Singly Linked List Code by Codingstreet.com */

/* Following Features are provided */

/*

Singly Linked List Menu :

[1] Insert Node:

[2] Delete Node:

[3] Print Node:

[4] Reverse List:

[5] Find Nth node from Last :

[6] Exit:

*/