In the file linkedlist.h implement a template class LinkedList. This should use the Node class you have written so far.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

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

 

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of