Singly &
Circular
Linked List
Outlines
Introduction
Advantage of a Link List over Array
Link List Declaration
Basic Link List Operation
Circular Link List
Application
Disadvantage
Introduction
What Is Linked List?
The most commonly used data structure to store data in memory.
A linear collection of data elements, called nodes.
Unlike arrays, linked list elements are not stored at adjacent location.
The nodes connect by pointers.
What’s wrong with Array and Why linked lists?
Disadvantages of arrays as storage data structures:
Insertion and deletion operations are slow.
Slow searching in unordered array.
Wastage of memory.
Fixed size.
Linked lists solve some of these problems :
Insertions and deletions are simple and faster.
Linked list is able to grow in size.
Linked List reduces the access time.
No wastage of memory.
Singly Linked List
Singly linked list is a collection of nodes.
Each node contains two parts.
The data contains elements .
Link contains address of next node .
Node
data link
Structure of singly linked list
The head always points to the first node .
All nodes are connected to each other through Link fields.
Null pointer indicated end of the list.
head
data link data link data link
A B C X
Circular linked list
A circular linked list is one which has
No ending.
The null pointer in the last node of a linked list is replaced with the
address of its first node .
Structure of circular linked list
CIRCULAR LINKED LIST:-
A 1000 B 2000 C 4000
4000 1000 2000
Operations on linked list
The basic operations on linked lists are :
1. Creation
2. Insertion
3. Deletion
4. Traversing
5. Searching
What Is creation
The creation operation is used to create a linked list.
Declare Node struct for nodes.
Data - any type
Link - a pointer to the next node.
Struct node{
int data;
Struct node *link;
}
What Is creation
Algorithm
Allocate a new node create a new node
Insert new element new->data=item
Make new node point to null new->link=NULL
Create head to point to new node head=new
Creation
new->data=item
new->link=NULL
head=new
head
New Node
A
What Is Insertion
Insertion operation is used to insert a new node in the
linked list at the specified position.
When the list itself is empty , the new node is inserted
as a first node.
Types of Insertion
There are many ways to insert a new node
into a list :
As the new first element.
As the new last element.
Before a given value.
After a given value.
Inserting at the beginng
Algorithm
Allocate a new node create a new node
Insert new element new->data=item
Make new node to point to old head new->link=head
Update head to point to new node head=new
Inserting at the beginning
head new->link=head
head=new
data link data link
New Node
X
B C
A
Inserting at the last
Algorithm
Allocate a new node
create a new node
Insert new element new->data=item
Searching the last node ptr=head while(ptr->link!=null) ptr=ptr>link
Have old last node point to new node ptr->link=new
Update new node that point to null new->link=NULL
Inserting at the last
head
data link data link New Node
B C A
ptr->link=new
new->link=NULL
Inserting before given a value
Algorithm
Allocate a new node create a new node
Insert new element new->data=item
Searching the given node ptr=head while(ptr->info!=data) temp=ptr
Store the previous node ptr = ptr>link
Update new to point to previous node link new->link=temp->link
Update previous node to point to new temp->link=new
node
Inserting before given a value
head
data link data link data link
X
temp ptr
B D
A
New Node
new->link=temp->link
temp->link=new
C
Inserting after given a value
Allocate a new node, new
Algorithm
Insert new element create a new node
Searching the node new->data=item
Update new to point to the link of the ptr=head while(ptr->info!=data) ptr=ptr>link
given node new->link=ptr->link
Update given node to point to new ptr->link=new
node
Inserting after given a value
head
data link data link data link
X
ptr
D
A B New Node
new->link=ptr->link
ptr->link=new
C
What Is Deletion?
Deletion operation is used to delete a particular node in
the linked list.
we simply have to perform operation on the link of the
nodes(which contains the address of the next node) to
delete a particular element.
Types of Deletion
Deletion operation may be performed in
the following conditions:
Delete first element.
Delete last element.
Delete before a given value.
Delete after a given value.
Delete a particular element
Deleting the first node
Algorithm
Declare a node srt=head
Assign head to the new node head=srt->link
Update head with the link of the
new node
Deleting the first node
head srt=head
head=srt->link
data link data link data link
X
srt
A B C
Deleting the last node
Algorithm
Declare nodes srt, temp declare srt, temp
Traverse the list and update temp for(srt=head;;temp=srt,
srt=srt->link)
with the value of srt
if(srt->link==NULL) temp-
If the link of srt is NULL, update the link >link=NULL; Exit;
of temp with NULL and break the loop
Deleting the last node
head
data link data link data link
X X
A B C
Deleting after a given value
Algorithm
Declare a node srt Node *srt
Search the element to delete after srt=head while(srt->info!=data) srt=srt>link
Update link of the node with the link of the srt->link=srt->link->link
next node ptr->link=new
Deleting after a given value
head
data link data link data link
srt
A B C
C
Deleting before a given value
Algorithm
Declare nodes srt, temp and prev Node *srt, *temp, *prev
Search the element to delete before srt=head while(srt->info!=data) srt=srt>link
prev = temp; temp = srt;
Update link of the previous node with the Prev->link = srt
link of the next node
Deleting before a given value
head
data link data link data link data link
prev temp srt
A B C D
Deleting a given value
Algorithm
Declare nodes srt and temp Node *srt, *temp
Search the element to delete Srt =head while(srt->info!=data) srt=srt->link
Update link of the previous node with temp = srt;
the link of the selected node temp->link = srt->link
Deleting after a given value
head
data link data link data link data link
temp srt
A B C D
Operations on a singly circular linked list
The basic operations on singly circular linked lists are :
1. Creation
2. Insertion
3. Deletion
4. Traversing
5. Searching
Operations on a singly circular linked list
The operations on a singly circular linked is almost same as that of a singly
linked list. The only difference between them is that the link of the last node of
a singly linked list contains NULL, whereas that of a circular list contains head
Creation of a circular linked list is same as singly list except that we will have to
use head instead of NULL
To traverse the list we have to start from head and end until the link of a node is
head
To insert a node at the beginning of the list we have to store the value of head
in a temporary node and operate accordingly
Operations on a singly circular linked list
The operation insert last, is almost the same as that of the singly list, difference: head
instead of NULL in the link of new node
The operation insert after, is same as that of the singly list. If the node is the last node
then we can perform the operation just by calling the insert last’s function
The operation insert before, is same as that of the singly list
The operation delete after and before, is same as that of the singly list. Deleting last
element is also almost the same, only have to update the link of previous node with
head. But the process of deleting the first element is different, it’ll be discussed in this
presentation
The operation delete element, is same as that of the singly list
Operations on a singly circular linked list
Most of the operations are almost the same as singly linked list incase of a singly
circular linked list, only a little variation in list creation and deleting the first element,
next contents contain these operations!
Creation of a circular list
Algorithm
Allocate a new node
create a new node
Insert new element
new->data=item
Make new node point to head
new->link=head
Update head to point to new node of first
element head=new, temp=new, if
head==NULL
If not first element update link of previous
element with current node address else temp->link=new,
temp=ptr
Creation
head
New Node New Node
head head
new->data=item B
A
new->link=head
Deleting the first node
Declare a new node, srt Algorithm
Assign head to the new node srt=head
Update head with the link of the new head=srt->link
node last->link=head
Update the link of last node with the link
of the new node
Deleting the first node
head last
data link data link data link
head
head=srt->link A B C
last->link=head
Doubly Linked List
1.) In doubly linked list each node contains two pointers.
2.) which points has a reference to both the next point and
pervious point of node in list.
3.) A doubly linked list is a two-way list because one can
move in either from left to right or from right to left
Node Data
Info : the user’s data.
Prev, Next : the address of next and previous node in list
prev next
Info
NODE
Operations on a Doubly linked list
1) Create list.
2) Insert element at beginning in list.
3) Insert element at end in list.
4) Insert element at any place in list.
5) Delete element from the beginning of list.
6) Delete element from the end of list.
7) Delete element from any place from list.
Insert an element at beginning
doubly linked list
Delete an element at any place
doubly linked list
Doubly Linked list
Advantages Disadvantages
1. We can traverse in both 1. It requires more space per space
directions i.e. from starting to end per node because one extra field
and as well as from end to is required for pointer to previous
starting. node.
2. It is easy to reverse the linked 2. Insertion and deletion take
list. more time than linear linked list
3. If we are at a node, then we because more pointer operations
can go to any node. But in linear are required than linear linked
linked list, it is not possible to list.
reach the previous node.
Application
Linked lists are used in many other data structures.
Linked lists are used in polynomial manipulation.
Representation of trees, stacks, queues. etc.
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.
No binary search.
Thank you
