Home > Store

Data Structures and Abstractions with Java, 4th Edition

Register your product to gain access to bonus material or receive a coupon.

Data Structures and Abstractions with Java, 4th Edition


  • Sorry, this book is no longer in print.
Not for Sale



Aid comprehension and facilitate teaching with an approachable format and content organization

  • Material is organized into small segments that focus a reader’s attention and provide greater instructional flexibility.
  • Unique object-oriented presentation separates the specification and use of a data collection from its implementation, and presents each in their own brief chapters.
  • Each ADT is introduced in its own chapter, including examples or applications. To make it easier for students to learn and retain each ADT concept, Carrano covers specification and implementation of each ADT in separate, but consecutive chapters. This grants instructors flexibility in their teaching approach, while retaining the advantage of separation of specification and implementation.
  • Flexible and extensive assignments include a variety of exercises and programming projects that can be used in- class or assigned as homework, as well as self-test questions throughout each chapter.
  • The visually appealing, attractive design includes many figures and simple illustrations to provide students with a more thorough understanding of the concepts. 

Keep your course current with updated material

  • NEW: Class design is covered in a new Prelude, which is positioned between the Introduction and Chapter 1.
  • NEW: Safe and secure programming is a new topic introduced in Chapter 2 and discussed in new Security Notes that are relevant to the implementations of the ADTs. The code throughout the book has been revised to reflect this subject matter.
  • UPDATED: Beginning with stacks in Chapter 5, most ADT methods now indicate failure by throwing an exception. Methods only return null in such cases when null cannot be a data value within a collection.
  • UPDATED: Additional coverage of generics treats generic methods and bounded types.
  • UPDATED: Illustrations show objects specifically instead of as values within nodes or array elements.
  • UPDATED: Vector-based implementations of the ADT list and queue are no longer covered, but are left as programming projects.
  • NEW: Line numbers appear in program listings.
  • UPDATED: All of the Java code is Java 8 compliant.

Support learning with student-friendly pedagogy

  • Help reinforce and test student understanding for sustained learning
    • NEW: Java Interludes – Relevant aspects of Java are covered in new Java Interludes that occur throughout the text. Java Interlude topics include: Generics; Exceptions; More About Generics; More About Exceptions; Iterators; Mutable and Immutable Objects; Inheritance; Generics Once Again; and Cloning.
    • Notes – Important ideas are presented or summarized in highlighted paragraphs that are meant to be read in line with the surrounding text.
    • Programming Tips – Suggestions to improve or facilitate programming are featured as soon as they become relevant.
    • Examples – Numerous examples illuminate new concepts.
    • Self-Test Questions – Questions are integrated within the text, throughout each chapter, to reinforce the concept just presented and help students understand the material. The reader must pause and reflect on the material to answer the question(s). Solutions to the self-test questions are provided at the end of each chapter.
    • VideoNotes – Step-by-step video tutorials are specifically designed to enhance the programming concepts presented in Carrano, Data Structures and Abstractions with Java, 4e. Students can view the entire problem-solving process outside of the classroom–when they need help the most. VideoNotes are available with the purchase of a new copy of select titles. Go to www.pearsonhighered.com/videonotes for a brief VideoNotes demo.
    • Exercises and Programming Projects – Further practice is available by solving the exercises and programming projects at the end of each chapter.
  • Teach students how to think critically about which DS is best to solve particular problems
    • A Problem Solved – Large examples are presented in the form of A Problem Solved,in which a problem is posed and its solution is discussed, designed, and implemented.
    • Design Decisions – To give readers insight into the design choices that one could make when formulating a solution, “Design Decision” elements lay out such options, along with the rationale behind the choice made for a particular example. These discussions are often in the context of one of the A Problem Solved examples.
      • UPDATED: Additional Design Decisions continue to present the options one has when specifying and implementing particular ADTs and provide the rationale behind our choices.
  • Complete instructor support package – Solutions Manuals, animations of various data structures, Lab Manual, and PowerPoint slides are available to instructors.
    • NEW: Instructor supplements now include a Test Bank.
  • Companion Web site – All of the Java code from the text, PowerPoint slides, and animations are available to students on the companion web site: www.pearsonhighered.com/carrano  
  • Frank’s Making it Real blog http://frank-m-carrano.com/blog/ extends his textbooks and lectures to a lively discussion with instructors and students about teaching and learning computer science.


  • Copyright 2015
  • Dimensions: 8" x 10"
  • Pages: 928
  • Edition: 4th
  • Book
  • ISBN-10: 0-13-374405-1
  • ISBN-13: 978-0-13-374405-7

Data Structures and Abstractions with Java is suitable for one- or two-semester courses in data structures (CS-2) in the departments of Computer Science, Computer Engineering, Business, and Management Information Systems. This book is also useful for programmers and software engineers interested in learning more about data structures and abstractions.


This is the most student-friendly data structures text available that introduces ADTs in individual, brief chapters — each with pedagogical tools to help students master each concept. Using the latest features of Java, this unique object-oriented presentation makes a clear distinction between specification and implementation to simplify learning, while providing maximum classroom flexibility.

Teaching and Learning Experience

This book will provide a better teaching and learning experience—for you and your students. It will help:

  • Aid comprehension and facilitate teaching with an approachable format and content organization: Material is organized into small segments that focus a reader’s attention and provide greater instructional flexibility.
  • Support learning with student-friendly pedagogy: In-text and online features help students master the material.

Sample Content

Table of Contents

Prelude: Designing Classes
Specifying Methods
Preconditions and Postconditions
Java Interfaces
Writing an Interface
Implementing an Interface
An Interface as a Data Type
Extending an Interface
Interfaces Versus Abstract Classes
Named Constants Within an Interface
Choosing Classes
Identifying Classes
CRC Cards
The Unifed Modeling Language
Reusing Classes
Chapter 1: Bags
The Bag
A Bag’s Behaviors
Specifying a Bag
An Interface
Using the ADT Bag
Using an ADT Is Like Using a Vending Machine
The ADT Set
Java Interlude 1: Generics
Generic Data Types
Generic Types Within an Interface
Generic Classes
Chapter 2: Bag Implementations That Use Arrays
Using a Fixed-Size Array to Implement the ADT Bag
An Analogy
A Group of Core Methods
Implementing the Core Methods
Making the Implementation Secure
Testing the Core Methods
Implementing More Methods
Methods That Remove Entries
Using Array Resizing to Implement the ADT Bag
Resizing an Array
A New Implementation of a Bag
The Pros and Cons of Using an Array to Implement the ADT Bag
Java Interlude 2: Exceptions
The Basics
Handling an Exception
Postpone Handling: The throws Clause
Handle It Now: The try-catch Blocks
Multiple catch Blocks
Throwing an Exception
Chapter 3: A Bag Implementation That Links Data
Linked Data
Forming a Chain by Adding to Its Beginning
A Linked Implementation of the ADT Bag
The Private Class Node
An Outline of the Class LinkedBag
Defning Some Core Methods
Testing the Core Methods
The Method getFrequencyOf
The Method contains
Removing an Item from a Linked Chain
The Methods remove and clear
A Class Node That Has Set and Get Methods
The Pros and Cons of Using a Chain to Implement the ADT Bag
Chapter 4: The Effciency of Algorithms
Measuring an Algorithm’s Effciency
Counting Basic Operations
Best, Worst, and Average Cases
Big Oh Notation
The Complexities of Program Constructs
Picturing Effciency
The Effciency of Implementations of the ADT Bag
An Array-Based Implementation
A Linked Implementation
Comparing the Implementations
Chapter 5: Stacks
Specifcations of the ADT Stack
Using a Stack to Process Algebraic Expressions
A Problem Solved: Checking for Balanced Delimiters in an Infx Algebraic Expression
A Problem Solved: Transforming an Infx Expression to a Postfx Expression
A Problem Solved: Evaluating Postfx Expressions
A Problem Solved: Evaluating Infx Expressions
The Program Stack
Java Class Library: The Class Stack
Chapter 6: Stack Implementations
A Linked Implementation
An Array-Based Implementation
A Vector-Based Implementation
Java Class Library: The Class Vector
Using a Vector to Implement the ADT Stack
Chapter 7: Recursion
What Is Recursion?
Tracing a Recursive Method
Recursive Methods That Return a Value
Recursively Processing an Array
Recursively Processing a Linked Chain
The Time Effciency of Recursive Methods
The Time Effciency of countDown
The Time Effciency of Computing xn
A Simple Solution to a Diffcult Problem
A Poor Solution to a Simple Problem
Tail Recursion
Indirect Recursion
Using a Stack Instead of Recursion
Java Interlude 3: More About Generics
The Interface Comparable
Generic Methods
Bounded Type Parameters
Bounded Wildcards
Chapter 8: An Introduction to Sorting
Organizing Java Methods That Sort an Array
Selection Sort
Iterative Selection Sort
Recursive Selection Sort
The Effciency of Selection Sort
Insertion Sort
Iterative Insertion Sort
Recursive Insertion Sort
The Effciency of Insertion Sort
Insertion Sort of a Chain of Linked Nodes
Shell Sort
The Java Code
The Effciency of Shell Sort
Comparing the Algorithms
Chapter 9: Faster Sorting Methods
Merge Sort
Merging Arrays
Recursive Merge Sort
The Effciency of Merge Sort
Iterative Merge Sort
Merge Sort in the Java Class Library
Quick Sort
The Effciency of Quick Sort
Creating the Partition
Implementing Quick Sort
Quick Sort in the Java Class Library
Radix Sort
Pseudocode for Radix Sort
The Effciency of Radix Sort
Comparing the Algorithms
Java Interlude 4: More About Exceptions
Programmer-Defned Exception Classes
Inheritance and Exceptions
The finally Block
Chapter 10: Queues, Deques, and Priority Queues
The ADT Queue
A Problem Solved: Simulating a Waiting Line
A Problem Solved: Computing the Capital Gain in a Sale of Stock
Java Class Library: The Interface Queue
The ADT Deque
A Problem Solved: Computing the Capital Gain in a Sale of Stock
Java Class Library: The Interface Deque
Java Class Library: The Class ArrayDeque
The ADT Priority Queue
A Problem Solved: Tracking Your Assignments
Java Class Library: The Class PriorityQueue
Chapter 11: Queue, Deque, and Priority Queue Implementations
A Linked Implementation of a Queue
An Array-Based Implementation of a Queue
A Circular Array
A Circular Array with One Unused Location
Circular Linked Implementations of a Queue
A Two-Part Circular Linked Chain
Java Class Library: The Class AbstractQueue
A Doubly Linked Implementation of a Deque
Possible Implementations of a Priority Queue
Chapter 12: Lists
Specifcations for the ADT List
Using the ADT List
Java Class Library: The Interface List
Java Class Library: The Class ArrayList
Chapter 13: A List Implementation That Uses an Array
Using an Array to Implement the ADT List
An Analogy
The Java Implementation
The Effciency of Using an Array to Implement the ADT List
Chapter 14: A List Implementation That Links Data
Operations on a Chain of Linked Nodes
Adding a Node at Various Positions
Removing a Node from Various Positions
The Private Method getNodeAt
Beginning the Implementation
The Data Fields and Constructor
Adding to the End of the List
Adding at a Given Position Within the List
The Methods isEmpty and toArray
Testing the Core Methods
Continuing the Implementation
A Refned Implementation
The Tail Reference
The Effciency of Using a Chain to Implement the ADT List
Java Class Library: The Class LinkedList
Java Interlude 5: Iterators
What Is an Iterator?
The Interface Iterator
The Interface Iterable
Using the Interface Iterator
Iterable and for-each Loops
The Interface ListIterator
The Interface List Revisited
Using the Interface ListIterator
Chapter 15: Iterators for the ADT List
Ways to Implement an Iterator
A Separate Class Iterator
An Inner Class Iterator
A Linked Implementation
An Array-Based Implementation
Why Are Iterator Methods in Their Own Class?
An Array-Based Implementation of the Interface ListIterator
The Inner Class
Java Interlude 6: Mutable and Immutable Objects
Mutable Objects
Immutable Objects
Creating a Read-Only Class
Companion Classes
Chapter 16: Sorted Lists
Specifcations for the ADT Sorted List
Using the ADT Sorted List
A Linked Implementation
The Method add
The Effciency of the Linked Implementation
An Implementation That Uses the ADT List
Effciency Issues
Java Interlude 7: Inheritance
Further Aspects of Inheritance
When to Use Inheritance
Protected Access
Abstract Classes and Methods
Chapter 17: Inheritance and Lists
Using Inheritance to Implement a Sorted List
Designing a Base Class
Creating an Abstract Base Class
An Effcient Implementation of a Sorted List
The Method add
Chapter 18: Searching
The Problem
Searching an Unsorted Array
An Iterative Sequential Search of an Unsorted Array
A Recursive Sequential Search of an Unsorted Array
The Effciency of a Sequential Search of an Array
Searching a Sorted Array
A Sequential Search of a Sorted Array
A Binary Search of a Sorted Array
Java Class Library: The Method binarySearch
The Effciency of a Binary Search of an Array
Searching an Unsorted Chain
An Iterative Sequential Search of an Unsorted Chain
A Recursive Sequential Search of an Unsorted Chain
The Effciency of a Sequential Search of a Chain
Searching a Sorted Chain
A Sequential Search of a Sorted Chain
A Binary Search of a Sorted Chain
Choosing a Search Method
Java Interlude 8: Generics Once Again
More Than One Generic Type
Chapter 19: Dictionaries
Specifcations for the ADT Dictionary
A Java Interface
Using the ADT Dictionary
A Problem Solved: A Directory of Telephone Numbers
A Problem Solved: The Frequency of Words
A Problem Solved: A Concordance of Words
Java Class Library: The Interface Map
Chapter 20: Dictionary Implementations
Array-Based Implementations
An Unsorted Array-Based Dictionary
A Sorted Array-Based Dictionary
Linked Implementations
An Unsorted Linked Dictionary
A Sorted Linked Dictionary
Chapter 21: Introducing Hashing
What Is Hashing?
Hash Functions
Computing Hash Codes
Compressing a Hash Code into an Index for the Hash Table
Resolving Collisions
Open Addressing with Linear Probing
Open Addressing with Quadratic Probing
Open Addressing with Double Hashing
A Potential Problem with Open Addressing
Separate Chaining
Chapter 22: Hashing as a Dictionary Implementation
The Effciency of Hashing
The Load Factor
The Cost of Open Addressing
The Cost of Separate Chaining
Comparing Schemes for Collision Resolution
A Dictionary Implementation That Uses Hashing
Entries in the Hash Table
Data Fields and Constructors
The Methods getValue, remove, and add
Java Class Library: The Class HashMap
Jave Class Library: The Class HashSet
Chapter 23: Trees
Tree Concepts
Hierarchical Organizations
Tree Terminology
Traversals of a Tree
Traversals of a Binary Tree
Traversals of a General Tree
Java Interfaces for Trees
Interfaces for All Trees
An Interface for Binary Trees
Examples of Binary Trees
Expression Trees
Decision Trees
Binary Search Trees
Examples of General Trees
Parse Trees
Game Trees
Chapter 24: Tree Implementations
The Nodes in a Binary Tree
A Class of Binary Nodes
An Implementation of the ADT Binary Tree
Creating a Basic Binary Tree
The Method privateSetTree
Accessor and Mutator Methods
Computing the Height and Counting Nodes
An Implementation of an Expression Tree
General Trees
A Node for a General Tree
Using a Binary Tree to Represent a General Tree
Java Interlude 9: Cloning
Cloneable Objects
Cloning an Array
Cloning a Chain
A Sorted List of Clones
Cloning a Binary Node
Chapter 25: A Binary Search Tree Implementation
Getting Started
An Interface for the Binary Search Tree
Duplicate Entries
Beginning the Class Defnition
Searching and Retrieving
Adding an Entry
A Recursive Implementation
An Iterative Implementation
Removing an Entry
Removing an Entry Whose Node Is a Leaf
Removing an Entry Whose Node Has One Child
Removing an Entry Whose Node Has Two Children
Removing an Entry in the Root
A Recursive Implementation
An Iterative Implementation
The Effciency of Operations
The Importance of Balance
The Order in Which Nodes Are Added
An Implementation of the ADT Dictionary
Chapter 26: A Heap Implementation
Reprise: The ADT Heap
Using an Array to Represent a Heap
Adding an Entry
Removing the Root
Creating a Heap
Heap Sort
Chapter 27: Balanced Search Trees
AVL Trees
Single Rotations
Double Rotations
Implementation Details
2-3 Trees
Searching a 2-3 Tree
Adding Entries to a 2-3 Tree
Splitting Nodes During Addition
2-4 Trees
Adding Entries to a 2-4 Tree
Comparing AVL, 2-3, and 2-4 Trees
Red-Black Trees
Properties of a Red-Black Tree
Adding Entries to a Red-Black Tree
Java Class Library: The Class TreeMap
Chapter 28: Graphs
Some Examples and Terminology
Road Maps
Airline Routes
Course Prerequisites
Breadth-First Traversal
Depth-First Traversal
Topological Order
Finding a Path
The Shortest Path in an Unweighted Graph
The Shortest Path in a Weighted Graph
Java Interfaces for the ADT Graph
Chapter 29: Graph Implementations
An Overview of Two Implementations
The Adjacency Matrix
The Adjacency List
Vertices and Edges
Specifying the Class Vertex
The Inner Class Edge
Implementing the Class Vertex
An Implementation of the ADT Graph
Basic Operations
Graph Algorithms
Appendix A: Documentation and Programming Style
Naming Variables and Classes
Single-Line Comments
Comment Blocks
When to Write Comments
Java Documentation Comments
Appendix B: Java Basics (online)
Applications and Applets
Objects and Classes
A First Java Application Program
Elements of Java
Reserved Words
Primitive Types
Assignment Statements
Assignment Compatibilities
Type Casting
Arithmetic Operators and Expressions
Parentheses and Precedence Rules
Increment and Decrement Operators
Special Assignment Operators
Named Constants
The Class Math
Simple Input and Output Using the Keyboard and Screen
Screen Output
Keyboard Input Using the Class Scanner
The if-else Statement
Boolean Expressions
Nested Statements
Multiway if-else Statements
The Conditional Operator (Optional)
The switch Statement
The while Statement
The for Statement
The do-while Statement
Additional Loop Information
The Class String
Characters Within Strings
Concatenation of Strings
String Methods
The Class StringBuilder
Using Scanner to Extract Pieces of a String
Array Parameters and Returned Values
Initializing Arrays
Array Index Out of Bounds
Use of = and == with Arrays
Arrays and the For-Each Loop
Multidimensional Arrays
Wrapper Classes
Appendix C: Java Classes (online)
Objects and Classes
Using the Methods in a Java Class
References and Aliases
Defning a Java Class
Method Defnitions
Arguments and Parameters
Passing Arguments
A Defnition of the Class Name
The Method toString
Methods That Call Other Methods
Methods That Return an Instance of Their Class
Static Fields and Methods
Overloading Methods
Enumeration as a Class
The Java Class Library
Appendix D: Creating Classes from Other Classes
Invoking Constructors from Within Constructors
Private Fields and Methods of the Superclass
Overriding and Overloading Methods
Multiple Inheritance
Type Compatibility and Superclasses
The Class Object
Appendix E: File Input and Output (online)
Why Files?
The Kinds of Files
File Names
Text Files
Creating a Text File
Reading a Text File
Changing Existing Data in a Text File
Defning a Method to Open a Stream
Binary Files
Creating a Binary File of Primitive Data
Reading a Binary File of Primitive Data
Strings in a Binary File
Object Serialization
Glossary (online)


Submit Errata

More Information

Unlimited one-month access with your purchase
Free Safari Membership