Concepts / Searching a List with Linear Search

Searching a List with Linear Search

The List interface extends Collection and adds methods that act on items by numerical position.

  • Programming

A Position Question You Can Predict

Suppose you have a list holding three names, Ann, Ben, and Cal, and you ask for the item at position 3. Your first instinct may be to count from one, so that position 3 means the third name, Cal. That instinct is common among new programmers, and it does not match how List methods are defined. This article follows one idea from start to finish: how positions in a list are numbered, and how the five positional methods get, set, add, remove, and indexOf behave once that numbering is clear.

What do you think happens?

For the list [Ann, Ben, Cal], what happens when you call get(3)?

  • It returns Cal

  • It returns null

  • It throws an IndexOutOfBoundsException

Reveal answer
Answer:

It throws an IndexOutOfBoundsException

Positions in a list are numbered starting at 0, so a list of three items has valid indices 0, 1, and 2. Index 3 is outside that range, so get(3) fails. The first item is at index 0, not index 1.

How List Extends Collection

Every list implements the methods of the Collection interface. These include size(), isEmpty(), add(T), remove(Object), and clear(). Those methods work on the collection as a whole. The List interface extends Collection and adds a second kind of access: finding and changing items by their numerical position in the list.

Think of Collection as the general promise that a group of items can be counted, added to, and emptied. List keeps that promise and adds the idea of order: each item has a place, and you can name that place with a number. The methods the List interface provides, such as get, set, add, remove, and indexOf, each either take a position, called an index, or return one. Once you know the numbering rule, the behavior of all five methods becomes much easier to predict.

Counting Positions from Zero

Items in a list are numbered 0, 1, 2, and so on, up to list.size() minus 1. The first item is at index 0. The last item is at index list.size() minus 1, not at index list.size(). For a list with five items, the valid indices are 0 through 4. The index equal to the size is not a valid position for an existing item, which is why using it with get, set, or remove causes an exception.

Index 0AnnIndex 1BenIndex 2CalIndex 3DeeIndex 4Eve
Which positions are valid for a list of five elements, and what does position 3 refer to?

In the diagram, position 3 refers to the fourth item, Dee, because counting starts at zero. The valid range for get, set, and remove is always 0 through size minus 1. Knowing the size tells you exactly where the valid range ends.

Tracing Set, Remove, and Add

The three methods that change a list each behave differently. The set method stores a new object at a position, replacing the object that was there, and it does not change the number of elements or move any other element. The remove method removes the object at a position, shifts later items one position toward the front, decreases the size by one, and returns the removed object. The add method inserts an object at a position, shifts later items one position toward the end, and increases the size by one.

Before
names = [Ann, Ben, Cal, Dee]
names.remove(1)

Four items, Ben at index 1

After
names = [Ann, Cal, Dee]

Three items, Cal and Dee moved one position toward the front

Annindex 0Annindex 0Benindex 1, removedCalindex 1, moved from 2Calindex 2Deeindex 2, moved from 3Deeindex 3
After calling remove(1), which elements move to new indices and what does the list look like afterward?

The before and after views show the key effect of remove. Ben is gone, so Cal and Dee each slide one position toward the front. Cal's index changes from 2 to 1, and Dee's index changes from 3 to 2. The removed object is also returned to the caller, which the list itself does not keep.

When Add Accepts the Size

The range for add is different from the range for get, set, and remove. For add(index, obj), the index must be in the range 0 to list.size(), inclusive. The extra position at list.size() is allowed because it is the position just past the last item. If the index equals list.size(), the object is added at the end of the list. This is the one positional method that accepts the size as a valid index, and it explains why adding at the end is safe even though get at the same position would fail.

Finding a Position with indexOf

The indexOf method works in the opposite direction from the other four. It takes an object rather than a position, and it returns the position of the first occurrence of that object, or -1 if the object does not appear in the list. Because it reports the first occurrence, it must examine positions from the front of the list and stop at the first match. This one-position-at-a-time examination from front to back is the linear search the title refers to.

index 0: Annnot Cal, continueindex 1: Bennot Cal, continueindex 2: Calmatch, return 2next positionnext position
In what order does indexOf check each position, and at which point does it stop and return an index?
Code walkthrough
import java.util.ArrayList;
import java.util.List;

List<String> names = new ArrayList<>();
names.add("Ann");
names.add("Ben");
names.add("Cal");
names.add("Dee");
names.add("Eve");

System.out.println(names.get(3));
System.out.println(names.indexOf("Cal"));
System.out.println(names.indexOf("Zed"));

names.remove(1);
System.out.println(names);
System.out.println(names.indexOf("Dee"));

names.set(0, "Amy");
System.out.println(names);

names.add(4, "Fay");
System.out.println(names);

names.get(5);
  1. 1
    The list is built with five names, so its size is 5 and its valid indices are 0 through 4.
  2. 2
    get(3) reads the position numbered 3, which is the fourth name, Dee.
  3. 3
    indexOf("Cal") examines positions from the front and stops at index 2, the first match.
  4. 4
    indexOf("Zed") never finds a match, so it returns -1.
  5. 5
    remove(1) removes Ben, shifts Cal and Dee and Eve forward, and leaves a list of size 4.
  6. 6
    indexOf("Dee") now returns 2 because Dee moved from index 3 to index 2.
  7. 7
    set(0, "Amy") overwrites Ann at index 0 without changing the size, which stays 4.
  8. 8
    add(4, "Fay") appends at index equal to the size, which is allowed for add, and the size becomes 5.
  9. 9
    get(5) asks for a position past the last valid index, 4, so Java throws IndexOutOfBoundsException.
  • get(3) returns the fourth item because positions start at 0
  • indexOf returns the first matching position, 2 for Cal
  • indexOf returns -1 because Zed is not in the list
  • remove(1) deletes Ben and shifts later items toward the front
  • set(0, Amy) replaces Ann and leaves the size unchanged
  • add(4, Fay) is valid because the size is 4 at that moment
  • get(5) fails because the list now has size 5, so valid indices are 0 through 4
Output
Dee
2
-1
[Ann, Cal, Dee, Eve]
2
[Amy, Cal, Dee, Eve]
[Amy, Cal, Dee, Eve, Fay]
(the final get(5) call throws an IndexOutOfBoundsException and stops the program)

Mistakes Beginners Make with Positions

  • Common mistake

    Assuming the first item is at index 1

    What it looks like

    For [Ann, Ben, Cal], calling get(1) expecting Cal

    Why it fails

    Positions are numbered from 0, so index 1 holds Ben and the first item is at index 0

    Do this instead

    Use get(0) for the first item and get(size() minus 1) for the last

  • Common mistake

    Using size() as the last valid index for get

    What it looks like

    For a list of five items, calling get(5)

    Why it fails

    The last valid index is size() minus 1, which is 4, so index 5 is out of range

    Do this instead

    Use indices from 0 through size() minus 1 with get, set, and remove

  • Common mistake

    Expecting set to change the size or shift items

    What it looks like

    Calling set(1, x) and expecting the list to grow or the other items to move

    Why it fails

    set replaces one object and does not change the number of elements or move any other element

    Do this instead

    Use add or remove when you need to insert or delete and shift positions

  • Common mistake

    Treating indexOf as a position lookup

    What it looks like

    Calling indexOf(2) on a list of strings and expecting the item at position 2

    Why it fails

    indexOf takes an object and returns its position, or -1 if it is absent

    Do this instead

    Use get(2) to read position 2, and use indexOf("Cal") to find where Cal is

  • Common mistake

    Forgetting that remove shifts later items, so later indices change after each removal

Predict the Result of a Sequence

MEDIUM

Start with the list [Ann, Ben, Cal, Dee]. Work out the final contents after these calls in order: remove(1), then set(0, Zoe), then add(3, Eli). Then state what indexOf("Dee") returns and whether get(4) would succeed.

Hints
  • After remove(1), the size is 3, so the valid indices are 0 through 2
  • set changes one item in place and does not shift any items
  • add at index equal to the current size appends to the end

Key Takeaways

  • A List extends Collection and adds methods that act on items by numerical position, starting from index 0.
  • For a list of size n, the valid indices for get, set, and remove run from 0 to n minus 1, so the last item is at n minus 1.
  • add accepts an index from 0 through size inclusive, appending at the end when the index equals size, while get, set, and remove do not.
  • set replaces without changing size, add inserts and shifts later items toward the end, and remove deletes, shifts later items toward the front, and returns the removed object.
  • indexOf takes an object and returns the position of its first occurrence, or -1 if it is absent, examining positions from the front to find that match.

Related Topics