**Algorithm for Doubly linked list**
Data structure definition: -
Node:
data {to store data in a node}
prev {to point to the previous node}
next {to point to the next node}
_____________________________________________________________________________
Algorithm to create a list: -
Input:
A,
set of data values
number of list elements, n
Output: A Doubly Linked List
Step
1: input n
Step
2: head = new node
Step
3: head=NULL
Step
4: end=NULL
Step
5: tempnode=new node
Step
6: Input tempnode->data
Step
7: tempnode->next=NULL
Step
8: for i=1 to n,
a)
if(head=end=NULL)
then
1.
tempnode->prev=NULL
2.
head=end=tempnode
b)
else
1.
tempnode->prev=end
2.
end->next=tempnode
3.
end=tempnode
(End of if condition)
(End of for loop)
Step
9: Return head
_____________________________________________________________________________
Algorithm for forward traversal of a Doubly
linked list: -
Input:
A Doubly linked list whose first node
is given by pointer head
Output: Data of each node
Step
1: list = head
Step
2: while (list->next <> NULL)
a.
Print list ->
data
b.
list = list ->
next
Step
3: return head
_____________________________________________________________________________
Algorithm for reverse traversal of a Doubly
linked list:
Input:
A Doubly linked list whose first node
is given by pointer head
Output: Data of each node
Step
1: list = end
Step
2: while (list->prev <> NULL)
a.
Print list ->
data
b.
list = list ->
prev
Algorithm for insertion of an element at the
beginning of a Doubly linked list:
Input: 1. A Doubly linked list whose first node is given
by pointer head
2.
Data to be inserted at the first node
Output: Linked list after
insertion of a new node at the beginning of the list
Step
1: tempnode = new node {creates a new node}
Step
2: Input tempnode -> data
Step
3: tempnode->prev=NULL
Step
4: tempnode -> next = head
Step
5: head->prev = tempnode
Step
6: head=tempnode
Algorithm for insertion of an element at the
end of a Doubly linked list: -
Input: 1. A Doubly
linked list whose first node is given by pointer head
2. Data to be inserted at the end of
the linked list
Output: Linked list after
insertion of a new node at the end of the list
Step
1: tempnode = new node {creates a new node}
Step
2: Input tempnode -> data
Step
3: tempnode -> next = NULL
Step
4: tempnode -> prev=end
Step
5: end->next=tempnode
Step
6: end = tempnode
Algorithm for insertion of an element after a
key node of a Doubly linked list: -
Input: 1. A
Doubly linked list whose first node is given by pointer head
2. Data to be inserted
3.
The key value of the node after which, the new node has to be inserted,
key
Output: Linked list after insertion
Step
1: Input key
Step
2: tempnode = new node
Step
3: Input tempnode -> data
Step
4: found=0
Step
5: list = head
Step
6: while (found = 0 and list <> NULL)
a.
If (list ->
data = key), then,
i.
list1 =
list->next
ii.
tempnode ->
next = list1
iii.
tempnode ->
prev = list
iv.
list -> next =
tempnode
v.
list1 -> prev
= tempnode
vi.
found = 1
b.
else,
i.
list = list ->
next
(End of if condition)
(End of while loop)
Step
7: if found=0, then
print “NODE NOT FOUND”
(End of if condition)
Step
8: return head
_____________________________________________________________________________
Algorithm for insertion of an element before a
key node of a Doubly linked list: -
Input: 1. A Doubly linked list whose first node is given
by pointer head
2. Data to
be inserted
3. The key value of the node before which, the
new node has to be inserted, key
Output:
Linked list after insertion
Step
1: Input key
Step
2: tempnode = new node
Step
3: Input tempnode -> data
Step
4: found=0
Step
5: list = head
Step
6: if head -> data = key, then
a.
tempnode ->
next = head
b.
tempnode ->
prev = NULL
c.
head -> prev =
tempnode
d.
head = tempnode
e.
Return head
(End of if condition)
Step
7: while (found = 0 AND list -> next
<> NULL)
a.
If (list ->
data = key), then,
1. listp=list->prev
2. tempnode -> next = list
3. list -> prev= tempnode
4. listp->next=tempnode
5. tempnode->prev=listp
6. found = 1
b.
else
1.
list = list -> next
(End of if condition)
(End of while loop)
Step 8: if found=0, then
print “NODE NOT FOUND”
(End of if condition)
Step
9: return head
_____________________________________________________________________________
Algorithm for insertion of an element at a
particular position of a Doubly linked list: -
Input:1. A Doubly linked list whose first node is given
by pointer head
2. Data to be inserted
3. Keyposition, which is the position in which
new node is to be inserted
Output: Linked
list after insertion
NOTE: Here the first node is
considered to be at position =0
Step
1: input keyposition
Step
2: tempnode = new node
Step
3: input tempnode -> data
Step
4: if (keyposition =1), then,
a.
tempnode ->
next = head
b.
tempnode ->
prev =NULL
c.
head -> prev
=tempnode
d.
head = tempnode
a.
Return head
(End of if condition)
Step
5: validposition = 0
Step
6: currentposition = 0
Step
7: list = head
Step
8: while (vaidpostion = 0 and list <>NULL)
a. If
(currentposition = keyposition-1), then,
1. currentposition = currentposition + 1
2. list = list -> next
(End of if condition)
(End of while loop)
Step
9: listp=list->prev
Step
10: tempnode->next=list
Step
11: list->prev=tempnode
Step
12: list p->next=tempnode
Step
13: tempnode->prev=listp
Step
14: Return head
____________________________________________________________________________
Algorithm for deletion of first node of a Doubly
linked list: -
Input: A Doubly linked list whose first node is
given by pointer head
Output: Linked list after deletion of a first node of
the list
Step
1: if (head = NULL), then,
a. print “EMPTY LIST”
b. Return NULL
(End of if condition)
Step 2: if (head = end) then
a. head = end = NULL
b. Return NULL
(End of if condition)
Step
3: head = head -> next
Step
4: head -> prev = NULL
Step
5: Return head
_____________________________________________________________________________
Algorithm for deletion of last node of a Doubly
linked list: -
Input: A Doubly linked list whose last node is
given by pointer head
Output: Linked list after deletion
of a last node of the list
Step
1: if (head = NULL), then,
a. print “EMPTY LIST”
b. Return NULL
(End of if condition)
Step
2: if (head = end), then,
a. head = end = NULL
b. Return NULL
(End of if condition)
Step
3: end = end -> prev
Step
4: end -> next = NULL
Algorithm for deletion of a node with a
particular value of a Doubly linked list: -
Input:
A Doubly linked list whose first node
is given by pointer head
The key value of the node which is to be
deleted
Output: The Doubly linked list after deletion
Step
1: Input keyvalue
Step
2: found = 0
Step
3: if (head -> data =keyvalue)
a.
head =head ->
next
b.
head -> prev =
NULL
c.
Return head
(End of if condition)
Step
4: list = head
Step
5: while (list <>NULL and found =0)
a. If (list -> data =keyvalue)
1. found = 1
2. nodep = list -> prev
3. noden = list -> next
4. nodep -> next = noden
5. noden -> prev = nodep
b. else
1. list = list -> next
(End of if condition)
(End of while loop)
Step
6: if(found=0), then,
1. print “Node not found”
(End of if condition)
Step
7: Return head
_____________________________________________________________________________
Algorithm for deletion of a node with a
particular position of a Doubly linked list: -
Input:
A Doubly linked list whose first node
is given by pointer head
The key position of the node
which is to be deleted
Output:
The Doubly linked list after deletion
_____________________________________________________________________________
Step 1: input pos
Step 2: currrentNode = head
Step 3: i=1
Step 4: while( i<pos AND
curNode<>=NULL)
a. curNode = curNode->next
b. i=i+1
Step 5: if (pos = 1) then
a. DlListDeleteFirstNode() //Write the algo of first node deletion
Step 6: else if (curNode = last) then
a. DlListDeleteLastNode() // Write the algo of last node deletion
Step 7: else if (curNode <>= NULL) then
a. curNode->prev->next=
curNode->next
b. curNode->next->prev =
curNode->prev
c. Remove (curNode)
Step 8: else
a. print" Invalid
position!...Try again."
Step 9: Return head
_____________________________________________________________________________
June 14, 2020
