Implement Doubly linked list using single pointer...
1 Answer
Implement Doubly linked list using single pointer...
| Flag | PURGE
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 D x:next XOR x:pre,
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.
Email me when people comment.
Email me when people comment.
Loading...
An error occurred in subscribing you.
Email me when people comment.
Email me when people comment.
Loading...
An error occurred in subscribing you.
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Search for "XOR linked list" on Google or Wikipedia. This is a well-known data structure that you can find high-quality explanations for.
- eugene.yarovoi December 12, 2012