Project 04 Solution

The sequence Class Using a Linked List

Discussion of the Assignment

Your sequence class for this assignment will differ from the your previous sequence in the following ways:

The sequence's items are now stored on a linked list. The head pointer of the linked list is a private member variable of the sequence class. I suggest that you also have a tail pointer as an additional private member variable of the sequence class. The reason for the tail pointer is explained in Section 5.4 of the textbook.

Because you are dynamically allocation memory within your sequence class, you will need to define a copy constructor, an assignment operator, and a destructor. You need to pay special attention to the value semantics of your new sequence class - you need not only to make a copy of the linked list, but also need to place the node pointers correctly. Please refer to page 260 for more detailed discussions on the value semantics.

Start by declaring the new sequence's private member variables in sequence3.h. You might try declaring these variables yourself, and then compare your solution with the suggestion in Section 5.4.

Once again, do your work in small pieces. For example, my first version of the sequence had only a constructor, start, insert, advance, and current. My other member functions started out as stubs.




Design a sequence class using a linked list could be little bit more complicated than using an array. Therefore, I recommend you to draw an example linked list such as the one shown in page 260 of the textbook when you are writing code for each member function. Always remember to show all the member variables in order to remind you making proper changes of them. You need to place the cursor and the precursor at various locations, head, tail and other places. Note that the sequence could be empty, and cursor and/or precursor could be NULL, even when the sequence is NOT empty. With the help of small drawings, jobs will be much easier!




Use the interactive test program and the debugger to track down errors in your implementation. If you have an error, do not start making changes until you have identified the cause of the error. If you come to me for help, we will always ask you to do the following:




Show us the invariant that describes how your private member variables implement the sequence class.

Use the debugger to show us the problem!

For those working in the Unix operating system: Spend some time writing your make file. A correct Unix makefile will save you time. Make sure that each compilation command in the make file has a TAB as the first character. In order to insert a TAB using emacs, type Ctrl-Q and then press the TAB key. Or, if you are working from a modem where the TAB key is disabled, you can type

ESCAPE x quoted-insert RETURN TAB

Run Time Analysis of the sequence classes and grading rules




We will use the number of items in a bag as the input size n of the project. Please give the Big-O of each function in your implementation, and compare them with the corresponding functions of the sequence using a dynamic array. You should write the time analysis in the comment lines of each function. The breakdowns of points (of 100) will be the followings:




Basis points (70) if your implementation passes the seq_ex3 exam

Invariant of the class (5 points)

Run time analysis (15 points)

Other implementation details such as compiling warning, code styles and efficiency, etc. (10 points)