3.10 Lists Lesson

How to use lessons

Lessons will guide you through each concept using questions.

It is vital to try your best at each question, even if they are difficult. The only way to build understanding and remember things is to actively interact with the concepts, so do not guess answers unless as a last resort.

Read everything that is shown to you and do not skip any text sections. Everything has a purpose and will further your understanding.

Click continue to continue to the next section.

Imagine you are shopping online for your favorite item. Hundreds of stores sell the same item, but all of them sell for different prices. You want to find the store that sells for the lowest price.

Manually going through all the stores would take hours, so you create an algorithm that can quickly find the cheapest store.

store1 ← price1
store2 ← price2
store3 ← price3

You create another variable store4 ← price4.

As you just figured out, you would need \(2n - 1\) variables and IF statements to find the cheapest of \(n\) stores. If you had 100 stores to choose from, you would need 199 variables and IF statements!

Not only can the number of variables and IF statements get out of control, but you would also need to recreate the algorithm for every specific number of stores!

Clearly, this can get very unmanagable, so programmers created a structure called lists.

A list is like a sequence of cubbyholes put in a straight line. Each cubbyhole is called an element and has a sticky-note containing a number attached to it, which is called its index. The first cubbyhole in this sequence has an index of 1, the second has an index of 2, the third has 3, and so on. This index is like the cubbyhole's address. Each cubbyhole can also store things like a stack of papers, which is called its value.

This sequence of cubbyholes is also mutable. New cubbyholes can be added and others can be removed. Cubbyholes can also be inserted between other cubbyholes.

A list is created in pseudocode using square brackets []. Brackets without anything inside them create an empty list with no elements inside. Brackets with values inside them like [value1, value2, value3] create a list with values. value1 is stored at index 1, value2 is stored at index 2, and so on in this bracket notation.

An element in a list can be retrieved by its index. list[index] is pseudocode for retrieving an element stored at index. In pseudocode, the first element of a list has index 1.

An element's value can be replaced by another value. list[index] ← value is pseudocode for replacing the value stored in the element located at index with value.

Let's get some practice with this before moving on to other ways to use lists.

list1 ← [1, 4, 0, 29, 2]
list2 ← [23, 0, 8, 9, 9]
element ← list2[list1[5]]
list1[element + 1] ← list2[element + list1[2]]
            

There are also other list operations.

• LENGTH(list)
  • Returns the number of elements in list.
• FOR EACH value IN list {}
  • Iterates through every element in list from start to finish, assigning value to the value of an element in list each iteration.
• INSERT(list, index, value)
  • Shifts all elements with an index greater than or equal to index up 1 index and sets the element located at index to a value of value.
• APPEND(list, value)
  • Adds value to the end of list.
• REMOVE(list, index)
  • Removes the element located at index and shifts all elements after that index down 1.

Let's get some practice with these concepts.

list1 ← [1, 4, 0, 29, 2]
list2 ← [23, 0, 8, 9, 9]
FOR EACH number IN list1
{
    APPEND(list2, number)
    REMOVE(list2, 1)
}
INSERT(list2, 3, 4);
x ← 0
FOR EACH number IN list2
{
    x ← x + number
}
x ← x / LENGTH(list2)

Let's go back to the original problem of creating an algorithm to find the cheapest store out of a number of stores.

You put each store's price in a list storePrices. The price at index 1 is the price for store1, the price at index 2 is the price for store2, and so on.

You make the algorithm below to find the cheapest price in storePrices, but it's missing a piece.

storePrices ← [price1, price2, price3, ...]
lowestPrice ← storePrice[1]
FOR EACH price IN storePrices
{
    IF (<MISSING CODE SEGMENT>)
    {
        lowestPrice ← price
    }
}
            

Just by using a list instead of individual variables, the algorithm was reduced to a few lines of code from the possibly hundreds for a large number of stores.

Not only did using a list reduce code length, but it also allowed the algorithm above to work with any number of stores. No matter how many prices storePrices contains, every price in the list is checked thanks to the FOR loop. Without lists, we would've had to recreate the above algorithm for any specific number of stores.

More abstractly, the algorithm you just created above finds the minimum value in a list.

But wait, the algorithm only outputs a price, not the index at which the price is stored! We need to know the price's index so that we know at which store we can find such a price.

The following code shows an algorithm that searches a list for a value and stores that value's index in targetIndex. This is a type of linear search algorithm.

list ← [value1, value2, value3, ...]
targetValue ← someValue
targetIndex ← -1
index ← 1
REPEAT UNTIL(index > LENGTH(list))
{
    IF(list[index] = targetValue)
    {
        targetIndex ← index
        <MISSING CODE SEGMENT>
    }
    index ← index + 1
}

Using these handy-dandy algorithms, you can now find which store sells your favorite item for the lowest price in mere milliseconds. Say goodbye to those days of meticulously comparing prices by hand!