Skip to content

Latest commit

 

History

History
85 lines (61 loc) · 3.23 KB

10.2.md

File metadata and controls

85 lines (61 loc) · 3.23 KB
Raw

Exercises 10.2-1

Can the dynamic-set operation INSERT be implemented on a singly linked list in O(1) time? How about DELETE?

Answer

INSERT - yes, words can be inserted directly at the beginning of the list, DELETE - no, because it requires traversing the whole list.

Exercises 10.2-2

Implement a stack using a singly linked list L. The operations PUSH and POP should still take O(1) time.

Answer

PUSH - make element list's head，POP - remove list's head，both operations take O(1).

Exercises 10.2-3

Implement a queue by a singly linked list L. The operations ENQUEUE and DEQUEUE should still take O(1) time.

Answer

Keep two pointers: one will point to the beginning of the list, other to the end.

  • ENQUEUE - insert into end of the list,
  • DEQUEUE - remove list's head

Exercises 10.2-4

As written, each loop iteration in the LIST-SEARCH′ procedure requires two tests: one for x ≠ nil[L] and one for key[x] ≠ k. Show how to eliminate the test for x ≠ nil[L] in each iteration.

Answer

LIST-SEARCH′(L, k):
	key[nil[L]] = k
	x ← next[nil[L]]
	while(key[x] != k):
		x ← next[x]
	if x == nil[L]:
		return NULL
	return x

Exercises 10.2-5

Implement the dictionary operations INSERT, DELETE, and SEARCH using singly linked, circular lists. What are the running times of your procedures?

Answer

implementation

Exercises 10.2-6

The dynamic-set operation UNION takes two disjoint sets S1 and S2 as input, and it returns a set S = S1 U S2 consisting of all the elements of S1 and S2. The sets S1 and S2 are usually destroyed by the operation. Show how to support UNION in O(1) time using a suitable list data structure.

Answer

This can be implemented using circular linked list. As in circular linked list the head pointer points to the last node to make insertion at beginning and end in O(1) time.

//Suppose L1 and L2 are two circular linked list whose head is at the last node.
Node *temp = L1.head->next
L1.head->next = L2.head->next
L2.head->next = temp;
return L2.head;

Exercises 10.2-7

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.

Answer

solution

Exercises 10.2-8

Explain how to implement doubly linked lists using only one pointer value np[x] per item instead of the usual two (next and prev). Assume that all pointer values can be interpreted as k-bit integers, and define np[x] to be np[x] = next[x] XOR prev[x], the k-bit "exclusive-or" of next[x] and prev[x]. (The value NIL is represented by 0.) Be sure to describe what information is needed 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.

Answer

为了访问下一个元素，只需要XOR(np,prev).为了访问前一个元素，只需要XOR(np,next).

Follow @louis1992 on github to help finish this task.