CSC161 Homework 3: Linked Lists

Contents

Overview

We started to work on the SinglyLinkedList class in class. For this homework, you are going to finish implementing SinglyLinkedList and make it templated. Then, you're going to demonstrate that it works. Like the Vector class, there is a slightly different implementation of SinglyLinkedList on the ADT page. You might have to do more than just simply copy and past, so make sure you understand the code. As always, ask me questions if you cannot work through something or if you have questions about this assignment. Ask early and ask often—do not wait until the last minute.

Requirements

• make SinglyLinkedList templated
• finish implementing SinglyLinkedList (all the methods we didn't get to in class)
• in main, create one list of ints and another of strings
• in main, demonstrate that each of the methods works
• make sure to follow the style guidelines

Extra credit

Extra credit will max out at 5 points.

EC-1 (3 points)

Create a single function that will print all items from a List—it should work for both Vectors and SinglyLinkedLists. Hint: the polymorphism section of the OOP topic mentioned how to do this.

EC-3 (5 points)

Make another class DoublyLinkedList that uses DoublyLinkedNodes, which have a next and a prev data member. Your add, set, and get functions should use the prev data member of nodes to find a position from the tail of the list if the given position is closer to the end than to the beginning of the list.

EC-3 (5 points)

Add an apply method to the List ADT that takes a function pointer, and implement this function in SinglyLinkedList. The function pointer should point to a function that takes an element of the array and returns nothing. The apply method should invoke this function once on each item in the list.

Submissions

Everything should be uploaded to Canvas by the deadline posted.