Week 6

We had some audio issues that turned out to be a bad cable, so we had some quick photo and question-and-answer opportunities with the handful of us who were there. (We get really casual on Fridays.)

Today we’ll look more at data structures for Problem Set 5: Mispellings, where we give you a dictionary of words to load into memory.

One way to do this is with a linked list. The linked list we introduced last time had at least one advantage over arrays.

Dynamism and flexibility are the advantages, but with that said:

Recall that insertion, search, and deletion on a linked list are Ο(n), or linear, as the element could be at the end. You might get lucky and find the element as the first in the list, for a lower bound of Ω(1).

But we want to be able to have Ο(1), finding or adding or removing elements in constant time.

Let’s look at some blue books, each labeled with some letter of the alphabet. If they were shuffled and we started to sort them, we might instinctively start putting them into piles based on the first letter, and later go sort each pile individually.

Let’s formalize this idea. The following is an array with the index of each row on the left:

This is one implementation of a hash table, a higher-level data structure, which could use an array or linked list or some other fundamental ingredient as a building block to making a more useful final result.

We can simply declare a hash table with something like char* table[CAPACITY];, in which case it will be an array with size CAPACITY, but we might call a hash table an abstract data type that is layering on top of this array.

Earlier we used a physical table to place piles of blue books by the letters they were labeled. But the table is actually a fixed size, and if we had two elements of the same number, we couldn’t really place them into the same spot if the table was really an array.

So maybe we could place it into the next spot, where a book with the letter B would go. But now the B will go lower, and could become problematic, but is a technique called linear probing where we look at each element in the array, looking for an available spot to put the next one.

Insertion starts by being Ο(1) since the array is empty and you can jump to the correct location immediately, but once your data set becomes larger, insertion becomes Ο(n) since we have to move down the array looking for a spot. If your array is big enough and your data is sparse enough, you get the advantage of constant time, but the risk makes linear probing imperfect.

Instead of a hash table, we can use a tree, like a family tree. If we started with an empty tree, we can create a node that looks like this:

If we wanted to insert the name of "Daven", we’d first need to hash his name and realize it starts with D. But we can’t fit Daven’s entire name into the rectangle, so we can build a tree by allocating another node (rectangle) for each letter, and setting the pointers of each letter to the next node like this:

For the final letter in Daven’s name, we don’t want to put just NULL since Daven is actually short for Davenport and we want to accept both strings, so we should actually split each box in all these rectangles into two. Here, we’ve only drawn the last box, labeled n, as containing two fields. We can use the top one as a signal for the end of a string, and the bottom one as the pointer:

This looks complicated, and already messy because of David’s handwriting, so consider a tree that looks like this:[1]

We’ll start to call this data structure a trie, a clever name for a tree optimized for retrieval, but that’s spelled with "ie", so it ends up being pronounced like "try." Go figure.

These tries use a lot of memory since each node allocates space for so many indices, and most of that space will be empty, at least initially when we have few strings.

But we gain speed and spend less time, since insertion time will be Ο(1), since no one has an infinitely long name. The longest word in the dictionary for the problem set will be 40-something letters long, but it will be constant and not depend on how many other names are in this data structure. The running time will now depend on the length of the string, which is asymptotically Ο(1).

We might implement this with something like this:

typedef struct node
{
    bool word;
    struct node* children[27];
}
node;

node* trie;

To declare our trie, all we need is a single node* that points to the root element, just like a linked list.

Looking back to our chart, if we wanted to insert a name like "Dave," all we need to do is follow the pointers and change the box to mark that we are at the end of a word:

Remember that trays from dining halls can be stacked, and there exists a data structure called a stack where you can perform two operations, push (adding a tray to the stack) and pop (taking a tray from the top).

We have this property where the last item in is the first item out (LIFO) with interesting applications that we’ll look at another time.

A similar idea is a queue where the first item in is the first item out, (FIFO), enqueue (adding) and dequeue (subtracting).

We won’t really go into the code but if we think abstractly about adding people to a line one at a time, a linked list would work since we can add spots and people as needed, but an array would also work if we knew we had a limited number of spots.

So we’re reaching the point of having higher-level problems that can be implemented in a number of ways, giving us the flexibility of choosing between tradeoffs like time and space and code complexity.

A stack can be an array (in Mather the trays in the dining hall are in an opening in a cabinet of a fixed height, so it’s almost as though they’re using an array) but can be a linked list too.

Let’s look at one more data structure, a simpler tree like this:[2]

Each node is just a number, with other words like leaves and children and parents and siblings as illustrated.

One way to implement a tree in code might look something like this:

typedef struct node
{
    int n;
    struct node* left;
    struct node* right;
}
node;

Thinking back to recursion, if we put the integers in a sorted way like this, we’ll have a binary search tree:[3]

So we can implement the binary search algorithm a bit more elegantly than an array would allow, with code like this:

bool search(int n, node* tree)
{
    if(tree == NULL)
    {
        return false;
    }
    else if (n < tree->n)
    {
        return search(n, tree->left);
    }
    else if (n > tree->n)
    {
        return search(n, tree->right);
    }
    else
    {
        return true;
    }
}

So we introduce these data structures for you to evaluate and use in Problem Set 5, but let’s conclude on a teaser of how the real world implements web applications, as we transition to using higher-level languages.