June 08, 2020
ALGORITHMS OF LINKED LIST
Algorithms to create a linked list
INPUT: A set of data values,
number of list element, n
OUTPUT: Singly linked list.
Step 1: Input n
Step 2:
head = new node
Step 3: list = head
Step 4: list -> next= NULL
Step 5: For I = 1 to n
(i).
Input list -> data
(ii). list = new node
(iii). list 1 -> next = NULL
(iv). list 1 = list
(End of for loop)
Step 6: Return head
End of Algorithm
Algorithm
for traversal of a singly linked list
INPUT: A
singly linked list whose first nodes given by pointer head.
OUTPUT: Data
of each nodes.
Step 1: list = head
Step 2: While (list NOT EQUAL to NULL)
(i). list -> data
(ii). list = list -> next
(End of while loop)
Step 3: Return
End of Algorithm
Algorithm
for insertion of a node at the beginning of
list
INPUT: i). A singly linked list
whose first node given by pointer head
ii). Data to be inserted at the last node
OUTPUT: Linked list with the new node inserted at the
beginning of list
Step 1: temp node = new node { Creates a
new node}
Step 2: Input temp -> data
Step 3:
temp node -> next = head
Step 4: temp = temp node
Step 5: Return head
End of Algorithm
Algorithm
for insertion of a node at the end of list
INPUT: i). A singly linked list
whose first nodes given by pointer head
ii). Data to be inserted at the last node
OUTPUT: Linked list with a new
node inserted at the end
Step 1: temp node = new node
Step 2: Input temp node -> data
Step 3: temp node -> link = NULL
Step 4: list = head
Step 5: While list -> next NOT EQUAL
to NULL
(i). list = list -> next
Step 6: list -> link = temp node
Step 7: Return head
End of Algorithm
Algorithm to insert a node after a key node
INPUT: i). A singly linked list
whose first nodes given by a pointer head
ii). The data
value to be inserted
iii). Key
value of the node after which the new node is to be inserted
OUTPUT: Linked list with a new node inserted key node
Step 1: Input key
Step 2: temp node = new node
Step 3: Input temp node -> data
Step 4: Found = 0
Step 5: list = head
Step 6: While(Found = 0 AND list !=
NULL)
i).
If(list -> data = key) then
(a). temp node -> next =list -> next
(b). list -> next = temp node
(c). found =1
ii). Else
(a). list = list
-> next
(End of if condition)
(End of while loop)
Step 7: If (Found = 0) then
(a). print “Node not
found”
Step 8:
Return head
End
of Algorithm
Algorithm
for insertion of a node before a key node
INOUT: i). A singly linked list whose first nodes given by pointer head
ii). The data value to be inserted
iii). Key value of the node before which new node is to be inserted
OUTPUT: Linked list with a new
node inserted key node
Step 1: Input
key
Step 2: temp
node = new node
Step 3: Input
temp node -> data
Step 4: Found
= 0
Step 5: list =
head
Step 6: If(
head -> data = key) then
i). temp node -> next = head
ii). head = temp node
iii). Return head
(End of if condition)
Step 7: While
(Found = 0 )AND (list -> next != NULL)
i). If (list -> next ->
data = key) then
a). temp node
-> next = list -> next
b). list ->
next = temp node
c). Found =1
ii). Else
a). list = list
-> next
( End of if condition)
(End
of while loop)
Step 8:
If(Found = 0 ) then
a). print “ node not found”
Step 9: Return
head
(End of Algorithm)
Algorithm for
insertion of a node
at a particular position
INPUT: i). A singly linked list
whose first nodes given by pointer head
ii). Data to be insert
iii). Key
position which is the position in which new node is to be inserted (Here the 1st node is consider to be at position 0 )
OUTPUT: Linked list with a new at the particular position
Step 1: Input
key position
Step 2: temp
node = new node
Step 3: Input
temp node -> data
Step 4: If ( key_position = 0) then
i). temp node -> next = head
ii). head = temp node
iii).
Return head
( End of if condition)
Step 5: valid_position = 0
Step 6: current_position = 1
Step 7: list = head
Step 8: While (valid_position = 0) AND (list != NULL)
i). if( current_
position) then
(a).
temp node -> next = list -> next
(b).
list -> next = temp node
(c). valid_position = 1
ii). Else
(a).
current_position = current_position + 1
(b).
list = list -> next
(End of if condition)
(End
of while loop)
Step 9: If (
valid_position = 0) then
i). print “ Invalid position”
Step 10:
Return head
(End
of Algorithm)
Algorithm
to delete the first node of a singly
linked list
INPUT: A singly linked list whose first node is
given by pointer head
OUTPUT: The singly linked list
after deletion of a first node
Step 1: head =
head -> next
Step 2: Return
head
(End of Algorithm)
Algorithm to delete the last node of a singly linked
list
INPUT: A singly linked list
whose first nodes given by pointer head
OUTPUT: The linked list of a
last node will be deleted
Step 1:
If(head -> next = NULL) then
(a). head = NULL
(b). Return NULL
Step 2: list =
head
Step 3: While
(list -> next -> = NULL )
(a). list = list -> next
Step 4: list
-> next = NULL
Step 5: Return
head
(End of Algorithm)
Algorithm for deletion of a particular value
INPUT: A singly linked list whose first node is
given by pointer head.
OUTPUT: The linked list with the new node of a
particular value.
Step 1: Input
key
Step 2: Found
= 0
Step 3: If (
head -> data = key) then
(a). head = head -> next
(b). Return head
( End of if condition)
Step 4: list =
head
Step 5: While
( list -> next != NULL)
(a). If ( list -> next ->
data = key)
i). found = 1
ii). list ->
next = list -> next -> next
(End of if condition)
(End
of while loop)
Step 6: If (
found = 0) then
(a). print “ node not found”
(End of if condition)
Step 7: Return
head
(End of Algorithm)
Algorithm
for deletion of a particular position
INPUT: A singly linked list whose first node is
given by pointer head.
OUTPUT: The linked list with the new node of a
particular position.
Step 1: Input pos
Step 3: If (
pos<1 ||pos>countNodes) then
(a). P= head
(b). Head =headà next
Step 5: While
( cnt<pos)
(a). Cnt+1
i). Temp= p
ii). Tempànext=pànext
(End of if condition)
(End
of while loop)
Step 6: If (
found = 0) then
(a). print “ node not found”
(End of if condition)
Step 7: Return
head
(End of Algorithm)
0 comments:
Post a Comment