The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
Explain how to implement doubly linked lists using only one pointer value $$ per item instead of the usual two (next and prev). Assume that all pointer values can be interpreted as $k$-bit integers, and define $$ to be $$ $XOR$ $x.prev$, the $k$-bit “exclusive-or” of $$ 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.3k points) | 50 views
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
49,845 questions
54,784 answers
80,448 users