Question

Onl. (a) i. What is a linear list? ii. Distinguish between linear list and circular linked list. (b) With the aid of diagrams i. Write an algorithm to delete the Kth element in the list. Vt--︶ 11. write an algorithm to insert an element Y immediately after the Kth element. (c) Using the Stack and the Queue structures explain the LIFO and FIFO principle in data management. (d). Explain the statement "the time taken by an algorithm grows with the size of the input" 15marks

Answer 1

(a)

i. Linear linked list is a data structure where nodes are linked one by one. One node points to its next node and finally the last node points to null.

ii. As in the linear linked list last node points to null but in case of circular linked list "last" node points back to start of the list which makes it circular.

(b)

i. Maintain 2 pointers prev and curr.

curr

|

[1]->[2]->[3]-----------------[k-1]->[k]->[k+1]--------

Initially prev points to null and curr points to start of list.

prev curr

| |

[1]->[2]->[3]-----------------[k-1]->[k]->[k+1]--------

Then we start traversing list and keep going until curr points to kth element.

prev

|

[1]->[2]->[3]-----------------[k-1]->[k+1]--------

Now we just do prev.next = curr.next, this will remove curr node from list.

Then delete curr to free up space occupied by it.

ii. Maintain 1 pointer curr.

curr

|

[1]->[2]->[3]-----------------[k]->[k+1]--------

Initially points to head.

curr

|

[1]->[2]->[3]-----------------[k]->[k+1]--------

Traverse list till curr points to kth element.

curr

|

[1]->[2]->[3]-----------------[k]->[y]--------

Finally insert the node y next to curr i.e.

y.next = curr.next and curr.next = y.