Solved–Assignment 3– Option A: Extending the Linked List Toolkit– Solution

Description

The Assignment:

You will add some new functions to the linked list toolkit from Section 5.2 of the textbook.

Purposes:

Ensure that you can write ordinary functions to manipulate linked lists. Note that these are not member functions, because you are not implementing a class in this assignment.

Before Starting:

Read Sections 5.1 – 5.2.

Files that you must write:

1. newnode.h: The header file for the new toolkit. Actually, you don’t have to write much of this file. Just copy our version from newnode.h (http://www.cs.colorado.edu/~main/projects/newnode.h) and add your name and other information at the top.

2. newnode.cxx: The implementation file for the new toolkit class. You may start with our implementation from node1.cxx(http://www.cs.colorado.edu/~main/chapter5/node1.cxx) and add the implementations of the four new functions. For each function, provide a short time complexity analysis using the Big-O notation.

Other files:

1. A simple interactive test program at http://www.cs.colorado.edu/~main/projects/newnodetest.cxx

2. A batch test file will be used for grading purposes. If you have tested your implementation using the interactive test program extensively, you can expect to get a full score.

Due Date:

11:59 pm, Thursday, Nov. 10

How to Turn In:

Pack your files (source code only!)  in a single WinZip file (Windows) or tar file (Unix/Linux) and submit it through Blackboard. Please do not submit your executable files.

​Grading:

Correct implementations of the four functions –80%

Time complexity analysis using the Big-O notation -20% (do not forget!)

​

​Discussion of the Assignment

As indicated above, you will add four new functions to the linked list toolkit. These new functions are all specified in the header file newnode.h (http://www.cs.colorado.edu/~main/projects/newnode.h), including list_occurrences, list_tail_attach, list_tail_remove and list_copy_front. You do not need to implement the list_piece function if you do use it in implementing any of the four functions. For your information, an implementation has been given in Lecture 10 slide #42.

​Hints

Check Preconditions

Your implementations should use the assert function to check preconditions of all functions.

Input and Output

Your implementations must NOT produce any output to cout, nor expect any input from cin. All the interaction with the member functions occurs through their parameters.