UMBC CMSC 202 Computer Science II

Lab6: Linked Lists


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:

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:

  1. Edit List.cpp. You will edit List::size() near the bottom of the file.

  2. 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.

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.

Step 5: Compile and Debug

  1. To compile, use: g++ -Wall -ansi List.cpp Lab6.cpp

  2. 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.