Collections - Java Software Solutions: Foundations of Program Design - page 636

Summary of Key Concepts

An object, with its well-defined interface, is a perfect mechanism for imple-
menting a collection.

■

The size of a dynamic data structure grows and shrinks as needed.

■

A dynamically linked list is managed by storing and updating references to
objects.

■

Insert and delete operations can be implemented by carefully manipulating
object references.

■

Many variations on the implementation of dynamically linked lists can be
defined.

■

A queue is a linear data structure that manages data in a first-in, first-out
manner.

■

A stack is a linear data structure that manages data in a last-in, first-out
manner.

■

A tree is a non-linear data structure that organizes data into a hierarchy.

■

A graph is a non-linear data structure that connects nodes using generic
edges.

■

The Java Collections API defines several collection classes implemented in
various ways.

■

The classes of the Java Collections API are implemented as generic types.

■

Generic classes ensure type compatibility among the objects stored by the
collection.

■

Exercises
Visit www.myprogramminglab.com to complete many of these Exercises
online and get instant feedback.
EX 13.1

Suppose current is a reference to a Node object and that it
currently refers to a specific node in a linked list. Show, in
pseudocode, the steps that would delete the node following
current from the list. Carefully consider the cases in which
current is referring to the first and last nodes in the list.

EX 13.2 Modify your answer to Exercise 13.1 assuming that the list was

set up as a doubly linked list, with both next and prev references.

EX 13.3 Suppose current and newNode are references to Node objects.

Assume current currently refers to a specific node in a linked