The Gateway to Computer Science Excellence
0 votes
92 views
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.
in Algorithms by Boss (41.9k points) | 92 views
0
Try to read XOR implemented linked list and try working out the solution on your own.

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,465 answers
195,380 comments
100,304 users