CSE 2050 Linked List

Description

In this assignment, you will:

• use dynamic memory allocation, pointers, and references.
• implement data structures
• implement classes in multiple files
• use overloading and overriding
• use inheritance
• understand the meaning of virtual keyword
• use template classes

Implementation Instructions

We provide a template for source files that you must use. You will find the files in the directory src/ which contains:

• .cpp files for the implementation of the data structures
• .h files for the declarations of the data structures
• a main.cpp file to test the code

You will write your code inside the provided source files.

Questions

1. Linked List

In this question you will implement a hierarchy of classes (Figure 1) with interfaces similar to the respective data structures in Java:

• Collection: http://docs.oracle.com/javase/7/docs/api/java/util/Collection. html
• LinkedList: http://docs.oracle.com/javase/7/docs/api/java/util/LinkedList. html

The type the data structures will hold is the template type T, which can be anything (while in the previous assignments it was a simple int).

Each class has his own header file and source file, with the exclusion of Collection which is an abstract class:

• collection.h
• linked_list.h, linked_list.cpp

In the header files you will also find the documentation in javadoc format (that you should know if you took java 1 and/or java 2 and/or algorithm & data structure classes) for each of those elements.

You will implement the class methods in the file .cpp and .h files.

main.cpp implements the Main() function and plays with your code a bit. It is meant as aid for debugging and grading purpose.

NOTE: IMPLEMENT ONLY THE OSTREAM OPERATOR (operator<<) IN THE HEADER FILE. ANY OTHER MODIFICATION OF THE HEADER FILE IS NOT ALLOWED.

HINT: while implementing your code you might wonder why you cannot access head/tail or Node as you did in your previous assignments. Here are a couple of links you should read (click the item to open the link...):

• why-do-i-have-to-access-template-base-class-members-through-the-this-pointer
• where-and-why-do-i-have-to-put-the-template-and-typename-keywords

Figure 1: The hierarchy of classes. Collection is an abstract base class. LinkedList implements Collection. see image.