1. Home
2. Computer Science & IT
4. Data Structures

# Data Structures and Algorithm Analysis in Java, 3rd edition

• Mark A. Weiss

3rd edition

Chosen format
View all

ISBN-13: 9780132835053

Includes: Unassigned

This product is not available in your country

• Unassigned

## Overview

Chapter 1 Introduction 1
1.1 What’s the Book About? 1
1.2 Mathematics Review 2
1.2.1 Exponents 3
1.2.2 Logarithms 3
1.2.3 Series 4
1.2.4 Modular Arithmetic 5
1.2.5 The P Word 6
1.3 A Brief Introduction to Recursion 8
1.4 Implementing Generic Components Pre-Java 5 12
1.4.1 Using Object for Genericity 13
1.4.2 Wrappers for Primitive Types 14
1.4.3 Using Interface Types for Genericity 14
1.4.4 Compatibility of Array Types 16
1.5 Implementing Generic Components Using Java 5 Generics 16
1.5.1 Simple Generic Classes and Interfaces 17
1.5.2 Autoboxing/Unboxing 18
1.5.3 The Diamond Operator 18
1.5.4 Wildcards with Bounds 19
1.5.5 Generic Static Methods 20
1.5.6 Type Bounds 21
1.5.7 Type Erasure 22
1.5.8 Restrictions on Generics 23
1.6 Function Objects 24
Summary 26
Exercises 26
References 28

Chapter 2 Algorithm Analysis 29
2.1 Mathematical Background 29
2.2 Model 32
2.3 What to Analyze 33
2.4 Running Time Calculations 35
2.4.1 A Simple Example 36
2.4.2 General Rules 36
2.4.3 Solutions for the Maximum Subsequence Sum Problem 39
2.4.4 Logarithms in the Running Time 45
2.4.5 A Grain of Salt 49
Summary 49
Exercises 50
References 55

Chapter 3 Lists, Stacks, and Queues 57
3.1 Abstract Data Types (ADTs) 57
3.2.1 Simple Array Implementation of Lists 58
3.3 Lists in the Java Collections API 61
3.3.1 Collection Interface 61
3.3.2 Iterators 61
3.3.3 The List Interface, ArrayList, and LinkedList 63
3.3.4 Example: Using remove on a LinkedList 65
3.3.5 ListIterators 67
3.4 Implementation of ArrayList 67
3.4.1 The Basic Class 68
3.4.2 The Iterator and Java Nested and Inner Classes 71
3.6.1 Stack Model 82
3.6.2 Implementation of Stacks 83
3.6.3 Applications 84
3.7.1 Queue Model 92
3.7.2 Array Implementation of Queues 92
3.7.3 Applications of Queues 95
Summary 96
Exercises 96

Chapter 4 Trees 101
4.1 Preliminaries 101
4.1.1 Implementation of Trees 102
4.1.2 Tree Traversals with an Application 103
4.2 Binary Trees 107
4.2.1 Implementation 108
4.2.2 An Example: Expression Trees 109
4.3 The Search Tree ADT–Binary Search Trees 112
4.3.1 contains 113
4.3.2 findMin and findMax 115
4.3.3 insert 116
4.3.4 remove 118
4.3.5 Average-Case Analysis 120
4.4 AVL Trees 123
4.4.1 Single Rotation 125
4.4.2 Double Rotation 128
4.5 Splay Trees 137
4.5.1 A Simple Idea (That Does Not Work) 137
4.5.2 Splaying 139
4.6 Tree Traversals (Revisited) 145
4.7 B-Trees 147
4.8 Sets and Maps in the Standard Library 152
4.8.1 Sets 152
4.8.2 Maps 153
4.8.3 Implementation of TreeSet and TreeMap 153
4.8.4 An Example That Uses Several Maps 154
Summary 160
Exercises 160
References 167

Chapter 5 Hashing 171
5.1 General Idea 171
5.2 Hash Function 172
5.3 Separate Chaining 174
5.4 Hash Tables Without Linked Lists 179
5.4.1 Linear Probing 179
5.4.3 Double Hashing 183
5.5 Rehashing 188
5.6 Hash Tables in the Standard Library 189
5.7 Hash Tables with Worst-Case O(1) Access 192
5.7.1 Perfect Hashing 193
5.7.2 Cuckoo Hashing 195
5.7.3 Hopscotch Hashing 205
5.8 Universal Hashing 211
5.9 Extendible Hashing 214
Summary 217
Exercises 218
References 222

Chapter 6 Priority Queues (Heaps) 225
6.1 Model 225
6.2 Simple Implementations 226
6.3 Binary Heap 226
6.3.1 Structure Property 227
6.3.2 Heap-Order Property 229
6.3.3 Basic Heap Operations 229
6.3.4 Other Heap Operations 234
6.4 Applications of Priority Queues 238
6.4.1 The Selection Problem 238
6.4.2 Event Simulation 239
6.5 d-Heaps 240
6.6 Leftist Heaps 241
6.6.1 Leftist Heap Property 241
6.6.

## For teachers

All the material you need to teach your courses.

Discover teaching material