Linked Lists

Notes

One downside of arrays is that they have a fixed size.

To solve this problem of fixed size, we’ll relax the constraint that the memory we use be contiguous. We can take a little bit of memory from here and a little bit of memory from there just so long as we can connect them together. This new data structure is called a linked list.

Each element of a linked list contains not only the data we want to store, but also a pointer to the next element. The final element in the list has the NULL pointer, represented by a cross through the bottom half of the last node in this slide.

To store a linked list, we just need to remember where the first element is. We can find the rest by following the pointers.

We’ll call each element of the linked list a node, which will contain the data we wish to store as well as a pointer to the next element in the list.

Here, we use struct syntax to create our own data type to encapsulate a node. int n is the data we wish to store in the node and struct node* next defines a pointer to the next node in the linked list.

Remember that a node won’t be typedef-ed until after all of these lines are executed. Thus, we have to write struct node instead of just node, both before the curly braces and inside the curly braces. On the very last line, we provide node to typedef as the name we want to use for this new data type for the rest of our program.

To search the list for 9, we'll need an additional pointer (depicted in yellow in the slide).

This pointer will point at each node successively and allow us to check if n == 9.

Note that this is linear search, and therefore the worst case runtime of this algorithm is O(n).

To begin with, ptr points to the first node of the list.

As long as ptr != NULL, we will dereference it and check to see if ptr->n is the value we are searching for. If so, the function returns true.

If we haven't yet found the value we're searching for, ptr must progress to the next node in the list. To point ptr to the next node in the list, we can’t simply write ptr++. The memory in a linked list is not contiguous, so the next node in the list is not necessarily right next to where ptr is pointing. Instead, ptr needs to point wherever ptr->next is pointing.

If ptr has reached the end of the list without finding the value we are searching for, the function returns false.

Insertion and deletion of elements is potentially expensive with arrays. If we want to insert an element in an array anywhere except the end, we have to shift the rest of the array to the right -- with long arrays, this takes a lot of time. And if the array is full, we can't even add to the end, and have to copy it!

In contrast, linked lists make element insertion and deletion very easy. A list is a good choice when the number of objects in your list is not known before you start to solve the problem, and the size of this list may grow and shrink during the task

Let's insert an element into this linked list. To begin with, we need to request memory for a new node, and initialize it with data. The n field of our new node here has been set to 1, and its next field has been set to NULL.

If we wish to maintain an ordered list, our new node belongs at the head of the list.

We need to be careful when updating pointers. If we first update head to point to our new node, then we orphan the remainder of the linked list.

Instead, we should point the new node's next field to the same node that head is pointing to.

And then have head point to the new node.

Voila! Our new node has been inserted without ever losing hold of the rest of the linked list!

To insert at the head of a linked list:

  • malloc a new node and initialize it with data
  • set the new node's next field to point to the first node in the list
  • set head to point to the new node

A doubly-linked list is a linked list in which each element contains pointers to both the next and the previous elements.

Doubly-linked lists are useful when you need to insert and remove objects from the center of the list, as well as from its ends, or when you need to traverse the list forward as well as backward.

Here's how to declare a node in a doubly-linked list.

Note that this node has two pointers: one which points to the next node in the list, and one which points to the previous node in the list.

Slides ( / )

study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide

Length

Write a function that returns the length of a singly linked list.

jharvard@run.cs50.net (~): ./a.out
Making sure the list length is indeed 10...
good!

Try out some pseudocode here!
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#define SIZE 10

typedef struct node
{
    // the value to store in this node
    int n;

    // the link to the next node in the list
    struct node* next;
}
node;

node* head = NULL;

int length(void)
{
    // TODO
}

int main(int argc, char* argv[])
{
    // create linked list
    for (int i = 0; i < SIZE; i++)
    {
        node* new = malloc(sizeof(node));

        if (new == NULL)
        {
            exit(1);
        }
        new->n = i;
        new->next = head;
        head = new;
    }

    printf("Making sure that list length is indeed %i...\n", SIZE);

    // test length function
    assert(length() == SIZE);
    printf("good!\n");

    return 0;
}

Prepend

Write a function that prepends a new node containing <tt>int i</tt> to the front of a singly linked list.

jharvard@run.cs50.net (~): ./a.out
Prepending ints 0-9 onto the list...
Your list contains 9 8 7 6 5 4 3 2 1 0

Try out some pseudocode here!
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#define SIZE 10

typedef struct node
{
    // the value to store in this node
    int n;

    // the link to the next node in the list
    struct node* next;
}
node;

node* head = NULL;

void prepend(int i)
{
    // TODO
}

int main(int argc, char* argv[])
{
    // creating list
    printf("Prepending ints 0-%i onto the list... ", SIZE - 1);
    for (int i = 0; i < SIZE; i++)
    {
        prepend(i);
    }
    printf("done!\n");

    // printing out list
    printf("Your list contains ");
    for (node*  ptr = head; ptr != NULL; ptr = ptr->next)
    {
        printf("%i ", ptr->n);
    }
    printf("\n");

    return 0;
}

Contains

Write a function that returns true if a node in the linked list contains int i and false otherwise.

jharvard@run.cs50.net (~): ./a.out
What value are you looking for? 9
Sorry, the list only contains 1 2 3 4 5

Try out some pseudocode here!
#include <cs50.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#define SIZE 5

typedef struct node
{
    // the value to store in this node
    int n;

    // the link to the next node in the list
    struct node* next;
}
node;

node* head = NULL;

bool contains(int i)
{
    // TODO
}

int main(int argc, char* argv[])
{
    // create linked list
    for (int i = SIZE; i > 0; i--)
    {
        node* new = malloc(sizeof(node));

        if (new == NULL)
        {
            exit(1);
        }
        new->n = i;
        new->next = head;
        head = new;
    }

    printf("What value are you looking for? ");
    int i = GetInt();

    if (contains(i))
    {
        printf("Found it! The list contains ");
    }
    else
    {
        printf("Sorry, the list only contains ");
    }
    for (node*  ptr = head; ptr != NULL; ptr = ptr->next)
    {
        printf("%i ", ptr->n);
    }
    printf("\n");

    return 0;
}

Append

Write a function that appends a new node containing int i at the end of a singly linked list.

jharvard@run.cs50.net (~): ./a.out
Appending ints 0-9 onto the list...
done!
Your list contains 0 1 2 3 4 5 6 7 8 9

Try out some pseudocode here!
#include <stdio.h>
#include <stdlib.h>

#define SIZE 10

typedef struct node
{
    // the value to store in this node
    int n;

    // the link to the next node in the list
    struct node* next;
}
node;

node* head = NULL;

void append(int i)
{
    // TODO
}

int main(int argc, char* argv[])
{
    // creating list
    printf("Appending ints 0-%i onto the list...\n", SIZE - 1);
    for (int i = 0; i < SIZE; i++)
    {
        append(i);
    }
    printf("done!\n");

    // printing out list
    printf("Your list contains ");
    for (node*  ptr = head; ptr != NULL; ptr = ptr->next)
    {
        printf("%i ", ptr->n);
    }
    printf("\n");

    return 0;
}

Insert Sorted

Write a function that inserts a new node containing int i into the appropriate position in a list sorted in ascending order.

jharvard@run.cs50.net (~): ./a.out
Inserting 5 random ints to the list...
Your list now contains 0 1 2 3 3

Try out some pseudocode here!
#include <stdio.h>
#include <stdlib.h>

#define SIZE 5

typedef struct node
{
    // the value to store in this node
    int n;

    // the link to the next node in the list
    struct node* next;
}
node;

node* head = NULL;

void insert_sorted(int i)
{
    // TODO
}

int main(int argc, char* argv[])
{
    printf("Inserting %i random ints to the list...\n", SIZE);
    for (int i = 0; i < SIZE; i++)
    {
        insert_sorted(rand() % SIZE);
    }
    printf("done!\n");

    // printing out list
    printf("Your list now contains ");
    for (node*  ptr = head; ptr != NULL; ptr = ptr->next)
    {
        printf("%i ", ptr->n);
    }
    printf("\n");

    return 0;
}

Videos

study50 video thumbnail

Monday, Week 6

An introduction to data structures
study50 video thumbnail

Jackson's Singly Linked Lists Short

Jackson gives a general overview