CSCI 261 - Programming Concepts - Spring 2022

This lab is due by Wednesday, April 13, 2022 11:59 PM.
As with all labs you may, and are encouraged, to pair program a solution to this lab. If you choose to pair program a solution, be sure that you individually understand how to generate the correct solution.

Instructions

You are encouraged to use your templated singly-linked list as the starting point for this lab.

The Doubly-Linked List Class

We are going to now make a new class called DoublyLinkedList. This will necessitate creating a new struct for a DoublyNode to store the previous and next pointers.

The DoublyLinkedList class needs to have the following public methods created:

• DoublyLinkedList() - Constructor that sets the head & tail pointers to be null and set the size to be zero
• DoublyLinkedList(const DoublyLinkedList& OTHER) - Copy Constructor that performs a deep copy of the other list
• ~DoublyLinkedList() - Destructor that deallocates the entire list, sets the head & tail pointers to be null, sets the size to be zero
• DoublyLinkedList& operator=(const DoublyLinkedList& OTHER) - Copy Assignment Operator that deallocates the existent list (if any) then performs a deep copy of the other list
• T get(const int POS) const - if POS exists, returns the value at that position. Otherwise, returns the templated constructor
• void set(const int POS, const T VAL) - if POS exists, sets the value at that position. Otherwise, does nothing
• void insert(const int POS, const T VAL) - inserts a node before the given POS. If POS is negative, inserts at the beginning of the list. If POS is greater than the current size, inserts at the end of the list. Updates head, tail, and size as appropriate
• void remove(const int POS) - removes a node at POS. If POS is negative, removes the head node. If POS is greater than the current size, removes the tail node. Updates head, tail, and size as appropriate
• int size() const - returns the current size of the list
• void print() const - prints to the standard out the contents of the list using a forward traversal
• void printReverse() const - prints to the standard out the contents of the list using a backwards traversal

To test your implementation, perform in main.cpp the following steps in order:

1. Create a doubly linked list of integers
2. Add the value 6 at pos 0
3. Add the value 5 at pos 0
4. Add the value 7 at pos 5
5. Add the value 1 at pos -3
6. Add the value 2 at pos 1
7. Add the value 9 at pos 2
8. Add the value 3 at pos 2
9. Print the list forwards (prints 1 2 3 9 5 6 7)
10. Print the list backwards (prints 7 6 5 9 3 2 1)
11. Set pos 3 to be 4
12. Print the list forwards (prints 1 2 3 4 5 6 7)
13. Remove pos -2
14. Remove pos 9
15. Remove pos 2
16. Get and print pos 2 (prints 5)
17. Print the size (prints 4)
18. Print the list forwards (prints 2 3 5 6)
19. Delete the doubly linked list

Lab Submission

Submit your DoublyNode.hpp, DoublyLinkedList.hpp, main.cpp file(s).

You will submit your solution to this lab with the rest of Set5. Detailed instructions for doing this are posted in Assignment 5.

This lab is due by Wednesday, April 13, 2022 11:59 PM.
As with all labs you may, and are encouraged, to pair program a solution to this lab. If you choose to pair program a solution, be sure that you individually understand how to generate the correct solution.