11: Dynamic Data Structures

What We Will Cover

Illuminations

Questions on Assignments?

Questions from last class?

^ top

11.1: Data Structures and Vectors

Objectives

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

  • Explain in general terms what is a dynamic data structures
  • Work with vectors
  • Use generic data in a vector or array
  • 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 including:
  • We will examine vectors and linked lists this week
  • Textbook has descriptions of the other data structures
  • National Institute of Standards and Technology (NIST) also contains a more comprehensive Dictionary of Algorithms and Data Structures

^ top

11.1.2: Creating Vectors

  • One type of data structure is a vector
  • Like an array, a vector stores data items that can be accessed using an integer index
  • Unlike an array, the size of vectors grow and shrink automatically
    • As data items are added and removed
  • Thus, vectors are more flexible and suitable for some coding situations
  • However, vectors do require more resources than arrays

Commonly Used Constructors of the Vector Class

Constructor Description
Vector() Creates an empty vector with an initial capacity of 10 objects
Vector(intCapacity) Creates an empty vector with the specified capacity
Vector(intCapacity, intIncrement) Creates an empty vector with the specified capacity and capacity increment

  • Vectors try to optimize the tradeoff between speed and storage using a capacity and capacity increment
  • Capacity is always as large as the current number of elements, but often larger
  • A vector's size increases by the capacity increment
  • If no capacity increment is specified, then a vector doubles in size each time it needs more capacity
  • Doubling is usually the optimum tradeoff between speed and storage

Example of Creating a Vector

  • Since JDK 1.5, specify vectors with a type like this:
    • Vector<String> days = new Vector<String>();
  • If you are using an earlier JDK, specify vectors like this:
    • Vector myList = new Vector();

^ top

11.1.3: Adding Data

  • To add or insert items into a vector, you use the add() method
  • You can add items to the end of the list
  • Alternatively, you can insert items anywhere in the current list

Some methods to Add Data to a Vector

Method Description
add(typeItem) Appends the item to the end of the vector.
add(intIndex, typeItem) Inserts the item at the specified index of the vector, pushing any other items higher by one.
set(intIndex, typeItem) Replaces the item at the specified index of the vector.

Examples of Adding Items to a Vector

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

import java.util.*;

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

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

        days.add(0, "Sunday"); // add to front
        days.add("Saturday");  // add to end
        days.set(1, "Monday"); // change

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

^ top

11.1.4: Retrieving and Deleting Data

  • If you know the index of an item, you can retrieve it using the get() method
  • To find the index of an item, you can use the indexOf() method
    • Searches each item in the vector until it finds the object
    • Uses the equals() method to determine if the objects match
  • To delete an item, you use the remove() method
  • To delete all items, you use the clear() method

Some methods to Ret rive and Delete the Data of a Vector

Method Description
get(intIndex) Returns an Object type for the item at the specified index.
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.
clear() Removes all of the items from the vector.

Examples of Retrieving and Deleting Items of a Vector

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import java.util.*;

public class VectorDays2 {
    public static void main(String[] args) {
        Vector<String> days = new Vector<String>();
        days.add("Sunday");
        days.add("Monday");
        days.add("Tuesday");
        days.add("Wednesday");
        days.add("Thursday");
        days.add("Friday");
        days.add("Saturday");

        int index = days.indexOf("Monday");
        String dayName = (String) days.get(index);
        System.out.println("No more " + dayName);
        days.remove(index);

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

^ top

11.1.5: Generic Data and Autoboxing

  • Note that vectors 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 vector required you to manually create a wrapper class
  • For example, to add the number 9 into a vector:
    • Integer integer = new Integer(9);
intVector.add(integer);
  • To retrieve values, you had to convert the value from the wrapper type
  • For example, to retrieve the previous value:
    • Integer integer = intVector.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 vector:
    • intVector.add(9);
  • To retrieve the same value:
    • int value = intVector.indexOf(index);

^ top

11.1.6: Iterating through Data

Iterate: to do again and again (iterate -- with an "i" as in pit, NOT as in pie).

  • Loops are a form of iteration with which we are familiar
  • For example:
    • for (int i = 0; i < days.size(); i++) {
    System.out.println(days.get(i));
}

The "For-Each" Loop

  • Starting in JDK 1.5, Java added a new way to iterate through a list
  • Known as the enhanced for loop or the for-each loop
  • Syntax:
    • for (typeName variableName : listName)
    statement
  • The enhanced for loop works with arrays, vectors and other collection types
  • For example, to iterate through our days vector:
    • for (String dayName : days) {
    System.out.println(dayName);
}

Examples of Iterating Through a Vector

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import java.util.*;

public class VectorDays3 {
    public static void main(String[] args) {
        Vector<String> days = new Vector<String>();
        days.add("Sunday");
        days.add("Monday");
        days.add("Tuesday");
        days.add("Wednesday");
        days.add("Thursday");
        days.add("Friday");
        days.add("Saturday");

        System.out.println("Using a for loop:");
        for (int i = 0; i < days.size(); i++) {
            System.out.println(days.get(i));
        }

        System.out.println("\nUsing a for-each loop:");
        for (String dayName : days) {
            System.out.println(dayName);
        }
    }
}

^ top

11.1.7: Summary

  • A data structure is an organization of data in a computer's memory
    • For example: an array
  • A dynamic data structure is one that can grow and shrink while a program is running
  • One such data structure is a vector, sometimes called a dynamic array
  • Like an array, a vector stores data items that can be accessed using an integer index
  • The size of a vector grows and shrinks automatically as data items are added or removed
  • To create an empty vector, you code something like:
    • Vector<String> days = new Vector<String>();
  • To add or change items in a vector use code like:
    • myVector.add("an object");
myVector.add(0, "another object");
myVector.set(1, "some object");
  • To find an item in a vector, you can use indexOf():
    • int index = myVector.indexOf("some object");
  • To retrieve an item from a vector you can use get():
    • Object value = myVector.get(index);
  • Similarly, you can delete an item from a vector using remove():
    • value = myVector.remove(index);
  • Vectors 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 vector using a for loop:
    • for (int i = 0; i < myVector.size(); i++) {
    System.out.println(myVector.get(i));
}
  • Since JDK 1.5, you can iterate through a vector or array using the enhanced for loop:
    • for (String dayName : days) {
    System.out.println(dayName);
}

^ top

Exercise 11.1

Take one minute to prepare an answer to the following questions:

  1. Which of the following types can NOT be stored directly in a Vector object?
    1. int
    2. String
    3. Date
    4. Vector
  2. What happens if you attempt to compile and run the following code?
    1. The code does not compile
    2. The code compiles but throws and exception when run
    3. The code compiles and displays "another object" when run
    4. The code compiles and displays "some object" when run
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.*;

public class VectorExercise {
    public static void main(String[] args) {
        Vector<String> myVector = new Vector<String>();
        myVector.add("an object");
        myVector.add(0, "another object");
        myVector.set(1, "some object");
        int index = myVector.indexOf("some object");
        Object value = myVector.get(index);
        value = myVector.remove(index);

        for (int i = 0; i < myVector.size(); i++) {
            System.out.println(myVector.get(i));
        }

        for (String str : myVector) {
            System.out.println(str);
        }

    }
}

^ top

11.2: Generics

Objectives

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

  • Explain the need for generic data types
  • Create generic classes that specify a set of related types
  • Create generic method that perform the same tasks on arguments of different types

^ top

11.2.1: Introduction to Generics

  • Generics refers to feature of Java that lets classes and methods contain parameters for types
  • Once defined with a type parameter, you specify the type when you use the class
  • Java has implemented generic types in several classes including Vector
  • To use a Vector with a type, you code something like:
    • Vector<String> products = new Vector<String>();
  • Once you define a type, the compiler checks that only that type is stored in the Vector object
  • Also, any value you retrieve from a typed Vector is automatically converted to the correct type

Motivation for Generics

  • Before JDK 1.5, the elements of a Vector were always stored as an Object
  • Since all objects in Java are descended from Object, this let you store any type of object in a Vector
    • Even primitive types can be stored using wrapper classes
  • At first, this flexibility may seem like an advantage.
  • However, this technique has two disadvantages:
    1. There is no way to write code guaranteeing that only one type of object is stored in a vector
    2. You have to downcast an object retrieved from the vector in order to use it fully
  • Both of these reasons produced many bugs in Java programs
    1. Objects of the wrong type were stored in vectors
    2. Objects retrieved from vectors were cast to the wrong type
  • Let us look at how to use generics to avoid these problems

^ top

11.2.2: Defining Generic Classes

  • To create a generic class, you specify one or more type parameters in angle brackets
  • Syntax:
    • accessModifier class ClassName<Type> { }
  • For example:
    • public class Value<T>
  • Type parameter names can be any valid identifier
  • By convention, type parameters are uppercase letters
  • This makes sense because classes are usually plugged in for type parameters.
  • Type parameters can be used as method parameters:
    • public void setData(T newData)
  • Also, type parameters can be used as method return types:
    • public T getData()
  • Following is a simple class showing these uses

Example Class Using a Generic Type

1
2
3
4
5
6
7
8
9
10
11

public class Value<T> {
    private T data;

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

    public T getData() {
        return data;
    }
}

^ top

11.2.3: Working with Generic Class Parameters

  • Once a generic class is defined, it is stored in a file and compiled like any other Java source code.
  • To use the class, you "plug in" a parameter type
  • For example:
    • Value<String> val = new Value<String>();
  • Following is a complete example:

Example Use of a Generic Class

1
2
3
4
5
6
7
8
9
10

public class ValueDemo {
    public static void main(String[] args) {
        Value<String> val = new Value<String>();
        val.setData("Hi Mom!");
        System.out.println(val.getData());
        Value<Integer> nine = new Value<Integer>();
        nine.setData(new Integer(9));
        System.out.println(nine.getData());
    }
}

^ top

11.2.4: Defining Generic Methods

  • If an overloaded method performs the same operations for each argument type, you can use generic types instead
  • Recall the showArray() method from lesson 4.2.2:
    • public static void showArray(String[] values) {
    for (int i = 0; i < values.length; i++) {
        System.out.println(values[i]);
    }
}
  • Rather than overloading the method with different types, we can code it using generic types:
    • public static <T> void showArray(T[] values) {
    for (T item : values) {
        System.out.println(item);
    }
}
  • Note that this technique works for both static and instance methods

Example Demonstrating showArray() Defined Using a Generic Type

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

import java.util.*;

public class GenericMethodDemo {
    public static <T> void showArray(T[] values) {
        for (T item : values) {
            System.out.println(item);
        }
    }
    public static void main(String[] args) {
        Integer[] ints = { 1, 2, 3, 4, 5 };
        Double[] doubles = { 1.1, 2.2, 3.3, 4.4, 5.5 };
        Character[] chars = { 'H', 'e', 'l', 'l', 'o' };

        System.out.println("Showing ints:");
        showArray(ints);
        System.out.println("\nShowing doubles:");
        showArray(doubles);
        System.out.println("\nShowing chars:");
        showArray(chars);
    }
}

Compiling with the -XLint Option

  • You can make many mistakes coding type parameters
  • The compiler error messages can be vague
  • However, if you compile with the -Xlint option you will get more information of problems or potential problems
  • For example, to compile the Value class you would use:
    • javac -Xlint Value.java

More Information

^ top

11.2.5: Summary

  • Generic classes let the Java programmer specify a set of related types with a single class declaration
  • Generic methods let the Java programmer specify a set of related methods with a single method declaration
  • Generic classes and methods offer compile-time type safety
  • Type parameters for classes are specified inside angle brackets
    • public class Value<T>
  • Then type parameters can be used as method parameters:
    • public void setData(T newData)
  • Also, type parameters can be used as method return types:
    • public T getData()
  • To specify a generic type for a single method, you code the type before the return type like:
    • public static <T> void showArray(T[] values)
  • Then you use the type parameter in the method in place of the specific type:
    • for (T item : values)
  • To better understand compiler errors and warnings, you can compile with the -Xlint option:
    • javac -Xlint Value.java

^ top

Exercise 11.2

Take one minute to prepare an answer to the following true-or-false questions:

  1. Generic methods have a type parameter immediately preceding the method name like this:
    2. public void <T> myMethod() { }
  2. A generic method can have the same name as (overload) a non-generic method

^ top

11.3: Linked Lists

Objectives

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.3.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 store 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 shown by the head node
  • The end of the list has a special end-of-list marker

^ top

11.3.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.3.3: Making a Simple Linked List

  • To make using the linked nodes easier, we need a container class
  • Our linked list 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.3.4: Traversing a List

  • To move around in a linked list, you 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 have our head field
  • To move our position, we create a position field of type Node
  • To detect the end of the list, you 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();
    }
}
  • Similarly, we could write 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();
}
  • In addition, we could write 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 operation.

^ top

11.3.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
    • Later we will consider the more general case
  • 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 at the start
    • Later we will consider the more general case
  • To remove a node at 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.3.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.3.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.3

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.4: Improving the Linked List

Objectives

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.4.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
  • 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
  • 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 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 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;
        }
    }

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

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

    // 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.4.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.4.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
  • 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.4.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?
  • In this case, our first line of code throws a NullPointerException!
    • previous.link = position.link;
  • In this case we can use the head field instead of the previous field:
    • 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.4.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 position 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 remove() 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.4.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.4.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.4

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 | WebCT | Announcements | Schedule | Room Policies | Course Info
Help | FAQ's | HowTo's | Links

Last Updated: May 02 2005 @14:41:05