A doubly linked list is a list where each node is linked to both neighbors. In the node structure there are most likely two pointers, a left pointer which points to the node to the left, and a right pointer which points to the node to the right.

node.png

The double links make it easy to traverse the list in either direction.

list.png

In a circularly linked list the first node is connected to the last node, forming a circle. There is still a head node pointing to the first node in the list, but you can move from the last node in the list to the first node in the list via a link. In a doubly linked circular list, the last node and the head node are fully linked to each other.

dlcirc.png

For a Doubly Linked Circular List with one node, that node will have two pointers pointing the node.

snDLCL.png

No templates should be used for now. For this exercise, use std::string as the data type to store in each node.

Until we learn how to deal with exceptions, your class will print an error and return a standard value when the user attempts to perform an illegal operation.

The Doubly Linked Circular List should be implemented in a separate source and header files to allow use in multiple programs. Please use DListT.h for your header file.

DListT.png

This class should support iterators, but since we don't yet have the ability to implement these, we will maintain an internal "current" pointer. This pointer will allow the user to manipulate and access the data stored in the structure. The user does not have direct access to the current pointer, but must manipulate it through calls to member functions such as Left, Right and Home.

The current pointer (current) should be invalid until data is inserted into the structured. When data is inserted, current should always point to the inserted data. When data is deleted, current should point to a valid node, if possible.

The Doubly Linked Circular List should support the following methods:

Size return the number of nodes in the list. Data return the data in the node pointed to by current. If current is valid Return the data in the node pointed to by current. Otherwise Print out the message "Error: Attempt to access Empty List." Return the string "NO DATA" Home move current to the head of the list

Right move current to the right by one node

Left move current to the left by one node

Delete remove the node pointed at by current If the list is empty Print out the message "Error: Attempt to delete in an Empty List." If the node is the only node in the list The list becomes empty The current is not longer valid. If current is pointing at the head of the list The node to the right of current becomes the new head of the list. Delete the old head node. Current points to the new head node. Otherwise The current node is deleted Current points to the node left of the previous current.

Insert insert a new node into the list at the current position. If the list is empty The new node is inserted at the head of the list Current points to the new node. Current points to the head of the listOtherwise The new node is inserted at the head of the list. Current points to the new node. The new node is inserted before current. Current points to the new node.

InsertAfter insert a new node into the list following the current position. If the list is empty The new node is inserted at the head of the list. Current points to the new node. Otherwise Insert the new node at the node following current. Current points to the new node.

It should also implement any routines needed to create a fully functional class containing dynamic memory. This includes the ability to pass the class by value, do assignment between instances of classes, and avoid memory leaks or other problems.

It must compile with the following flags:

-g -O3 -Wpedantic -Wall -Wextra -Wmisleading-indentation -Wunused -Wuninitialized -Wshadow -Wconversion -Werror -std=c++17

And the Mikefile for the basis of the build is:

.PHONY: all memcheck clean

CXXFLAGS = -g -O3 -Wpedantic -Wall -Wextra -Wmisleading-indentation -Wunused -Wuninitialized -Wshadow -Wconversion -Werror -std=c++17

OBJS = main

all: ${OBJS}

memcheck: lean main

valgrind --leak-check=summary main

main: DListT.o

DListT.o: DListT.h

clean:

rm -f ${OBJS} *.o *.gcov *.gcno *.gcda

I just need the code for the main.cpp for this program to work as outlined here, it uses the DListT.h header file, so please be mindful of that.