Doubly Linked List 2

Your objective for this project is to implement a Doubly-Linked List.

Part 1

Define a class DoubleNode that is capable of holding an item of any arbitrary type ItemType. As a node of a Doubly-Linked list, it should additionally contain two pointers that respectively point to other objects of type DoubleNode.

The following methods will be required of your DoubleNode class, but feel free to add methods as you see fit:

• Default Constructor
• Parameterized Constructor(s)
  • Hint: You can use default parameters as you did in Project 1 to require the use of only a single parameterized constructor.
• ItemType getItem() const
• A method that allows you to set the next node of the DoubleNode.
• A method that allows you to set the previous node of the DoubleNode

Entitle your header (.hpp) file DoubleNode.hpp, and entitle your implementation file (.cpp) DoubleNode.cpp.

Part 2

Define a class DoublyLinkedList that is a demonstration of the Doubly-Linked List concept discussed in class. It should contain a head pointer to a DoubleNode of any arbitrary type ItemType, and it should contain a member that keeps track of its size.

Hint: If you get stuck on the way to design DoublyLinkedList, take a look at the LinkedBag header from Project 2.

The following methods are required of your DoublyLinkedList class:

• Default Constructor
• Copy Constructor
• Destructor
• bool insert(const ItemType& item, const int& position), which is intended to insert item at index position in your list. Note: Let the list be 1 indexed unlike arrays, which are 0 indexed.
• bool remove(const int& position), which is intended to remove the node at index position
• int getSize() const, which is intended to return the number of the nodes in the list
• DoubleNode< ItemType> *getHeadPtr() const, which is intended to return a copy of the hearPtr
• DoubleNode< ItemType> *getAtPos(const int& pos) const, which returns a pointer to the node located at pos
• bool isEmpty() const, which returns whether the list is empty
• void clear(), which clears the list
• void display() const, which prints the contents of the list in order
• void displayBackwards() const, which prints the contents of the list backwards.
• DoublyLinkedList< ItemType> interleave(const DoublyLinkedList< ItemType>& a list), which alters the calling list to be the interleaved list of the original and parameter lists

Example: Define the calling list as a set of ordered nodes, L1 = {4, 2, 8, 5, 8}, and define the list that is passed as a parameter as the set of ordered nodes, L2 = {5, 1, 8, 4, 5, 9}. L1.interleave(L2) should yield the set {4, 5, 2, 1, 8, 8, 5, 4, 8, 5, 9}. In other words, to create the interleaved list, first add a node from L1, then L2, and then repeat. If there are any nodes left over in L1 or L2 exclusively, append them to the end of the list.

Entitle you header (.hpp) file DoublyLinkedList.hpp, and entitle your implementation file (.cpp) DoublyLinkedList.cpp.

Testing

You must always implement and test you programs INCREMENTALLY!!!

What does this mean?

• Implement and test one method at a time.
• For each class:
  • Implement one function/method and test it thoroughly (multiple test cases + edge cases if applicable)
  • Implement the next function/method and test in the same fashion.

How do you do this?

Write your own main() function to test your classes. In this course you will never submit your test program, but you must always write one to test your classes. Choose the order in which you implement your methods so that you can test incrementally (i.e. implement mutator functions before accessor functions). Sometimes functions depend on one another. If you need to use a function you have not yet implemented, you can use stubs: a dummy implementation that always returns a single value for testing (don't forget to go back and implement the stub!!! If you put the word STUB in a comment, some editors will make it more visible.