Introduction to Linked Lists

CS 106B: Programming Abstractions

Fall 2024, Stanford University Computer Science Department

Lecturers: Cynthia Bailey and Chris Gregg, Head CA: Jonathan Coronado

A long line of people

Slide 2

Announcements

Assignment 5 is due Friday

Slide 3

Today's Topics

Structs and pointers
Can you architect a queue?
- Let's do it with a Vector
- Let's try it with links
Introduction to the Linked List data structure
- The Node struct
Lord of the Linked Lists
How is the Stack implemented with a linked list?
Linked List Queue implementation

Slide 4

Using pointers with `class` and `struct` objects

Let's define a class (or it could be a struct) as follows:

class Date {
public:
    int day;
    int month;
    int year;
    string dayOfWeek; 
    int daysInMonth();
};

Pointers can point to a class or struct just like they can to any other variable:
```
Date* dPtr = new Date; // we now have a pointer to a Date object
```

If we want to access the class variables and functions, we could do this:

(*dPtr).day = 7;
int numDays = (*dPtr).daysInMonth();
cout << (*dPtr).month << endl;

But, this notation is cumbersome, and the parentheses are necessary becasue the "dot" has a higher precedence than the *.

So, there is a different, more intuitive syntax, called the arrow syntax: ->

dPtr->day = 7;
int numDays = dPtr->daysInMonth();
cout << dPtr->month << endl;

Arrow notation, x->var is equivalent to (*x).var, and we will use it exclusively when using classes and structs.

Slide 5

Can you architect a queue?

Let's investigate building a queue from a Vector

The following class definition for an integer queue would suffice for the enqueue and dequeue functions, with a Vector holding the data.

class QueueInt {          // in QueueInt.h
public:
    QueueInt ();          // constructor
  
    void enqueue(int value); // append a value 
    int dequeue();           // return the first-in value
  
private:
    Vector<int> data;     // member variables
};

Let's assume that we have the front of the queue on the left (earlier in memory), and the back of the queue on the right. If we enqueue eight values from 0 to 7, the vector would look like this:
```
front         back
↓             ↓ 
0 1 2 3 4 5 6 7
```
The enqueue operation is straightforward: we simply append to the back of the vector, one element at a time. enqueue(8) onto the queue just looks like this, and it is an O(1) operation:

front           back
↓               ↓ 
0 1 2 3 4 5 6 7 8

But, dequeue is more involved. Because the front is earlier in memory (on the left side of the vector), if we want to dequeue and remove the front element, we have to move all the other elements over one, one at at time. If we dequeue() on our vector, this is what happens:
```
1 1 2 3 4 5 6 7 8
1 2 2 3 4 5 6 7 8
1 2 3 3 4 5 6 7 8
1 2 3 4 4 5 6 7 8
1 2 3 4 5 5 6 7 8
1 2 3 4 5 6 6 7 8
1 2 3 4 5 6 7 7 8
1 2 3 4 5 6 7 8 8
↑             ↑
front         back
```
If we look at the complexity of enqueue() and dequeue(), we have:
- enqueue: O(1)
- dequeue: O(n)

An image that says 'WE CAN DO BETTER'

Slide 6

And Now for Something Completely Different

Let's use pointers to make things a bit more interesting.
Let's say that we have an 0 that we want to put into a queue. We can make a variable that holds an 0, and let's say we do this with dynamic memory.
Now, let's say we have a data pointer that points to an integer. In this case, it will point to the 0. We now have a queue! The front of the queue is the 0, as is the back of the queue.
Now, what if we want to enqueue(1) into the queue? Well, we can create a 1 "node" just like we created the 0.
What if we simply put a 1 somewhere in memory, and made the 0 (somewhow) "point" to the 1? (The somehow, by the way, is a pointer that is associated with the 0 called its next pointer, in a struct – we will get to that!).
Now we have enqueued the 1 into the back of the queue! Our data points to the 0, which we have now "pointed" to the 1.
We can do the same thing to enqueue(2). We create a new 2 node, and point the 1 to the 2:
There are two bits of extra information that we need to make this list a proper queue
- We need to figure out what the 2 points to. In this case, we will point 2 to nullptr, indicating that it is the end of the queue. If we check 2's pointer and find that it is nullptr, then we are at the back of the queue. In the diagram, we just represent this with a slash through 2's next pointer region.
- We need to designate the front as such, and the back as such:
At this point, we have enqueued, but what about dequeuing? Because we have a pointer to the front of the queue, dequeueing is actually fairly easy: we simply "follow" the pointer to the front, remove the 0, and then change our front pointer to point to the 1. To do this we "follow" 0's next pointer to find out where the 1 is:

We have dequeued 0 by pointing the front to the 1

At this point we can release the 0 "node" using the delete method.

We have dequeued 0 by pointing the front to the 1

Slide 7

Linked Lists

What we've just examined is the beginning of a linked list
A linked list is a chain of nodes
Each node contains two pieces of information:
- Some piece of data that is stored in the sequence
- A link to the next node in the list
- Although we had a "back" pointer for our queue, most linked lists just keep track of the front of the list.
We can traverse the list by starting at the first node (the front) and repeatedly following its link.
Each element is stored separately from the rest.
The elements are then chained together into a sequence.
To add a node at the end, we chain the last element to the end, by first finding the end (traversing the list), and then adding it:

Slide 8

Adding a node in the middle of a linked list

To insert a node into the middle of a linked list, we first need to find the location where we are adding it – this can be a slow process because we have to travers from the beginning!
Let's say we want to insert between 2 and 3. First, we need to find 2 by traversing from 1, and then we split the list and insert our new element:

Slide 9

Removing a node in the middle of a linked list

To remove a node into the middle of a linked list, we first need to find the location where we are adding it, as with insert.
Let's say we want to remove 100. First, we need to find 100 by traversing from 1, then 2, and then to 100. Then, we rewire the list so 100 points to 4:

Slide 10

Why linked lists?

We can efficiently splice new elements into the list or remove existing elements anywhere in the list
We never have to do a massive copy step
Linked lists have many tradeoffs, and are not often the best data structure!

Slide 11

Linked lists in C++

Let's take a look at building a linked list of strings
In C++, we represent the node in the linked list as a struct, with two fields, a data field, and a next field:
```
struct Node {
    string data;
    /* ? */ next;
```
But, what is the type of next? It must point to another Node, so…it is a Node* type:
```
struct Node {
    string data;
    Node* next;
};
```
The structure is defined recursively! The compiler can handle the fact that in the definition of the Node there is a Node*, becuase it knows it is simply a pointer. We could not recursively define the Node with an actual Node object inside the struct, as that would be impossible to realize.

Slide 12

Always!

Always draw pictures when you are building linked lists! This is critical to getting the hang of it.

Slide 13

Lord of the Linked Lists

In a scene that was brilliantly captured in Peter Jackson’s film adaptation of The Return of the King, Rohan is alerted to the danger to Gondor by a succession of signal fires moving from mountain top to mountain top. This scene is a perfect illustration of the idea of message passing in a linked list.

Slide 14

Return of the King

An image of Aragorn from Lord of the Rings, Return of the King

Return of the King clip

Slide 15

Lord of the Linked Lists

We are going to make a San Francisco-based linked list, based on CalTrain stops. Step 1, make the linked list:

Step 2: Light the fires!

struct Tower {
   string name;  /* The name of this tower    */
   Tower* next;  /* Pointer to the next tower */
};

Add the first tower:

// add the first tower
Tower * head = new Tower; 
head->name = "San Jose";
head->next = nullptr;

The main function:

// main
Tower * head = new Tower; 
head->name = "San Jose";
head->next = nullptr;
  
head = createTower("Santa Clara", head);
head = createTower("Mountain View", head);
head = createTower("Palo Alto", head);
head = createTower("Menlo Park", head);
head = createTower("Redwood City", head);
head = createTower("Millbrae", head);
head = createTower("Bayshore", head);
head = createTower("San Francisco", head);

The createTower function:

Tower* createTower(string name, Tower *next) {
   Tower* tp = new Tower;
   tp->name = name;
   tp->next = next;
   return tp;
}

The signal function (which is recursive!):

void signal(Tower* start) {
   if (start != nullptr) {
      cout << "Lighting " << start->name << endl;
      signal(start->next);
   }
}

We call the function with the head:
```
signal(head);
```
By the way: the head pointer is not a Tower! it is only a pointer to a Tower, and the first Tower is San Francisco.

Slide 16

How is the Stack implemented with a linked list?

The qt logo

The Node definition we've seen before:

struct Node {
    int data;
    Node *next;
};

Slide 17

Stack

Let's assume we have the following stack already, with 8 at the top, and 9 below 8. We then want to push(7) onto the stack:
Here is our goal:
Our first attempt at push(7):
```
Node* temp = new Node;
temp->data = 7;
```
If we try to rewire by changing head first…
```
head = temp;
```
In other words: a linked list's elements must be pointed to, because we need to keep track of them. In our attempt above, we've lost access to the 8, becuase the only thing pointing at the 8 was head. If we reassign head to point to another object (the 7 in this case), we've broken the chain and lost 8. This is a common bug!
Let's try again:
Here is our goal:
Our next attempt at push(7):
```
Node* temp = new Node;
temp->data = 7;
```
Now we rewire 7's next pointer first:
```
temp->next = head;
```
You might be thinking, wait – why didn't the arrow go from the 7 to the head? – this is a common misconception of what is happening!
- Remember, head is not a Node. head is a pointer to a Node. Notice that head does not have a next – it's not an object, just a pointer.
- The statement temp->next = head; says, "give 7's next pointer the same data as head", which is what we want to do.
Now, we are able to reassign head to point to the 7, and we will have a correct linked list with 7 pushed onto the top:
Our temp pointer actually disappears when the push operation is complete (it goes out of scope), so we are left with the following:

Slide 18

Stack `pop()`

To pop a data from our stack, we start like this:
```
int toReturn = head->data;
```
What if we tried this to reassign head?
```
head = head->next;
```
This is a bug! Our linked list is fine, but we have a memory leak! We have left the 7 in memory and not returned it to the operating system with delete.
Instead, we need to do this:
```
Node* temp = head;
```
Now we can reassign head:
```
head = head->next;
```
Because we still have access to the 7, we can return the memory to the operating system:
```
delete temp;
```
Finally, we return the data, and temp goes out of scope:
```
return toReturn;
```

Slide 19

Stack Code

Header, intStack.h:

#pragma once

class IntStack {
public:
    IntStack(); // constructor
    ~IntStack();

    bool isEmpty();
    
    void push(int value);
    int top();
    int pop();

private:
    struct Node {
      int data;
      Node* next;
    };
    
    Node* head;
};

Class code, intStack.cpp

#include "intStack.h"

IntStack::IntStack()
{
    head = nullptr;
}

IntStack::~IntStack()
{
    while (head != nullptr) {
        Node *temp = head;
        head = head->next;
        delete temp;
    }
}

void IntStack::push(int value)
{
    Node* node = new Node;

    node->data = value;
    node->next = head;

    head = node;
}

int IntStack::pop()
{
    if (isEmpty()) {
        throw "Error! Trying to pop from empty stack!";
    }
   
    int toReturn = head->data;
 
    Node* temp = head;
    head = head->next;

    delete temp;
    return toReturn;
}

Slide 20

A Linked List Queue

intQueue.h

#pragma once

class IntQueue {
public:
    IntQueue(); // constructor
    ~IntQueue();

    bool isEmpty();

    void enqueue(int value);
    int front();
    int dequeue();

private:
    struct Node {
        int data;
        Node* next;
    };

    Node* _front;
    Node* _back;
};

intQueue.cpp:

#include "intQueue.h"

IntQueue::IntQueue()
{
    _front = nullptr;
    _back = nullptr;
}

IntQueue::~IntQueue()
{
    while (_front != nullptr) {
        Node *temp = _front;
        _front = _front->next;
        delete temp;
    }
}

void IntQueue::enqueue(int value)
{
    Node* node = new Node;

    node->data = value;
    node->next = nullptr;

    if (_back == nullptr) { // enqueue on empty queue
        _front = node;
        _back = node;
    } else {
        _back->next = node;
        _back = node;
    }
}

int IntQueue::dequeue()
{
    if (isEmpty()) {
        throw "Error! Trying to dequeue from empty queue!";
    }

    int toReturn = _front->data;

    Node* temp = _front;
    _front = _front->next;

    if (_front == nullptr) {
        _back = nullptr; // empty queue
    }

    delete temp;
    return toReturn;
}

bool IntQueue::isEmpty()
{
    return _front == nullptr;
}

int IntQueue::front()
{
    return _front->data;
}

Introduction to Linked Lists

CS 106B: Programming Abstractions

Fall 2024, Stanford University Computer Science Department

Lecturers: Cynthia Bailey and Chris Gregg, Head CA: Jonathan Coronado

Announcements

Today's Topics

Using pointers with class and struct objects

Can you architect a queue?

And Now for Something Completely Different

Linked Lists

Adding a node in the middle of a linked list

Removing a node in the middle of a linked list

Why linked lists?

Linked lists in C++

Always!

Lord of the Linked Lists

Return of the King

Lord of the Linked Lists

How is the Stack implemented with a linked list?

Stack

Stack pop()

Stack Code

A Linked List Queue

Using pointers with `class` and `struct` objects

Stack `pop()`