Week 5

We started talking about pointers, an address to a location in memory where a piece of data might be stored.

In C, we can go to these locations and allocate more memory to use.

We looked at this diagram, which showed how memory is divided up into regions for specific things:

We also figured out how to swap variables by passing in pointers and changing the values they point to:

void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

We also looked at images and file formats, and also our own data types.

Arrays store the same type of data in a consecutive chunk of memory, so we can jump to each location by knowing its index.

But we have some limitations. If we wanted to increase the size of an array, we can’t always add another element to the end of it, since the memory right after it might be used to store some other variables.

We could allocate memory of a bigger size, copy what we had before to the new location, and add elements there, but that requires more and more work as our array grows bigger and we have more to copy.

But with the ability to dynamically allocate memory and create our own data types, we can do something like this:

We’ll create nodes with a struct like this:

typedef struct node
{
    int n;
    struct node *next;
}
node;

With this data structure, we can have operations like delete, insert, and search.

We can implement these functions fairly intuitively.

Going back to our first diagram, we need at least a pointer called first to point to the first node, the start of the list. And the last node will have a pointer to NULL, so we can know we’re at the end of the list.

To search for an element in the list, we need to start with the first element, follow the pointer to the second element, and so on. This is because each node could be anywhere in memory, so we can’t use strategies like binary search. So the running time of this linear search will be O(n), even if our list is sorted.

Insertion would be O(1) if we didn’t want to keep the list sorted, since we can just insert the number at the beginning. We’ll have first point to our new node, and have the new node’s next pointer point to the previously first node. But if we want to keep the list sorted, we’d have to find the correct location to insert the number first, which would again take running time O(n).

Similarly, deleting a node will also take O(n) since we’ll need to find the number want to delete first.

We demonstrate inserting with a few volunteers. We need to be careful when inserting at the end of the list, since we need to update the last node to point to the new node before we follow its NULL pointer and lose track of it. We also need to be careful when inserting into a list, since we need to change the new node to point to the next node before we change the previous node’s pointer (since that’s the only place we keep track of the next node).

Removing elements would require carefully ordering the operations we do, since we don’t want to lose parts of our list or our node before we free its memory.

Let’s implement the search function, which will help us with learning the syntax of using nodes, structs, and pointers:

bool search(int n, node *list)
{
    node *ptr = list;
    while (ptr != NULL)
    {
        if (ptr->n == n)
        {
            return true;
        }
        ptr = ptr->next;
    }
    return false;
}

With linked lists, we get the ability to grow and shrink it as we need, but slower searches and insertions and deletions, and overall in CS there tends to be a theme of tradeoffs between time or space or complexity.

Imagine a stack of trays, where you can easily take the top tray off or put another tray on top, but not much else. A data structure with this metaphor, called a stack, does exist, with the operations push and pop, that stores and removes items respectively.

The property we now get is that the last item we pushed, will be the first one we pop. And there are applications where this property is useful, such as our stack in memory where the next function being called is placed on top of the previous function.

We could implement this ourselves:

typedef struct
{
    int numbers[CAPACITY];
    int size;
}
stack;

And instead of storing the entire array in our struct, we can store just the pointer to the first element:

typedef struct
{
    int *numbers;
    int size;
}
stack;

A queue would be the opposite of a stack. In a queue, the first item in will be the first item out, like a line of people. We’ll have operations enqueue, which places an element at the end of the list, and dequeue, which takes the first element from the beginning of the list.

With a queue, we need to keep track of a little more information:

typedef struct
{
    int front;
    int numbers[CAPACITY];
    int size;
}
queue;

And we can similarly dynamically allocate memory:

typedef struct
{
    int front;
    int *numbers;
    int size;
}
queue;

A stack and queue are both abstract data types, where we can implement them in any number of different ways but expect the same properties and operations.

We watch a quick animation about stacks and queues.

With pointers, we can also now build data structures that aren’t just one-dimensional:

Now imagine if we had some numbers and wanted to be able to search them efficiently with a binary search algorithm. We could use an array, but we could also use what’s called a binary search tree: