10: Dynamic Data Structures

Advanced Search Quick Index Instructor's Page Home Blackboard Schedule Syllabus Room Policies Help FAQ's How To's Links Español Chinese Japanese Hide Navigation
Edward Parrish © 2002-2006

10: Dynamic Data Structures
What We Will Cover

Reminders:

Please silence all cell phones and pagers

When class is over, please shut down your computer if it is on.

Continuations

10.1: Dynamic Data Structures

10.1.1: About Dynamic Data Structures

10.1.2: Array Lists

10.1.3: Linked Lists

10.1.4: Hash Maps

10.1.5: Primitive Data and Autoboxing

10.1.6: Summary

Exercise 10.1

10.2: Linked Lists

10.2.1: Introduction to Linked Lists

10.2.2: Defining a Node

10.2.3: Making a Simple Linked List

10.2.4: Traversing a List

10.2.5: Adding and Removing Nodes

10.2.6: Working with a Linked List

10.2.7: Summary

Exercise 10.2

10.3: Improving the Linked List

10.3.1: Making the Node an Inner Class

10.3.2: Introduction to Iterators

10.3.3: Defining a List Iterator Class

10.3.4: Deleting Nodes

10.3.5: Inserting Nodes

10.3.6: Working with the Linked List iterator

10.3.7: Summary

Exercise 10.3

Wrap Up

Assignments Due Next: A8-Image Manipulation (4/21/10)
A9-Card Games Redux (4/28/10)

Illuminations

Questions from last class?

Homework Questions?

A8-Image Manipulation (4/21/10)

Homework Discussion Questions

How efficient is PPM file storage, using total file size for the comparison?

What other features would you like to see in the Picture class?

What image file manipulations did people add to the Picture class?

^ top

10.1: Dynamic Data Structures

Learner Outcomes

At the end of the lesson the student will be able to:

Describe in general terms what is a dynamic data structures

Use an ArrayList, LinkedList or HashMap

Explain the terms autoboxing and auto-unboxing

Write code to iterate through list structures

^ top

10.1.1: About Dynamic Data Structures

Data structures are a way to organize data in a program

Arrays are one such data structure we have covered

However, once an array is defined, you cannot change it's size

One could define a new array and copy contents from one array to another

Another solution is to use a dynamic data structure

Dynamic data structures can grow and shrink while the program is running

Several useful types of dynamic data structures include:

Dynamic Arrays (a.k.a. array lists or vectors)

Hash tables (a.k.a. hash maps)

Linked lists

Stacks

Queues

Trees

We will examine some of the data structures that Java provides in its Collections Framework

The textbook has descriptions of the other data structures

Another good source of information is the Java Tutorial Trail on Collections

National Institute of Standards and Technology (NIST) also has a comprehensive Dictionary of Algorithms and Data Structures

Enhanced for Loop
Recall the enhanced for loop we discussed in lesson 6.1.6
Syntax:
for (dataType variableName : listName) {
    // statements to execute
}
Where:

dataType: the data type of all the array items

variableName: the name to use for each variable

listName: the name of the list such as an array
For example:
String[] days = {"Sunday", "Monday", "Tuesday",
    "Wednesday", "Thursday", "Friday", "Saturday"};
for (String dayName : days) {
    System.out.println(dayName);
}
In addition to arrays, the enhanced for loop works with some of the collection types

We will see examples in the following sections
^ top

10.1.2: Array Lists
An ArrayList is a class that uses an array to store its data

The advantage of an ArrayList is that you do not need to specify a size before using it

An ArrayList will grow (and shrink) automatically as you add (or remove) elements

To create an ArrayList, you specify the type of elements inside angle brackets
For instance, to create an ArrayList to store String objects:
ArrayList<String> days = new ArrayList<String>();
To add an element, you use an add() method:
days.add("Tuesday");
days.add("Wednesday");
days.add("Thursday");
To determine the size of the list, you use the size() method
Also, to retrieve an element from the list, you use the get() method:
for (int i = 0; i < days.size(); i++) {
    String day = days.get(i);
    System.out.println(day);
}
Some commonly used constructors and methods are shown below

Also, you can see an example program using an ArrayList
Some Commonly Used Constructors and Methods of the ArrayList<type> Class

Constructor/Method Description

ArrayList() Creates an empty list an initial capacity of ten objects of the specified type.

add(object) Adds the specified object to the end of the list.

add(index, object) Inserts the object at the specified position in the list, shifting any existing elements at that position and later in the list up by one.

clear() Removes all of the items from the list.

get(index) Returns the object at the specified position in the list.

indexOf(objItem) Returns an int value for the index of the first occurrence of the specified object testing with the equals() method; if not found, returns -1.

remove(intIndex) Deletes the item at the specified position, shifting any items at higher indexes down by one.

remove(objItem) Deletes the first occurrence of the item, shifting any items at higher indexes down by one.

set(intIndex, objItem) Replaces the item at the specified index of the list.

size() Returns the number of elements in the list.

Example of Using an ArrayList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.*;

public class ArrayListDemo {
    public static void main(String[] args) {
        ArrayList<String> days = new ArrayList<String>();
        days.add("Unknown");
        days.add("Tuesday");
        days.add("Wednesday");
        days.add("Thursday");
        days.add("Friday");

        System.out.println("The first list");
        for (int i = 0; i < days.size(); i++) {
            System.out.println(days.get(i));
        }

        System.out.println("Adding the missing days...");
        days.add(0, "Sunday"); // add to front
        days.add("Saturday");  // add to end
        days.set(1, "Monday"); // change

        System.out.println("\nNow the list is complete");
        for (String dayName : days) {
            System.out.println(dayName);
        }

        System.out.println("\nRemoving a bad day...");
        int index = days.indexOf("Monday");
        String badDay = days.remove(index);

        System.out.println("\nNo more " + badDay);
        for (String dayName : days) {
            System.out.println(dayName);
        }
    }
}
^ top

10.1.3: Linked Lists

The LinkedList class operates like the ArrayList class

However, it uses a different technique to store its data

Each element of a linked list is stored as a separate object

Also, each list element is stored along with a pointer to the object that precedes it and a pointer to the object that follows it

The linked list can use these pointers to navigate through the list

Advantages and Disadvantages of a Linked List

The elements of a linked list are not stored in an array

Because of this, inserting an element into the middle of a list is more efficient that inserting an element into an array

To insert elements into the middle of an array, you must move all the following elements down the list

The more elements you have on the list, the longer it takes to insert the element

In contrast, you can insert an element into a linked list by simply adjusting the pointers to the surrounding elements

However, there are always trade-offs to this efficiency

Although a linked list can be updated more efficiently, you cannot find a random element in the list as quickly

In an array, you can calculate where to look for any memory element because array elements are stored in adjacent memory locations

By contrast, access to elements of a linked list is generally slower because you must navigate through the list using the pointers

Some commonly used constructors and methods are shown below

Also, you can see an example program using a LinkedList

Some Commonly Used Constructors and Methods of the LinkedList<type> Class

Constructor/Method Description

LinkedList() Creates an empty list.

add(object) Adds the specified object to the end of the list.

add(index, object) Inserts the object at the specified position in the list, shifting any existing elements at that position and later in the list up by one.

clear() Removes all of the items from the list.

get(index) Returns the object at the specified position in the list.

indexOf(objItem) Returns an int value for the index of the first occurrence of the specified object testing with the equals() method; if not found, returns -1.

remove(intIndex) Deletes the item at the specified position, shifting any items at higher indexes down by one.

remove(objItem) Deletes the first occurrence of the item, shifting any items at higher indexes down by one.

set(intIndex, objItem) Replaces the item at the specified index of the list.

size() Returns the number of elements in the list.

Example of Using a LinkedList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.*;

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList<String> days = new LinkedList<String>();
        days.add("Unknown");
        days.add("Tuesday");
        days.add("Wednesday");
        days.add("Thursday");
        days.add("Friday");

        System.out.println("The first list");
        for (int i = 0; i < days.size(); i++) {
            System.out.println(days.get(i));
        }

        System.out.println("Adding the missing days...");
        days.add(0, "Sunday"); // add to front
        days.add("Saturday");  // add to end
        days.set(1, "Monday"); // change

        System.out.println("\nNow the list is complete");
        for (String dayName : days) {
            System.out.println(dayName);
        }

        System.out.println("\nRemoving a bad day...");
        int index = days.indexOf("Monday");
        String badDay = days.remove(index);

        System.out.println("\nNo more " + badDay);
        for (String dayName : days) {
            System.out.println(dayName);
        }
    }
}
^ top

10.1.4: Hash Maps
A map is a collection of values that are associated with a key

A HashMap is like an array, except you can use non-integer values for the keys
Unlike other lists, you specify two types when you declare and instantiate a HashMap
HashMap<Integer, String> days = new HashMap<Integer, String>()
The HashMap also has some different methods than an ArrayList or LinkedList

Some commonly used constructors and methods are shown below

Also, you can see an example program using a HashMap
Some Commonly Used Constructors and Methods of the HashMap<keyType,valueType> Class

Constructor/Method Description

HashMap() Creates an empty map with an initial capacity of 16 entries.

clear() Removes all of the items from the map.

containsKey(key) Returns true if this map contains an entry for the specified key.

entrySet() Returns a set of all entries in the map as Map.Entry objects.

get(key) Returns the value to which the specified key is mapped in this identity hash map, or null if the key is not found.

put(key, value) Adds an entry with the specified key and value, or replaces the value if an entry with the key already exists.

remove(key) Removes the entry with the specified key.

size() Returns the number of entries in the map.

Example of Using a HashMap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.*;

public class HashMapDemo {
    public static void main(String[] args) {
        // Make the HashMap
        HashMap<String, Integer> days =
            new HashMap<String, Integer>();
        days.put("Sunday", 1);
        days.put("Monday", 2);
        days.put("Tuesday", 3);
        days.put("Wednesday", 4);
        days.put("Thursday", 5);
        days.put("Friday", 6);
        days.put("Saturday", 7);

        // Use the HashMap
        System.out.println("The HashMap has "
            + days.size() + " entries");
        Scanner input = new Scanner(System.in);
        String weekDay;
        do {
            System.out.print("Enter the weekday name: ");
            weekDay = input.nextLine();
            if (days.containsKey(weekDay.trim())) {
                int dayNumber = days.get(weekDay);
                System.out.println("The day number for "
                    + weekDay + " is " + dayNumber);
            } else {
                System.out.println("Invalid name");
            }
        } while (!weekDay.trim().equals(""));
        System.out.println("Goodbye");
    }
}
^ top

10.1.5: Primitive Data and Autoboxing

Note that collections can only be used with objects and not primitive types

All classes in Java are extended from Object

Thus, you can use an Object reference to store data for all class types

To store primitive types, you must use a wrapper class

Java has wrapper classes for all the primitive types including:

Character

Double

Integer

Autoboxing and Auto-Unboxing
Before JDK 1.5, inserting a primitive value into a list required you to manually add a wrapper class
For example, to add the number 9 into an ArrayList named intList:
Integer integer = new Integer(9);
intList.add(integer);
To retrieve values, you had to convert the value from the wrapper type
For example, assuming we know the index, we retrieve the previous value with:
Integer intObj = (Integer) intList.get(index);
int value = intObj.intValue();
Starting in Java 1.5, these conversions are handled automatically
For example, to add the number 9 into a list:
intList.add(9);
To retrieve the same value:
int value = intList.get(index);
^ top

10.1.6: Summary
A data structure is an organization of data in a computer's memory

The most basic data structure is the array

While arrays are useful, their size is fixed when they are created

A dynamic data structure is one that can grow and shrink while a program is running

Java has several dynamic data structures you can use instead of an array

We looked at several dynamic data structures including:

ArrayList

HashMap

LinkedList

Dynamic data structures store data as objects

To store primitive types, you use a wrapper class

Since JDK 1.5, Java will automatically convert between primitive types and wrapper classes:

Known as autoboxing and auto-unboxing
You can iterate through a list using a for loop:
System.out.println("Using a for loop:");
for (int i = 0; i < days.size(); i++) {
    System.out.println(days.get(i));
}
Another way to iterate through an array or list is the enhanced for loop:
System.out.println("\nUsing a for-each loop:");
for (String dayName : days) {
    System.out.println(dayName);
}
Check Yourself

What is the most basic list structure in Java?

What is meant by the term "dynamic data structure"?

How do you code an ArrayList that can store double values?

What is the difference between an ArrayList and a LinkedList

What are the advantages and disadvantageous of using a HashMap data type

What is the syntax of a "for-each" loop?

^ top

Exercise 10.1

Take one minute to review the Check Yourself questions. We will review the questions as time permits.

^ top

10.2: Linked Lists

Learner Outcomes

At the end of the lesson the student will be able to:

Generate a self-referential class suitable for a linked list

Traverse a linked list and perform operations on each node

Add and delete nodes from the head of a linked list

^ top

10.2.1: Introduction to Linked Lists

A linked data structure is made up of containers of data and links known as nodes

Data for each node is stored in the data field

Each node is connected to other nodes via their link fields

To design linked data structures, you will find it helpful to draw diagrams

You draw a node as a rectangle and the links between nodes as an arrow:

Linked Lists

The simplest kind of linked data structure is a chain of nodes each connected by a link

This type of structure is known as a linked list

Each node is represented as a rectangular box

Inside the box is a string representing the data

The links are arrows and show that you can traverse the list in one direction only

There is a first node, a second node, and so on to the last node

The start of the list is indicated by the head node

The end of the list has a special end-of-list marker

^ top

10.2.2: Defining a Node

The key to a linked list structure is the node

So let us first define a node in Java

As everything else in Java, a node is a class

Our node class needs private fields for both data and links

In addition, we need to code a constructor for the fields

Example Node Class
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Node {
    private String data;
    private Node link;

    public Node(String newData, Node newLink) {
        setData(newData);
        setLink(newLink);
    }

    public void setData(String newData) {
        data =  newData;
    }

    public String getData() {
        return data;
    }

    public void setLink(Node newLink) {
        link = newLink;
    }

    public Node getLink() {
        return link;
    }
}
Self-Referential Classes
A class like Node above is known as a self-referential class
This is because the class has a reference variable that is an object of that same class:
private Node link;
Each link field refers to the next node in the list
^ top

10.2.3: Making a Simple Linked List

To make using linked nodes easier, we need a container class

Our linked list container class needs to both:

Connect all the links between nodes in the correct order

Manage the getting and setting of data in the nodes

Starting the List
We need some variable that refers to the start of our list
For this we use a special Node named head:
private Node head;
When we first create our list, it has no nodes
To indicate an empty list we assign the special value null to the head field:
public LinkedList1() {
    head = null;
}
First we show the complete LinkedList1 class and then consider the key parts
Simple Linked-List Class
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import java.util.*;

public class LinkedList1 {
    private Node head;

    public LinkedList1() {
        head = null;
    }

    public void clear() {
        head = null;
    }

    public int indexOf(String item) {
        Node position = head;
        int count = 0;
        while (position != null) {
            if (item.equals(position.getData())) {
                return count;
            }
            count++;
            position = position.getLink();
        }
        throw new NoSuchElementException();
    }

    public String get(int index) {
        Node position = head;
        int count = 0;
        while (position != null && count < index) {
            count++;
            position = position.getLink();
        }
        if (count != index) {
            throw new NoSuchElementException();
        }
        return position.getData();
    }

    public void showList() {
        Node position = head;
        while (position != null) {
            System.out.println(position.getData());
            position = position.getLink();
        }
    }

    public void addToStart(String newData) {
        head = new Node(newData, head);
    }

    public void removeFromStart() {
        if (head != null) {
            head = head.getLink();
        }
    }

    // For testing
    public static void main(String[] args) {
        LinkedList1 list = new LinkedList1();
        System.out.println("The list is empty");
        list.showList();
        list.addToStart("Jam");
        list.addToStart("Bread");
        list.addToStart("Milk");
        System.out.println("After adding 3 items:");
        list.showList();
        int index = list.indexOf("Bread");
        System.out.println(
            "Found 'Bread' at index: " + index);
        System.out.println("At the index we retrieved: "
            + list.get(index));
        list.removeFromStart();
        System.out.println(
            "After removing the first item:");
        list.showList();
    }
}
^ top

10.2.4: Traversing a List
To move around in a linked list, we need to be able to:

Move the position to the first node

Move the position from the current node to the next node

Detect when you have reached the end of the list
To move to the first node, we use our head node:
private Node head;
To move our position, we create a position field of type Node:
Node position = head;
To detect the end of the list, we set the value of the last link field to null

Pictorially we have something like:
To code a list traversal, we write something like:
Node position = head;
while (position != null) {
    // do something with node if necessary
    position = position.getLink();
}
As an example of traversing the list, we write a showList() method:
public void showList() {
    Node position = head;
    while (position != null) {
        System.out.println(position.getData());
        position = position.getLink();
    }
}
Another example is a findIndex() method:
public int findIndex(String item) {
    Node position = head;
    int count = 0;
    while (position != null) {
        if (item.equals(position.getData())) {
            return count;
        }
        count++;
        position = position.getLink();
    }
    throw new NoSuchElementException();
}
Still another example is a getData() method:
public String getData(int index) {
    Node position = head;
    int count = 0;
    while (position != null && count < index) {
        count++;
        position = position.getLink();
    }
    if (count != index) {
        throw new NoSuchElementException();
    }
    return position.getData();
}
These are all variations on the basic traversal algorithm
^ top

10.2.5: Adding and Removing Nodes

Now we look at how to add and remove nodes from our list

Adding Nodes
To add a node in the list takes two steps:

Create a new Node with our data

Insert the new Node in the correct location

To keep things simple, we will add the node at the start of the list

If we have a list like the following:

We create a new node for our data and add it to the start of the list

After adding the node, we want the list to look like:
To code an addToStart() method, we write something like:
public void addToStart(String newData) {
    head = new Node(newData, head);
}
Removing Nodes
The easiest place to remove a node from the list is from the start

To remove a node from the start, we want to move the head node so that it points to the second node on the list
We can do this with an assignment statement:
head = head.getLink();
However, what if the there are no nodes in the list?

We need to protect ourselves from this case with an if statement

In addition, we throw an exception from the Java core libraries: IllegalStateException
We end up with a method that looks like:
public void removeFromStart() {
    if (head == null) {
        throw new IllegalStateException();
    } else {
        head = head.link;
    }
}
What happens to the deleted node?

Java's garbage collection automatically recycles the memory
Removing All the Nodes
Garbage collection makes removing all the nodes in our list quite simple
All we need to do is set the head node to null:
public void clear() {
    head = null;
}
^ top

10.2.6: Working with a Linked List
We use the main() method of our LinkedList1 class for testing
To create a LinkedList1 object we use:
LinkedList1 list = new LinkedList1();
We start out with an empty list and show that it is indeed empty:
System.out.println("The list is empty");
list.showList();
Next we add some items to the list and call showList() again:
list.addToStart("Jam");
list.addToStart("Bread");
list.addToStart("Milk");
System.out.println("After adding 3 items:");
list.showList();
Now we test our ability to find items in the list and retrieve the data:
int index = list.findIndex("Bread");
System.out.println(
    "Found 'Bread' at index: " + index);
System.out.println("At the index we retrieved: "
    + list.getData(index));
Finally, we test our ability to remove items from the list
list.removeFromStart();
System.out.println(
    "After removing the first item:");
list.showList();
^ top

10.2.7: Summary
A linked data structure is made up of containers of data and links known as nodes

Data for each node is store in the data field

Each node is connected to other nodes via their link fields

The simplest kind of linked data structure is a linked list:

The key to a linked list is the node
A node contains a reference field that is an object of that same class:
public class Node {
    private String data;
    private Node link;
To keep track of the start of our list we use a variable of type Node named head:
public class LinkedList1 {
    private Node head;
When the list is empty the head field is set to null

To move around in a linked list, we use the following:

To move to the first node, we have our head field

To move our position, we create a position field of type Node

To detect the end of the list, we set the value of the last link field to null

Pictorially we have something like:
We looked at code to traverse the list:
Node position = head;
while (position != null) {
    // do something with node if necessary
    position = position.getLink();
}
We used this code to write findIndex() and getData() methods
In addition, we looked at code to add nodes to the start of the list:
public void addToStart(String newData) {
    head = new Node(newData, head);
}
Also, we looked at code to remove nodes from the start of the list:
public void removeFromStart() {
    if (head != null) {
        head = head.getLink();
    }
}
Finally, we looked at code to test the list
More Information

Wikipedia: Linked List

^ top

Exercise 10.2

Take one minute to fill in the blanks of the following statements:

A self-__________ class is used to form dynamic data structures that can grow and shrink at execution time.

The reference to the next node in a linked list is referred to as a(n) __________.

The end of a linked list is usually marked with the special value __________.

Automatically reclaiming dynamically-allocated memory in Java is called __________.

^ top

10.3: Improving the Linked List

Learner Outcomes

At the end of the lesson the student will be able to:

Code a node using an inner class

Discuss the purpose of an iterator

Use iterators to access the elements of a linked list

Add and delete nodes using an iterator

^ top

10.3.1: Making the Node an Inner Class
A linked list requires a node class to operate

To make our linked list self contained, we can make Node an inner class

An inner class is a class that is contained within the curly-braces of another (outer) class
Syntax:
public class OuterClass {
    // code for outer class
    class InnerClass {
        // code for inner class
    }
}
For example, here is our new Node class:
private class Node {
    private String data;
    private Node link;

    public Node(String newData, Node newLink) {
        data = newData;
        link = newLink;
    }
}
Since we do not plan to use our Node anywhere else, we make it private

This has an added benefit of allowing us to access the private data of Node without using set and get methods

Since Node is declared private, only members of the outer class can access Node

Thus we maintain encapsulation and data hiding

The following example shows our previous linked list but using an inner class for Node
Linked List with an Inner Class Node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import java.util.*;

public class LinkedList2 {
    private class Node {
        private String data;
        private Node link;

        public Node(String newData, Node newLink) {
            data = newData;
            link = newLink;
        }
    }

    private Node head;

    public LinkedList2() {
        head = null;
    }

    public void clear() {
        head = null;
    }

    public int indexOf(String item) {
        Node position = head;
        int count = 0;
        while (position != null) {
            if (item.equals(position.data)) {
                return count;
            }
            count++;
            position = position.link;
        }
        throw new NoSuchElementException();
    }

    public String get(int index) {
        Node position = head;
        int count = 0;
        while (position != null && count < index) {
            count++;
            position = position.link;
        }
        if (count != index) {
            throw new NoSuchElementException();
        }
        return position.data;
    }

    public void showList() {
        Node position = head;
        while (position != null) {
            System.out.println(position.data);
            position = position.link;
        }
    }

    public void addToStart(String newData) {
        head = new Node(newData, head);
    }

    public void removeFromStart() {
        if (head != null) {
            head = head.link;
        }
    }

    // For testing
    public static void main(String[] args) {
        LinkedList2 list = new LinkedList2();
        System.out.println("The list is empty");
        list.showList();
        list.addToStart("Jam");
        list.addToStart("Bread");
        list.addToStart("Milk");
        System.out.println("After adding 3 items:");
        list.showList();
        int index = list.indexOf("Bread");
        System.out.println(
            "Found 'Bread' at index: " + index);
        System.out.println("At the index we retrieved: "
            + list.get(index));
        list.removeFromStart();
        System.out.println(
            "After removing the first item:");
        list.showList();
    }
}
^ top

10.3.2: Introduction to Iterators

Iterator: An object that allows you to move through and access items over a collection of objects (from iterate -- with an "i" as in pit, NOT as in pie).
Iterators are often used with collections of objects such as the nodes of a linked list

Many times you need to step through all the objects and perform some action on each object:

Like displaying to a screen or finding the index of a node

An iterator is an object that allows you to step through a collection one object at a time
So far we have used code like the following to iterate through our linked list:
Node position = head;
while (position != null) {
    position = position.getLink();
    // do something with node
}
Now we want to encapsulate the iterating code into an object
^ top

10.3.3: Defining a List Iterator Class
There are two requirements for an iterator:

Some way to move the iterator position and get the next value

Some way to determine if you have moved over the entire collection

Java has an Iterator interface we will implement to make our code operate as expected

An interface specifies public static final variables and abstract methods that must be implemented by a class using the interface

Iterator interface requires implementing three methods shown in the table below
The hasNext() and next() methods are intended to be used together in loops like this:
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}
Note that the remove() method is not really required by the interface

It can simply throw an UnsupportedOperationException

Even so, we will implement the remove() method in our iterator

In addition, we will implement an add() method to insert objects into our list
Methods of the Iterator Interface

Method Description

hasNext() Returns true if the iteration has more elements

next() Returns the next element in the iteration and moves the position forward by one element.

remove() Removes from the collection the last element returned by the iterator.

Starting the Iterator Class
We decide to name our class ListIter since it will be a list iterator
Also, we declare that it will implement the Iterator interface:
public class ListIter implements Iterator
In addition, to keep our LinkedList class self-contained, we decide that will make our ListIter class an inner class
We will need to keep track of two variables in our iterator class:
private Node position;
private Node previous;
The first Node object is our current position

The second Node object is our previous position:

Having two Node fields will prove useful when we add and remove nodes
Also, we declare a constructor for our object:
ListIter() {
    position = head;
    previous = null;
}
These values make sure that a new iterator starts at the beginning of the list
Writing the hasNext() Method
The hasNext() returns true while there are more elements remaining in the iteration
Since the end of a list is marked with null, we can code this method simply like:
public boolean hasNext() {
    return position != null;
}
Writing the next() Method
The next() method both returns an element of the iteration and increments the position

Also we need to handle the condition where we try to use next() when no elements remain
When we put all these requirements together, we end with a method like:
public String next() {
    if (!hasNext()) {
        throw new NoSuchElementException();
    }
    String value = position.data;
    previous = position;
    position = position.link;
    return value;
}
We cover the remove() and add() methods in the next two sections
Writing Linked-List Methods

After writing a few methods for linked lists, you notice a pattern

First you write the code for the usual case in the middle of a list

Then you consider the less usual cases:

An empty list

When position is at the start of the list

When position is at the end of the list

If the code for your usual case will not handle the less usual cases, you add code to test and handle these less usual cases

^ top

10.3.4: Deleting Nodes
Since deleting is easier than inserting, we cover the remove() method first

When you delete a node from a linked list, you are removing the linked list's reference to the node

Assume that we have positioned our iterator in the list to the node we want to delete

First we set the link field of the previous node to point to the node after the one being deleted:
In code, this looks like:
previous.link = position.link;
Next we move the position forward to the node after the deleted node
In code, this looks like:
position = position.link;
Note that the deleted node is still in memory and needs to be reclaimed

In Java, the deleted node will be reclaimed automatically

When all references to an object are removed, the object is garbage collected

Which leaves use with our final list with the node deleted
Additional Cases
There are a few problems with our code that we need to consider

What if we are deleting the first node from the list?
When this happens, our first line of code throws a NullPointerException!
previous.link = position.link;
To resolve the problem we can use the head field like this:
head = head.link;
position = head;
Another case is trying to delete a node when the list is empty
To solve this case, we throw an exception specified by the interface:
throw new IllegalStateException();
Putting all this together we have our completed remove() method
public void remove() {
    if (position == null) { // no nodes
        throw new IllegalStateException();
    } else if (previous == null) { // at head
        head = head.link;
        position = head;
    } else { // usual case
        previous.link = position.link;
        position = position.link;
    }
}
^ top

10.3.5: Inserting Nodes
To add a node, we want to put the new node between previous and position

Thus we make some space for it in our diagram as follows:

To start the insertion, we create a new node and assign it to a local variable temp:
In code, this looks like:
Node temp = new Node(newData, position);
The constructor for Node is doing some of the work for us:
public Node(String newData, Node newLink) {
    data = newData;
    link = newLink;
}
Next we want to have the previous node to point to the new node:
In code, this looks like:
previous.link = temp;
Finally, we adjust our previous node to point to the newly inserted node:
In code, this looks like:
previous = temp;
After we return from the add() method, the local temp variable is garbage collected:
Additional Cases
There are a few problems with our code that we need to consider
Putting all this together we have our completed add() method:
public void add(String newData) {
    if (position == null && previous != null) {
        // at end of list
        previous.link = new Node(newData, null);
        previous = previous.link;
    } else if (position == null || previous == null) {
        // list is empty or position is at head node
        addToStart(newData);
    } else {
        // usual case: previous and position are
        // consecutive nodes
        Node temp = new Node(newData, position);
        previous.link = temp;
        previous = temp;
    }
}
^ top

10.3.6: Working with the Linked List Iterator
Since our ListIter class is an inner class, we need some way to create an object
The usual way in Java is to write an method that returns an iterator:
ListIter iterator() {
    return new ListIter();
}
Thus, to construct a new ListIter you simply call the iterator method:
LinkedList.ListIter lit = myList.iterator();
Note that to declare a variable of type ListIter you must include both the outer and inner class names
With the iterator we can walk through the complete linked list using:
while (lit.hasNext()) {
    lit.next();
}
We can use an iterator to insert elements at the end of the list:
while (lit.hasNext()) {
    lit.next();
}
lit.add("Tea3");
In addition, we can delete items from the list
lit = list.iterator();
System.out.println("Remove at start");
lit.remove();
System.out.println("Remove after moving next: ");
lit.next();
lit.remove();
Note that if you try to remove an element after traversing the list that you get an error:
lit = list.iterator();
while (lit.hasNext()) {
    lit.next();
}
lit.remove(); // throws an exception
To replace an item at the end of the list, you must count as you traverse the list:
lit = list.iterator();
for (int i = 0; i < length - 1; i++) {
    lit.next();
}
lit.remove();
To replace an item in the list:
lit = list.iterator();
for (int i = 0; i < index; i++) {
    lit.next();
}
lit.remove();
lit.add("New bread");
Note that you must get a new ListIter after every call to the add() method

For the methods that we have implemented, our ListIter has the same behavior as a ListIterator retrieved from ArrayList
Code for the LinkedList Class

Code for the LinkedList class: LinkedList.java

Code for the LinkedListTest class: LinkedListTest.java

^ top

10.3.7: Summary

Making Node an inner class makes our linked list class more self contained and easier to code

An iterator is an object that allows you to move through and access items over a collection of objects like a linked list

We defined a ListIter class to work with our LinkedList as an iterator

For the methods that we implemented, we have the same functionality as an iterator retrieved from Vector

Code for the LinkedList class: LinkedList.java

Code for the LinkedListTest class: LinkedListTest.java

^ top

Exercise 10.3

Take one minute to fill in the blanks of the following statements:
To make our Node class simpler and easier to code, we used a(n) class.

A(n) is used to step through a collection and access items in the collection.
The following code is used to , or traverse, a linked list.
Iterator it = list.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}
^ top

Wrap Up

Due Next:
A8-Image Manipulation (4/21/10)
A9-Card Games Redux (4/28/10)

^ top
Home | Blackboard | Schedule | Room Policies | Syllabus
Help | FAQ's | HowTo's | Links Last Updated: April 27 2010 @18:19:28

What We Will Cover

Illuminations

Questions from last class?

Homework Questions?

Homework Discussion Questions

10.1: Dynamic Data Structures

Learner Outcomes

10.1.1: About Dynamic Data Structures

Enhanced for Loop

10.1.2: Array Lists

Some Commonly Used Constructors and Methods of the ArrayList<type> Class

Example of Using an ArrayList

10.1.3: Linked Lists

Advantages and Disadvantages of a Linked List

Some Commonly Used Constructors and Methods of the LinkedList<type> Class

Example of Using a LinkedList

10.1.4: Hash Maps

Some Commonly Used Constructors and Methods of the HashMap<keyType,valueType> Class

Example of Using a HashMap

10.1.5: Primitive Data and Autoboxing

Autoboxing and Auto-Unboxing

10.1.6: Summary

Check Yourself

Exercise 10.1

10.2: Linked Lists

Learner Outcomes

10.2.1: Introduction to Linked Lists

Linked Lists

10.2.2: Defining a Node

Example Node Class

Self-Referential Classes

10.2.3: Making a Simple Linked List

Starting the List

Simple Linked-List Class

10.2.4: Traversing a List

10.2.5: Adding and Removing Nodes

Adding Nodes

Removing Nodes

Removing All the Nodes

10.2.6: Working with a Linked List

10.2.7: Summary

More Information

Exercise 10.2

10.3: Improving the Linked List

Learner Outcomes

10.3.1: Making the Node an Inner Class

Linked List with an Inner Class Node

10.3.2: Introduction to Iterators

10.3.3: Defining a List Iterator Class

Methods of the Iterator Interface

Starting the Iterator Class

Writing the hasNext() Method

Writing the next() Method

Writing Linked-List Methods

10.3.4: Deleting Nodes

Additional Cases

10.3.5: Inserting Nodes

Additional Cases

10.3.6: Working with the Linked List Iterator

Code for the LinkedList Class

10.3.7: Summary

Exercise 10.3

Wrap Up

Enhanced `for` Loop

Some Commonly Used Constructors and Methods of the `ArrayList<type>` Class

Example of Using an `ArrayList`

Some Commonly Used Constructors and Methods of the `LinkedList<type>` Class

Example of Using a `LinkedList`

Some Commonly Used Constructors and Methods of the `HashMap<keyType,valueType>` Class

Example of Using a `HashMap`

Writing the `hasNext()` Method

Writing the `next()` Method

Code for the `LinkedList` Class