Question

5. (20%) Suppose we have an array int a [8] = {1, 2, 3, 5, 6}; and we also have a linked list L of 5 entries 1 -> 2 -> 3 -> 5 -> 6, where 1 is the first in the linked list L, followed by 2 etc. We want to put a new item 4 between 3 and 5 in the array a and in the linked list L

(a) Explain in plain English how you do that in the array a. You may have to shift items right (or left?) Do you use a loop like a for loop? You can write some C / C++ / C# / Java code etc. to convince me, but the code does not have to run.

(b) Explain in plain English how you do that in the linked list L. How do you change the link from 3 to 5 in the original list L? You can write some code or pseudo code to convince me.

Answer 1

(a) In order to insert the number 4 between 3 and 5 in the array, we have to first find the element after which we have to insert the element 4. In this case, the element we have to find is 3. So, we will need a for loop for searching for an element. Once the element is found, we will first increase the array size by 1, add the new element (here 4) and shift the rest of the elements to the right by one. Let us see the c++ for loop to achieve this.

Let n = number of elements = 5

f = is set to 0 if element we are looking for(3) is not found, othwerise false = 0

ins = initially set to the element to be inserted = 4

//start of code snippet

for(int i = 0; i < n; i++){

int temp;

if(a[i] == 3){

f = 1;

n++;

continue;

}

if(f==1){

temp = a[i];

a[i] = ins;

ins = temp;

}

}

(b) In order to insert a new element anywhere inside a linked list, all we need to do is forst find the node after which the new element is to be inserted, in this case, 3. Then we make a new node containing the element to be inserted(4) and change the link field of 3 to point to node 4, and the link field of node 4 to point to node 5. A snippet of c++ code to explain this:

node = abstract data type to store declare variables of node type. It has 2 fields, int data and node* next

head = pointer to the head of linked list

//start of snippet

node *ptr = new node;

ptr->data = 4;

ptr->next = NULL;

node *temp = head;

while(temp != NULL){

if(temp->data == 3){

ptr->next = temp->next;

temp->next = ptr;

}

}