logo

APSU Notes


Dynamic Data Structures and Generics

Savitch 12

Objectives

  • Define and use an instance of ArrayList
  • Introduction to the Java Collections Framework
  • Describe general idea of linked list data structures and implementation
  • Manipulate linked lists
  • Use inner classes in defining linked data structures
  • Describe, create, use iterators
  • Define, us classes with generic types

Array-Based Data Structures: Outline

Class ArrayList

  • Consider limitations of Java arrays
    • Array length is not dynamically changeable
    • Possible to create a new, larger array and copy elements — but this is awkward, contrived
  • More elegant solution is use instance of ArrayList
    • Length is changeable at run time
  • Drawbacks of using ArrayList
    • Less efficient that using an array
    • Can only store objects
    • Cannot store primitive types
  • Implementation
    • Actually does use arrays
    • Expands capacity in manner previously suggested
  • Class ArrayList is an implementation of an Abstract Data Type (ADT) called a list
  • Elements can be added
    • At end
    • At beginning
    • In between items
  • Possible to edit, delete, access, and count entries in the list.

Figure12.1

  • Figure 12.1 Methods of class ArrayList:

Creating Instance of ArrayList

  • Necessary to import java.util.ArrayList;
  • Create and name instance ArrayList<String> list = new ArrayList<String>(20);
  • This list will
    • Hold String objects
    • Initially hold up to 20 elements

Using Methods of ArrayList

  • Object of an ArrayList used like an array
    • But methods must be used
    • Not square bracket notation
  • Given ArrayList<String> aList = new ArrayList<String>(20);
    • Assign a value with:
    • aList.add(index, "Hi Mom");
    • aList.add(index, "Yo Dad");

Programming Example

  • A To-Do List
    • Maintains a list of everyday tasks
    • User enters as many as desired
    • Program displays the list
  • View source code, listing 12.1 class ArrayListDemo

outputArrayListDemo

  • When accessing all elements of an ArrayList object
    • Use a For-Each loop
  • Use the trimToSize method to save memory
  • To copy an ArrayList
    • Do not use just an assignment statement
    • Use the clone method

Parameterized Classes, Generic Data Types

  • Class ArrayList is a parameterized class
    • It has a parameter which is a type
  • Possible to declare out own classes which use types as parameters
  • Note earlier versions of Java had a type of ArrayList that was not parameterized

The Java Collections Framework

  • A collection of interfaces and classes that implement useful data structures and algorithms
  • The Collection interface specifies how objects can be added, removed, or accessed from a Collection
  • Brief introduction to just two implementations, HashSet and HasMap
    • See other references for more info

HashSet Class

  • Used to store a set of objects
  • Uses the same <> notation as an ArrayList to specify the data type
  • View source code, listing 12.2 class HashSetDemo
  • If you use HashSet of you own class, it must override hashCode() and equals()

HashMap Class

  • Used like a database to efficiently map from a key to an object
  • Uses the same <> notation as an ArrayList to specify the data type of both the key and object
  • View source code, listing 12.3 class HashMapDemo
  • If you use HashMap of your own class as key, it must override hashCode() and equals()

Linked Data Structures: Outline

Class LinkedList

  • Linked data structure
    • Collection of objects
    • Each object contains data and a reference to another object in the collection
  • Java provides a class to do this, LinkedList
    • More efficient memory use than ArrayList
  • We will write our own version to learn the concepts of a linked list

Linked Lists

  • A dynamic data structure
  • Links items in a list to one another

LinkedLists

  • Figure 12.4, a linked list

  • Node of a linked list object requires two instance variables
    • Data
    • Link
  • View sample class, listing 12.4 class ListNode
    • This example has String data
    • Note the link, a reference to the type which is the class

Implementing Operations of Linked Lists

  • Now we create a linked list class which uses the node class
  • View class, listing class StringLinkedList
  • Note the single instance variable of type ListNode
  • Note method to traverse and print the contents of the list
  • Figure 12.5 Moving down a linked list

Figure12.5

  • Figure 12.6 Adding a node at the start of a linked list

Figure12.6

  • View linked-list demonstration, listing 12.6 class StringLinkedListDemo

Output12.6

  • Java automatically returns memory used by deleted node to the operating system.
    • Called automatic garbage collecting
  • In this context, not the significance of NullPointerException messages
  • Consider the fact that our program has a reference (name) to only the head node

A Privacy Leak

  • Note results of getLink in class ListNode
    • Returns reference to ListNode
    • This is a reference to an instance variable of a class type … which is supposed to be private
  • Typical solution is to make ListNode a private inner class of StringLinkedList

Inner Classes

  • Defined within other classes
  • Example


1
2
3
4
5
6
7
8
9



public class OuterClass {
    //Declarations of OuterClass Instance Variables
    //Definitions of OuterClass Methods

    private class InnerClass {
        //Declarations of InnerClass Instance Variables
        //Definitions of InnerClass Methods
    }
}
  • Inner class definition local to the outer-class definition
    • Inner-class definition usable anywhere within definition of outer class
  • Methods of inner and outer classes have access to each other’s methods, instance variables

Node Inner Classes

  • We show ListNode as a private inner class
    • This is safer design
    • Hides method getLink from world outside StringLinkedList definition
  • View new version, listing 12.7 class StringLinkedListSelfContained

Iterators

  • A variable that allows you to step through a collection of nodes in a linked list
    • For arrays, we use an integer
  • Common to place elements of a linked list into an array
    • For display purposes, array is easily traversed
  • View method to do this, listing 12.8 method ToArray
  • Consider an iterator that will move through a linked list
    • Allow manipulation of the data at the nodes
    • Allow insertion, deletion of nodes
  • View sample code, listing 12.9 class StringLinkedListWithIterator

Figure12.7

  • Figure 12.7 The effect of goToNext on a linked list

Figure12.8a

  • Figure 12.8a Adding node to linked list using insertAfterIterator

Figure12.8b

  • Figure 12.8b Adding node to linked list using insertAfterIterator

Figure12.9a

  • Figure 12.9a Deleting a node

Figure12.9b

  • Figure 12.9b Deleting a node

Java Iterator Interface

  • Java formally considers an iterator to be an object
  • Note interface named Iterator with methods
    • hasNext — returns boolean value
    • next — returns next element in iteration
    • remove — removes element most recently returned by next method

Exception Handling with Linked Lists

  • Recalled class StringLinkedListWithIterator
    • Methods written so that errors caused screen message and program end
  • More elegant solution is to have them throw exceptions
    • Programmer decides how to handle
  • Note class which does this, listing class LinkedListException

Variations on a Linked List

  • Possible to make a linked where data element is of any type
    • Replace type String in definition of node class with desired data type
  • Consider keeping a reference to last node in list
    • Called the tail of the list
    • Constructors, methods modified to accommodate new reference
  • Consider having last link point back to head
    • Creates a circular linked list

Figure12.10

  • Figure 12.10 Circular linked list

  • Also possible to have backward as well as forward links in the list

    • Doubly linked list
    • Possible to traverse in either direction

Figure12.11

  • Figure 12.11 Doubly linked list

Other Linked Data Structures

  • Stack
    • Elements removed from ADT in reverse order of initial insertion
    • Can be implemented with linked list
  • Tree
    • Each node leads to multiple other modes
    • Binary tree leads to at most two other nodes

Figure12.12

  • Figure 12.12 Binary Tree

Generics: Outline

Basics of Generics

  • Beginning with Java 5.0, class definitions may include parameters for types
    • Called generics
  • Programmer now can specify any class type for the type parameter
  • View class definition, listing 12.11 class `Sample<T>1
  • Note use of <T> for the type parameter
  • Legal to use parameter T almost anywhere you can use class type
    • Cannot use type parameter when allocating memory such as anArray = new T[20];
  • Example declaration:
    • Sample <String> sample1 = new Sample<String>();
  • Cannot specify a primitive type for the type parameter

Programming Example

  • Generic linked list
    • Revision of listing 12.5
    • Use type parameter E instead of String
  • Note similarities and differences of parameterized class with non-parameterized classes
  • View generic class, listing 12.12 class LinkedList <E>
  • View demo program, listing 12.13 class LinkedListDemo

Listing12.13

Graphics Supplement

  • The Scene Builder can simplify the creation of JavaFX GUI applications by providing a graphical way to arrange the components on a form
  • Binaries of the Scene Builder available from Gluon Labs
    • http://gluonhq.com/labs/scene-builder
  • Use in conjunction with an IDE such as NetBeans or Eclipse
    • Consult your IDE documentation for further information on integration
  • JavaFX applications split up into three files that separate the layout from the code logic
    • FXML file — contains information about the presentation and layout of nodes but no code for what happens when events occur
    • Application file — Java source code that contains the start method and typically loads the FXML file
    • Controller file — Java source code that implements event handlers that respond to the UI controls

Sample FXML File

  • Can build the FXML file by hand, similar to HTML. Example File:

SampleFXMLFile

  • This file is what is built automatically for us by the scene builder!

Scene Builder UI

SceneBuilderUI

  • Drag controls from the library to the view in the middle
  • The AnchorPane allows us to anchor the sides of a control to edges in the pane

AnchoringButton

  • Anchoring a Button to the left and right sides of the pane using Scene Builder 2.0

SceneBuilderPreview

  • Preview Window

The JavaFX Application Class

  • This class loads the FXML document in the start method
  • It is typically created automatically by the IDE
  • View JavaFX application class, listing 12.14 class JavaFXApp

The JavaFX Controller Class

  • This class contains event handlers for controls in the GUI
  • We need to link variables in the controller to the control in the Scene Builder
    • Add the @FXML annotation above the class variable and event handler that corresponds to the control in the Scene Builder
    • E.g. for a Button the Scene Builder we would add this in the controller class


1
2
3
4
5
6
7
8
9



@FXML
private Button btnClick;

@FXML
private void handleButtonAction(ActionEvent event) {
    int val = Integer.parseInt(txtNumber.getText());
    val++;
    lblNumber.set(Intger.toString(val));
}
  • You would use the variable name of your choice

The JavaFX Controller Class

  • The class variable and event handler method need to be linked to the corresponding component in the Scene Builder

JavaFXController

  • View JavaFX controller class, listing 12.15 class JavaFXAppController

OutputJavaFXController

  • Sample Output of Final Program

Summary

  • Java Class Library includes ArrayList
    • Like an array that grow in length
    • Includes methods to manipulate the list
  • Java Collections Framework contains many classes to store and manipulate objects
  • Linked list data structure contains nodes (objects)
  • Linked data structure is self-contained by making the node class an inner class
  • Variable or object which allows stepping through linked list called an iterator
  • Class can be declared with type parameter
  • Object of a parameterized class replaces type parameter with an actual class type
  • Classes ArrayList, HashSet, HashMap, and LinkedList are parameterized classes
  • The Scene Builder provides a graphical way to construct JavaFX applications.

Powerpoint

View presentation