摘要:
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
閱讀全文
摘要:
Give a Θ(n)-time nonrecursive procedure that reverses a singly linked list of n
elements. The procedure should use no more than constant storage beyond that
needed for the list itself.
閱讀全文
摘要:
As written, each loop iteration in the LIST-SEARCH' procedure requires two tests:
one for x ≠ L.nil and one for x.key ≠ k. Show how to eliminate the test for
x ≠ L.nil in each iteration.
閱讀全文