So we started learning about linked lists to start which are basically another data structure with nodes. What's special about this one is that each node in the linked list has a reference to the next node in a 'list' of nodes and of course its own value. While the linked list itself has a reference to all the nodes starting from the front as well as the node at the very back.
With linked lists you can easily add elements in the middle of the linked list. If you had a linked list with two nodes you could add a third node in the middle of them, say x, and do this by simply setting the first node's reference of the next node to x and x's next node to the original second node. With a similar method you can seamlessly remove elements from the linked list too.
Sadly you can't just go into a linked list and say you want the data contained in the 6th element so you would have to use some sort of loop in order to access through the nodes sequentially until you find the data/x'th element that you wanted to find.
I really do think that these were pretty cool to learn about, creating our own method of storing data from scratch even though it is rather simple. You can customize them however you want and add different functions that are unique to it too.
Binary Search Trees
While we had already previously encountered BSTs we already know how they work. Given a node, n, it has a reference to its 2 children and the one on its left's data is less than n's data and the child on the right's data is greater than n's data, etc...
But we also started thinking about more functions that BST could have as well as the the efficiency in the manner in which we write code. I mean let me use the numbers 1-10 here for the sake of simplicity. You COULD make a BST such that it would look something like:
10
9
8
All the way down to 1. And you would have to access each and every value if you wanted to find if 1 was there.
It could also look like
8
7
6
5
3
And so on but it's much to tedious to try and illustrate that here without a picture or something instead. But here you can already see that if you want to find 6, you just have to look through the 5 and the 7, 2 nodes instead if we had the first example we would go through 10,9,8,7 to find 6.
It really depends on how you write the code to perform certain actions. While there are undoubtedly a myriad of ways to perform a single action, more often than not one of the ways are the most efficient.
No comments:
Post a Comment