Basic Operations on Lists

ELEC 278: Fundamentals of Information Structures

Nick Mertin

Department of Electrical and Computer Engineering, Queen’s University

September 11, 2023

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 1 / 17
 Basic Operations

1 Basic Operations
Overview
Insertion
Removal

2 More Complex Operations

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 2 / 17
 Basic Operations Overview

What can we do with a list?

Last lecture we saw appending an element and removing the first

element.
What other operations do we need to be able to perform on a list for
it to be useful in practical applications?

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 3 / 17
 Basic Operations Overview

What can we do with a list?

Last lecture we saw appending an element and removing the first

element.
What other operations do we need to be able to perform on a list for
it to be useful in practical applications?
Insert at an arbitrary location.

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 3 / 17
 Basic Operations Overview

What can we do with a list?

Last lecture we saw appending an element and removing the first

element.
What other operations do we need to be able to perform on a list for
it to be useful in practical applications?
Insert at an arbitrary location.
Remove from an arbitrary location.

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 3 / 17
 Basic Operations Overview

What can we do with a list?

Last lecture we saw appending an element and removing the first

element.
What other operations do we need to be able to perform on a list for
it to be useful in practical applications?
Insert at an arbitrary location.
Remove from an arbitrary location.
Update the value at an arbitrary location.

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 3 / 17
 Basic Operations Overview

What can we do with a list?

Last lecture we saw appending an element and removing the first

element.
What other operations do we need to be able to perform on a list for
it to be useful in practical applications?
Insert at an arbitrary location.
Remove from an arbitrary location.
Update the value at an arbitrary location.
Find the location of an element.

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 3 / 17
 Basic Operations Overview

Operations on Linked Lists

We will show how we can implement each of these operations on

linked lists.
One of the challenges of linked lists is how we navigate them.
Remember: all we can do is read or write the contents of a box
(memory location) whose number (address) we know.

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 4 / 17
 Basic Operations Insertion

Inserting into a Linked List

Recall that a singly linked list consists of several connected nodes.

Each node has a value and a pointer to the next node.
To store the list in a variable, we store the pointer to the first node.
How would we insert an element at a set position in the list (e.g., 5)?

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 5 / 17
 Basic Operations Insertion

Example

Suppose we have a linked list containing: 3, 5, 9, -10, 0, 14

After inserting 23 at position 5:

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 6 / 17
 Basic Operations Insertion

Example

Suppose we have a linked list containing: 3, 5, 9, -10, 0, 14

After inserting 23 at position 5: 3, 5, 9, -10, 0, 23, 14
To accomplish this:

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 6 / 17
 Basic Operations Insertion

Example

Suppose we have a linked list containing: 3, 5, 9, -10, 0, 14

After inserting 23 at position 5: 3, 5, 9, -10, 0, 23, 14
To accomplish this:
1 Allocate a new node containing the new value.
2 Find the box which contains the pointer to the 5th node.
3 Store the pointer to the current 5th node in the “next” box of the new
node.
4 Store the pointer to the new node in that box.

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 6 / 17
 Basic Operations Insertion

Attempted Implementation

// Inserts a number at a given index in a list.

void insert_at(list *nums, size_t index, int num) {
// Construct a new node to splice into the list.
struct list_node *new_node = malloc(sizeof(struct list_node));
new_node->value = num;

// Traverse the list until we get to the desired index.

for (size_t i = 0; i < index; i++)
nums = &(*nums)->tail;

// 'nums' now points to the 'tail' slot where we need to insert the node.
new_node->tail = *nums;
*nums = new_node;
}

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 7 / 17
 Basic Operations Insertion

Attempted Implementation

// Inserts a number at a given index in a list.

void insert_at(list *nums, size_t index, int num) {
// Construct a new node to splice into the list.
struct list_node *new_node = malloc(sizeof(struct list_node));
new_node->value = num;

// Traverse the list until we get to the desired index.

for (size_t i = 0; i < index; i++)
nums = &(*nums)->tail;

// 'nums' now points to the 'tail' slot where we need to insert the node.
new_node->tail = *nums;
*nums = new_node;
}

What if the list is too short?

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 7 / 17
 Basic Operations Insertion

Revised Implementation

// Inserts a number at a given index in a list.

// Returns false if it was not possible (i.e., list was too short).
bool insert_at(list *nums, size_t index, int num) {
// Traverse the list until we get to the desired index.
for (size_t i = 0; i < index; i++) {
if (*nums == NULL)
return false;
nums = &(*nums)->tail;
}

// Construct a new node to splice into the list.

struct list_node *new_node = malloc(sizeof(struct list_node));
new_node->value = num;

// 'nums' now points to the 'tail' slot where we need to insert the node.
new_node->tail = *nums;
*nums = new_node;
return true;
}

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 8 / 17
 Basic Operations Removal

Removing from a Linked List

Conceptually, how do we modify our approach so it removes the

element at the given position instead of inserting it?

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 9 / 17
 Basic Operations Removal

Removing from a Linked List

Conceptually, how do we modify our approach so it removes the

element at the given position instead of inserting it?
1 Find the box which contains the pointer to the target node.
2 Copy the tail pointer of the target node to that box.
3 Free the target node.

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 9 / 17
 Basic Operations Removal

Removing from a Linked List

Conceptually, how do we modify our approach so it removes the

element at the given position instead of inserting it?
1 Find the box which contains the pointer to the target node.
2 Copy the tail pointer of the target node to that box.
3 Free the target node.
We still need to gracefully handle lists that are too short.

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 9 / 17
 Basic Operations Removal

Implementation

// Remove the element at a given index in a list.

// Returns false if it was not possible (i.e., list was too short).
bool remove_at(list *nums, size_t index) {
// Traverse the list until we get to the desired index.
for (size_t i = 0; i < index; i++) {
if (*nums == NULL)
return false;
nums = &(*nums)->tail;
}

// Make sure the node there exists.

if (*nums == NULL)
return false;

// 'nums' now points to the 'tail' slot where we need to remove the node.
struct list_node *old_node = *nums;
*nums = old_node->tail;
free(old_node);
return true;
}

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 10 / 17
 More Complex Operations

1 Basic Operations

2 More Complex Operations

Search
Update
Looking Forward

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 11 / 17
 More Complex Operations Search

How do we know where to insert or remove?

These algorithms take an index to indicate where to insert or which

element to remove.
What if we only know the value we wish to remove, or some similar
indication of where we want to insert (e.g., “insert 23 before the 14”).

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 12 / 17
 More Complex Operations Search

How do we know where to insert or remove?

These algorithms take an index to indicate where to insert or which

element to remove.
What if we only know the value we wish to remove, or some similar
indication of where we want to insert (e.g., “insert 23 before the 14”).
Many of these problems can be solved by introducing another
algorithm to search the list for a target value, returning its index.
Then, we can combine that with insert_at or remove_at to get a
more sophisticated algorithm.

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 12 / 17
 More Complex Operations Search

Searching for a known value

Idea: go through each node, one by one, incrementing our index as

we go.
Once we find the target value, we return that index.
If we don’t find the target value (i.e., we reach the end of the list), we
need a way to indicate that.

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 13 / 17
 More Complex Operations Search

Implementation

// Finds the index of a given value in a list.

// Returns false if the value is not present in the list.
bool index_of(list nums, int target, size_t *out) {
// Traverse the list until we see the target value.
for (size_t i = 0; nums != NULL; i++) {
if (nums->value == target) {
*out = i;
return true;
}
nums = nums->tail;
}

// We've reached the end of the list without finding the target value.
return false;
}

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 14 / 17
 More Complex Operations Update

What if we want to modify/replace an element?

We could remove and then insert.

We could also create an algorithm which modifies it in-place.

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 15 / 17
 More Complex Operations Update

Implementation

// Replaces the value at the given index in a list.

// Returns false if the value is not present in the list.
bool replace_at(list nums, size_t index, int new_num) {
// Traverse the list until we get to the desired index.
for (size_t i = 0; i < index; i++) {
if (nums == NULL)
return false;
nums = nums->tail;
}

// Make sure the node there exists.

if (nums == NULL)
return false;

// 'nums' now points to the node we need to change the value of.
nums->value = new_num;
return true;
}

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 16 / 17
 More Complex Operations Looking Forward

For Next Class

We are repeating ourselves a lot with our current approach to

developing algorithms for linked lists.

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 17 / 17
 More Complex Operations Looking Forward

For Next Class

We are repeating ourselves a lot with our current approach to

developing algorithms for linked lists.
The resulting algorithms are also somewhat inefficient in practice.
We traverse the list to find the index of a node, then we traverse the
list again using the index to manipulate the node.
If we were to build more complex algorithms out of these building
blocks, this would happen all over the place.

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 17 / 17
 More Complex Operations Looking Forward

For Next Class

We are repeating ourselves a lot with our current approach to

developing algorithms for linked lists.
The resulting algorithms are also somewhat inefficient in practice.
We traverse the list to find the index of a node, then we traverse the
list again using the index to manipulate the node.
If we were to build more complex algorithms out of these building
blocks, this would happen all over the place.
How can we create a more efficient approach to working with linked
lists?

Nick Mertin (Queen’s ECE) Basic Operations on Lists September 11, 2023 17 / 17