CSC 161 Program #4

Doubly Linked List
Assigned: Sat Jul 26, 2003 Due: Fri Aug 8, 2003
Grade: 75 points  

Concepts

The "new" concepts covered in this program are:

  • Linked lists

  • Exceptions

Description

In this program, you are charged to create a doubly linked list data type.

Implement a doubly linked list for integers. You are provided with:

  • IntList.h - header file for the list
  • prog04.cpp - a test driver for your list

Nodes in the IntList will have pointers to both the next and previous nodes in the list. Also, your doubly linked list will maintain both a head pointer to the first node in the list and a tail pointer to the last node in the list.

You need to implement all the member functions in the list header (in IntList.cpp) and test them using the main() program that I have provided. When all your member functions are working correctly, the test driver will run silently. If there's a problem, then you should see an error message pointing to the test that failed.

Implementation

This program is a little different with me providing a test driver for you to run. I do have the following hints:

  • The FloatList example in Chapter 16 should be a nice starting point. The code for FloatList appears on pages 1069-1073 of our textbook.
  • There is a snippet about doubly linked lists on Section 16.4, page 1078 of our textbook, and I will be lecturing on this as well.
  • Comment out test code that you haven't implemented yet. Go one step at a time.
  • I strongly suggest you work out diagrams of the insert & remove operations before attempting to code them. If you're not careful, you'll be spending a lot of "quality time" in the debugger on this one.
  • Notice the class exceptions thrown by the insertBefore(), insertAfter() and remove() functions. 
  • Notice that your toString() function must use the format expected in my test function check() function in main().

Grading

Your program will be graded on three areas: design, quality, and function. Their description and weighting in your grade is given below.

1. Program Design (0%)

I've given you the design for this program.

2. Program quality (33%, 25 points)

Please reference the 10-step quality checklist.

3. Program function (67%, 50 points)

If your program doesn't compile or link, your grade for this section will automatically be cut in half and then I'll start from there. Please leave a README file in your prog01 folder with notes you want me to read.

Good luck.

Notes

July 26, 2003

I apologize that this was posted a day late. If you're scoping this out at home, here are links to the two files that are also found in the Common Area: