Chapter 12: Data Structures

Presentation slides for

Java Software Solutions

Foundations of Program Design

Third Edition

by John Lewis and William Loftus

Java Software Solutions is published by Addison-Wesley

Presentation slides are copyright 2002 by John Lewis and William Loftus. All rights reserved.

Instructors using the textbook may use and modify these slides for pedagogical purposes.

Data Structures

Now we can now explore some convenient techniques for organizing and managing information

Chapter 12 focuses on:

collections

Abstract Data Types (ADTs)

dynamic structures and linked lists

queues and stacks

non-linear data structures

predefined collection classes

Collections

A collection is an object that serves as a repository for other objects

A collection usually provides services such as adding, removing, and otherwise managing the elements it contains

Sometimes the elements in a collection are ordered, sometimes they are not

Sometimes collections are homogeneous, sometimes the are heterogeneous

Abstract Data Types

Collections can be implemented in many different ways

An abstract data type (ADT) is an organized collection of information and a set of operations used to manage that information

The set of operations defines the interface to the ADT

As long as the ADT fulfills the promises of the interface, it doesn't really matter how the ADT is implemented

Objects are a perfect programming mechanism to create ADTs because their internal details are encapsulated

Abstraction

Our data structures should be abstractions

That is, they should hide unneeded details

We want to separate the interface of the structure from its underlying implementation

This helps manage complexity and makes it possible to change the implementation without changing the interface

Static vs. Dynamic Structures

A static data structure has a fixed size

This meaning is different from the meaning of the static modifier

Arrays are static; once you define the number of elements it can hold, the number doesn’t change

A dynamic data structure grows and shrinks at execution time as required by its contents

A dynamic data structure is implemented using links

Object References

Recall that an object reference is a variable that stores the address of an object

A reference also can be called a pointer

References often are depicted graphically:

References as Links

Object references can be used to create links between objects

Suppose a Student class contains a reference to another Student object

References as Links

References can be used to create a variety of linked structures, such as a linked list:

Intermediate Nodes

The objects being stored should not be concerned with the details of the data structure in which they may be stored

For example, the Student class should not have to store a link to the next Student object in the list

Instead, we can use a separate node class with two parts: 1) a reference to an independent object and 2) a link to the next node in the list

The internal representation becomes a linked list of nodes

Magazine Collection

Let’s explore an example of a collection of Magazine objects

The collection is managed by the MagazineList class, which has an private inner class called MagazineNode

Because the MagazineNode is private to MagazineList, the MagazineList methods can directly access MagazineNode data without violating encapsulation

See MagazineRack.java (page xxx)

See MagazineList.java (page xxx)

See Magazine.java (page xxx)

MagazineRack.java

MagazineList.java

Magazine.java

Magazine Collection

A method called insert could be defined to add a node anywhere in the list, to keep it sorted, for example

(Figure 12.2 here)

Magazine Collection

A method called delete could be defined to remove a node from the list

(Figure 12.3 here)

Other Dynamic List Representations

It may be convenient to implement as list as a doubly linked list, with next and previous references

Other Dynamic List Implementations

It may be convenient to use a separate header node, with a count and references to both the front and rear of the list

Other Dynamic List Implementations

A linked list can be circularly linked in which case the last node in the list points to the first node in the list

If the linked list is doubly linked, the first node in the list also points to the last node in the list

The representation should facilitate the intended operations and should make them easy to implement

Classic Data Structures

Classic linear data structures include queues and stacks

Classic nonlinear data structures include trees, binary trees, graphs, and digraphs

Queues

A queue is similar to a list but adds items only to the rear of the list and removes them only from the front

It is called a FIFO data structure: First-In, First-Out

Analogy: a line of people at a bank teller’s window

Queues

We can define the operations for a queue

enqueue - add an item to the rear of the queue

dequeue (or serve) - remove an item from the front of the queue

empty - returns true if the queue is empty

As with our linked list example, by storing generic Object references, any object can be stored in the queue

Queues often are helpful in simulations or any situation in which items get “backed up” while awaiting processing

Queues

A queue can be represented by a singly-linked list; it is most efficient if the references point from the front toward the rear of the queue

A queue can be represented by an array, using the mod operator (%) to “wrap around” when the end of the array is reached and space is available at the front of the array

Stacks

A stack ADT is also linear, like a list or a queue

Items are added and removed from only one end of a stack

It is therefore LIFO: Last-In, First-Out

Analogies: a stack of plates in a cupboard, a stack of bills to be paid, or a stack of hay bales in a barn

Stacks

Stacks often are drawn vertically:

Stacks

Some stack operations:

push - add an item to the top of the stack

pop - remove an item from the top of the stack

peek (or top) - retrieves the top item without removing it

empty - returns true if the stack is empty

A stack can be represented by a singly-linked list; it doesn’t matter whether the references point from the top toward the bottom or vice versa

A stack can be represented by an array, but the new item should be placed in the next available place in the array rather than at the end of the array

Stacks

The java.util package contains a Stack class

Like ArrayList operations, the Stack operations operate on Object references

See Decode.java (page xxx)

Decode.java

Trees and Binary Trees

A tree is a non-linear data structure that consists of a root node and potentially many levels of additional nodes that form a hierarchy

Nodes that have no children are called leaf nodes

Nodes except for the root and leaf nodes are called internal nodes

(Figure 12.8 here)

Trees and Binary Trees

A binary tree is defined recursively. Either it is empty (the base case) or it consists of a root and two subtrees, each of which is a binary tree

Binary trees and trees typically are represented using references as dynamic links, though it is possible to use fixed representations like arrays

Graphs and Digraphs

A graph is a non-linear structure

Unlike a tree or binary tree, a graph does not have a root

Any node in a graph can be connected to any other node by an edge

Analogy: the highway system connecting cities on a map

(Figure 12.9 here)

Graphs and Digraphs

In a directed graph or digraph, each edges has a specific direction.

Edges with direction sometimes are called arcs

Analogy: airline flights between airports

(Figure 12.10 here)

Graphs and Digraphs

Both graphs and digraphs can be represented using dynamic links or using arrays.

As always, the representation should facilitate the intended operations and make them convenient to implement

Collection Classes

The Java standard library contains several classes that represent collections, often referred to as the Java Collections API

Their underlying implementation is implied in the class names such as ArrayList and LinkedList

Several interfaces are used to define operations on the collections, such as List, Set, SortedSet, Map, and SortedMap

Summary

Chapter 12 has focused on:

collections

Abstract Data Types (ADTs)

dynamic structures and linked lists

queues and stacks

non-linear data structures

predefined collection classes


	Presentation slides for

	Java Software Solutions
	Foundations of Program Design
	Third Edition

	by John Lewis and William Loftus

	Java Software Solutions is published by Addison-Wesley

	Presentation slides are copyright 2002 by John Lewis and William Loftus. All rights reserved.
	Instructors using the textbook may use and modify these slides for pedagogical purposes.


	Now we can now explore some convenient techniques for organizing and managing information

	Chapter 12 focuses on:
		collections
		Abstract Data Types (ADTs)
		dynamic structures and linked lists
		queues and stacks
		non-linear data structures
		predefined collection classes


	A collection is an object that serves as a repository for other objects

	A collection usually provides services such as adding, removing, and otherwise managing the elements it contains

	Sometimes the elements in a collection are ordered, sometimes they are not

	Sometimes collections are homogeneous, sometimes the are heterogeneous


	Collections can be implemented in many different ways

	An abstract data type (ADT) is an organized collection of information and a set of operations used to manage that information

	The set of operations defines the interface to the ADT

	As long as the ADT fulfills the promises of the interface, it doesn't really matter how the ADT is implemented

	Objects are a perfect programming mechanism to create ADTs because their internal details are encapsulated


	Our data structures should be abstractions

	That is, they should hide unneeded details

	We want to separate the interface of the structure from its underlying implementation

	This helps manage complexity and makes it possible to change the implementation without changing the interface


	A static data structure has a fixed size

	This meaning is different from the meaning of the static modifier

	Arrays are static; once you define the number of elements it can hold, the number doesn’t change

	A dynamic data structure grows and shrinks at execution time as required by its contents

	A dynamic data structure is implemented using links


	Recall that an object reference is a variable that stores the address of an object

	A reference also can be called a pointer

	References often are depicted graphically:


	Object references can be used to create links between objects

	Suppose a Student class contains a reference to another Student object


	References can be used to create a variety of linked structures, such as a linked list:


	The objects being stored should not be concerned with the details of the data structure in which they may be stored

	For example, the Student class should not have to store a link to the next Student object in the list

	Instead, we can use a separate node class with two parts: 1) a reference to an independent object and 2) a link to the next node in the list

	The internal representation becomes a linked list of nodes


	Let’s explore an example of a collection of Magazine objects

	The collection is managed by the MagazineList class, which has an private inner class called MagazineNode

	Because the MagazineNode is private to MagazineList, the MagazineList methods can directly access MagazineNode data without violating encapsulation

	See MagazineRack.java (page xxx)
	See MagazineList.java (page xxx)
	See Magazine.java (page xxx)


	A method called insert could be defined to add a node anywhere in the list, to keep it sorted, for example

	(Figure 12.2 here)


	A method called delete could be defined to remove a node from the list

	(Figure 12.3 here)


	It may be convenient to implement as list as a doubly linked list, with next and previous references


	It may be convenient to use a separate header node, with a count and references to both the front and rear of the list


	A linked list can be circularly linked in which case the last node in the list points to the first node in the list

	If the linked list is doubly linked, the first node in the list also points to the last node in the list

	The representation should facilitate the intended operations and should make them easy to implement


	Classic linear data structures include queues and stacks

	Classic nonlinear data structures include trees, binary trees, graphs, and digraphs


	A queue is similar to a list but adds items only to the rear of the list and removes them only from the front

	It is called a FIFO data structure: First-In, First-Out

	Analogy: a line of people at a bank teller’s window


	We can define the operations for a queue
		enqueue - add an item to the rear of the queue
		dequeue (or serve) - remove an item from the front of the queue
		empty - returns true if the queue is empty

	As with our linked list example, by storing generic Object references, any object can be stored in the queue

	Queues often are helpful in simulations or any situation in which items get “backed up” while awaiting processing


	A queue can be represented by a singly-linked list; it is most efficient if the references point from the front toward the rear of the queue

	A queue can be represented by an array, using the mod operator (%) to “wrap around” when the end of the array is reached and space is available at the front of the array


	A stack ADT is also linear, like a list or a queue

	Items are added and removed from only one end of a stack

	It is therefore LIFO: Last-In, First-Out

	Analogies: a stack of plates in a cupboard, a stack of bills to be paid, or a stack of hay bales in a barn


	Some stack operations:
		push - add an item to the top of the stack
		pop - remove an item from the top of the stack
		peek (or top) - retrieves the top item without removing it
		empty - returns true if the stack is empty

	A stack can be represented by a singly-linked list; it doesn’t matter whether the references point from the top toward the bottom or vice versa

	A stack can be represented by an array, but the new item should be placed in the next available place in the array rather than at the end of the array


	The java.util package contains a Stack class

	Like ArrayList operations, the Stack operations operate on Object references

	See Decode.java (page xxx)


	A tree is a non-linear data structure that consists of a root node and potentially many levels of additional nodes that form a hierarchy

	Nodes that have no children are called leaf nodes

	Nodes except for the root and leaf nodes are called internal nodes

	(Figure 12.8 here)


	A binary tree is defined recursively. Either it is empty (the base case) or it consists of a root and two subtrees, each of which is a binary tree

	Binary trees and trees typically are represented using references as dynamic links, though it is possible to use fixed representations like arrays


	A graph is a non-linear structure

	Unlike a tree or binary tree, a graph does not have a root

	Any node in a graph can be connected to any other node by an edge

	Analogy: the highway system connecting cities on a map

	(Figure 12.9 here)


	In a directed graph or digraph, each edges has a specific direction.

	Edges with direction sometimes are called arcs

	Analogy: airline flights between airports

	(Figure 12.10 here)


	Both graphs and digraphs can be represented using dynamic links or using arrays.

	As always, the representation should facilitate the intended operations and make them convenient to implement


	The Java standard library contains several classes that represent collections, often referred to as the Java Collections API

	Their underlying implementation is implied in the class names such as ArrayList and LinkedList

	Several interfaces are used to define operations on the collections, such as List, Set, SortedSet, Map, and SortedMap


	Chapter 12 has focused on:
		collections
		Abstract Data Types (ADTs)
		dynamic structures and linked lists
		queues and stacks
		non-linear data structures
		predefined collection classes