In my data structures class, we've been talking about things like Linked Lists
and Search Trees.
One thing that I've noticed in common with most of these structures is that
they're made up of nodes.
A node is just a simple way to store data. In a linked list, a node will also
store a reference to the next node. In a tree structure, it will store
references to its parent node, as well as child nodes one to the left and one to
A linked list has a head and a tail (first and last elements). In the version I
wrote for class, I made a doubly-linked circular list. That's a fancy way of
saying that each node kept track of the next and previous and the tail element
kept a reference to the head and vice-versa.
attr_accessor :next, :prev, :value
value = nodevalue
In order to keep track of the head and tail elements, I used what's called a
sentinel node. That's a special node in the list with a value of null.
sentinel = ListNode.new(null)
That makes for a linked list that looks like this:
It's the basis for all array type storage.
The next topic that we covered was trees. Specifically, we discussed the various
Binary Search Trees. Don't be scared of the words Binary and Search in there (or
even tree). It just means that the tree data structure is sorted.
See how each node on the left is less than the one above? And every node on the
right is greater than the one above it? That's what makes it a binary search
There are several different kinds of these trees because one of the biggest
things that effects how long it takes to find a given element in the tree is how
tall it is, called its height.
In the tree that I've drawn, the height is 3. I started at the root element (5)
and walked down the longest path to the bottom. That's the easiest way to
determine the height.
To try to minimize the height, there is a way to rotate the tree around a
different node. In this tree, we've got a pretty balanced tree already. However,
we could rotate the tree and choose 4 as our new root. That would make the tree
It's not much of a difference since it still has a height of 3.
So far I've been doing pretty well in this class. I'm looking to finish strong.
Next week is the end of class.