Core -- Making a LinkedList class [6 marks]
In the file linkedlist.h implement a template class LinkedList. This should use the Node class you have written so far. As member variables you should have:
A pointer to the head of the list
A pointer to the tail of the list
A count of how many elements are in the list
The functions in LinkedList should be:
A constructor, that creates an empty list (head and tail are nullptr, 0 elements in the list)
A push_front function that takes an item and pushes it onto the front of the list, i.e. it becomes the head of the list. (Note this should not take a Node: for a LinkedList, we should be able to pass a T to push_front.)
A front() function, that returns a reference to the data inside the head node
A push_back function that takes an item and pushes it onto the back of the list, i.e. it becomes the tail
A back() function, that returns a reference to the data inside the tail node
A size() function that returns the count of how many elements are in the list
A begin() function that returns an iterator pointing to the head of the list
An end() function that returns an iterator pointing to nullptr (NB it doesn't point to the tail: it points off the endof the list -- and the Node after the tail is nullptr.)
A destructor, that deletes every node in the list.
A reverse()function that reverses the order of the nodes in the list (NB it doesn't make new nodes, it should re-order the existing nodes.)
(It is recommended you implement them in roughly this order.)
To test your LinkedList at this point, compile and run TestList.cpp. You can do this using:
make TestList
It may help you to comment out tests that use code you haven't written yet (as they won't compile). Alternatively, if you push your code to github, the automated tests will be run individually and should work even if you have not completed all parts.
Note: when your work is marked, deductions will be made for memory leaks. Take care to ensure that you have deleted every object you created with new, exactly once.
Once you're happy with your work so far, it's time to make the class a bit more useful.
First, extend your class to have a constructor that takes a std::initializer_list as its argument, and makes a list containing these. You can #include for this. This will allow lists to be created using the handy syntax:
LinkedList numbers{4,6,8,10,12};
When we write this, the numbers in braces are put in the initializer_list and passed to the constructor.
Next, inserting and erasing elements from linked lists is a classic interview question. Add functionality as follows:
insert(), taking as arguments a NodeIterator pointing to where to insert the new element in the list; and the element itself. The element should be inserted in this position, and an iterator to the new element returned. For instance for the list:
[3,5,7]
...if we have an iterator pointing to 5 and call insert with this and 4 the new list would be:
[3,4,5,7]
...and insert() would return an iterator pointing to 4.
Note you may edit your iterator class to provide a function to access the Node pointer from inside the iterator.
erase(), taking as argument a NodeIterator pointing to an element to erase; and returning what is now in its place -- after removing element i, it should return a NodeIterator to what is now element i. For instance, if the list was:
[3,5,7]
...and an iterator pointing to 5 was erased, that would update the list to be:
[3,7]
...and return an iterator pointing to 7. If you are deleting the last item off the list, it should return an iterator pointing to nullptr.
Again, as above, make sure your implementation avoids memory leaks.
To test your LinkedList now, compile and run TestListD.cpp. You can do this using:
make TestListD
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme
