22C:21: Computer Science II: Data Structures

Quiz 5: October 22, 2004


Write a function that takes a doubly linked list and creates an equivalent singly linked list. The function header you should use is the following:
			SinglyLinkedList doubleToSingle(DoublyLinkedList L)
For example, if L contains three nodes with data 10, 2, and 4 (read in order from the head of the list to the tail) then the SinglyLinkedList that is returned by the function should also contain three nodes with data 10, 2, and 4 (read in order from the head of the list).

Notes:

			SinglyLinkedList doubleToSingle(DoublyLinkedList L)
			{
				SinglyLinkedList SL;
				SL = new SinglyLinkedList();
				
				while(!L.isEmpty())
					SL.addFirst(L.removeLast());

				return SL;
			}

The above function takes O(n) time because the function calls to isEmpty(), removeLast(), and addFirst all take O(1) time each. Note that removeLast() takes O(1) time on a doubly linked list, but O(n) time on a singly linked list with n nodes. In each execution of the while-loop one node is removed from the doubly linked list and therefore the while-loop executes n times.

Also note that the order of the elements in preserved in transferring the elements from L to SL.