I have just taken a new course, Game Programming III.
There is one major assignment which is divided into three steps. The first part is to construct the most common data structures used in programming, a linked list and a binary search tree. Both are used to store data. The linked list is a list of objects containing data, called nodes. The nodes are linked to each other forming a kind of chain of nodes. The binary search tree is similar, but instead of one potentially long chain of nodes, it branches from one original node into two directions. The following objects can also themselves branch into two sub chains of nodes.
This post is about this part of the assignment. The other parts will be blogged about later, as I do them.
What I’ve done is a doubly linked list. As opposed to a single linked list that links the data nodes from head to its end, my list are linked from head to tail and from tail to head. This is a little more efficient than the single linked lists because if you’d want to place something in the back of the list, you don’t need to follow the whole list from head to tail to place it there. With the doubly linked list you can simply place it at its tail directly.
I have also created functions to add nodes at the front or at the back and to delete nodes from the front or the back. A function to search the list for specific data, another to erase a node at a specific index and a function to see how many nodes it contains.
To add a new node at the front, I instantiate a new node and allocate it to the heap memory and set its data member to the desired value. Then I point its link going in the direction towards the tail to the node which the head is currently pointing to. Since this new node is to be added to the front, its other link is set to point to null. This is to mark the end, or beginning depending on what direction you start from, when iterating through the list. Then the head is set to point to this node instead.To add a node to the back, the exact same thing is done only instead of the head pointer I use the tail pointer and link the new node in the opposite direction.
To delete the front node, a temporary pointer is instantiated and set to point to the node currently pointed to by the head pointer. Then the head pointer is set to point to the following node and the node now currently pointed to by the temporary pointer is now deleted. Again, same procedure when deleting the back node.
To search the list, I take a value to be looked for and create a temporary pointer and set it to point to the head node. Then I let it follow the links until I find a nullptr link, indicating the end of the list. Every loop I evaluate if the nodes data is equal to the target value and return the pointer to that node. If I can’t find the value I return nullptr. I return a pointer because there could be other data to be accessed from the node, should the node hold other data than a number.
The erase function was a little trickier. If you only iterate through the list the number of times equal to the given index number to erase, you would loose the rest of the list and perhaps be unable to recover it. Another problem was if there only was one or two nodes there. I use no less than three different node pointers, so one would definitely be invalid in these cases. How I did was this:
First I check if head is nullptr, which means that the list is empty and tail is also nullptr. In that case I print a string informing that the list is empty.Then I check if size() (the function count the nodes and return the value) is lesser than index and return an out of range message. Then I check to see if head == tail, meaning there is only one node in the list. Then I chose to call pop_front(), but pop_back() would have worked as well. After that I check to see if size() == 2 and index <= 1, meaning if there are two nodes in the list and index is 0 or 1, I use pop_back() if index is one, and pop_front() if index is zero. Then the rest of the cases have at least three nodes, required for the following operation. I iterate trough the nodes and each loop I check if a counter is one less than the index, equal to the index or one more than index. When I find them, I set the temporary pointers: before, delete and after respectively to the current node being pointed to in the loop. Then I bypass the designated node to be deleted by assigning before’s and after’s corresponding links to the delete node’s links and delete that node.
figure 1 illustrates a singly linked list and a doubly list
For those interested in the code, here: http://pastebin.com/UsW7hse9
the comments look a little weird, but never mind that.
The next thing to do is the binary search tree. I will have to update on that later. It’s sunday night, I can’t finish it today.