data structure

• Function CREATE (FRONT)
This function is used to create list. FRONT is a NODE type pointer variable of structure DoublyLinkList having three member variables, structure type pointer variable PRV which stores address of previous node, INFO which stores actual information and structure type pointer NEXT which store address of next node. This function returns the address of first node.

Variable :
FIRST : is NODE type pointer which stores address of first node
CH : which is used to get whether user want to continue or not.

1. [Allocate the memory for first node]
FRONT <= NODE
2. [Read the information]
Read (INFO(FRONT))
3. [storing NULL in previous of head node]
PRV(FRONT) ← NULL
4. [Temporary storage of head]
FIRST ← FRONT
5. [Check for continuity]
Read (CH)
6. [Iterate the loop]
Repeat through step 11 while CH ≠ ‘N’
7. [Allocate memory for next node]
NEXT(FRONT) <= NODE
8. [Storing address of current node into previous of next node]
PRV(NEXT(FRONT)) ← FRONT
8. [Move FRONT pointer to next node]
FRONT ← NEXT(FRONT)
9. [Read the information of new node]
Read (INFO(FRONT))
10. [Check for continuity]
Read (CH)
11. [Termination of loop]
NEXT(FRONT) ← NULL
12. [Return address of first node]
Return FIRST

• Procedure PRINT (FRONT)
This procedure prints the information of all the nodes. Description as per create function.

1. [Iterate the loop till next of current node is not NULL]
Repeat through step 3 while NEXT(FRONT) ≠ NULL
2. [Print information of current node]
Write (INFO(FRONT))
3. [Move FRONT pointer to next node]
FRONT ← NEXT(FRONT)
4. [Iterate the loop]
Repeat through step 6 while FRONT ≠ NULL
5. [Print information of current node]
Write (INFO(FRONT))
6. [Move FRONT pointer to previous node]
FRONT ← PRV(FRONT)
7. [Finish]
Exit


• Procedure APPEND(FRONT,VAL)
This procedure is used to append new node at last. Description as per create function. VAL is used to store the value to be inserted at last.

Variable :
NEW : is a NODE type pointer which store information of new node to be append.

1. [Allocate the memory for first node]
NEW <= NODE
2. [Store information of new node]
INFO(NEW) ← VAL
3. [Repeat loop up to last node]
Repeat while NEXT(FRONT) ≠ NULL
FRONT ← NEXT(FRONT)
4. [Add new node at last]
(store address of current node in previous of new node)
PRV(NEW) ← FRONT
(store address of next of current node into next of new node)
NEXT(NEW) ← NEXT(FRONT)
(store address of new node in next of last node)
NEXT(FRONT) ← NEW
5. [Finish]
Exit

• Function DELETE (FRONT,KEY)
This function is used to delete a node from the list. Description as per create function. KEY is node which is to be deleted. This function returns address of first node.

Variable :
FIRST : is NODE type pointer which stores address of first node
REMOVE : is NODE type pointer which stores the node to be deleted.

1. [Deletion as first node]
If INFO(FRONT) = KEY
Then
REMOVE ← FRONT
(store null in previous of second node)
PRV(NEXT(FRONT)) ← PRV(FRONT)
FRONT ← NEXT(FRONT)
(Free the memory of deleted node)
Restore REMOVE
Return FRONT
2. [Store head into temporary variable]
FIRST ← FRONT
3. [Repeat loop up to last node]
Repeat while NEXT(FRONT) ≠ NULL
(Check for key value in next node)
If INFO(NEXT(FRONT)) = KEY
Then
REMOVE ← NEXT(FRONT)
NEXT(FRONT) ← NEXT(NEXT(FRONT))
(store address of current node in pre of next node)
PRV(NEXT(FRONT)) ← FRONT
(Free the memory of deleted node)
Restore REMOVE
Return FIRST
Else
(move first pointer on next node)
FRONT ← NEXT(FRONT)
4. [Prompt message key not found]
Write ‘Key value is not in list’
5. [Return head]
Return FIRST

• Function INSERT(FRONT,KEY,VAL)
This function inserts value before the given value. Description as per create function. KEY is node before which we want to insert. VAL is variable which store the information of value to be inserted. This function returns address of first node.

Variable :
NEW : is a NODE type pointer which store information of new node to be inserted.
TEMP : is NODE type pointer which stores address of first node.

1. [Allocate the memory for first node]
NEW <= NODE
2. [Store information of new node]
INFO(NEW) ← VAL
3. [Insertion as first node]
If INFO(FRONT) = KEY
Then
(storing null in previous of new node)
PRV(NEW) ←PRV(FRONT)
NEXT(NEW) ← FRONT
(storing address of new node in previous of first node)
PRV(FRONT) ← NEW
FRONT ← NEW
Return FRONT
4. [Store head into temporary variable]
TEMP ← FRONT
5. [Repeat loop up to last node]
Repeat while NEXT(FRONT) ≠ NULL
(Check for key value in next node)
If INFO(NEXT(FRONT)) = KEY
Then
(store address of current in previous of new node)
PRV(NEW) ← FRONT
NEXT(NEW) ← NEXT(FRONT)
(store address of new node in pre of current node)
PRV(NEXT(FRONT)) ←NEW
NEXT(FRONT) ← NEW
Return TEMP
Else
(move first pointer on next node)
FRONT ← NEXT(FRONT)
6. [Prompt message key not found]
Write ‘Key value is not in list’
7. [Return head]
Return TEMP