637 views
0 votes
0 votes
Explain how to implement doubly linked lists using only one pointer value $x.np$ per item instead of the usual two (next and prev). Assume that all pointer values can be interpreted as $k$-bit integers, and define $x.np$ to be $x.np=x.next$ $XOR$ $x.prev$, the $k$-bit “exclusive-or” of $x.next$ and $x.prev$.(The value $NIL$ is represented by $0$.)Be sure to describe what information you need to access the head of the list. Show how to implement the $SEARCH$, $INSERT$, and $DELETE$ operations on such a list. Also, show how to reverse such a list in $O(1)$ time.

Please log in or register to answer this question.

Related questions

0 votes
0 votes
1 answer
1
akash.dinkar12 asked Jun 30, 2019
887 views
Give a $\Theta(n)$ time nonrecursive procedure that reverses a singly linked list of $n$ elements. The procedure should use no more than constant storage beyond that need...
1 votes
1 votes
1 answer
3
akash.dinkar12 asked Jun 30, 2019
607 views
Implement the dictionary operations $INSERT$, $DELETE$, and $SEARCH$ using singly linked, circular lists. What are the running times of your procedures?