369 views
0 votes
0 votes
LIST-SEARCH’(L, k)
1     x = L.nil.next
2     while x != L.nil and x.key != k
3     x = x.next
4     return x

As written, each loop iteration in the LIST-SEARCH’ procedure requires two tests: one for $x\neq L.nil$ and one for $x.key\neq k$. Show how to eliminate the test for $x\neq L.nil$ in each iteration.

Please log in or register to answer this question.

Related questions

1 votes
1 votes
1 answer
1
akash.dinkar12 asked Jun 30, 2019
605 views
Implement the dictionary operations $INSERT$, $DELETE$, and $SEARCH$ using singly linked, circular lists. What are the running times of your procedures?
1 votes
1 votes
2 answers
2
akash.dinkar12 asked Jun 30, 2019
386 views
Implement a queue by a singly linked list $L$. The operations of $ENQUEUE$ and $DEQUEUE$ should still take $O(1)$ time.
1 votes
1 votes
1 answer
3
akash.dinkar12 asked Jun 30, 2019
392 views
Implement a stack using a singly linked list $L$. The operations $PUSH$ and $POP$ should still take $O(1)$ time.
0 votes
0 votes
1 answer
4
akash.dinkar12 asked Jun 30, 2019
497 views
Can you implement the dynamic-set operation $INSERT$ on a singly linked list in $O(1)$ time? How about $DELETE$?