Introduction #

A binary tree is a tree where each node has up to two leaves, and each of those leaves has up to two leaves. So you start with a root node and then fan out, like a genealogical tree.

The way the insertion works is that you look at the root node and decided whether the value you are trying to insert is less than or greater than the root node node value. If less than then you go down the left hand, if more than then the right. You repeat this process for each node in turn. The result is that the tree is automatically sorted, just by insertion. Because you are essentially halving the number of items you need to investigate each time, this is very efficient.

Introduction #

A doubly linked list is the same as a linked list, execept that now each item is linked to both the next one and the previous one. So if you have a linked list with the following items (1, 2, 3, 4) it would look like this:

flowchart LR;
    H(["HEAD"]) --> A([1]);
    A([1]) <--> B([2]);
    B([2]) <--> C([3]);
    C([3]) <--> D([4]);
    D([4]) --> E(["NIL"])

The operations available on a doubly linked list can vary - in this case we provide a function to check to see if the doubly linked list is empty or not, a function to get the length of the list, a function to get the items without removing them, a function to list the items without removing them, a function to search the doubly linked list, as well as functions to add or remove items from the front of the list, the back of the list, as well as a specified position in the list.

Introduction #

A linked list is literally that, a list where each item is linked to the next one. So if you have a linked list with the following items (1, 2, 3, 4) it would look like this:

flowchart LR;
    H(["HEAD"]) --> A([1]);
    A([1]) --> B([2]);
    B([2]) --> C([3]);
    C([3]) --> D([4]);
    D([4]) --> E(["NIL"])

The operations available on a linked list can vary - in this case we provide a function to check to see if the linked list is empty or not, a function to get the length of the list, a function to get the items without removing them, a function to list the items without removing them, a function to search the linked list, as well as functions to add or remove items from the front of the list, the back of the list, as well as a specified position in the list.

Introduction #

Queues, in there simplest form, are like stacks, except that the first element in is the first element out, or FIFO (First In First Out). It’s a bit like a stack of plates were you alway put on the top of the stack but if you remove a plate you take it from the bottom.

As noted for stacks, we are using any type instead of a specific type like string or int. This means we don’t have to write different stacks for different types.

Introduction #

The stack is one of the simplest data structures and one that is easy to image from every day life. If you have a stack of dishes, you normally add to the top of the stack and when you want to take one off you also take it from the top. This is known as First In First Out, or FIFO. The act of adding a plate is called pushing a new plate onto the stack, removing one is called popping the plate from the stack. A stack has a length - the number of plates in the stack. You also know when the stack is empty - there are no plates left. And that essentially tells you everything you need to know about a stack.

Introduction #

The Quick Sort algorithm uses what is known as a divide and conquor technique. It revolves around the idea of choosing a particular element in the array and then doing what is called pivoting around that. Essentially, all the elements less than the pivot go into the left hand array, all the elements greater than the pivot go into the right had array. The pivot itself can be choosen in different ways. It can be:

Introduction #

The merge sort is a bit more complicated than the bubble sort and insertion sort as you can see by the code below. In principle the merge sort works by splitting the array in half, and then splitting each of those two parts in half, and then splitting each of those four parts in half, etc, until we have elements of a maximum of two elements. We then sort and merge those elements in a specific order to ensure that the end result is the sorted array we were wanting.

Introduction #

Another way of sorting an array is by using the insertion sort method. In this case we start at position 1 in the array¹. We then set j = i, or in this case, 1. We then compare array[j - 1] with array[j], i.e. array[0] and array[1]. If array[0] is greater than array[1], we swap them. Then we subtract 1 from j and if j is greater than zero, we do the next j, other we break and do the next i. In one sense this is very similar to the bubble sort, but we do not have to loop through the entire array each time, just part of it, which makes this faster and more efficient than the bubble sort. Let’s look at the code.

Introduction #

There are many different ways of sorting an array. One the simplest ways is the bubble sort. Essentially you start at the beginning of the array and compare element i with element i + 1. If i > i + 1, swap them, and increment i. This way the larger value bubbles up the array, hence the name bubble sort. You repeat this until there you can run through the entire array without swapping anything. At this point the array is sorted. As you can image, this works, but is certainly not very efficient.

Introduction #

The Fibonacci sequence is probably one of the best know number sequences, with each number in the sequence being the sum of the two numbers that precede it, with 0 and 1 normally being the first two numbers of the sequence. The mathematical equation describing it is Xn+2= Xn+1 + Xn.

Solution Using a For Loop #

We can use the basic structure of the fizzbizz program as a template for writing this program. There are various ways to program the fibonacci sequence. The simplest way is to use a for loop. The more elegant solution is to use recursion. For this program we will assume that the only user input is to be able to specify the number of terms the user wants to calculate for the sequence.