Linked List FAQ

Template classes are a type of structure whose functionality can be adapted to more than one type or class without repeating the entire code for each type. You've actually used template classes very often! Look at vector for example. When you instantiate a vector object you always give it the type that you want it to contain. For example,

std::vector<string> myStrings;

creates a vector that will contain string objects. You will learn how to create your own template classes as you complete this lab.

VERY IMPORTANT NOTE
If you have functions longer than 10 lines in your .h file, you WILL NOT be able to implement them in your .cpp. You can just implement them in your .h file instead.
They still need to be moved outside of your class declaration, but can, (and should) stay in your .h file. For example:

template <typename T>
class LinkedList {
...
public:
    void remove(const T& value); //FUNCTION LONGER THAN 10 LINES
...
}; //END OF LINKED LIST CLASS

template <typename T>
void LinkedList<T>::remove(const T& value) {
    //REMOVE FUCTION DEFINITION
}

Nodes are devices or data points on a larger network.Your linked list will be a collection of nodes. Each node contains the data it holds and a reference to the next node. For example you might create a node struct inside of you LinkedList class as follows:

template <typename T>
class LinkedList {
...
private:
    struct Node{
        T data;
        Node* next;
        ...
    }
}

You can then instantiate a node object as follows:

Node* n = new Node();

This line of code creates a node reference pointer called n and points it to the memory address of the newly allocated node object. Note: It's generally a good idea to create some strategic constructors for your nodes, depending on how they are being used.

Make sure you refer to the first FAQ for a more general understanding of this topic.

This biggest issue with memory leaks is keeping track of all of your nodes. Make sure when you create a node with the word new that you don't lose track of it. For example:

insertHead(T data) {
    Node* node = new Node(data);
    if(find(data)) { //WE ARE GOING TO ASSUME THIS IF-STATEMENT WILL EXECUTE IN THIS EXAMPLE
        return false;
    }
    else {
        //DO SOMETHING ELSE
    }
}

Do you see the issue here? We created a new node on the second line, (using the word new means we allocated memory), but then we returned false before we had a chance to keep track of that new node.
There are two solutions to fix this memory leak. Either wait to say new until we have verified there are no duplicates, or right before we return false on the 4th line, change it to say:

delete node;
return false;

so we don't have any leaks.

A segmentation fault could mean any number of things. For this lab, what you are most likely encountering is a segmentation fault from accessing NULL or out of bounds memory.
For example:

Node* head = NULL;
cout << head->data;

Or:

node* temp = head;
while(temp->next != NULL) {
    temp = temp->next;
}

//LETS ASSUME THAT YOU DON'T EVER SET THE END OF THE LIST TO BE NULL, MEANING THAT THE STATEMENT
//TEMP->NEXT WILL NEVER RETURN A NULL VALUE AND INSTEAD KEEP GOING TO THE END OF YOUR LIST
//UNTIL IT GOES OUT OF BOUNDS.

In the first example, we tried to access the data member of a NULL pointer; this will always cause a seg fault. To avoid errors like this, make sure that you always know your pointers are not pointing to NULL before you try to do stuff with them. You could solve that with something like this:

if(head != NULL) {
    cout << head->data;
}

This will ensure you don't try to access anything on a NULL pointer.

To solve the second issue, you will want to find some way to make sure that the last node in your list is pointing to NULL. We will let you try and figure out how to make that one work on you own!

The reverse function is a little bit trickier than any of the other ones. I would reccomend finding an online tutorial if you find yourself gettting stuck. This one: geeksforgeeks.com is a really good one. Obviously don't just copy and paste the code, but really try and understand what is going on here. The lab specs also have some helpful .gif images that might be able to help you understand what is going on.

This could be one of a few things. Make sure you have implemented every function in the interface. If you haven't done them all yet, comment out the functions you haven't finished from the interface until you can write them. Make sure you include everything from the definitions in your implementations (i.e. string LinkedList::toString() const {...}
Don't forget the const from the interface or your code won't compile.