Write functions to implement a basic set of operations $($create$,$ delete, traverse, search

$($key$)$ on a linked list. Moreover add functions to do the following:

$($B$)$ Concatenate two given list into a concatenated list such that the final list is in sorted order

Input

$1357$

$2468$

Output:

$12345678$

$($C$)$ Insert an element in a linked list in sorted order. The function will be called for every

element to be inserted. $[8]$

void insert$\_$sorted $($node $**$ head, node $*$element$)$;

Input: $,391116$

$15$

Output:

$391115$

$16$

$($D$)$ Alwaysinsert elements at one end, and delete elements from the other end $($first$-$in

first$-$out QUEUE$).[10]$

void insert$\_$q $($node $****$ head, node $*$element$)$

node Return the deleted node

Input $($for insertion$)$:

$3579$

$6$

Output:

$($E$)$ Always Insert elements at one end, and delete elements from the other end $($last$-$in first$-$out

STACK$)[10]$

void insert$\_$s $($node $****$ head, node $**$ element$)$

node Return the deleted node $63579$

Input $($for deletion$)$:

$3579$

Output:

$3$

Input $($for insertion$)$:

$3579$

Output:

$63579$

Input $($for deletion$)$:

$3579$

Output:

$9$ second$-$highest element in the list $($unsorted input$)[10]$ node

$*$second$\_$highest$($node $**$ head$)$

Input

$47269$

Output

$7$