Linked List

Structures
It is a data type used for handling a group of logically related data items.
For example: record of student : name, roll number, marks
#include <stdio.h>
struct employee
{
int emp_id;
char emp_name[20];
} e1;
int main()
{
struct employee *e;
printf("enter the details of employee1\n");

scanf("%d%s",&e1.emp_id,e1.emp_name);
printf("employees details\nemployee id
=%d\nemployee name =
%s",e1.emp_id,e1.emp_name);
e=&e1;
printf("\n%d%s",e->emp_id,e->emp_name);
return 0;
}
 Self Referential Structure
A self-referential structure is a structure that can have members which point to a structure
variable of the same type
Linked List
 Linked list as Abstract data type

• Linked List is an Abstract Data Type (ADT) that holds a collection of Nodes,
the nodes can be accessed in a sequential way. Linked List doesn’t provide
a random access to a Node.

• Usually, those Nodes are connected to the next node and/or with the
previous one, this gives the linked effect. When the Nodes are connected
with only the next pointer the list is called Singly Linked List and when it’s
connected by the next and previous the list is called Doubly Linked List.
• Perform following operations
Insertion at the beginning, end, at particular position
Deletion at the beginning, end, at particular position
Traversal
Reversal
Memory Representation of Linked List
Arrays Vs Linked List
 Free Pool/ Avail List
list of available space is called the free pool/ Avail list

Garbage Collection: The operating system scans through all the memory cells and marks
those cells that are being used by some program. Then it collects all the cells which are not
being used and adds their address to the free pool, so that these cells can be reused by
other programs. This process is called garbage collection.
 Singly Linked list

• A start pointer stores address of the next node.

• Each node contains two parts information and link( pointer to next
node)
• Link of the last node is NULL (indicates end of linked list).
Operations on Linked List
 Creation of Linked List
struct node
{
int info;
struct node *link;
} *start=NULL;

void create_List(int data)

{
struct node *q, *tmp;
tmp = (struct node*) malloc(sizeof(struct node));
tmp->info = data;
tmp->link = NULL;

if (start == NULL)
{
start = tmp;
}
}
 Creation of Linked List
else
{
q = start;
while (q->link != NULL)
{
q = q->link;
}
q->link = tmp;
}
 Traversal of Linked
void display() List
{
struct node *q;

if (start == NULL)
{
printf("\nList is empty");
return;
}

q = start;
printf("\nList is: ");
while (q != NULL)
{
printf("->%d", q->info);
q = q->link;
}

printf("\n");
}
 Searching in a Linked List
void Search(int data)
{
struct node *ptr = start;
int pos = 1;

while (ptr != NULL)

{
if (ptr->info == data)
{
printf("\nItem %d is found at position: %d", data, pos);
return;
}
ptr = ptr->link;
pos++;
}

if (ptr == NULL)
printf("\nItem %d is not found", data);
}
 Insertion in linked list

Case 1: The new node is inserted at the beginning.

Case 2: The new node is inserted at the end.
Case 3: The new node is inserted after a given node.

Overflow is a condition that occurs when no free memory cell is present in the
system.
Insertion at the beginning
 Insertion at the beginning
void Insert_at_Beg(int data)
{
struct node *tmp;
tmp = (struct node*) malloc(sizeof(struct
node));
if (start == NULL)
{
start = tmp;
}
else
[ tmp->info = data;
tmp->link = start;
start = tmp;
}}
Insertion at the end of the linked list
 Insertion
void insert_at_end(int data)
at the end of the linked list
{
struct node *tmp, *q;
tmp = (struct node*) malloc(sizeof(struct
node));

tmp->info = data;
tmp->link = NULL;
if (start == NULL)
{
start = tmp;
}
else{
q = start;
while (q->link != NULL)
{
q = q->link;
}
q->link = tmp;
}}
Insertion after a given node
 Insertion after a given node

// Insert after a specific position

void insert_at_pos(int data)
{
struct node *tmp, *q;
int i;

q = start;

for (i = 0; i < pos - 1; i++)

{
q = q->link;
}
if (q == NULL)
{
printf("\nInvalid position: %d", pos);
return;
}
 Insertion after a given node

tmp = (struct node*) malloc(sizeof(struct node));

tmp->info = data;
tmp->link = q->link;
q->link = tmp;
}
 Deletion of a node from linked list
Case 1: The first node is
deleted. Case 2: The last node
is deleted.
Case 3: The node after a given node is deleted.

Underflow: when linked list is empty no deletion is

possible such condition is known as underflow
Free Memory after deletion
 Deletion from first node

void delete_from_beg()
{
struct node *tmp; Time Complexity Deletion at
beg = O(1)
if (start == NULL)
{
printf("List is empty");
return;
}
else
{
tmp = start;
start = start->link;
free(tmp);
}}
 Deletion of last node
void DeleteFromEnd()
{
struct node *prevnode, *tmp;
tmp = start;
if (start == NULL)
{
printf("List is empty");
return;
while (tmp->next != NULL)
{
prevnode = tmp;
tmp = tmp->next;
}
if (tmp == start)
{start = NULL;
free(tmp);}
else
{
prevnode->next = NULL;
free(tmp);
}
}
Delete a node after given node
 Delete a node after given node
void deleteAfterPos(int pos)
{
struct node *ptr, *ptr1;
ptr = start;
for (int i = 0; i < pos; i++)
{
ptr1 = ptr;
ptr = ptr->next;
if (ptr == NULL)
{
printf("Invalid position\n");
return;
}
}
ptr1->next = ptr->next;
free(ptr);
}
Doubly linked list
Doubly linked list VS singly linked list
 Operations on Doubly linked list
Insertion at beginning Insertion at end
Insertion after given position
Traversal
Deletion at the beginning Deletion at the end
Delete a node
 Creation of Doubly Linked
struct node
List
{
int info;
struct node *prev;
struct node *next;
} *start=NULL;

void create_list(int x)
{
struct node *tmp, *q;
tmp = (struct node*) malloc(sizeof(struct
node));
tmp->info = x;
tmp->prev = NULL;
tmp->next = NULL;

if (start == NULL)
{
start = tmp;
}
 Creation of Doubly Linked
List
else
{
q = start;
while (q->next != NULL)
{
q = q->next;
}

q->next = tmp;
tmp->prev = q;
}}
 Insertion at Beginning
void add_at_beg(int x)
{
struct node *tmp;
tmp = (struct node*) malloc(sizeof(struct node));
tmp->info = x;
tmp->prev = NULL;
tmp->next = NULL;

if (start == NULL)
{
start = tmp;
}
else
{
tmp->next = start;
start->prev = tmp;
start = tmp;
}
 Insertion at End
void insert_at_end(int x)
{
struct node *tmp, *q;
tmp = (struct node*) malloc(sizeof(struct node));
tmp->info = x;
tmp->prev = NULL;
tmp->next = NULL;

if (start == NULL)
start = tmp;
else
{
q = start;
while (q->next != NULL)
{
q = q->next;
}
q->next = tmp;
tmp->prev = q;
}
}
 Insertion after Position
void add_after_pos(int num, int pos)
{
struct node *tmp, *q;
int i;
q = start;
for (i = 0; i < pos - 1; i++)
{
q = q->next;
if (q == NULL)
{
printf("Invalid position");
return;
}
}
tmp = (struct node*)
malloc(sizeof(struct node));
tmp->info = num;
q->next->prev = tmp;
tmp->next = q->next;
tmp->prev = q;
q->next = tmp; }
 Traversal

void display()
{
struct node *q;
if (start == NULL)
printf("List is empty");
else
{
Time Complexity = O(n)
q = start;
while (q != NULL)
{
printf("%d ", q->info);
q = q->next;
}
}
}
 Deletion at Beginning

void delete_from_beg()
{
struct node *tmp = start;
if (start == NULL)
{
printf("List is empty");
return;
}
else if (tmp->next == NULL)
{
start = NULL;
return;
}
else
{
tmp = start;
start = start->next;
start->prev = NULL;
free(tmp);
}
}
 Deletion at End

void delete_from_end()
{
struct node *tmp = start;
if (start == NULL)
{
printf("List is empty");
return;
}
else if (tmp->next == NULL)
{
start = NULL;
return;
}
else {
while (tmp->next != NULL)
{
tmp = tmp->next;
}
 Deletion at End

struct node *q = tmp->prev;

q->next = NULL;
free(tmp);
}}}
 Deletion after Position

void delafterpos(int pos)

{
int i = 0;
struct node *temp = start;

while (i < pos)

{
temp = temp -> next;
Time Complexity Deletion after pos = O(n)
i++;
}
if (temp == NULL)
{
printf("Invalid position\n");
return;
}
temp -> prev -> next = temp -> next;
temp -> next -> prev = temp -> prev;
free(temp);
}
Deletion after Position
 Stack Using Linked List
struct stack
{
int data;
struct stack *link;
};
struct stack *Top = NULL;
void push(int x)
{
struct stack *t;
t = (struct stack *)malloc(sizeof(struct stack));
t -> data = x;
t -> link = NULL;

if (Top == NULL)
Top = t;
else
{
t -> link = Top;
Top = t;
}
}
 Stack Using Linked List

void pop()
{
struct stack *p;
if (Top == NULL)
{
printf("Stack is underflow");
return;
}
else
{
p = Top;
Top = Top -> next;
free(p);
}
}
 Stack Using Linked List

void display()
{
struct stack *p;
if (Top == NULL)
{
printf("Stack is underflow");
return;
}
else
{
p = Top;
while (p != NULL)

{
printf("%d", p -> data);
p = p -> next;
}
}
}
Stack Using Linked List
 Queue Using Linked List
struct que
{
int data;
struct que *next;
};
struct que *f = NULL, *r = NULL;
void enqueue(int x)
{
struct que *t;
t = (struct que *)malloc(sizeof(struct que));
t -> data = x;
t -> next = NULL;

if (f == NULL && r == NULL)

f = r = t;
else
{
r -> next = t;
r = t;
}
}
Queue Using Linked List
 Queue Using Linked List

void dequeue()
{
struct node *t;
if (f == NULL && r == NULL)
{
printf("Underflow");
return;
}
else
{
t = f;
f = f -> next;
free(t);
}}
 Queue Using Linked List
void display()
{
struct node *t;
if (f == NULL && r == NULL)
{
printf("queue is empty");
return;
}
else
Time Complexity = O(n)
{
struct node *q = f;
while (q != NULL)
{
printf("%d", q->data);
q = q->next;
}
}
}
Circular Linked List
Advantages and Disadvantages of
Circular Linked List
 Creation of Circular Linked List

void create(int x)
{
struct node
{
int data;
struct node *next;
} *start = NULL;

void Create(int x)
{
struct node *tmp;
tmp = (struct node *)malloc(sizeof(struct node));
tmp->data = x;
tmp->next = NULL;
 Creation of Circular Linked List

if (start == NULL)
{
start = tmp;
tmp->next = start;
}
else
{
struct node *tmpl = start;
while (tmpl->next != start)
{
tmpl = tmpl->next;
}
tmpl->next = tmp;
tmp->next = start;
}}
Creation of Circular Linked List
 Traversal of Circular Linked List

void display()
{
struct node *p;
p = start;
if (start == NULL)
printf("Linked list is empty");
else
{ Time Complexity = O(n)
while (p->next != start)
{
printf("%d", p->data);
p = p->next;
}
printf("%d", p->data);
}
}

}
 Insertion at Beginning of Circular
Linked List
void insert at beg(int x)
{
struct node *tmp;
tmp = (struct node*)malloc(sizeof(struct node));
tmp->data = x;
tmp->next = NULL;
if (start == NULL)
{
start = tmp;
tmp->next = start;
}
else
{
struct node *q = start;
while(q->next != start)
{
q = q->next;
} tmp->next = start;
q->next = tmp;
start = tmp;
}}
Insertion at Beginning of Circular
Linked List
 Insertion at End of Circular Linked List

void insert at end(int x)

{
struct node *tmp;
tmp = (struct node *) malloc(sizeof(struct node));
tmp->data = x;
tmp->next = NULL;
if(start == NULL)
{
start = tmp;
tmp->next = start;
}
else
{
struct node *q = start;
while(q->next != start) {
q = q->next;
}
q->next = tmp;
tmp->next = start;
}
Insertion at End of Circular Linked List
 Deletion at Beginning of Circular Linked
void deletion at beg()
List
{
struct node *p;
if (start == NULL)
printf("List is empty");
else
{
p = start;
while (p->next != start)
{
p = p->next;
}
p->next = start->next;
free(start);
start = p->next;
}
}
Time Complexity Deletion at beg = O(n)
 Deletion at End of Circular Linked List

void deletion at end()

{
struct node *p, *q;
if (head == NULL)
{
printf("List is empty");
return;
Time Complexity Deletion at end =
}
O(n)
else
{
p = start;
while (p->next != start)
{
q = p;
p = p->next;
}
q->next = p->next;
free(p);
}
}
END