4. Insert node at the ith position #

Created Wednesday 15 January 2020

There are 2 variables:

1. Existence: head==NULL or not
2. Index: wether 0 or not
   1. 0

   2. 0

• Wrote the general algorithm, then the exceptions. Only requirements, no need for optimizations here.

1. index 0 is always valid, heads need to be updated.
2. index > 0 has two cases:
   1. Within bound
   2. Greater than length
   3. negative indices

void insertNode(Node &head, int index, int data) { / cases possible

1. Empty list
   1. Index at 0, i.e make the first node
   2. Index != 0 do nothing
2. Non Empty list
   1. index at 0, Make the node shift the head

how to prevent negative indices ?

2. index < length -1, reach the (i-1)th node, create a node
3. index > length - 1 , do nothing

Conclusion: 1. 1.a and 2. a are the same thing, create a node at the beginning

2. 1.b is different // impossible
3. 2.b and 2.c are intertwined //

*/

if (index == 0) // case 1.a and 2.a done { Node *newnode = new Node(data); newnode->next = head; // handles both cases, i.e empty and non-empty lists head = newnode; return; }

if (head == NULL) // case 1. b done return;

// case 2.b and 2.c Node *trav = head; for (int i = 0; i < index - 1 && trav != NULL; i++, trav = trav->next) // also prevents negative indices ;

// 2.c handled if (trav == NULL) // the construction site is null, this is possible if index > length-1 return;

Node *newnode = new Node(data); newnode->next = trav->next; trav->next = newnode; return; }--------------------