NB: Use C$++$ for the coding part

Question $1$ Linked List

$($a$)$ Draw a linked list from items $5,2,8,4,1$ with the head pointer pointing at node $5.$

i$.$ Describe the steps covered to add item $6$ at the end with two conditions: with and

without the tail pointer.

ii$.$ Using linked list in $($a$),$ write an algorithm to print the items of the above singly linked list

in reverse order as $1,4,8,2,5$ in $O(n^2)$ time. The structure used for the implementation

has the tag Node with fields item and next. $[$NB: You may use an extra pointer in

necessary$]$

$($b$)$ Draw a sorted doubly linked list for the items in $($a$).$ Show every step for adding each item and how

the sorted list is maintained.