UMBC CMSC 202 Computer Science II

Lab6: Linked Lists

Objective

In this lab you will use a linked list to practice using dynamic memory.

Assignment: Linked List Member Functions

Your assignment is to finish implementing three of the member functions of the class List: insert, remove and size.

The linked list provided is a linked list of ints. It keeps the list in sorted order. There is a dummy node, called m_head, that is always present in the list. This node contains no data and is not actually considered an element. It is simply there to provide as a placeholder.

Step 1: Get the files

Here are the files you need:

List.h: the header file for the List class. You will not need to change this file.
List.cpp: the implementation file for the List class. Most of the member functions have been implemented for you. Some parts of the functions have been omitted.
Lab6.cpp: a file with a main function that exercises the List class. You will not need to change this file.

Step 2: Complete the `size` function

The size function should return the number of elements in the list, not including the dummy node.

Follow these steps:

Edit List.cpp. You will edit List::size() near the bottom of the file.
Write a while loop that traverses the linked list with a current pointer, like in other functions. Keep track of how many nodes have been visited with a counter, then return that counter.

Step 3: Complete the insert function

Insert a node that stores the "data" passed in the list while still maintaining the sorted order.

The traversal and if condition are already done for you.

Edit List.cpp. You will edit List::insert(int data).
Implement the pointer logic in the section of code labeled "PUT CODE HERE". For example, if the linked list is: Lets say you wanted to insert 6. current would stop at the node that has 5. It is your task to get a new Node with the value of 6 inserted between 5 and 7.

Step 4: Complete the remove function

Delete a node that stores the "data" passed in the list. Return true if the node was found, false if not.

The traversal and if condition are already done for you.

Edit List.cpp. You will edit List::remove(int data).
Implement the pointer logic in the section of code labeled "PUT CODE HERE". For example, if the linked list is: Lets say you wanted to delete 4. current would stop at the node that has 1. It is your task to delete the Node that has 4 in it and have the 1 Node's next point to the 5 node. Make sure you make the connection between the two surrounding nodes before you delete the middle one!

Step 5: Compile and Debug

To compile, use:
Bugs? Try to figure it out yourself first. If that doesn't work, as the TA for help.

Extra Credit: Reverse Print Function (4 points)

Write a print function that prints out exactly like List::Print(), except that it prints in reverse order. This is harder than just traversing the list since the pointers only go in one direction!

Think about how you could use recursion (can use a "helper" function) or think about how you could use a stack.