Programming Blog – Week 2

This week I created my linked list for the first assignment of this course.

The first idea I had for this was a struct Node shown below.

struct Node {

int data;

Node *next;

}

Then I had to tackle the problem of having several Nodes and where to store them, and while thinking of using actual std::lists or vectors a friend told me that I only needed to define the root-node and the rest would just be layered through the Node *next without needing a way of storing them. so, I created the rootnode as a member-variable of the class LinkedList that I created for this assignment.

Any additions to this “linked list” would just add a node to this base, or switching the head to a new node (push_front() does this) while moving the previous head one step into the hierarchy.

Removing additions through pop_back/front just reversed this process by removing either the last node (found by looping through until the node no longer had a defined next-node) or the first one (removed by making head = head->next then deleting the old head).

The search method takes an argument for T data (everything had to be done using general coding, templates) and returning a bool found. This was done by looping through the nodes and comparing each nodes data by the argument.

Size loops through and counts every node, everything so far has used the same looping-method, this is the code for the loop in the size-method.

Node *current = m_root;
++size; //The root exists, count it
while (current->next != nullptr) {
++size;
current = current->next;
}

Basically it loops until the final node is found (the one who has no defined next-node) and then returns the number of times it looped.

Erase was trickier, this method takes an argument int index for what position in the linked list it wants removed, meaning that to remove a node in the middle of the list I would have to make the previous nodes’ next pointing to the targeted nodes next, which in turn meant that I had to keep track of both the current node and the previous one while looping through the list.

I am now working on a Binary Search Tree which is the second part of the first assignment, and I will also be looking into unit testing which is required for this assignment as well. Thank you for your time and I’ll see you next week,