Lecture 5/20: Linked Lists 2

May 20, 2020

📂Associated files

Questions and Answers

Announcements

Section leaders are working on releasing assessment grades and feedback. We are aiming to get all feedback released by the end of the day today.
- All grades will be calculated and reported only as Pass / No Pass.
- If you scored a No Pass on either one of the two parts, you should expect to get an email from me in the next day or two to check-in about how the assessment went from your perspective and to schedule a time to revist the content and have a make-up assessment with one of Chris, Julie, or Nick next week.
- If you have any concerns about your performance on the assessment or the feedback provided by your section, please feel free to reach out to Chris, Julie, or myself and we would be happy to chat with you further.
Assignment 5 is due on Friday! The YEAH slides and recording were both posted last night if you're looking for help on how to get started.
Memorial Day Holiday
- No lecture next Monday, May 25
- No LaIR on Sunday, May 24 nor Monday morning on the 25th
- Extra Wednesday morning shift added on Wednesday, May 27
- Chris will still be holding OHs from 11am-1pm on Monday, May 25

Slide 3

Today's Topics

How to build a stack from a linked list
How to build a queue from a linked list
Building a full LinkedIntList class

Slide 4

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 5

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 6

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 7

A Better Linked List Queue

At the beginning of this topic, we discussed how to build a queue with a linked list. We had the back as the first element in the list, and the front as the second element. This led to O(1) behavior for enqueue, and O(n) behavior for dequeue. We can do better!
If we hold a pointer to the front and to the back, and we make the front the first element in the list, and the back the last element in the list, we can successfully make a queue with O(1) behavior for both enqueue and dequeue.
Here is the code, then we'll walk through some examples:
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;
}

Slide 8

A LinkedIntList class

Let's create a full LinkedIntList class
- We should keep a private pointer to its front node
- We will write functions to add, insert, and remove from the list
- We need to properly traverse the list
LinkedIntList.h:

// Represents a linked list of integers.
#pragma once
#include<ostream>

using namespace std;

struct ListNode {
    int data;
    ListNode* next;
    ListNode(int value) { // constructor
        data = value;
        next = nullptr;
};

class LinkedIntList { 
public:
    LinkedIntList(); 
    ~LinkedIntList();
    void addBack(int value); 
    void addFront(int value); 
    void clear();
    int get(int index);
    void insert(int index, int value); 
    bool isEmpty();
    void remove(int index);
    void set(int index, int value); 
    int size();
private:
    ListNode* _front; // null if empty
};

The ListNode definition is a bit different than what we've seen before.
- It has a constructor which sets the value for us. We create a new ListNode using dynamic memory like this:
```
ListNode* node = new ListNode(value);
```
It looks like this in memory:
Why are there two separate objects in the diagram above?
- The ListNode* node is a variable that is simply a pointer.
- The value / next box is the memory that has been allocated for the ListNode object.
- node points to the object in memory
The constructor for the ListNode class looks like this (pretty simple):
```
_front = nullptr;
```

Slide 9

Adding to the front of a linked list

This should look familiar, from the stack above:

void ListNode::addFront(int value)
{
    ListNode* newNode = new ListNode(value);
    newNode->next = _front;
    _front = newNode;
}

If we are adding to the front of an empty list (ex. list.addFront(42)), this is what it looks like. We start with _front pointing to nullptr:
Next, we create a new ListNode and a pointer, newNode that points to it:
We point the next of the new node to _front (which is also nullptr), and then we point _front to the new node. That's it!
When the function returns, we have a single node in our linked list:
If we want to list.addFront(84), we repeat the process from above, but now the new node gets added before the 42:
We first change newNode's next pointer to point to where _front points to:
Then we change _front to point to newNode:
After the function ends, we have a two-node list:

Slide 10

Adding to the back of a linked list

If we want to add to the back of a linked list, and we don't have an explicit _back pointer, we must traverse the entire list to get to the back. This requires a traversal idiom that is common for linked lists. Here is the code for addBack:

void LinkedIntList::addBack(int value)
{
    ListNode* newNode = new ListNode(value);
  
    if (_front == nullptr) {
        _front = newNode;
    } else {
        ListNode* curr = _front;
        while (curr->next != nullptr) {
            curr = curr->next;
        }
        // at this point, we're at the back
        curr->next = newNode;
    }
}

First, we create a new ListNode
If we are adding to the back of an empty list, this is a special case (handled by the if statement).

The interesting part is the traversal:

ListNode* curr = _front;
while (curr->next != nullptr) {
    curr = curr->next;
}
// at this point, we're at the back
curr->next = newNode;

Let's look at this specifically with a three-node list from before:
First, we create a curr pointer that points to the current node, and we set curr to point at the first node, via _front:
Now, we start traversing the list in a while loop, checking if curr->next != nullptr.
- We update curr at each iteration with curr = curr->next. This may seem like strange syntax, but it is just assigning pointer values. We keep iterating until we have reached the last node. In the first iteration:
After the second iteration:
Now, we are at the end of the list, and we can append our new node with curr->next = n;:
After the function ends, this is our list:

Slide 11

Removing at an index

Sometimes, you have to traverse but stop before the node you want to do somthing with.
For example, the LinkedList::remove(int index) function needs to insert at a particular index, which is before the node we actually want to remove

If we stopped on the index, we would be too late, and would not have access to the pointer we need to rewire . Here is the code:

void LinkedIntList::remove(int index)
{
    // similar to insert, we need to find the node before
    // the one we want to remove
    // assumes that 0 <= index < size
    ListNode* temp;
    if (index == 0) {
        temp = _front;
        _front = _front->next;
    } else {
        ListNode* curr = _front;
  
        for (int i = 0; i < index - 1; i++) {
            temp = curr;
            curr = curr->next;
        }
        temp = curr->next;
        curr->next = curr->next->next;
    }
    delete temp;
}

Let's say we want to remove the node at index 2, or list.remove(2). Initially:
After one iteration:
This is where we stop, and start rewiring. First, we set a temp to the node we want to remove (because we want to call delete on it). temp = curr->next:
Then, we point our current pointer's next to the next of the next! curr->next = curr->next->next:
Finally, we call delete on temp to clean it up:
After the function returns, this is the list we have: