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.

Tagged in: ,