DATA STRUCTURES – Linked List

UNIT-3
Dr. SELVA KUMAR S
ASSISTANT PROFESSOR
B.M.S. COLLEGE OF ENGINEERING
 Linked List
• Linked List is a very commonly used linear data
structure which consists of group of nodes in a
sequence.
• Each node holds its own data and the address of the
next node hence forming a chain like structure.
• Linked Lists are used to create trees and graphs.
 Advantages of Linked Lists
• They are a dynamic in nature which allocates
the memory when required.
• Insertion and deletion operations can be easily
implemented.
• Stacks and queues can be easily executed.
Disadvantages of Linked Lists
• The memory is wasted as pointers require
extra memory for storage.
• No element can be accessed randomly; it has
to access each node sequentially.
• Reverse Traversing is difficult in linked list.
Applications of Linked Lists
• Linked lists are used to implement stacks,
queues, graphs, etc.
• Linked lists let you insert elements at the
beginning and end of the list.
• In Linked Lists we don't need to know the
 mple
• Syntax for malloc():
ptr=(datatype *)malloc(specified-size);
• Example 1:
int ptr;
ptr=(int*)malloc(10*sizeof(int));
• Example 2: struct *str; str=(struct
node*)malloc(sizeof(struct node));
 Singly Linked List
• What is a Node?
• A Node in a linked list holds the data value and
the pointer which points to the location of the
next node in the linked list.
 Node Implementation
// A linked list node struct
Node
{
int data; struct
Node *next;
};

typedef struct Books {

char title[50]; char
author[50]; char
subject[100]; int
book_id; struct
Books *add;
} Book;
 Inserting a node
• A node can be added in three ways
1) At the front of the linked list 2)
After a given node.
3) At the end of the linked list.
Add a node at the front
/* Given a reference (pointer to pointer) to the head of a list
and an int, inserts a new node on the front of the list. */
void push(struct Node** head_ref, int new_data)
{
/* 1. allocate node */ struct Node* new_node = (struct Node*)
malloc(sizeof(struct Node));

/* 2. put in the data */ new_node-

>data = new_data;
 /* 3. Make next of new node as head */ new_node-
>next = (*head_ref);

/* 4. move the head to point to the new node */

(*head_ref) = new_node;

}
Add a node at the end
Display the content of Linked List
Add a node at specified position
Complete code
 Singly Linked List:Deleting a node
• A node can be deleted in three ways 1)
At the front of the linked list
2) After a given node/specified position
3) At the end of the linked list.
Delete a node at the front
void Pop()
{
struct node *ptr;
if(head == NULL)
{
printf("\nList is empty");
}
else
{
 ptr = head; head = ptr->next; free(ptr);
printf("\n Node deleted from the
begining ...");
}

Delete a node at the end

void end_delete()
{
struct node *ptr,*ptr1;
if(head == NULL)
{
printf("\nlist is empty");
}
else if(head -> next == NULL)
{
free(head);
head = NULL;
printf("\nOnly node of the list deleted ...");
}
 else
{
ptr = head;
while(ptr->next != NULL)
{
ptr1 = ptr;
ptr = ptr ->next;
}
ptr1->next = NULL;
free(ptr);
printf("\n Deleted Node from the last ...");
}
}

Delete a node at specified position

void delete_specified()
{
struct node *ptr, *ptr1;
int loc,i;
scanf("%d",&loc);
ptr=head; for(i=0;i<loc;i+
+)
{
ptr1 = ptr; ptr
= ptr->next;

if(ptr == NULL)
{
 printf("\nThere are less than %d elements in the list..\n",loc);
return;
}
}
ptr1 ->next = ptr ->next;
free(ptr); printf("\nDeleted %d
node ",loc);
}
Complete Code
Singly Linked List Operations
• Search
• Count number of nodes
• Concatenation
• Merging
• Reversing
Search
 Count number of nodes
void Count_nodes()
{
/* temp pointer points to head
*/ struct node* temp =
head;
/* Initialize count
variable */ int
count=0;
/* Traverse the linked list and maintain the count */
while(temp != NULL)
{
temp = temp->next;
/* Increment count variable. */
count++;
}
/* Print the total count. */
printf("\n Total no. of nodes is %d",count);
}
Concatenation
Merging
Reversing
 Applications of Linked List
• Stack
• Queue implementation
Stack Implementation using Linked
List
void push(struct Node** head_ref, int new_data)

Circular 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.
 Operations on Circular List
• Insertion at the beginning
• Insertion at the end
• Deletion at the beginning
• Deletion at the end
• Searching
• Traversing
Insertion at the beginning
void beg_insert(int item)
{

struct node *ptr = (struct node

*)malloc(sizeof(struct node)); struct node *temp;
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
ptr -> data = item;
if(head == NULL)
{
head = ptr;
ptr -> next = head;
}
else
{
temp = head; while(temp->next != head)
temp = temp->next;
ptr->next = head; temp -> next = ptr;
 head = ptr;
}
printf("\nNode Inserted\n");
}

Insertion at the end

void lastinsert(struct node*ptr, struct node *temp, int item)
{
ptr = (struct node
*)malloc(sizeof(struct node)); if(ptr ==
NULL)
{
printf("\nOVERFLOW\n");
}
else
{
ptr->data = item;
if(head == NULL)
{
head = ptr;
ptr -> next = head;
}
else
{
temp = head;
while(temp -> next != head)
{
temp = temp -> next;
}
temp -> next = ptr;
ptr -> next = head;
 }
}

Deletion at the beginning

void beg_delete()
{
struct node *ptr;
if(head == NULL)
{
printf("\nUNDERFLOW\n");
}
else if(head->next == head)
{
head = NULL;
free(head);
printf("\nNode Deleted\n");
}

else
{
ptr = head; while(ptr -> next != head) ptr = ptr
-> next;
ptr->next = head->next;
free(head);
head = ptr-
>next;
printf("\
nNode
Deleted\n");
}
}
 Deletion at the end
void last_delete()
{
struct node *ptr, *preptr;
if(head==NULL)
{
printf("\nUNDERFLOW\n");
}
else if (head ->next == head)
{
head = NULL;
free(head);
printf("\nNode Deleted\n");
}
else
{
ptr = head;
while(ptr ->next != head)
{
preptr=ptr;
ptr = ptr->next;
}
preptr->next = ptr ->
next; free(ptr);
printf("\nNode Deleted\n");
}
}
 Searching
void search()
{
s
t
r
u
c
t
n
o
d
e
*
p
t
r
;
i
n
t
i
t
e
m
,i
=
0
,
f
l
a
g
=
1
;
p
t
r
=
h
e
a
d
;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
if(head ->data == item)
{
printf("item found at location %d",i+1);
f
l
a
g
=
0
;

r
e
t
u
r
n
;
}
else
{
while (ptr->next != head)
{
if(ptr->data == item)
{
printf("item found at location %d ",i+1);
flag=0;
return;
}
 else
{
f
l
a
g
=
1
;
}
i++;
ptr = ptr -> next;
}
}
if(flag != 0)
{
printf("Item not
found\n");
return;
}
• }

Traversing
void traverse()
{
struct node
*ptr; ptr=head;
if(head == NULL)
{
printf("\nnothing to print");
}
 else
{
printf("\n printing values ... \n");

while(ptr -> next != head)

{

printf("%d\n", ptr -> data);

ptr = ptr -> next;
}
printf("%d\n", ptr -> data);
}

}
Doubly Linked List
 Operations on Doubly Linked
List
• Insertion at beginning
• Insertion at end
• Insertion after specified node
• Deletion at beginning
• Deletion at end
• Deletion of the node given data
• Searching
• Traversing
Insertion at beginning
void insertbeginning(int item)
{

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

if(head==NULL)
{
ptr->next = NULL; ptr->prev=NULL; ptr->data=item;
head=ptr;
}
else
{
ptr->data=item; ptr->prev=NULL; ptr->next = head;
head->prev=ptr;
head=ptr;
}
}
 Insertion at end
void insertlast(int item)
{

struct node *ptr = (struct node *)

malloc(sizeof(struct node)); struct node *temp;

ptr->data=item;
if(head == NULL)
{
ptr->next = NULL; ptr->prev =
NULL;
head = ptr;
}
else
{
temp = head; while(temp-
>next!=NULL)
{
temp = temp->next;
}
temp->next = ptr; ptr ->prev=temp;
ptr->next = NULL;
}
printf("\nNode Inserted\n");

}
 Insert after specified node
void insert_specified(int item)
{
struct node *ptr = (struct node
*)malloc(sizeof(struct node)); struct node
*temp; int i, loc;
printf("\nEnter the location\n");
scanf("%d",&loc); temp=head;
for(i=0;i<loc;i++)
{
temp = temp->next; if(temp == NULL)
{
printf("\ncan't insert\n"); return;
}
}
ptr->data =
item; ptr-
>next =
temp-
>next; ptr -
> prev =
temp;
temp->next
= ptr;
temp-
>next-
>prev=ptr;
printf("Nod
 e Inserted\
n");
}
}

Deletion at beginning
void beginning_delete()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW\n");
}
else if(head->next == NULL)
{
head = NULL; free(head); printf("\nNode
Deleted\n");
}
else
{
ptr = head; head = head -> next;
head -> prev = NULL;
free(ptr);
printf("\nNode
Deleted\n");
 }
}

Deletion at end
void last_delete()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW\n");
}
else if(head->next == NULL)
{
head = NULL;
free(head);
printf("\nNode Deleted\n");
}
else
{
ptr = head;
if(ptr->next != NULL)
{
ptr = ptr -> next;
}
ptr -> prev ->
next = NULL;
free(ptr);
 printf("\nNode
Deleted\n");
}
}

Deletion of a specified node

void delete_specified( )
{
struct node
*ptr,
*temp; int
val;
printf("Ente
r the
value");
scanf("%d",&
val); temp =
head;
while(temp -
> data != val)
temp = temp
-> next;
if(temp -> next == NULL)
{
printf("\nCan't delete\n");
}
else if(temp -> next -> next == NULL)
{
temp ->next = NULL;
 printf("\nNode Deleted\n");
}
else
{
ptr = temp ->
next; temp ->
next = ptr ->
next;
ptr -> next -> prev = temp;
free(ptr);
printf("\nNode Deleted\n");
}
}

Searching
void search()
{
s
t
r
u
c
t

n
o
d
e

*
p
t
r
;
i
n
t

i
t
e
m
,
i
=
0
,
f
l
a
g
;

p
t
r

h
e
a
d
;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
while (ptr!=NULL)
{
if(ptr->data == item)
{
 printf("\nitem found at location %d ",i+1);
flag=0;
break;
}
else
{
f
l
a
g
=
1
;
}
i++;
ptr = ptr -> next;
}

i
f
(
f
l
a
g
=
=
1
)
{
printf("\nItem not found\n");
}
}

Traversing
int traverse()
{
struct node *ptr;
if(head == NULL)
{
printf("\nEmpty List\n");
}
else
{
ptr = head;
while(ptr != NULL)
{
printf("%d\n",ptr->data);
ptr=ptr->next;
}
}
}