CS 2413 001 Summer 2000
Homework #3 Solutions

1. Put check marks to indicate the statements that are true for each data structure.
   
   

   Property/Data Structure	Array	Vector	Linked List
   Contiguous in memory	X	X
   Can access an element in O(1) time	X	X
   Length can change		X	X
   Causes fragmentation of the free store		X
   Can add a new element to the front of the list in O(1) time			X

   
   
   Note: O(1) time is also called constant time, meaning that the amount of time the operation takes does not grow with input size.

   Discussion:

   • Contiguous in memory
     • An array is contiguous in memory, meaning that it is allocated in one big chunk, where each succeeding element of the array is located immediately after the previous element. For example, if myArray is an int array of length 10, and if an int requires 4 bytes, then the address of myArray[1] will be 4 higher than the address of myArray[0].
     • A vector is also contiguous in memory, because it is implemented as an array whose address can change.
     • A linked list is not contiguous in memory, because its elements are allocated independently, not in a single chunk.
   • Can access an element in O(1) time
     • Both arrays and vectors can access a given element in O(1) time. All elements of a given array or vector have the same size, so to access the kth element, one need only know the address of element 0 and the size of each element; in the above example, the address of myArray[k] is the address of myArray[0] plus 4k.
     • Accessing a given element of a linked list takes O(n) time; see the answers to question 3 and 4, below.
   • Length can change
     • An array's length is set when it is instantiated and cannot change, by definition.
     • A vector's length can grow or shrink as elements are inserted or removed, by definition.
     • A linked list's length will grow or shrink as elements are inserted or removed.
   • Causes fragmentation of the free store
     • An array is allocated exactly once and is deleted exactly once, so using it does not cause fragmentation of the free store.
     • A vector can be allocated and deallocated many times, and its size can be quite large and will vary from allocation to allocation, so it often causes fragmentation of the free store.
     • Although a linked list's elements can be allocated and deallocated many times, and the entire list's size can be quite large, each element's size is (typically) small. So, a linked list rarely causes fragmentation of the free store, because when an element of the linked list is freed, that same space can be used to store a new element of the linked list later on.
       Note: this property breaks down in the case of a linked list of arrays (or vectors) of widely varying sizes.
   • Can add a new element to the front of the list in O(1) time
     • An array cannot have a new element added anywhere.
     • A vector can have a new element added anywhere, but if the element is added to the front of the vector, then the rest of the vector's elements must be shifted down one position, which takes O(n) time.
     • A linked list can add a new element to the front of the list in O(1) time, because a linked list is recursively defined as the front of a chain of elements, so adding an element to the front of the list requires nothing more than creating the new element and setting a few pointers.

   Ask for help with this question.

   ---

2. Write the following methods for LinkedList:
   1. insertBefore (Object& target, Object& newObject):
      inserts a node containing newObject into the list immediately before the node containing target, or throws a LinkedListNotFound exception.
      
      Answer:

      template <class Object>
      void LinkedList<Object>::insertBefore (
              Object& target, Object& newObject)
      { // LinkedList<Object>::insertBefore
          if (isEmpty())
              throw LinkedListNotFoundException();
          if (*_info == target) add(newObject);
          else {
              if (_next == NULL)
                  throw LinkedListNotFoundException();
              _next->insertBefore(target, newObject);
          } // if (*_info == target)...else
      } // LinkedList<Object>::insertBefore
      

   2. insertAfter (Object& target, Object& newObject):
      inserts a node containing newObject into the list immediately after the node containing target, or throws a LinkedListNotFound exception.
      
      Answer:

      template <class Object>
      void LinkedList<Object>::insertAfter (
              Object& target, Object& newObject)
      { // LinkedList<Object>::insertAfter
          if (isEmpty())
              throw LinkedListNotFoundException();
          if (*_info == target) {
              if (_next == NULL)
                   _next = new LinkedList(newObject);
              else _next->add(newObject);
          } // if (*_info == target)
          else {
              if (_next == NULL)
                  throw LinkedListNotFoundException();
              _next->insertAfter(target, newObject);
          } // if (*_info == target)...else
      } // LinkedList<Object>::insertAfter
      

   3. remove (Object& target):
      removes all nodes containing target from the list.
      
      Answer:

      template <class Object>
      void LinkedList<Object>::remove (Object& target)
      { // LinkedList<Object>::remove
          if (isEmpty()) return;
          if (*_info == target) {
              Object temp = remove();
          } // if (*_info == target)
          if (_next != NULL)
              _next->remove(target);
      } // LinkedList<Object>::remove
      

   4. Two linked lists are equivalent if they contain the same set of elements, regardless of order. Overload the == operator to determine whether two linked lists are equivalent. You should not assume that either list has a particular order, nor that the two lists have the same order.
      
      Answer:

      template <class Object>
      bool LinkedList<Object>::operator== (LinkedList<Object>& ll)
      { // LinkedList<Object>::operator==
          if (isEmpty() && ll.isEmpty()) return true;
          if (isEmpty() || ll.isEmpty()) return false;
          try {
              Object temp = ll.find(*_info);
          } // try
          catch (LinkedListNotFoundException e) {
              return false;
          } // catch (LinkedListNotFoundException e)
          if ((_next == NULL) && (ll._next == NULL)) return true;
          if ((_next == NULL) || (ll._next == NULL)) return false;
          return _next->operator==(ll);
      } // LinkedList<Object>::operator==
      

   Ask for help with this question.

   ---

3. For each of the methods in the previous question, what is the time complexity? Explain your answer. You do not need a formal proof, nor to choose values for c and n₀.
   
   Answers:
   (Note that n is the length of the linked list.)
   1. insertBefore (Object& target, Object& newObject): O(n)
      The method recursively traverses the list, which takes O(n) time, examining each node until target is found. It then uses the add method, which takes O(1) time, to insert the element immediately before the target element that it has found.
      
      
   2. insertAfter (Object& target, Object& newObject): O(n)
      The method recursively traverses the list, which takes O(n) time, examining each node until target is found. It then either uses the add method, which takes O(1) time, to insert the element immediately before the next element, or, if there is no next element, simply allocates a new element and places it after the target element that it has found, which also takes O(1) time.
      
      
   3. remove (Object& target): O(n)
      The method recursively traverses the list, which takes O(n) time, examining each node. Every time target is found, it removes that element, which takes O(1) time, because the element it intends to remove is always at the front of the list.
      
      
   4. operator== (LinkedList& target): O(n²)
      The method recursively traverses the linked list that owns the method (i.e., *this, which appears on the left side of the == operator in the call to operator==), which takes O(n) time. For each element in this traversal, the method invokes the find method of the other linked list, ll (which appears on the left side of the == operator in the call to operator==), which takes O(n) time. Thus, there are O(n) calls to a method that takes O(n) time, so the total time is O(n²).
   
   Discussion:
   
   Why does recursively traversing a list to find a particular element take O(n) time?
   
   • Best case: the target value is found at the front of the list. In this case, the traversal terminates in O(1) time, because the target is found by examining only a single element.
   • Worst case: the target value is found at the rear of the list. In this case, the traversal takes O(n) time, because it has to examine all n elements of the list to find its target.
   • Average case: the target value is found somewhere near the middle of the list, because the average case is obtained by examining all possible searches on the list, half of which have the target element before the midway point in the list, and the other half of which have the target element after the midway point in the list. In this case, the traversal takes O(n) time, because on average it has to visit half of the n elements of the list to find its target, and 1/2n is O(n) (i.e., it is n times a constant).

   Remark: In general, we ignore the best case, because it occurs so infrequently.

   Ask for help with this question.

   ---

4. A linked list is ordered if it stores objects in a sorted order based on some data field (or fields) of the objects, called the key field(s). (Therefore, the type of the key field would need to have inequality operators defined.) What would be the time complexity of a binary search function on an ordered linked list? (Hint: what is the time complexity of the LinkedList method infoAt? What is the time complexity of binary search?) Note: you do not have to implement the linked list binary search function.

   Answer: O(nlogn)

   The time complexity of the LinkedList method infoAt is O(n), by the same reasoning as for insertBefore, above.

   The time complexity of binary search is O(logn), as explained in OODS, Chapter 3.

   The binary search algorithm requires examining the kth element of the list for each iteration of the binary search; specifically, k is the midpoint of the portion of the list currently being examined.

   So, each of the O(logn) iterations of the binary search algorithm requires a call to infoAt, each of which takes O(n) time.

   Because binary search on a linked list requires O(logn) calls to a method that takes O(n) time for each call, the algorithm takes O(nlogn) time.

   Remark:
   Not surprisingly, binary search is not a popular approach to searching a sorted linked list, because a simple linear traversal takes only O(n) time, which is substantially more efficient than O(nlogn).

   Ask for help with this question.

   ---

5. Rewrite the merge function (OODS, chapter 3) to operate on two linked lists instead of two arrays. You may assume that both linked lists are sorted in ascending order.

   Note: because this question may appear on an exam, a solution is not provided here.

References

S. Rhadakrishnan, L. Wise & C. N. Sekharan, Object-Oriented Data Structures Featuring C++, 1999.
A. Drozdek, Data Structures and Algorithms in C++, PWD Publishing Co., New York, 1996.

Ask for help with this question.