Data Structures – 20ADS33

Module 4
Linked List
Other list structures
Hashing
Syllabus
Module 1 Data Structure operations
Sorting algorithms
Dynamic memory allocation

Module 2 Stacks
Representation of Stacks in C
Applications
Module 3 Queues
Module 4 Linked List
Other list structures
Hashing

Module 5 Binary Trees

Contents
Linked Lists: Introduction and definition, representation of linked list in memory,
primitive operations on linked list, Linked Implementation of Stacks, getnode and
free node Operations, Linked Implementation of Queues

Other list structures - Circular lists and it’s primitive operations, Doubly linked
lists and it’s primitive operations, Applications of linked lists: Addition of long
positive integers, addition of Polynomials.

Hashing: Hash tables, Hash function, Overflow handling: Open Addressing,

Chaining
Linked list Data Structure

A linked list is a linear data structure that includes a

series of connected nodes. Here, each node stores
the data and the address of the next node.
For example,

Special name is given to the address of first node as Head and last
node in the linked list can be identified because its next portion
points to Null
Linked list Data Structure
• A node contains two fields i.e. data stored at that particular
address and the pointer which contains the address of the next
node in the memory.
• The last node of the list contains pointer to the null.
Uses of Linked List
✓The list is not required to be contiguously present in the memory.
The node can reside any where in the memory and linked together
to make a list. This achieves optimized utilization of space.
✓list size is limited to the memory size and doesn't need to be
declared in advance.
✓Empty node can not be present in the linked list.
✓We can store values of primitive types or objects in the singly
linked list.
Why use linked list over array?
Array contains following limitations:
1.The size of array must be known in advance before using it in the program.
2.Increasing size of the array is a time taking process. It is almost impossible
to expand the size of the array at run time.
3.All the elements in the array need to be contiguously stored in the memory.
Inserting any element in the array needs shifting of all its predecessors.
Linked list is the data structure which can overcome all the limitations
of an array. Using linked list is useful because,
1.It allocates the memory dynamically. All the nodes of linked list are non-
contiguously stored in the memory and linked together with the help of
pointers.
2.Sizing is no longer a problem since we do not need to define its size at the
time of declaration. List grows as per the program's demand and limited to
the available memory space.
Singly Linked List
Arrange the name of the students
according to the 1st letter of their names
Michael
Rock
John
Smith
Tony
Alpha
Mark

Alpha John Mark Michael Rock Smith Tony

How to maintain this list in the memory
There are two ways
1. Array
2. Linked List
Types of Linked List
1. Single Linked List: Navigation is forward only
2. Doubly Linked List: Forward and Backward
navigation is possible.
3. Circular Linked List: Last Element is linked to
the first element
 Single Linked List
A Single Linked List is a list made up of nodes that
consists of two parts:
▪ Data
▪ Link
Contains the
Contains address of the
the actual Data Link next node of the
data list
Node
 Representation of the single linked
list
Suppose we want to store a list of the numbers: 23, 54, 78, 90

23 54 78 90
1000 2000 3000 4000

23 2000 54 3000 78 4000 90 Null

1000 2000 3000 4000
 How to access the 1st node of the
linked list
Suppose we want to store a list of the numbers: 23, 54, 78, 90

23 2000 54 3000 78 4000 90 Null

1000 2000 3000 4000

1000
Head
Self Referential Structure: It is a structure which contains
a pointer to a structure of the same type.

struct abc {
int a;
char b;
struct abc *self;
};
We use self referential structure for creating a node of the
single linked list
Node representation in C

struct node {
Node
int data;
struct node *link;
};
Creating a node in C
#include<stdio.h>
#include<stdlib.h>
struct node {
int data;
struct node *link;
Node
};
void main() Null
{
struct node *head = Null; head
1000
head=(struct node *)malloc(sizeof(struct node ));
head->data = 45; head
head->link=Null;
45 Null
printf(“%d”, head->data); 1000
} 1000
head
Traversal if(head==0)
#include <stdio.h> {
#include <stdlib.h> head=temp=newnode;
struct node { }
int data; else
{
struct node* next;
temp->next=newnode;
};
temp=newnode;
struct node *head, *newnode, *temp;
}
head=0;
printf(“Do you want to continue (0, 1)\n”);
int choice; scanf(“%d”, & choice);
while(choice) } TraversingCode
{ temp=head;
newnode = (struct node*)malloc(sizeof(struct node)); while(temp!=0)
printf(“Enter the data\n”); {
scanf(“%d”, &newnode->data); printf("%d", temp->data);
newnode->next=0; temp=temp->next;
}
 Operations on Singly Linked List
• Insertion
The insertion into a singly linked list can be performed at different positions.
Based on the position of the new node being inserted, the insertion is categorized
into the following categories.
Sl. No Operation Description
1. Insertion at It involves inserting any element at the front of the list. We just
beginning need to a few link adjustments to make the new node as the
head of the list.
2. Insertion at end It involves insertion at the last of the linked list. The new node
of the list can be inserted as the only node in the list or it can be inserted
as the last one.
3. Insertion after It involves insertion after the specified node of the linked list. We
specified node need to skip the desired number of nodes in order to reach the
node after which the new node will be inserted
 head
500
Insertion at 100

beginning 7 200 1 300 9 0

struct node { 100 200 300
int data; 2 100
struct node *next; 500
}; 500
newnode
struct node *head, *newnode;
newnode=(struct node *) malloc(sizeof(struct node));

printf("\nEnter value\n");
scanf("%d",&newnode->data);
newnode->next = head;
head = newnode;
printf("\nNode inserted");
}
 head
500
Insertion at end 100

0 7 200 1 300 9 400

struct node {
int data; 300 100 200 300
200
struct node *next;
100 5 0
};
temp 400
400
struct node *head, *newnode *temp;
newnode = (struct node *) malloc(sizeof(struct node)); newnode

printf("\nEnter value\n");
scanf("%d",&newnode->data);
newnode->next = 0
temp=head;
while(temp->next!=0)
{
temp=temp->next;
}
temp->next=newnode;
 newnode
Insertion at specified location 100 400 5 400
400
int pos, i=1;
struct node { 7 200 1 400 9 0
int data;
struct node *next; 100 200 300
100
};
struct node *head, temp
3 pos
*newnode, *temp;
newnode =
(struct node *) malloc(sizeof( 21 i
struct node));
printf("\nEnter the
position");
scanf("%d",&pos);
if(pos>count)
{
printf(“Invalid position”);
} printf("Enter the data");
else scanf("%d", &newdata->data);
{ newnode->next=temp->next;
temp=head; temp->next=newnode;
while(i<pos)
{
Deletion
The Deletion of a node from a singly linked list can be performed at
different positions. Based on the position of the node being deleted,
the operation is categorized into the following categories.

Sl. No Operation Description

1 Deletion at beginning It involves deletion of a node from the beginning of the
list. This is the simplest operation among all. It just
need a few adjustments in the node pointers.
2 Deletion at the end It involves deleting the last node of the list. The list can
either be empty or full.
3 Deletion after specified node It involves deleting the node after the specified node in
the list. we need to skip the desired number of nodes to
reach the node after which the node will be deleted.
This requires traversing through the list.
Deletion head

struct node { 100

int data;
5 200 3 300 9 400 1 0
struct node* next;
100 200 300 400
};
100
struct node *head;
if(head==Null) temp
{ Delete from the beginning
Printf(“List is empty’):
}
else{
DeleteFromBeg()
{
struct node *temp;
temp=head;
head=head->next; or temp=temp->next
head=temp;
free(temp);
struct node {
int data; head

struct node* next; 200

Delete from the End
}; 3 300 9 400 1 0
struct node *head, *temp; 200 300 400
DeleteFromEnd() 200
{ temp 200 300 temp
struct node *prevnode; Previous node Previous node
temp=head;
while(temp->next!=0)
{
prevnode=temp;
temp=temp->next;
}
if(temp==head){
head=0;
}
else{
prevnode->next=0;
}
struct node {
int data; head

struct node* next; 100

Delete from the Pos
}; 5 200 6 300 1 400 2 0
struct node *head, *temp; 100 200 300 400
DeleteFromPos()
{ temp temp 300
struct node *nextnode; nextnode
int pos, i=1;
temp=head;
printf(“Enter the position\n”);
Pos = 3
scanf(“%d”, &pos);
while(i<pos-1)
{
temp=temp->next;
i++;
}
nextnode=temp->next;
temp->next=nextnode->next;
free(nextnode);
Implementation of stack using linked list
head
top
200
300
7 400 8 100 1 0 2 0
8 200 5 100 2 0 200 400 100 200
300 200 100
struct node
{
8 200
int data;
struct node *link; 300
}; 5 100
struct node *top = 0;
void push(int x) 200
{
2 0
struct node *newnode;
100
newnode=(struct node *)malloc(sizeof(struct node));
newnode->data=x;
newnode->next=top;
top=newnode;
}
Implementation of stack using linked list
head
top
200
300
7 400 8 100 1 0 2 0
8 200 5 100 2 0 200 400 100 200
300 200 100

void display()
{ 8 200
void peek()
struct node *temp; 300
{
temp=top;
if(top==0) 5 100
if(top==0)
{
{ 200
printf("stack is empty\n");
printf("stack is empty\n");
} 2 0
}
else 100
else
{
{
printf("Top element us %d", top->data);
while(temp!=0)
}
{
}
printf("%d", temp->data);
temp=temp->link;
}}}
Implementation of stack using linked list
head
top
200
300
7 400 8 100 1 0 2 0
8 200 5 100 2 0 200 400 100 200
300 200 100
void pop()
{ 8 200
struct node *temp;
300
temp=top;
if(top==0) 5 100
{
200
printf("No elements");
} 2 0
else 100
{
printf("%d", top->data);
top=top->link;
free(temp)
}
}
Implementation of Queue using Linked List
Front rear
100 100 200 300
struct node
5 0 200 0 300 -3 0
{
int data; 100 200 300
void main()
struct node *next; if(front==0&&rear==0) {
}; { front=rear=newnode;
} enqueue(5);
struct node *front=0;
else enqueue(0);
{
struct node *rear=0; rear->next=newnode;
enqueue(-3);
void enqueue(int x) rear=newnode; } } display();
{ dequeue();
struct node *newnode; peek();
newnode=(struct node *) malloc(sizeof(struct node));
newnode->data=x;
}
newnode->next=0;
}
Implementation of Queue using Linked List
Front rear
100 100 200 300
struct node {
5 0 200 0 300 -3 0
int data;
struct node *next; 100 200 300
void main()
}; else {
{
struct node *front=0; temp=front; enqueue(5);
struct node *rear=0;
while(temp!=0) { enqueue(0);
printf(“%d”, temp->data);
void display() { temp=temp->next;
enqueue(-3);
struct node *temp; } display();
if(front==0 && rear ==0) dequeue();
{ peek();
printf(“Queue is empty);
}
}
Implementation of Queue using Linked List
Front rear

struct node { 100 100 200 300

int data; 5 0 200 0 300 -3 0

struct node *next;
200
}; 100
100 300
void main()
temp {
struct node *front=0; enqueue(5);
struct node *rear=0; else enqueue(0);
void dequque() { {
struct node *temp; enqueue(-3);
front=front->next; display();
temp=front
if(front==0 && rear ==0) free(temp) } dequeue();
{ peek();
printf(“Queue is empty); }
}
Doubly Linked List
Doubly linked list is a complex type of linked list in which a node contains
a pointer to the previous as well as the next node in the sequence.
Therefore, in a doubly linked list, a node consists of three parts: node data,
pointer to the next node in sequence (next pointer) , pointer to the previous
node (previous pointer). A sample node in a doubly linked list is shown in
the figure.
Doubly Linked List
A doubly linked list containing three nodes having numbers from 1
to 3 in their data part, is shown in the following image.
Doubly Linked List
In C, structure of a node in doubly linked list can be given as :

struct node
{ The prev part of the first node and
struct node *prev; the next part of the last node will
always contain null indicating end in
int data; each direction.
struct node *next;
}
Doubly Linked List
In a singly linked list, we could traverse only in one direction,
because each node contains address of the next node and it doesn't
have any record of its previous nodes.

However, doubly linked list overcome this limitation of singly linked

list. Due to the fact that, each node of the list contains the address
of its previous node, we can find all the details about the previous
node as well by using the previous address stored inside the
previous part of each node.
Memory Representation of a doubly linked
list
Memory Representation of a doubly linked list is shown in the
following image. Generally, doubly linked list consumes more space
for every node and therefore, causes more expansive basic
operations such as insertion and deletion.

However, we can easily manipulate the elements of the list since the
list maintains pointers in both the directions (forward and
backward).
• In the following image, the first
element of the list that is i.e. 13
stored at address 1. The head
pointer points to the starting
address 1. Since this is the first
element being added to the list
therefore the prev of the
list contains null. The next node
of the list resides at address 4
therefore the first node contains 4
in its next pointer.
• We can traverse the list in this
way until we find any node
containing null or -1 in its next
part.
Operations on doubly linked list
• Node Creation

struct node
{
struct node *prev;
int data;
struct node *next;
};
struct node *head;
 Operations
Sl. No Operations Descriptions
1 Insertion at beginning Adding the node into the linked list at beginning.
2 Insertion at end Adding the node into the linked list to the end.
3 Insertion at specified Adding the node into the linked list at the specified node.
node
4 Deletion at beginning Removing the node from beginning of the list
5 Deletion at the end Removing the node from end of the list.
6 Deletion of the node Removing the node which is present just after the node
having given data containing the given data.
7 Searching Comparing each node data with the item to be searched and
return the location of the item in the list if the item found
else return null.
8 Traversing Visiting each node of the list at least once in order to
perform some specific operation like searching, sorting,
display, etc.
Insertion Operation
head
100

struct node{
int data; 0 5 200 100 4 250 200 2 0
struct node *prev; 250
head 100 200
struct node *next; tail
}; 0 100 0 100 200 250
struct node *head, *tail; tail
0 5 0 200 0 100 6 0
void createdll(){
struct node *newnode; 100 200
while(choice) {
newnode=(struct node*)malloc(size of(struct node) if(head==0){
head=0; head=tail=newnode;
printf(“Enter the data”); }
scanf(“%d”, &newnode->data); else{
newnode->prev=0; tail->next=newnode;
newnode->prev=tail;
newnode->next=0;
tail=newnode;
printf(“Do you want to continue(1,0)”);
scanf(“%d”, &choice);
Insertion Operation:
head
Insert at the beginning
150 500

struct node{
int data; 0 500 5 100 150 4 200 100 1 0
struct node *prev; 200
150 100
struct node *next;
}; 200
0 6 0 150 500
struct node *head, *tail; tail
newnode
void insertatbeg(){ 500
struct node *newnode;
newnode=(struct
node*)malloc(size of(struct head->prev=newnode;
node); newnode->next=head;
head=0; head=newnode;
printf(“Enter the data”); }
scanf(“%d”, &newnode->data);
newnode->prev=0;
newnode->next=0;
Insertion Operation:
head
Insert at the end
tail
500
200
struct node{
int data; 500 5 100 150 4 200 100 1 0 400
struct node *prev; 200
150 100
struct node *next;
};
0 6 150
struct node *head, *tail; 0 200 7 0
void insertatend(){ 500
400
struct node *newnode;
newnode=(struct node*)malloc(size of(struct node); 400
head=0; tail->next=newnode; newnode
printf(“Enter the data”); newnode->prev=tail;
scanf(“%d”, &newnode->data); tail=newnode;
newnode->prev=0; }
newnode->next=0;
Insertion Operation:
head
Insert
temp
at the pos
tail
150 150 100
200
500 500
struct node{
int data; 500 5 100 150 4 200 100 1 0
struct node *prev; 200
150 100
struct node *next;
0 100 7 0 200
};
struct node *head, *tail; struct node *newnode, *temp; 500 newnode
void insertatpos() { temp=head;
int pos, i=1; newnode=(struct node*)malloc(size of(struct node);
printf(“Enter the position”); head=0;
scanf(“%d”, &pos); printf(“Enter the data”);
if(pos<=0 && pos>count){ scanf(“%d”, &newnode->data);
printf(“Invalid position”); newnode->prev=0;
newnode->prev=temp;
} newnode->next=0;
newnode->next=temp->next;
else if(pos==1){ while(i<pos-1) {
temp->next=newnode;
insertatbeg(); temp=temp->next;
newnode->next->prev=newnode;
} i++;
}
else{ }
 deletefromBeg()
Deletion Operation:
head
Delete
temp
from Beg deletefromEnd()
deletefromPos()
200 400 200

0 7 400 200 1 150 400 6 0

200 400 150

void deletefromBeg(){ 150

struct node *temp; tail
if(head==0)
{
printf(“List is empty”);
}
else{
temp=head;
head=head->next;
head->prev=0;
free(temp);
}
Deletion Operation:
head
Delete from End
200

0 7 400 200 1 150 0 400 6 0

200 400 150

void deletefromEnd(){ 150 150 400

struct node *temp; tail
temp
if(tail==0)
{
printf(“List is empty”);
}
else{
temp=tail;
tail->prev->next=0;
tail=tail->prev;
free(temp);
}
 deletefromBeg()
Deletion Operation:
head
Delete
temp
from
temp
Pos
temp deletefromEnd()
deletefromPos()
200 200 100 500

0 3 100 200 1 500 100 1 150 500 9 0

200 100 500 150
void deletefromPos(){ 150
struct node *temp;
temp=head; tail
int pos,i=1;
printf(“Enter the position”);
scanf(“%d”, &pos);
while(i<pos){
temp=temp->next;
i++;
}
temp->prev->next=temp->next;
temp->next->prev=temp->prev;
free(temp);
}
Circular Linked List
• Circular Linked List is a variation of Linked list in which the first
element points to the last element and the last element points to
the first element. Both Singly Linked List and Doubly Linked List
can be made into a circular linked list.
Singly Linked List as Circular
• In singly linked list, the next pointer of the last node points to the
first node.
Circular Linked List
Doubly Linked List as Circular
• In doubly linked list, the next pointer of the last node points to the first node and
the previous pointer of the first node points to the last node making the circular
in both directions.
Circular Singly Linked List
• In a circular Singly linked list, the last node of the list contains a pointer to the
first node of the list. We can have circular singly linked list as well as circular
doubly linked list.
• We traverse a circular singly linked list until we reach the same node where we
started. The circular singly liked list has no beginning and no ending. There is
no null value present in the next part of any of the nodes.
• The following image shows a circular singly linked list.
Memory Representation of circular
linked list:
 Operations on Circular Singly linked list:
• Insertion
Sl. No Operation Description
1 Insertion at beginning Adding a node into circular singly linked list at the beginning.
2 Insertion at the end Adding a node into circular singly linked list at the end.
3. Insertion at the specified loc Adding a node into circular singly linked list at the specified
location

• Deletion & Traversing

Sl. No Operation Description
1 Deletion at beginning Removing the node from circular singly linked list at the beginning.
2 Deletion at the end Removing the node from circular singly linked list at the end.
3 Deletion from the Removing the node from circular singly linked list from the specified loc
specified loc
4 Searching Compare each element of the node with the given item and return the
location at which the item is present in the list otherwise return null.
5 Traversing Visiting each element of the list at least once in order to perform some
Implementation of Circular Linked List
struct node
temp->next=head;
{
printf(“Enter your choice (1 or 0)”);
int data;
scanf(“%d”, &choice);
struct node *next;
}}
};
struct node *head; head
void createCLL() 200
{ int choice =1;
struct node *newnode, *temp;
6 150 7 300 1 100 9 200
head=0;
while(choice){ 200 150 300 100
newnode=(struct node*)malloc(sizeof(struct node));
printf(“Enter the data”);
scanf(“%d”, &newnode->data);
newnode->next=0;
if(head==0)
{
head=temp=newnode;
}
else{
temp->next=newnode;
temp=newnode; }
Traversing

struct node {
int data;
struct node *next;
};
struct node *head;
void display()
{
struct node *temp;
if(head==0) {
printf(“List is empty”);
}
else
{
temp=head;
while(temp->next!=head){
printf(“%d”, temp->data);
temp=temp->next;
}
printf(“%d”, temp->data);
}}
 head tail
struct node
200 200 100 Create using head and tail
{
int data;
struct node *next; 7 100 1 200
}; 200 100
struct node *head, *tail;
void createCLL(){
int choice=1;
struct node *newnode;
else
head=0; {
while(choice){ tail->next=newnode;
newnode=(struct node *)malloc(sizeof(struct node)); tail=newnode;
printf(“Enter the data\n”); }
scanf(“%d”, &newnode->data); tail->next=head;
newnode->next=0; printf(“Enter your choice\n”);
if(head==0) scanf(“%d”, &choice);
}
{
printf(“%d”, tail->next->data);
head=tail=newnode;
}
}
Creation tail
100 500
struct node { 150
int data;
7 100 6 0 100 1 0 100
struct node *next;
100 500 150
};
struct node *tail;
void createCLL(){
int choice=1;
struct node *newnode; else {
tail=0; newnode->next=tail->next;
while(choice){ tail->next=newnode;
newnode=(struct node *)malloc(sizeof(struct node)); tail=newnode;
}
printf(“Enter the data\n”);
printf(“Enter your choice\n”);
scanf(“%d”, &newnode->data);
scanf(“%d”, &choice);
newnode->next=0; }
if(tail==0) printf(“%d”, tail->next->data);
{ }
tail=newnode;
tail->next=newnode; }
struct node { temp tail

int data; 150 200 Display

struct node *next;

1 100 2 200 3 150
}; 150 100 200
struct node *tail;
void displayCLL(){
struct node *temp;
if(tail==0)
{ while(temp->next!=tail->next)
{
printf(“List is empty”);
printf(“%d”, temp->data);
} temp=temp->next;
else{ }
temp=tail->next; printf(“%d”, temp->data);
}
}
 Insertion at beginning tail
tail
struct node {
0 500
int data;
struct node *next;
}; 7 0 100 5 200 1 150 2 500 4 100 600
struct node *tail; 600 100 200 150 500
void insertatBeg(){ newnode
struct node *newnode;
newnode=(struct node*)malloc(sizeof(struct node));
printf(“Enter the data”); else{
scanf(“%d”, &newnode->data); newnode->next=tail->next;
tail->next=newnode;
newnode->next=0;
}
if(tail==0) printf(“%d”, tail->next->data);
{ }
tail=newnode;
tail->next=newnode;
}
 Insertion at End tail
struct node {
500
int data;
struct node *next;
}; 7 100 5 200 1 150 2 500 4 600 700
struct node *tail; 600 100 200 150 500
void insertatEnd(){
struct node *newnode;
newnode=(struct node*)malloc(sizeof(struct node));
printf(“Enter the data”); 10 0 600
scanf(“%d”, &newnode->data); 700
else{
newnode->next=0; newnode
newnode->next=tail->next;
if(tail==0) tail->next=newnode;
{ tail=newnode;
tail=newnode; }
tail->next=newnode; printf(“%d”, tail->next->data);
} }
 Insertion at Pos tail
temp
struct node {
100 500
int data;
struct node *next; 250
}; 5 200 1 150 2 500 4 100
struct node *tail; 100 200 150 500
void insertatPos(){
struct node *newnode, *temp;
int pos,i=1; 7 0 150
printf(“Enter the pos\n”);
250
scanf(“%d”, &pos);
newnode
if(pos<0 || pos>count) newnode=(struct node*)malloc(sizeof(struct node));
{ printf(“Enter the data”);
printf(“Invalid position”); scanf(“%d”, &newnode->data); newnode->next=temp->next;
} newnode->next=0; temp->next=newnode;
elseif(pos==1){ temp=tail->next; }
insertatBeg(); } while(i<pos-1){
else{ temp=temp->next;
i++; }
Deletion from Circular Linked List:
Deletion from Beginning temp tail

500 200
struct node{
int data;
5 600 4 100 1 200 7 500
struct node *next;
}; 500 600 100 200
struct node *tail;
void deletefromBeg(){
struct node *temp;
temp=tail->next; temp tail
if(tail==0) 600 600
{
tail->next=temp->next;
printf(“List is empty”);
free(temp); 5 600
}
else{ 600
if(tail==temp)
{
tail=0;
free(temp);
}
else{
Deletion from Circular Linked List:
Deletion from End temp
tail

500 200
struct node{
int data;
5 600 4 100 1 200 7 500
struct node *next;
}; 500 600 100 200
struct node *tail;
void deletefromEnd(){
struct node *temp, *prev;
temp=tail->next; temp tail
if(tail==0) 600 600
{
while(temp->next!=tail->next){
printf(“List is empty”);
prev=temp; 5 600
}
temp=temp->next;
else if(tail==temp) 600
}
{
prev->next=tail->next;
tail=0;
tail=prev;
free(temp);
free(temp);
}
}
else{
Deletion from Circular Linked List:
Deletion from Pos temp prev
tail

500 100 200

struct node{
int data;
5 600 4 100 1 200 7 500
struct node *next;
}; 500 600 100 200
struct node *tail;
void deletefromEnd(){
struct node *temp, *prev;
int pos, i=1; temp tail
temp=tail->next; 600 600
printf(“Enter the position\n”);
while(i<pos-1){
scanf(“%d”, &pos);
temp=temp->next; 5 600
if(pos<1||pos>count)
i++;
{ 600
}
printf(“Invalid position”);
prev=temp->next;
}
temp->next=prev->next;
else if(pos==1)
temp=prev;
{
free(temp);
deletefromBeg()
}
}
}
Circular Doubly Linked list
➢ Circular doubly linked list is a more complexed type of data structure in
which a node contain pointers to its previous node as well as the next node.
➢ Circular doubly linked list doesn't contain NULL in any of the node.
➢ The last node of the list contains the address of the first node of the list.
➢ The first node of the list also contain address of the last node in its
previous pointer.
➢ Due to the fact that a circular doubly linked list contains three parts in its
structure therefore, it demands more space per node and more expensive
basic operations.
Memory Management of Circular Doubly linked list
 Operations on circular doubly linked list :
SN Operation Description
1 Insertion at beginning Adding a node in circular doubly linked list at the
beginning.
2 Insertion at end Adding a node in circular doubly linked list at the end.
3 Insertion at Pos Adding a node at the specified position
4 Deletion at beginning Removing a node in circular doubly linked list from
beginning.
5 Deletion at end Removing a node in circular doubly linked list at the end.
6 Deletion at Pos Removing the node from the specified pos
Implementation of Doubly Circular Linked List
struct node{
int data;
head tail
struct node *next;
struct node *prev; 500 600
};
struct node *head, *tail;
void createDCLL() 600 7 300 500 6 600 300 1 500
{ 500 300 600
struct node *newnode;
head=0; int choice=1;
while(choice){ head tail
newnode=(struct node*)malloc(sizeof(struct node)); else{ 500 500
printf(“Enter the data\n”); tail->next=newnode;
scanf(“%d”, &newnode->data); newnode->prev=tail;
500 7 500
newnode->next=0; newnode->prev=0; newnode->next=head;
if(head==0) head->prev=newnode; 500
{ tail=newnode;
head=tail=newnode; }
tail->next=tail; printf(“Do you want to continue (1 or 0)\n”);
scanf(“%d”, &choice);
head->prev=head; }
}}
Implementation of Doubly Circular Linked List Display
head temp tail
struct node{
500 500 600
int data;
struct node *next;
struct node *prev;
}; 600 7 300 500 6 600 300 1 500
struct node *head, *tail; 500 300 600
void display()
{
struct node *temp;
temp=head;
else{
if(head==0) while(temp!=tail) {
{ printf(“%d”, temp->data);
printf(“List is empty”); temp=temp->next;
} }
printf(“%d”, temp->data);
}
Insertion in Doubly Circular Linked List: Insert at
beginning
head temp tail
struct node{
int data; 500 500 100
newnode
struct node *next;
0 100 7 0 200
struct node *prev;
}; 500 100 500 6 300 200 5 100 300 1 200 500
struct node *head, *tail; 200 300 100
void insertatBeg()
{
struct node *newnode; head tail
newnode=(struct node*)malloc(sizeof(struct node));
printf(“Enter the data\n”); 500 500
else{
scanf(“%d”,&newnode->data);
newnode->next=head;
newnode->next=0; newnode->prev=tail; 500 7 500
newnode->prev=0; head->prev=newnode; 500
if(head==0){ tail->next=newnode;
head=tail=newnode; head=newnode;
tail->next=newnode; }
head->prev=newnode; }
Insertion in Doubly Circular Linked List: Insert at end
struct node{ head temp tail
int data; 500 500 100
struct node *next;
struct node *prev; 700 7 200
}; 500 500 6 300 200 5 100 300 1 200 700
struct node *head, *tail; 200 100
300
void insertatEnd()
{
struct node *newnode; 0 100 8 0 500
newnode=(struct node*)malloc(sizeof(struct node)); 700
printf(“Enter the data\n”); newnode
scanf(“%d”,&newnode->data); else{
newnode->prev=tail; head tail
newnode->next=0;
newnode->prev=0; tail->next=newnode;
500 500
newnode->next=head;
if(head==0){
head->prev=newnode;
head=tail=newnode; tail=newnode; 500 7 500
tail->next=newnode; }
head->prev=newnode; } 500
Insertion in Doubly Circular Linked List: Insert at pos
struct node{
int data; head temp tail
newnode
struct node *next; 200 100 100
struct node *prev; 300 5 100
}; 400
struct node *head, *tail; 100 6 300 200 5 100 400 300 400 1 200
void insertatPos() 200 300 100
{
struct node *newnode, *temp;
int pos, i=1;
temp=head; else{
printf(“Enter position\n”); newnode=(struct node*)malloc(sizeof(struct node));
printf(“Enter the data\n”);
scanf(“%d”, &pos); newnode->prev=temp;
scanf(“%d”,&newnode->data);
if(pos<1 && pos>count){ newnode->next=temp->next;
newnode->next=0;
printf(“Invalid position”); temp->next->prev=newnode;
newnode->prev=0;
} temp->next=newnode;
while(i<pos-1){
}}
else if(pos==1){ temp=temp->next;
insertatBeg(); i++;
} }
Deletion from Doubly Linked List – Deletion from Beginning
head temp head tail
struct node{
int data; 200 200 100 250
struct node *next;
struct node *prev; 250 1 100 200 2 300 100 3 250 300 7 200
};
struct node *head, *tail; 200 100 300 250
void deletefromBeg(){
struct node *temp;
temp=head;
if(head==0){ head tail
printf(“List is empty\n”);
} 500 500
else if(head->next=head){
head=tail=0;
500 7 500
free(temp);
}
else{
head=head->next;
head->prev=tail;
tail->next=head;
free(temp); }
Deletion from Doubly Linked List – Deletion
tail
from End
head temp tail
struct node{
int data; 200 250 250 250
struct node *next;
struct node *prev; 250 1 100 200 2 300 100 3 250 300 7 200
};
struct node *head, *tail; 200 100 300 250
void deletefromEnd(){
struct node *temp;
temp=tail;
if(head==0){ head tail
printf(“List is empty\n”);
} 500 500
else if(head->next=head){
head=tail=0;
500 7 500
free(temp);
}
else{
tail=tail->prev;
tail->next=head;
head->prev=tail;
free(temp); }
Deletion from Doubly Linked List – Deletion from Pos
struct node{ temp tail
head
int data;
struct node *next; 200 200 250
struct node *prev;
}; 250 1 100 200 2 300 100 3 250 300 7 200
struct node *head, *tail;
void deletefromBeg(){ 200 100 300 250
struct node *temp;
int pos, i=1;
temp=head;
printf(“Enter the position\n”); head tail
scanf(“%d”, &pos); temp->prev->next=temp->next;
if(pos<1 ||pos>count){ temp->next->prev=temp->prev;
500 500
printf(“Invalid position\n”); free(temp);
} } 500 7 500
else if(pos==1){
deletefromBeg();
}
else{
while(i<pos){
temp=temp->next;
i++; }
 Hashing
• Storing and Retrieving data from database in order of O(1) time.
• Terminology:
• Search key: We will store the data in database based on the key.
• The search key will be stored in the hash table.
• Hash table: It is a data structure where we store the data.
• Hash Function: k mod 10, k mod n, mid square, folding method.
Example: search key – 24, 52, 91, 67, 48, 83 0

Hash function: k mod 10. 91 1

52 2
24 mod 10 = 4
83 3
52 mod 10 = 2
24 4

67 mod 10 = 7 Storing
Retrieving / Searching
5
6
67 7
48 8
9
 Collision in Hashing
0
1 91
2 52 Suppose if we want to add 62 then how to store 62?
3 83 This process is called collision
4 24
0
5 Collision Resolution Techniques
1 91
6
2 52 62
7 67
8 48
3 83 Chaining Open addressing
4 24 (Open hashing) (Closed hashing)
9 • Linear Probing
5 • Quadratic Probing
6 • Double Probing
7 67
8 48
9
Chaining (Open hashing) 0 10
1
2 42
Keys: 42, 19, 10, 12 3
Hash Function: k mod 5 4 19
Advantages: Deletion is easy
Insertion is easy O(1)
0 10
1
Disadvantages: Searching is O(n) 2 12 42
Extra space 3
Load factor = Total number of elements/slots 4 19

= 4/5
Linear Probing 0 19
1
2 72
• Keys: 43, 135, 72, 23, 99, 19, 82 3 43
• Hash Function h(k): k mod 10 4 23

• When collision occurs use hash function 5 135

6 82
• h(k)=(h(k)+i)mod 10) where i is the collision number
7
• 23
8
• h(k)=23 mod 10 9 99
=3
h(k)=(3+1)mod 10=4
Advantages: No extra space

Disadvantages: Search time O(n)

Deletion difficult
Quadratic Probing 0 36
1 91
2 42
• Keys: 42, 16, 91, 33, 18, 27, 36, 62 3 33
• Hash Function h(k): k mod 10 4

• When collision occurs use hash function 5

6 16
• h(k)=(h(k)+i^2)mod 10) where i is the collision number
7 27
• 36
8 18
• h(k)=36 mod 10 9
=6
h(k)=(6+1^2)mod 10=7 , 6+2^2=10
Advantages: No extra space
Insertion is easy O(1)

Disadvantages: Search time O(n)

No guarantee of finding slot
 56
56 mod 11 = 1
Double hashing h2(k)=8-(56 mod 8)
=8-0 0
=8
1+1(8) mod 11 1 34
• h1(k)=k mod 11 1+8 mod 11 2
9 mod 11 = 9
• h2(k)=8-(k mod 8) 3 56
1+2(8) mod 11= 17 mod 11=6
• h1(k)+i h2(k)mod 11 1+3(8) mod 11=25 mod 11=3 4 45
• Keys: 20, 34, 45, 70, 56 5

20 6 70
70 7
20 mod 11 = 9 70 mod 11=4
h2(k)=8-(70 mod 8) 8
=8-6 9 20
34 =2
h2(k)=8-(45 mod 8) 10
34 mod 11=1 =8-5
4+1(2) mod 11
4+2 mod 11
=3 6 mod 11
45 h1(k)+i h2(k)mod 11 6
1+ 1(3) mod 11
45 mod 11=1 1+3 mod 11
4 mod 11= 4