C++ Program to Implement Doubly Linked List Operations (Algorithm)
AIM:
Write a program to implement doubly linked list operations.
ALGORITHM:
PROCEDURE CREATE_QUEUE(TOP)
[Where ‘head’ pointer has been caught in pointer ‘TOP’ and function is void]
1. [Allocating memory for new node & having the value from user]
Call GETNODE (TOP)
DATA (TOP) <– ‘xyz’
LINK (TOP) <– 0.
2. [Checking the value of last node & calling the function recursiverly]
if(DATA (TOP) <= 0)
return
else
Call CREATE_QUEUE (LINK(TOP))
3. [FINISH]
return.
PROCEDURE INSERT_CD(T, KEY, POS)
[Where pointer ‘T’ is a pointer which can be either pointing to first in or lasting element and key is the value after or before u want to insert new node and pos is a variable which is giving direction ‘right’ or ‘left’ of key value.]
1. [Checking the value of pointer and traversing the destination]
if (T==HEAD)
while (DATA(T) != KEY)
T <– RIGHT (T)
else
while (DATA(T) != KEY)
T <– LEFT (T).
2. [Inserting an element to the right of the destination]
if (POS == ‘R’)
if (T == P)
Call GETNODE (S)
DATA (S) <– ‘xyz’
RIGHT (P) <– S
LEFT (S) <– P
RIGHT (S) <– HEAD
LEFT (HEAD) <– S
P <– S
else
Call GETNODE (S)
DATA (S) <– ‘xyz’
RIGHT (S) <– RIGHT (T)
LEFT (S) <– T
RIGHT (T) <– S
LEFT (RIGHT(S)) <– S
P <– S.
3. [Inserting an element to the left side of destination]
else if (T == HEAD)
Call GETNODE (S)
DATA (S) <– ‘xyz’
RIGHT (S) <– HEAD
LEFT (HEAD) <– S
LEFT (S) <– P
RIGHT (P) <– S
HEAD <– S
else
Call GETNODE (S)
DATA (S) <– ‘xyz’
RIGHT (S) <– T
LEFT (S) <– LEFT (T)
LEFT (T) <– S
RIGHT (LEFT(S)) <– S.
4. [FINISH]
return.
PROCEDURE DELETE_CD(T, KEY)
[Where pointer ‘T’ is a pointer which is pointing to first in or lasting element and key is the value which we want to delete.]
1. [Checking the value of pointer and traversing the destination]
if (T==HEAD)
while (DATA(T) != KEY)
T <– RIGHT (T)
else
while (DATA(T) != KEY)
T <– LEFT (T).
2. [Deleting node from the list].
Q <– LEFT (T)
RIGHT (Q) <– RIGHT (T)
LEFT (RIGHT(T)) <– Q
if (T == HEAD)
HEAD <– RIGHT (HEAD)
else if (T == P)
P <– LEFT (P)
Call REMOVE NODE (T).
3. [FINISH]
return.
