$2015$ ICS QUESTION pure comp sci extra Q $,$ given extra Q than CSB $...$

$4.$ Question Four:

In a normal singly$-$linked list, there is a pointer in each element of the list that

points to the next element:

Header A B c D

rndin $|$ Joa$\}\{$ Tl $[$ Teo$\}$ N

tail $|$&D$|$

in a subtraction linked list, the next pointer instead contains a computed

value. This value is the address of the next element in the list minus the

address of the previous element:

Header A B C D

vesdsa $|$ o Taw$0][$Jacea$][$Jevea$][$oac

tail $|$&D

The main advantage of a subtraction linked list is that it is possible to traverse

the list from either head to tail, or from tail to head. If one knows the address

of the previous element and the contents of the current element, it is always

possible to compute the address of the next element for forward traversal.

Similarly, if one knows the address of the next element and the contents of

the current element, it is always possible to compute the address of the

previous element; this allows the list to be traversed in reverse order from tail

to head.

Subtraction linked lists combine many of the advantages of singly$-$ and

doubly$-$linked lists. Like a doubly$-$linked list, the list can be traversed in both

directions. Like a singly linked list, only one pointer value per element needs

to be stored.

Write an abstract data type $($ADT$)$ to represent lists of floating point numbers

that internally uses a subtraction linked list. Your ADT should provide

functions to perform each of the following operations:

struct list $*$ list$\_$new$()$; $/$I create new empty list

float list$\_$sum$($struct list $*$ this$)$; $11$ return sum of values in list

float list$\_$get$($struct list $*$ this, int n$)$; $1$ return value of n$\text{'}$th item in list

float list$\_$val$\_$end$($struct list $*$ this, int n$)$; $1$ return n$\text{'}$th value from end of list

void list$\_$remove$($struct list $*$ this, float num$)$; $//$ remove all list elements $==$ num

void list$\_$insert$($struct list $*$ this, float val, int n$)$; $//$ insert value val to the list; new value

$/$Ishould inserted just before existing

$/$l item n in the list; if n$==0,$ insert at start

$1$ of list

void list$\_$free$($struct list $*$ this$)$; $1/$ free memory of existing list

Your ADT should be implemented using a subtraction list and not another

data structure. Your code should be written with appropriate comments,

indentation, meaningful names, and good style.