11:Dynamic Data Structures

What We Will Cover

Illuminations

Questions from last class?

Homework Questions?

Homework Discussion Questions

  1. How easy was it to draw simple shapes using a Graphics2D object?
  2. Did anyone use the Turtle class?

^ top

11.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

11.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:
  • 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

11.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

11.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

11.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
35
36
37
38
39

import java.util.*;

public class HashMapDemo {
    public static void main(String[] args) {
        HashMap<Integer, String> days =
            new HashMap<Integer, String>();
        days.put(0, "Unknown");
        days.put(2, "Tuesday");
        days.put(3, "Wednesday");
        days.put(4, "Thursday");
        days.put(5, "Friday");

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

        System.out.println("Adding the missing days...");
        days.put(0, "Sunday"); // replace existing
        days.put(6, "Saturday");
        days.put(1, "Monday");

        System.out.println("\nNow the collection is complete");
        for (int i = 0; i < days.size(); i++) {
            System.out.println(days.get(i));
        }

        System.out.println("\nRemoving a bad day...");
        if (days.containsKey(1)) {
            System.out.println("I found " + days.get(1));
        }
        String dayName = days.remove(1);

        System.out.println("\nNo more " + dayName);
        for (int i = 0; i < days.size(); i++) {
            System.out.println(days.get(i));
        }
    }
}

^ top

11.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

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, to retrieve the previous value:
    • Integer integer = intList.indexOf(index);
int value = integer.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.indexOf(index);

^ top

11.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:
  • 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

  1. What is the most basic list structure in Java?
  2. What is meant by the term "dynamic data structure"?
  3. How do you code an ArrayList that can store double values?
  4. What is the difference between an ArrayList and a LinkedList
  5. What are the advantages and disadvantageous of using a HashMap data type
  6. What is the syntax of a "for-each" loop?

^ top

Exercise 11.1

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

^ top

11.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

11.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

11.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

11.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

11.2.4: Traversing a List

  • To move around in a linked list, we need to be able to:
    1. Move the position to the first node
    2. Move the position from the current node to the next node
    3. 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

11.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
    1. Create a new Node with our data
    2. 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

11.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

11.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

^ top

Exercise 11.2

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

  1. A self-__________ class is used to form dynamic data structures that can grow and shrink at execution time.
  2. The reference to the next node in a linked list is referred to as a(n) __________.
  3. The end of a linked list is usually marked with the special value __________.
  4. Automatically reclaiming dynamically-allocated memory in Java is called __________.

^ top

11.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

11.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

11.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 allow 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

11.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

11.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

11.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);
    } 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

11.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();
}
  • Note that to declare a variable of type ListIter you must include the outer class name:
    • LinkedList.ListIter lit = myList.iterator();
  • Once we return an iterator we can use it to display all the items in the list
    • Iterator it = list.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}
  • Also, we can insert new elements in the list:
    • ListIter lit = list.iterator();
System.out.println("Add at start");
lit.add("Tea1");
System.out.println("Add after moving next: ");
lit.next();
lit.add("Tea2");
System.out.println("Add at end");
while (lit.hasNext()) {
    lit.next();
}
lit.add("Tea3");
list.showList();
  • In addition, we can delete items in the list
    • lit = list.iterator();
System.out.println("Remove at start");
lit.remove();
System.out.println("Remove after moving next: ");
lit.next();
lit.remove();
list.showList();
  • Note that if you try to remove an element after traversing the list that you get an error:
    • System.out.println("Remove at end");
while (lit.hasNext()) {
    lit.next();
}
lit.remove(); // throws an exception
  • For the methods that we have implemented, our ListIter has the same behavior as a ListIterator retrieved from Vector

Code for the LinkedList Class

^ top

11.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 11.3

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

  1. To make our Node class simpler and easier to code, we used a(n) __________.
  2. A(n)__________ is used to step through a collection and access items in the collection.
  3. The following code is used to __________ a linked list.
    4. Iterator it = list.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

^ top

Wrap Up

^ top

Home | Blackboard | Announcements | Schedule | Room Policies | Course Info
Help | FAQ's | HowTo's | Links
Last Updated: May 03 2009 @20:22:20