Question

Tasks 2
Write algorithms in pseudocode to implement a LinkedList
The following operations must be performed on the LinkedList:
*Add an element
*Insert an element at a given position x.
*Retrieve/Read the value of an element at position y.
*Delete an element from position z.
(x,y and z represent any value in the valid range of indices of the LinkedList).

Answer 1

1) If Linked list is empty then make the node as
   head and return it.
2) If the value of the node to be inserted is smaller 
   than the value of the head node, then insert the node 
at the start and make it head.
3) In a loop, find the appropriate node after 
   which the input node (let 9) is to be inserted. 
   To find the appropriate node start from the head, 
   keep moving until you reach a node GN (10 in
   the below diagram) who's value is greater than 
   the input node. The node just before GN is the
appropriate node (7).
4) Insert the node (9) after the appropriate node
   (7) found in step 3.

​​​​using namespace std;

/* Link list node */

class Node {

public:

    int data;

    Node* next;

};

/* function to insert a new_node

in a list. Note that this

function expects a pointer to

head_ref as this can modify the

head of the input linked list

(similar to push())*/

void sortedInsert(Node** head_ref,

                  Node* new_node)

{

    Node* current;

    /* Special case for the head end */

    if (*head_ref == NULL

        || (*head_ref)->data

               >= new_node->data) {

        new_node->next = *head_ref;

        *head_ref = new_node;

    }

    else {

        /* Locate the node before the

point of insertion */

        current = *head_ref;

        while (current->next != NULL

&& current->next->data

< new_node->data) {

            current = current->next;

        }

        new_node->next = current->next;

        current->next = new_node;

    }

}