TITLE

IMPLEMENTING AND EXERCISING A LINKED LIST recursively

INTRODUCTION

An ordered list is a sequence of elements, all of the same type, that is ordered by the elements' values. One way to represent an ordered list is in a linked list.

DESCRIPTION

Design and write a class that implements an ordered list type using a linked list, and a program that exercises and tests the class's list implementation. The items in the List will be integers, but it should be easy to change this type.

The class should implement the following operations on ordered lists of its element type:

• Initialize a List to be empty (the default constructor).
• Dispose of the dynamic part of a List structure (the destructor).
• Re-initialize an existing List to be empty.
• Insert a value into a List, in the appropriate position. If the value is already present, the List is unchanged.
• Remove a value from a List. If the value is not present, the List is unchanged.
• Is a List empty?
• Return the length of a List.
• Report whether or not a particular value is present in a List.
• Return the value of the k^th element of a List.
• Write out the values in a List, in order, to an output stream.

The exercising program should be menu-driven and interactive. The program will read and respond to commands that the user enters to manipulate an ordered list.

INPUT

The program reads commands to manipulate its List. These commands consist of a letter sometimes followed by an integer. For example, the command "i 25" tells the program to insert the value 25 into the List.

OUTPUT

The program writes instructions and a menu of commands to the terminal, it prompts for the user's input, and it outputs lists and elements of lists.

ERRORS

The program may assume that the input the user provides is correct; except that it will report if a position is beyond the end of a list (See the example below). Otherwise, it need not detect any errors.

EXAMPLE

A run of the program might look something like this:

 This program responds to commands the user enters to manipulate an ordered list of integers, which is initially empty. In the following commands, k is a position in the list, and v is an integer. e -- Re-initialize the list to be empty. i v -- Insert the value v into the list. r v -- Remove the value v from the list. m -- Is the list empty? l -- Report the length of the list. p v -- Is the value v present in the list? k k1 -- Report the k1th value in the list. w -- Write out the list. h -- See this menu. q -- Quit. 

This example does not illustrate everything the program might do; it is your responsibility to test all its features.

OTHER REQUIREMENTS

Use a typedef statement to specify the item type in the class's list, so that this type can be changed easily.

Represent the list in a linked list with header and trailer nodes,

Maintain the List's elements in order; this is part of the invariant of the implementation.

Consider carefully whether functions associated with the class should be member functions, friend functions, or nonmember functions.

HINTS

Commands will consist of a letter followed perhaps by an integer. These can be easily read with the extractor operator ">>".