Data structures

What did I do?

I wrote algorithms for two basic generic data structures: a linked list and a binary search tree (BST). This was done for two reasons: to derust after not coding for a while, and to learn a bit about data structures.

Some short definitions: a linked list consists of nodes, which contain some data and a pointer to the next node in line. This creates a list which can be easily iterated through in order to find whatever data you are looking for. It is also very easy to add and remove elements from the list, since you at most need to edit one existing object in a list in its simplest form. However, it can take a while to traverse, since you have no way of knowing exactly where that data is, meaning that you potentially have to traverse the entire list to find it.

Similar to a linked list, a binary search tree also consists of nodes. However, instead of having just one pointer to the next object in line, you have two. One points to a node with a greater value, while the other points to a node with lesser value. For example, if your original node contains the data 3, and you try to add 10, it will create a node with the data 10, and point 3’s “greater than”-pointer to the new node. If you then add 5, it will create a new node and point 10’s “lesser than”-pointer to the new node.

A BST can effectively cut the time spent looking for a particular object in half, since you immediately can eliminate half the values by comparing if the asked data is greater or less than the first value, and accordingly traversing that part of the tree.

Code can be found here. I consider the linked list to be complete for now, while the BST still has some methods that need to be added, as well as some polish (safeguards for crashes, more informative errors, and so on).

How did I do it?

I followed explanations on how the two data structures worked from our lecture on them, as well as pages such as Wikipedia[1] [2] and Stack Overflow [1]. This gave me a good general idea of how they needed to function in order to be called linked list respectively BST. After that I just… wrote code. I fixed issues that I realized while coding, tried to compile, fixed the compile errors, and so on until they behaved as required.

Why did I do it like this?

Most of the code is fairly straight-forward, at least to me. Some perhaps questionable code are the ternary operations (?:) in the BST methods. I did those simply because they looked way more neat compared to if … else‘s.

Some of the methods could also have been done using recursion instead of loops. Reason for using loops was that they are way easier for me to process and understand, both when structuring the code and when reading it afterwards.