data structure - sorting

BUBBLE SORT

BUBBLE _SORT [N,A]


The bubble sort loops through the elements in the list comparing the adjacent element and moves the largest element to the top of the list

Here , n= total no of elements
a= represent the list of element
i &j =are the integer variable
Temp=temporary variable of type integer


step 1: [ Initialize]

I0


Step 2: repeat through step 5 while (i

Step 3: [Initialize]

J0

Step 4: repeat through step 5 while ( j< n-i)


Step 5: if (a[j] > a[j+1]) then

(temp is a temporary variable which store the largest element )

tempa[j]
a[j]  a[j+1]
a[j+1]  temp

endif

step 6: Exit






SELECTION SORTING


SELECTION _SORTING (A,N)



Selection sorting starts from fist element and searches the entire list until finds the minimum value. The sort places minimum value in the first place, select the second element and searches for the second smallest element.

Here , n= represent the size of list
a= represent the list of elements
i &j =are the integer variable
Temp=temporary variable of type integer


Step 1: [initialize]

I0

Step 2: Repeat through step 7 while ( i
Step 3: [initialize]

J I+1

Step 4: Repeat through step 6 while (j
step 5: if (a[j] > a[j]) then

(temp is a temporary variable which store the largest element )

temp a[j]
a[j]  a[j]
a[j]  temp

endif

step 6: j  j+1

step 7: I I+1

step 8: Exit



LINEAR SEARCH

LINEAR _SEARCH (I,N,KEY)

This is a technique to find out an element an unsorted list. In this technique value is compared with the first element if match is found then search is successful otherwise next element from the list is fetched and compared with the key.
This process is continue till the key is found or list is completed.

Where a= represent the list of element
N=represent the no of element in the list
Key=represent the value to be search in the list
Flag =0 means True
Flag =1 means False


Step 1: [initaialize]

I0
Flag1

Step 2: Repeat step 3 for k=0,1,2………..n-1

Step 3: a[i] = key then

Flag0
( prompt the message search successful)
write “search is successful”
(increasing the value of variable I by 1)

II+1

Step 4: [prompt the message if search is not done]
Write “Search is unsuccessful”

Step 5: Exit








BINARY SEARCH

BINARY_SEARCH (KEY,N,A)

Binary search works for sorted list and is a very efficient technique.It is use to find the location of a given element or record in a list.


Where low= lower limit of the list
upper =upper limit of the list
mid= average of low and high

a= represent the list of element
N=represent the no of element in the list
Key=represent the value to be search in the list
Flag =0 means True
Flag =1 means False



Step 1: [initialize]

Low0
uppern-1
Flag1

Step 2: Repeat through step 4 while ( low<=upper)

Step 3: [find average]

mid (low+upper)/2
step 4: if (key = a[I]) then

(change the lower to mid)

uppermid-1
else if
(change upper to mid)
lowmid+1

else if
(when key is found)

(key = a[mid])

write “Search is successful”
flag0

return

step 5: if (flag =1)
write “search is unsuccessful”

step 6: Exit





DOUBLE ORDER LINK LIST

DOUBLE_LIST (HEAD,VAL)

[This function to insert an element in the list which sorted to its info field and value is the info field of the new node and prev is the field which point to previous node]

step 1: [Allocate the memory for the new node]

new=node

step 2: [Copy the information field of the new node]

info(new)=val

step 3: [is the list empty?]

if (temphead=NULL) then

temphead newnode
next(temphead) NULL
return (temphead)

step 4: [does the newnode precede all other node in the list?]

if (val < info(temphead) then

prev(newnode) prev(temphead)
next(newnode) temphead
tempheadnewnode
return (temphead)
else

firsttemphead

while(val > info(next(temphead)) && next(temphead) !=NULL)
tempheadnext(temphead)

endwhile

next(newnode) next(temphead)
prev(newnode) temphead
next(temphead) newnode
return (first)
step 5: exits

Read more »

data structure - tree

1. Algorithm For Create of Binary Tree:-

Function CREATE(T,VAL)
[ROOT=Dummy header for the root of the binary tree initialized by NULL,
NEWNODE=Variable points to the new element,
T=Temporary variables for traverse the tree,
INFO=Information part of node.]

Step 1: [Allocate the memory for new node .]
NEWNODE<=NODE

Step 2: [Read the element.]
Read(VAL)

Step 3: [Store element into new node.]
INFO(NEWNODE )VAL

Step 4: [Temporary store right and left tree is NULL.]
LEFT(NEWNODE)RIGHT(NEWNODE)NULL

Step 5: [Check if the root is NULL.]
If ROOT=NULL
Then
ROOTNEWNODE
Return

Step 6: [Search the place to insert the element.]
While T!=NULL
(Check for element is less than information of T)
if VAL < INFO (T)
then
PARENTT
TLEFT(T)
Else
PARENTT
TRIGHT(T)

Step 7: [Check element is less than information of parent.]
If VAL < INFO(PARENT)
Then
LEFT(PARENT)NEWNODE
Else
RIGHT(PARENT)NEWNODE


2. Algorithm For Inorder Traversal of Binary Tree:-

Function INORDER(T)
[T = Temporary pointer variable initialized with root,




INFO=Information part of node,
LEFT=Pointer to left most node,
RIGHT=Pointer to right most node,]

Step 1: [Repeat step 2,3,4 and check that T is not equal to NULL ]
If T!=NULL
Then

Step 2: [Call function itself as a left most node.]
INORDER(LEFT(T))

Step 3: [Print information part of node.]
Write INFO(T)

Step 4: [Call function itself as a right most node.]
INORDER(RIGHT(T))


3. Algorithm For Preorder Traversal of Binary Tree:-

Function PREORDER(T)
[T = Temporary pointer variable initialized with root,
INFO=Information part of node,
LEFT=Pointer to left most node,
RIGHT=Pointer to right most node,]

Step 1: [Repeat step 2,3,4 and check that T is not equal to NULL ]
If T!=NULL
Then

Step 2:[Print information part of node.]
Write INFO(T)

Step 3: [Call function itself as a left most node.]
PREORDER(LEFT(T))

Step 4: [Call function itself as a right most node.]
PREORDER(RIGHT(T))



4. Algorithm For Postorder Traversal of Binary Tree:-

Function POSTORDER(T)
[T = Temporary pointer variable initialized with root,
INFO=Information part of node,
LEFT=Pointer to left most node,
RIGHT=Pointer to right most node,]

Step 1: [Repeat step 2,3,4 and check that T is not equal to NULL ]
If T!=NULL
Then

Step 2: [Call function itself as a left most node.]
POSTORDER(LEFT(T))

Step 3: [Call function itself as a right most node.]
POSTORDER(RIGHT(T))

Step 4: [Print information part of node.]
Write INFO(T)


5. Algorithm For Depth of Binary Tree:-

Function DEPTH(T, LEVEL)
[T = Temporary pointer variable initialized with root,
INFO=Information part of node,
LEFT=Pointer to left most node,
RIGHT=Pointer to right most node.]

Step 1: [Repeat step 2,3,4 and check that T is not equal to NULL ]
If T!=NULL
Then

Step 2: [Check D is less than LEVEL.]
If D Then
(Store LEVEL into D)
DLEVEL

Step 3: [Call function itself as a left most node.]
DEPTH(LEFT(T),LEVEL+1)

Step 4: [Call function itself as a right most node.]
DEPTH(RIGHT(T),LEVEL+1)

Step 5: [Print the LEVEL.]
Write ‘level’,D


6. Algorithm For Search of Binary Tree:-

Function SEARCH(T,KEY)
[T = Temporary pointer variable initialized with root,
INFO=Information part of node,
LEFT=Pointer to left most node,
RIGHT=Pointer to right most node.]

Step 1:[Read the KEY]
Read(KEY)
Step 2: [Repeat step 2,3,4 and check that T is equal to NULL ]
If T = NULL
Then
(Prompt the message key not found)
write ‘Key not found’
return

step 3: [Check the that information of T is equal to key.]
If INFO(T)=KEY
Then
(Prompt the message key found)
write ‘Key found’
return

step 4: [Check that key is less than information of T.]
If KEY Then
(Call function itself as a left most node.)
SEARCH(LEFT(T),KEY)
Else
(Call function itself as a right most node.)
SEARCH(RIGHT(T),KEY)


7. Algorithm For Modify of Binary Tree:-

Function MODIFY (T,KEY,VAL)
[T = Temporary pointer variable initialized with root,
INFO=Information part of node,
LEFT=Pointer to left most node,
RIGHT=Pointer to right most node.
VAL=New element.]

Step 1: [Read the KEY]
Read (KEY)

Step 2: [Read the value.]
Read(VAL)

0Step 3: [Repeat step 4,5,6 and check that T is equal to NULL ]
If T = NULL
Then
(Prompt the message key not found)
write ‘Key not found’
return

step 4: [Check the that information of T is equal to key.]
If INFO(T)=KEY
Then
(To store value in information of T)
INFO(T)VAL
return

step 5: [Check that key is less than information of T.]
If KEY Then
(Call function itself as a left most node.)
MODIFY(LEFT(T),KEY,VAL)
Else
(Call function itself as a right most node.)
MODIFY(RIGHT(T),KEY,VAL)

Read more »

circular queue

4) CIRCULAR QUEUE :

7) Procedure ( VAL )
[Description]

Step 1: [Check Queue is overflow or not]

If REAR = 0 AND REAR=SIZE – 1
Then
Write (‘Overflow…..’)
Return

If REAR = FRONT -1
Then
Write (‘Overflow…..’)
Return

Step 2: [If needed Reset the pointer, and insert value]

If REAR = SIZE – 1
Then
REAR = 0
Q [REAR]  VAL

Else If REAR= -1
Then
REAR  FRONT  0
Q [REAR]  VAL
Else
REAR  REAR +1
Q [REAR]  VAL
Step 3: [Finished]

Return
--------------------------------------------------------------------------------------------
8) Function DELETE ( )
[Description]

Step 1: [Check Queue is empty or not]

If FRONT < 0
Then
Write (‘Queue Underflow……’)
Return -1

Step 2: [Delete an element]

VAL  Q [FRONT]

Step 3: [Queue Empty?]

If FRONT = REAR
Then
FRONT  REAR  -1
Else If FRONT = SIZE – 1
Then
FRONT  0
Else
FRONT  FRONT + 1

Step 4: [Return the Deleted element]

Return VAL
----------------------------------------------------------------------------------------------
9) Procedure PRINT
[Description]

Step 1: [Check Queue is empty or not]

If FRONT < 0
Then
Write (‘Underflow…..’)
Return

Step 2: [Print the element of Queue]

If FRONT < = REAR
Then
Repeat for I = FRONT, FRONT+1…… I < = REAR
Write Q [I]
Else
Repeat for I = FRONT, FRONT+1…… I < SIZE
Write Q [I]
Repeat for I = 0, 1….I < = REAR
Write Q [I]

Step 3: [Finished]

Return

Read more »

Queue

2) QUEUE USING ARRAY:

1) Procedure ( VAL )
[Description]

Step 1: [Check Queue is overflow or not]

If REAR >= SIZE – 1
Then
Write (‘Overflow…..’)
Return

Step 2: [Check it is first element or not]

If FRONT = = -1
Then
FRONT  0

Step 3: [Increment REAR pointer by 1]

REAR  REAR +1

Step 4: [Assign value]

Q [REAR]  VAL

Step 5: [Finished]

Return
--------------------------------------------------------------------------------------------
2) Function DELETE ( )
[Description]

Step 1: [Check Queue is empty or not]

If FRONT < 0
Then
Write (‘Queue Underflow……’)
Return -1

Step 2: [Delete an element]

VAL  Q [FRONT]

Step 3: [Queue Empty?]

If (FRONT = REAR)
Then
FRONT  REAR  -1
Else
FRONT  FRONT +1

Step 4: [Return the Deleted element]

Return VAL
----------------------------------------------------------------------------------------------
3) Procedure PRINT
[Description]

Step 1: [Check Queue is empty or not]

If FRONT < 0
Then
Write (‘Underflow…..’)
Return

Step 2: [Print the element of Queue]

Repeat For I = FRONT, FRONT + 1 …While I < = REAR
Write Q [I]

Step 3: [Finished]

Return


3) QUEUE USING LINK LIST :

4) Procedure INSERT( VAL )
[Description]

Step 1: [Allocate the memory location]

NEWNODE  NODE

Step 2: [Check memory is available or not]

If NEWNODE = NULL
Then
Write (‘Queue Overflow……)
Return

Step 3: [Insertion as a first NODE]

If REAR = NULL
Then
FRONT  REAR  NEWNODE
NEXT (REAR)  NULL
Return

Step 4: [Insertion as other NODE]

NEXT (REAR)  NEWNODE
REAR  NEWNODE
NEXT (REAR)  NULL
Return
--------------------------------------------------------------------------------------------
5) Function DELETE ( )
[Description]

Step 1: [Check Queue is empty or not]

If FRONT = NULL
Then
Write (‘Queue Underflow……’)
Return -1

Step 2: [Delete an element]

VAL  INFO (FRONT)

Step 3: [If needed reseat pointer]
If FRONT = REAR
Then
FRONT  REAR  NULL
Else
FRONT  NEXT (FRONT)

Step 4: [Return the Deleted element]

Return VAL
----------------------------------------------------------------------------------------------
6) Procedure PRINT
[Description]

Step 1: [Check Queue is empty or not]

If TEMP = NULL
Then
Write (‘Underflow…..’)
Return

Step 2: [Store FRONT into TEMP]

TEMP  FRONT

Step 3: [Print the element of Queue]

Repeat While TEMP # NULL
Write INFO (TEMP)
TEMP  NEXT (TEMP)

Step 4: [Finished]
Return

Read more »

data structure - stack

1)         STACK USING ARRAY: -

            1)         Procedure PUSH (VAL)

                        [Description]

                        Step 1: [Check stack is empty or not]

                                    If TOS >=SIZE-1

                                    Then

                                                Write (‘Stack Overflow……..’)

                                                Return

                        Step 2: [Increment TOS by 1]

                                   

                                    TOS ¬ TOS+1

                        Step 3: [Assign value]

                                   

                                    S [TOS] ¬ VAL

                        Step 4: [Finished]

                       

                                    Return

--------------------------------------------------------------------------------------------------

2)            Function POP ( )

            [Description]

            Step 1: [Check stack is empty or not]

                        If TOS < 0

                        Then

                                    Write (‘Stack Underflow…..’)

                                    Return -1

            Step 2: [Decrement pointer]

           

                        VAL ¬ S [TOS]

                        TOS ¬ TOS – 1

            Step 3: [Return deleted value]

                        Return VAL

---------------------------------------------------------------------------------------

2)                  Function PEEP ( KEY)

            [Description]

            Step 1: [Find the element number]

                        INDEX ¬ TOS – KEY +1

            Step 2: [Check stack is empty or not]

                        If INDEX < 0

                        Then

                                    Write (‘Stack Underflow…..’)

                                    Return -1

            Step 3: [Return the element from stack]

                        Return S [INDEX]

--------------------------------------------------------------------------------------

3)                  Function CHANGE ( KEY , VAL)

            [Description]

            Step 1: [Find the element number]

                        INDEX ¬ TOS – KEY +1

            Step 2: [Check stack is empty or not]

                        If INDEX < 0

                        Then

                                    Write (‘Stack Underflow…..’)

                                    Return -1

            Step 3: [Change the value from stack]

                        S [INDEX] ¬VAL

                        Return 1

--------------------------------------------------------------------------------------

4)                  Procedure PRINT ( )

            [Description]

                        Step 1: [Check Stack is empty or not]

                                    If TOS < 0

                                    Then

                                                Write (‘Stack Underflow……’)

                                                Return

                       

                                    Step 2: [Print the value from stack]

           

                                                Repeat For I = TOS, TOS-1…….While I >= 0

                                                Write S [I]

           

                                    Step 3: [Finished]

                                                Return

1)         STACK USING LINK LIST: -

            1)         Procedure PUSH (VAL)

                        [Description]

                        Step 1: [Allocate the memory]

                                    NEWNODE  Ü NODE

                        Step 2: [Read the INFO]

                                   

                                    Read (INFO (NEWNODE))

                                   

                        Step 3: [Arrange the address]

                                   

                                    NEXT (NEWNODE) ¬ TOS

                                    TOS ¬ NEWNODE

                        Step 4: [Finished]

                                    Return

--------------------------------------------------------------------------------------------------

3)            Function POP ( )

            [Description]

            Step 1: [Check stack is empty or not]

                        If TOS = NULL

                        Then

                                    Write (‘Stack Underflow…..’)

                                    Return -1

            Step 2: [Assign deleted value in VAL]

           

                        VAL ¬ INFO (TOS)

            Step 3: [Assign the address of next NODE in TOS]

                        TOS ¬ NEXT [TOS]

                        Return VAL

---------------------------------------------------------------------------------------

5)                  Function PEEP ( KEY)

            [Description]

            Step 1: [Store TOS into TEMP]

                       

                        TEMP ¬ TOS

            Step 2: [Repeat the loop up to last NODE]

                       

                        I ¬ 1

                        Repeat While TEMP # NULL

                                    If I = KEY

                                    Then

                                                Return 1

                                    Else

                                                TEMP ¬ (NEXT) TEMP

                                                I ¬ I+1

                                               

            Step 3: [KEY not found, so return false]

                       

                        Return -1

            --------------------------------------------------------------------------------------

6)                  Function CHANGE ( KEY , VAL)

            [Description]

            Step 1: [Store TOS into TEMP]

                        TEMP ¬ TOS

            Step 2: [Repeat the loop up to last NODE]

                       

                        I ¬ 1

                        Repeat While TEMP # NULL

                                    If I = KEY

                                    Then

                                                INFO (TEMP) ¬ VAL

                                                Return 1

                                    Else

                                                TEMP ¬ (NEXT) TEMP

                                                I ¬ I+1

                                               

            Step 3: [KEY not found, so return false]

                       

                        Return -1

--------------------------------------------------------------------------------------

7)                  Procedure PRINT ( )

            [Description]

            Step 1: [Store TOS into TEMP]

                        TEMP ¬ TOS

                        Step 2: [Repeat the loop till the last NODE]

                                   

                                    Repeat While TEMP # NULL

                                                Write INFO (TEMP)

                                                TEMP ¬ NEXE (TEMP)

                       

                        Step 3: [Finished]

                       

                                    Return

Read more »

data structure

• Function CREATE (FRONT)
This function is used to create list. FRONT is a NODE type pointer variable of structure LinkList having two member variables INFO which stores actual information and structure type pointer NEXT which store address of next node. Its last node contains address of first 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. [Temporary storage of head]
FIRST ← FRONT
4. [Check for continuity]
Read (CH)
5. [Iterate the loop]
Repeat through step 9 while CH ≠ ‘N’
6. [Allocate memory for next node]
NEXT(FRONT) <= NODE
7. [Move FRONT pointer to next node]
FRONT ← NEXT(FRONT)
8. [Read the information of new node]
Read (INFO(FRONT))
9. [Check for continuity]
Read (CH)
10. [Termination of loop]
NEXT(FRONT) ← FIRST
11. [Return address of first node]
Return FIRST


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

Variable :
FIRST : Description as per create function.

1. [Temporary storage of head]
FIRST ← FRONT
2. [Iterate the loop]
Repeat through step 3 while NEXT(FRONT) ≠ FIRST
3. [Print information of current node]
Write (INFO(FRONT))
4. [Move FRONT pointer to next node]
FRONT ← NEXT(FRONT)
3. [Print information of last node]
Write (INFO(FRONT))
6. [Finish]
Exit

• 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. [Store head into temporary variable]
TEMP ← FRONT
4. [Insertion as first node]
If INFO(FRONT) = KEY
Then
NEXT(NEW) ← FRONT
(iterate loop till last node)
Repeat while NEXT(FRONT) ≠ TEMP
FRONT ← NEXT(FRONT)
NEXT(FRONT) ← NEW
TEMP← NEW
Return TEMP
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
NEXT(NEW) ← NEXT(FRONT)
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


• 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. [Store head into temporary variable]
FIRST ← FRONT
2. [Deletion as first node]
If INFO(FRONT) = KEY
Then
REMOVE ← FRONT
(iterate loop till last node)
Repeat while NEXT(FRONT) ≠ TEMP
FRONT ← NEXT(FRONT)
NEXT(FRONT) ← NEXT(FIRST)
FIRST ← NEXT(FIRST)
(Free the memory of deleted node)
Restore REMOVE
Return FIRST
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))
(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

Read more »

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

Read more »

data structure

• Function CREATE (FRONT)

This function is used to create list. FRONT is a NODE type pointer variable of structure LinkList having two member variables 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.         [Temporary storage of head]

                                    FIRST  ← FRONT

            4.         [Check for continuity]

                                    Read (CH)

            5.         [Iterate the loop]

                                    Repeat through step 9 while CH ≠ ‘N’

            6.         [Allocate memory for next node]

                                    NEXT(FRONT) <= NODE

            7.         [Move FRONT pointer to next node]

                                    FRONT ← NEXT(FRONT)

            8.         [Read the information of new node]

                                    Read (INFO(FRONT))

            9.         [Check for continuity]

                                    Read (CH)

            10.       [Termination of loop]

                                    NEXT(FRONT) ← NULL

            11.       [Return address of first node]

                                    Return FIRST

• Function COUNT (FRONT)

This function is used to count total number of node in the list. Description as per create function. This function return total number of node in list.

            Variable :

                        COUNT : is used to store the total number of node.

            1.         [Initialize COUNT variable with 0]

                                    COUNT ← 0

            2.         [Iterate the loop]

                                    Repeat through step 4 while FRONT ≠ NULL

            3.         [Increment the COUNT value by 1]

                                    COUNT ← COUNT + 1

            4.         [Move FRONT pointer to next node]

                                    FRONT ← NEXT(FRONT)

            5.         [Return total number of node in list]

                                    Return COUNT

• Procedure PRINT (FRONT) 

This procedure prints the information of all the nodes. Description as per create function.

            1.         [Iterate the loop]

                                    Repeat through step 3 while FRONT ≠ NULL

            2.         [Print information of current node]

                                    Write (INFO(FRONT))

            3.         [Move FRONT pointer to next node]

                                    FRONT ← NEXT(FRONT)

            4.         [Finish]

                                    Exit

• 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

                                                NEXT(NEW) ← FRONT

                                                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

                                                            NEXT(NEW) ← NEXT(FRONT)

                                                            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

• Function SEARCH (FRONT, KEY)

This function is used search any key value from the given list. Description as per create function. KEY is value which is to be searched. This function return true or false whether given value is in list or not.

           

            Variable :

                        TRUE : it stores 1

                        FALSE : it stores 0.

            1.         [Iterate the loop]

                                    Repeat through step 3 while FRONT ≠ NULL

            2.         [Check whether information of current node is the key value or not]

                                    If  INFO(FRONT) = KEY

                                    Then

                                                Return TRUE

                                    Else

                                                (move first pointer on next node)

                                                FRONT ← NEXT(FRONT)

            3.         [return value not found]

                                    Return FALSE

• Function UPDATE (FRONT, KEY,VAL)

This function is used update any key value from the given list with new value. Description as per create function. KEY is value which is to be updated; VAL is variable which stores new value to be updated. This function return true or false whether given value is in list or not.

           

            Variable :

                        TRUE : it stores 1

                        FALSE : it stores 0

            1.         [Iterate the loop]

                                    Repeat through step 3 while FRONT ≠ NULL

            2.         [Check whether information of current node is the key value or not]

                                    If  INFO(FRONT) = KEY

                                    Then

                                                (update current information with new value)

                                                INFO(FRONT) ← VAL

                                                Return TRUE

                                    Else

                                                (move first pointer on next node)

                                                FRONT ← NEXT(FRONT)

            3.         [Return value not found]

                                    Return FALSE

• 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 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

                                                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))

                                                            (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

• Procedure SORT(FRONT)

This procedure is used to sort the list. Description as per create function.

            Variable :

                        OUTER : is NODE type pointer variable used to iterating the outer loop.

                        INNER : is NODE type pointer variable used to iterating the inner loop.

TEMP : is NODE type pointer variable used for swapping the values of two nodes.

           

            1.         [Store address of first node]

                                    OUTER ← FRONT

2.         [Repeat the outer loop up to last node]

                                    Repeat through step 5 while OUTER ≠ NULL

            3.         [Assign address of next node]

                                    INNER ← NEXT(OUTER)

            4.         [Repeat loop up to last node]

                                    Repeat while INNER ≠ NULL

(Check whether information of outer node is greater than the information of inner node)

                                                If  INFO(OUTER) > INFO(INNER)

                                                Then

                                                            (swap both the values)

                                                            INFO(TEMP) ← INFO(INNER)

                                                            INFO(INNER) ← INFO(OUTER)

                                                            INFO(OUTER) ← INFO(TEMP)

                                                Else

                                                            (move inner pointer on next node)

                                                            INNER ← NEXT(INNER)

            5.         [move the outer pointer to next node]

                                    OUTER ← NEXT(OUTER)

            6.         [Finish]

                                    Exit

Read more »