some final solutions

Problem 3a

The idea is to go along the list, counting nodes. Once the node with the required count is reached, return its data. If the end of the list is reached before the count equals n, signal error.

Solution I:

  
template< class T >
T List<T>::nth( int n ){
  int i=1;   // node count
  Node<T> * ptr = first;

  // stop at n-th node, or at the end of the list
  while( ptr != NULL && i < n ){  
    ptr = ptr->next;
    i++;
  }

  // we stopped either because ptr == NULL (end of the list) or
  // because  i == n  (n-th node reached)
  // Figure out which of the two things above had happened
  if( ptr == NULL ){
    cerr << "nth: List not long enough.\n";
    exit(-1);
  }
  else 
    return ptr->data;
}

Solution II. Notice that the counter is treated differently!

  
template< class T >
T List<T>::nth( int n ){
  int i=0;   // node count
  Node<T> * ptr = first;

  while( ptr != NULL ){  
  
    if( i==n ) 
      return ptr->data; 	  

    ptr = ptr->next;
    i++;
  }

  // we stopped because ptr == NULL (end of the list), so we know
  // we didn't reach the n-th node 
  cerr << "nth: List not long enough.\n";
  exit(-1);
}

Problem 3b

The idea is basically the same.

Solution I:

  
template< class T >
int List<T>::find_first( const T & elt ){
  int i=0;   // node count
  Node<T> * ptr = first;

  // stop at the node whose data == elt, or at the end of the list
  while( ptr != NULL && ptr->data != elt ){  
    ptr = ptr->next;
    i++;
  }

  // we stopped either because ptr == NULL (end of the list) or
  // because  ptr->data == elt .
  // Figure out which of the two things had happened
  if( ptr == NULL )
    return -1;
  else 
    return i;
}

Solution II, breaking out of the llop early: is treated differently!

  
template< class T >
T List<T>::nth( int n ){
  int i=0;   // node count
  Node<T> * ptr = first;

  while( ptr != NULL ){  
  
    if( ptr->data == elt ) 
      return i;	  

    ptr = ptr->next;
    i++;
  }

  // we stopped because ptr == NULL (end of the list), so we know
  // that elt was nowhere in the list.
  return -1;
}

Sergey Bratus

Last modified: Tue Jun 8 16:47:51 EDT 1999