In certain programming languages like C $/$C$++,$ links are represented by pointers,

and we are allowed to do "pointer arithmetic", such as bitwise XORing two pointers

together. Under the assumption that this is legal, show how a doubly$-$linked list can

be implemented with only one "link" variable.

$($a$)(15$ points$)$ Implement in pseudocode the Access$(i)$ operation that returns the

node at index $i$ in linear time.

$($b$)(15$ points$)$ Implement in pseudocode the RemOVE$(i)$ operation that removes the

node at index $i$ in linear time.

$($c$)(10$ points$)$ Given a link to a node old, is it possible to implement a constant

time operation Remove$($old$)$ similar to the one discussed in class for the usual

implementation of doubly$-$linked lists that contain two links per node? Why or

why not?

With regards to link arithmetic, assume that the NULL link is represented by an

all zero bitstring. $[$Hint: Remember that for any two bitstrings a and $b,$ we have

$(axORb)xORb=a.]$