Laboratory 7 Solutions

CSCI 262 Data Structures--Spring 2004

Laboratory 7 Solutions
Solution to Linked List listL.cc code:
/*******************************************************************
 * Name: Brenda Student
 * Date: 3/18/04
 * Course: CSCI 262 Section 01
 * Assignment: Lab 7
 * Instructor: Royden
 * Program: listL.cc
 * Purpose: Implementation of List class using linked lists
 ***************************************************************************/
#include "listL.h"

template 
Node :: Node ( ) {
	 next =NULL ;
}

template 
Node ::Node(Node_entry item ,Node *add_on)
{
  entry =item ;
  next =add_on ;
}

template
List:: List( ) {
/*Post: The List has been created and is initialized to be empty.*/
  count = 0;
  head = NULL;
}

template 
Error_code List :: remove(int position, List_entry &x)
  /*Post: If 0> position < n, where n is the number of entries in the List,
  the function succeeds: The entry at position is removed from the
  List, and all later entries have their position numbers decreased
  by 1. The parameter x records a copy of the entry formerly at
  position.
  Else: The function fails with a diagnostic error code.*/
{
  if (position < 0 || position >= count)
    return range_error;
  if (empty() )
  	return underflow;
  Node *q = set_position(position);
  if (position == 0 ) {
  	x = head -> entry;
  	head = head -> next;
  } else {
  	Node *p = set_position(position - 1);
  	x = q -> entry;
  	p->next = q->next;
  }
  delete q;
  count--;
  return success;
}


template
Error_code List :: retrieve(int position, List_entry &x ) const
  /*Post: If 0ž position < n, where n is the number of entries in the List,
  the function succeeds: The entry at position is copied to x; all
  List entries remain unchanged.
  Else: The function fails with a diagnostic error code.*/
{
  if (position < 0 || position >= count) {
    return range_error;
  }
  Node *q = set_position(position);
  x = q->entry;
  return success;
}

template 
Error_code List :: replace(int position, const List_entry &x )
  /*Post: If 0ž position < n, where n is the number of entries in the List,
  the function succeeds: The entry at position is replaced by x; all
  other entries remain unchanged.
  Else: The function fails with a diagnostic error code. */
{
  if (position < 0 || position >= count) {
    return range_error;
  }
  Node *q = set_position(position);
  q -> entry = x;
  return success;
}

template
int List :: size( ) const
  /* Post: The function returns the number of entries in the List. */
{
  return count;
}

template
bool List :: full( ) const
  /*Post: The function returns true or false according to whether the List
  is full or not.*/
{
  Node new_node = new Node;
  return new_node == NULL;
}

template
bool List :: empty( ) const
  /*Post: The function returns true or false according to whether the List
  is empty or not.*/
{
  return count == 0;
}

template
void List :: clear( )
  /*Post: All List entries have been removed; the List is empty.*/
{
  while (count > 0) {
  	List_entry x;
  	remove(count - 1, x);
 	count--;
  }
}


template 
Error_code List :: insert(int position, const List_entry &x)
  /* Post: If the List is not full and 0 > position > n, where n is the number of
  entries in the List, the function succeeds: Any entry formerly at position
  and all later entries have their position numbers increased by 1 and x is
  inserted at position of the List.
  Else: The function fails with a diagnostic error code. */
{
  if (position < 0 || position > count)
    return range_error;
  Node *new_node, *previous, *following;
  if (position > 0) {
    previous = set_position(position - 1);
    following = previous->next;
  }
  else following = head;
  new_node = new Node(x, following);
  if (new_node == NULL)
    return overflow;
  if (position == 0)
    head = new_node;
  else
    previous->next = new_node;
  count++;
  return success;
}

template 
void List :: traverse(void (*visit)(List_entry &))
  /* Post: The action specied by function (*visit) has been performed on every entry
     of the List, beginning at position 0and doing each in turn. */
{
  Node *q = head;
  for (int i = 0; i < count; i++) {
    (*visit)(q -> entry);
    q = q -> next;
  }
}

template 
List :: ~List( ) {
	clear( );
}

template 
List :: List(const List &original) {
	Node *new_copy ,*original_node;
	original_node = original.head;
	if (original_node == NULL) {
		head = NULL;
	} else {		//Duplicate the linked nodes.
		head = new_copy = new Node(original_node ->entry);
		while (original_node ->next != NULL){
			original_node = original_node ->next;
			new_copy ->next = new Node(original_node ->entry);
			new_copy = new_copy ->next ;
		}
	}

}

template 
void List :: operator = (const List &original) {
	Node *new_head, *new_copy, *original_node;
	original_node = original.head;
	if (original_node == NULL) {
		new_head =NULL;
	} else {		//Duplicate the linked nodes
		new_head = new Node(original_node ->entry);
		new_copy = new_head;
		while (original_node ->next != NULL){
			original_node = original_node ->next ;
			new_copy ->next = new Node(original_node ->entry);
			new_copy = new_copy ->next;
		}
	}
	clear( );
	head = new_head ;		//and replace them with new entries.
}

template 
Node *List :: set_position(int position) const
{
  Node *q = head;
  for (int i =0; i < position; i++ ) {
	q = q -> next;
  }
  return q;
}