Using pseudocode

The six basic actions to take on lists are pretty straightforward. Here are examples of each action in pseudocode:

Create a list:

• List listName

  List listName = (item1, item2, …)

• Example:

  List classmates

  List classmates = ("Sarah", "Camille", "Steve", "Rebecca")

  List classmates = ("Sarah")

Add items to a list:

• listName.add(item)

• Example:

  List classmates = ("Sarah")

  classmates.add("Luke")

• Result:

  classmates = ("Sarah", "Luke")

When adding an item to a list, the item that you’re adding gets added to the end of the list.

Remove items from a list:

• listName.remove(item)

  listName.remove(position)

• Example:

  List classmates = ("Sarah", "Camille", "Steve", "Rebecca")

  classmates.remove("Camille")

• Result:

  classmates = ("Sarah", "Steve", "Rebecca")

• Example:

  List classmates = ("Sarah", "Camille", "Steve", "Rebecca")

  classmates.remove(3)

• Result:

  classmates = ("Sarah", "Camille", "Rebecca")

Get the size of a list:

• listName.size

• Example:

  List classmates = ("Sarah", "Camille", "Steve", "Rebecca")

  int size = classmates.size

Get an item or position in a list:

• listName.get(position)

  listName.getPositionOf(item)

• Example:

  List classmates = ("Sarah", "Camille", "Steve", "Rebecca")

  String name = classmates.get(2)

  int position = classmates.getPositionOf("Sarah")

Iterate through a list:

• for(item in list)

  item.performAction

• Example:

  List classmates = ("Sarah", "Camille", "Steve", "Rebecca")

  for(classmate in classmates)

  print "Hi " + classmate

Using Scratch

Scratch makes using lists really easy and straightforward! The following sections offer examples of the six basic interactions with lists in Scratch.

Creating a list

Figure 11-2 shows how to create a list in Scratch. Select Make a List under the Data category and give your list a name.

After you create the list, you see a lot of new blocks for your list, as shown in Figure 11-3, as well as the list being displayed on the stage.

Adding items to a list

Figure 11-4 shows how to add four names to the “classmates” list in Scratch. The list on the stage shows what it looks like after the green flag has been pressed.

Removing items from a list

Figure 11-5 shows how to remove one name from the “classmates” list in Scratch. Notice that you can specify removing the first item, the last item, or all the items from the list. You can also specify a specific position to remove by typing any other number instead of using the drop-down list. The list on the stage shows what it looks like after the green flag has been pressed.

Getting the size of a list

Figure 11-6 shows how to get the size of the “classmates” list in Scratch. The list on the stage shows what it looks like after the green flag has been pressed.

Getting an item at a position in a list

Figure 11-7 shows how to get an item from a certain position from the “classmates” list in Scratch. Notice that you can specify getting the first item, the last item, or a random item from the list. You can also specify any other position by typing the number instead of using the drop-down list. The list on the stage shows what it looks like after the green flag has been pressed.

Iterating through a list

To iterate through a list in Scratch, you have to use a loop. Figure 11-8 shows an example of a program that says Hello to each person in the classmates list.

Using Java

Java has a List class that makes the six basic list operations fairly simple to use in your code. The only thing is that you have to import the List library into your program first. For more on code libraries, check out Chapter 8.

Each example in this section should be surrounded by the basic Java main class, and in this case you need to import the necessary libraries. If you want to test the examples in this section, make sure you create a file called Lists.java in your favorite IDE (see Chapter 3 for more information on coding environments for Java). Your Lists.java file should have the following code:

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

public class Lists

{

  public static void main(String [] args)

  {

    // INSERT EXAMPLE CODE HERE

//You can use this line to print the list to see it

System.out.println(listName);

  }

}

Java also has a generic List class, which you can learn all about on the Java documentation site for lists at https://docs.oracle.com/javase/8/docs/api/java/util/List.html. When you actually create a list, however, you might have to specify what type of list. In this chapter, you see examples of array lists, which are simple lists.

Unlike the pseudocode examples in this book and Scratch, Java (and other text-based languages like Python and JavaScript) start numbering positions in lists at 0. This makes sense if you think about it from a place-value point of view. The first ten numbers are: 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9 — all numbers in the place value for One. This can cause a lot of confusion for young coders when working with lists because it can cause off-by-one errors. An example of an off-by-one error is when the coder thinks they're getting the first item in the list, but used 1 as the position instead of 0. You find more about fixing off-by-one errors in Chapter 13.

Java is a strongly typed language. This means that when working with lists in Java, you have to specify what type the data is inside the list. To specify this, you have to put <Type> next to the declaration of a list. You see this throughout the examples in this section.

Create a list:

• List<Type> listName = new ArrayList<Type>();

  List<Type> listName = Arrays.asList(item1, item2, …);

• Example:

  List<String> classmates = new ArrayList<String>();

  List<String> classmates = Arrays.asList("Sarah", "Camille", "Steve", "Rebecca");

  List<String> classmates = Arrays.asList("Sarah");

Add items to a list:

• listName.add(item);

  listName.add(position, item);

• Example:

  List<String> classmates = new ArrayList<String>();

  classmates.add("Sarah");

  classmates.add("Luke");

  classmates.add(1, "Camille");

• Result:

  classmates = ("Sarah", "Camille", "Luke")

When adding an item to a list, you can either add to the end of the list or at a specific position in the list.

Remove items from a list:

• listName.remove(item);

  listName.remove(position);

• Example:

  List<String> classmates = new ArrayList<String>();

  classmates.add("Sarah");

  classmates.add("Luke");

  classmates.add(1, "Camille");

  classmates.remove("Camille");

• Result:

  classmates = ("Sarah", "Luke")

• Example:

  List<String> classmates = new ArrayList<String>();

  classmates.add("Sarah");

  classmates.add("Luke");

  classmates.add(1, "Camille");

  classmates.remove(2);

• Result:

  classmates = ("Sarah", "Camille")

Get the size of a list:

• listName.size();

• Example:

  List<String> classmates = new ArrayList<String>();

  classmates.add("Sarah");

  classmates.add("Luke");

  classmates.add(1, "Camille");

  int size = classmates.size();

• Result:

  size = 3

Get an item or position in a list:

• listName.get(position);

  listName.indexOf(item);

• Examples:

  List<String> classmates = new ArrayList<String>();

  classmates.add("Sarah");

  classmates.add("Luke");

  classmates.add(1, "Camille");

  String name = classmates.get(2);

  int position = classmates.indexOf("Sarah");

• Result:

  name = Luke

  position = 0

Iterate through a list:

• for(indexName = startIndex; condition; iterationAmount)

  {

  listName.get(indexName);

  }

• Example:

  List<String> classmates = new ArrayList<String>();

  classmates.add("Sarah");

  classmates.add("Luke");

  classmates.add(1, "Camille");

  for(int position = 0; position < classmates.size(); position++)

  {

    System.out.println(“Hi “ + classmates.get(position));

  }

• Example:

  List<String> classmates = new ArrayList<String>();

  classmates.add("Sarah");

  classmates.add("Luke");

  classmates.add(1, "Camille");

  for(String classmate : classmates)

  {

    System.out.println(“Hi “ + classmate);

  }

• Result (same for both iteration examples):

  Hi Sarah

  Hi Camille

  Hi Luke

Selection sort: An easy sorting algorithm

Though many sorting algorithms get used fairly often in coding, one of the most common ones is called selection sort. If you did the unplugged activity of this chapter with your young coder, you might have stumbled upon this algorithm. Basically, in selection sort, you search the entire list for the next smallest item.

Here’s how the selection sort works:

1. Iterate through the list until you have found the smallest item and swap it with the first item.
2. Iterate through the list starting at the second item, find the smallest item in the list, and swap it with the second item.
3. Iterate through the list starting at the third item, find the smallest item in the list, and swap it with the third item.
4. Repeat moving your start position and finding the smallest item in the list until your start position is the final item in the list.

Common application: Arranging numbers in order

This section shows how to implement the selection sort algorithm in Java on a list of integer numbers.

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

public class sort

{

  public static void main(String [] args)

  {

    List<Integer> numbers = Arrays.asList(6, 8, 3, 4, 5, 10, 13, 22, 9, 21);

    System.out.println("Unordered: " + numbers);

    for (int startPosition = 0; startPosition < numbers.size(); startPosition++)

    {

      int positionOfSmallest = startPosition;

      for (int iterator = startPosition + 1; iterator < numbers.size(); iterator++)

      {

        if (numbers.get(iterator) < numbers.get(positionOfSmallest))

        {

          positionOfSmallest = iterator;

        }

      }

      int smallestNumber = numbers.get(positionOfSmallest);

      numbers.set(positionOfSmallest, numbers.get(startPosition));

      numbers.set(startPosition, smallestNumber);

    }

    System.out.println("Ordered: " + numbers);

  }

}

A challenge for you and your coder is to follow the steps in the Java code and make the comparisons in the list yourself. Figure 11-9 shows one way of tracing the code. It’s a little tedious, but basically you match each line of code to making a change to variables on your paper. Then you can make sure you and your coder truly understand why this code matches the algorithm!

Linear versus binary searching algorithms

When it comes to lists, linear search is pretty straightforward. Essentially you start at the beginning of the list, and check to see if the first item is the item you’re looking for. If it is, you’re done! If it isn’t, you move to the next item in the list. And you repeat this sequence until you’ve either found your item, or you’ve reached the end of the list and know that your item isn’t in the list.

Binary searching is a little more complicated than linear searching. Luckily, you’ve probably already used the binary search algorithm in your everyday life though. For example, when you’re looking for the word “Search” in a dictionary, you probably don’t read each word in order until you get to the word “Search.” Instead, you flip to the middle of the dictionary and check to see whether the word “Search” comes before the page you opened, or after. You know this because the dictionary is in alphabetical order! If “Search” comes after the page you’re on, you flip to a page to the right and repeat the process until you end up on the right page.

This is called binary search, also known as “divide and conquer.” When writing the code for this type of search, you literally go to the middle of the list, and then the middle of the side that you know the word is on; each time dividing your search space by half. In your everyday life you might not be exactly at half, but it’s close enough to still call it a binary search.

The only caveat to binary search is that the list must be sorted for the sorting to work. A linear search implementation doesn’t require your list to be sorted before searching.

Common application: Finding a phone number

In this section we include the code for finding a phone number in a list of names that are ordered alphabetically. This code is written in Java and, because the names are sorted but the phone numbers are not, this implementation uses the linear search algorithm.

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

import java.util.Scanner;

public class sort2

{

  public static void main(String [] args)

  {

    Person sarah = new Person("Sarah", "555-7765");

    Person camille = new Person("Camille", "555-9834");

    Person steve = new Person("Steve", "555-2346");

    Person rebecca = new Person("Rebecca", "555-1268");

    List<Person> directory = Arrays.asList(sarah, camille, steve, rebecca);

    Scanner scanner = new Scanner(System.in);

    System.out.println("Please enter the phone number so I can tell you the name: ");

    String number = scanner.nextLine();

    String nameFound = "";

    for(int index = 0; index < directory.size(); index++)

    {

      Person personInDirectory = directory.get(index);

      String numberInDirectory = personInDirectory.getNumber();

      if(numberInDirectory.equals(number))

      {

        nameFound = personInDirectory.getName();

        break;

      }

    }

    if(nameFound.equals(""))

    {

      System.out.println("Sorry, the number you are looking for does not belong to anyone in this directory");

    }

    else

    {

      System.out.println("The number " + number + " belongs to " + nameFound);

    }

  }

}

This code relies on another class in a file called Person.java. The code for this file is:

public class Person

{

  String name;

  String number;

  public Person(String p_name, String p_number)

  {

    name = p_name;

    number = p_number;

  }

  public String getName()

  {

    return name;

  }

  public String getNumber()

  {

    return number;

  }

}