1．The JavaScript Programming Environment and Model 1
The JavaScript Environment 1
JavaScript Programming Practices 2
Declaring and Initializing Variables 3
Arithmetic and Math Library Functions in JavaScript 3
Decision Constructs 4
Repetition Constructs 6
Functions 7
Variable Scope 8
Recursion 10
Objects and Object-Oriented Programming 11
Summary 12
2．Arrays 13
JavaScript Arrays Defined 13
Using Arrays 14
Creating Arrays 14
Accessing and Writing Array Elements 15
Creating Arrays from Strings 15
Aggregate Array Operations 16
Accessor Functions 17
Searching for a Value 18
String Representations of Arrays 18
Creating New Arrays from Existing Arrays 19
Mutator Functions 20
Adding Elements to an Array 20
Removing Elements from an Array 21
Adding and Removing Elements from the Middle of an Array 21
Putting Array Elements in Order 22
Iterator Functions 23
Non-Array-Generating Iterator Functions 23
Iterator Functions That Return a New Array 26
Two-Dimensional and Multidimensional Arrays 27
Creating Two-Dimensional Arrays 28
Processing Two-Dimensional Array Elements 28
Jagged Arrays 30
Arrays of Objects 31
Arrays in Objects 32
Exercises 33
3．Lists 35
A List ADT 35
A List Class Implementation 36
Append:Adding an Element to a List 37
Remove:Removing an Element from a List 37
Find:Finding an Element in a List 38
Length:Determining the Number of Elements in a List 38
toString:Retrieving a List's Elements 38
Insert:Inserting an Element into a List 39
Clear:Removing All Elements from a List 39
Contains:Determining if a Given Value Is in a List 40
Moving To and Retrieving a List Element 40
Iterating Through a List 40
Iterating Through a List 42
A List-Based Application 43
Reading Text Files 43
Using Lists to Manage a Kiosk 44
Exercises 47
4．Stacks 49
Stack Operations 49
A Stack Implementation 50
Using the Stack Class 53
Multiple Base Conversions 53
Palindromes 54
Demonstrating Recursion 56
Exercises 57
5．Queues 59
Queue Operations 59
An Array-Based Queue Class Implementation 60
Using the Queue Class:Assigning Partners at a Square Dance 63
Sorting Data with Queues 67
Priority Queues 70
Exercises 73
6．Linked Lists 75
Shortcomings of Arrays 75
Linked Lists Defined 76
An Object-Based Linked List Design 77
The Node Class 77
The Linked List Class 78
Inserting New Nodes 78
Removing Nodes from a Linked List 80
Doubly Linked Lists 83
Circularly Linked Lists 87
Other Linked List Functions 88
Exercises 88
7．Dictionaries 91
The Dictionary Class 91
Auxiliary Functions for the Dictionary Class 93
Adding Sorting to the Dictionary Class 95
Exercises 96
8．Hashing 99
An Overview of Hashing 99
A Hash Table Class 100
Choosing a Hash Function 100
A Better Hash Function 103
Hashing Integer Keys 105
Storing and Retrieving Data in a Hash Table 108
Handling Collisions 109
Separate Chaining 109
Linear Probing 112
Exercises 113
9．Sets 115
Fundamental Set Definitions,Operations,and Properties 115
Set Definitions 115
Set Operations 116
The Set Class Implementation 116
More Set Operations 118
Exercises 122
10．Binary Trees and Binary Search Trees 123
Trees Defined 123
Binary Trees and Binary Search Trees 125
Building a Binary Search Tree Implementation 126
Traversing a Binary Search Tree 128
BST Searches 131
Searching for the Minimum and Maximum Value 132
Searching for a Specific Value 133
Removing Nodes from a BST 134
Counting Occurrences 136
Exercises 139
11．Graphs and Graph Algorithms 141
Graph Definitions 141
Real-World Systems Modeled by Graphs 143
The Graph Class 143
Representing Edges 143
Building a Graph 144
Searching a Graph 146
Depth-First Search 146
Breadth-First Search 148
Finding the Shortest Path 150
Breadth-First Search Leads to Shortest Paths 150
Determining Paths 151
Topological Sorting 152
An Algorithm for Topological Sorting 153
Implementing the Topological Sorting Algorithm 153
Exercises 158
12．Sorting Algorithms 159
An Array Test Bed 159
Generating Random Data 161
Basic Sorting Algorithms 161
Bubble Sort 162
Selection Sort 165
Insertion Sort 167
Timing Comparisons of the Basic Sorting Algorithms 168
Advanced Sorting Algorithms 171
The Shellsort Algorithm 171
The Mergesort Algorithm 176
The Quicksort Algorithm 181
Exercises 186
13．Searching Algorithms 187
Commonly Used Functions in Examples 187
Searching for Minimum and Maximum Values 190
Using Self-Organizing Data 193
Binary Search 197
Counting Occurrences 201
Searching Textual Data 204
Exercises 207
14．Advanced Algorithms 209
Dynamic Programming 209
A Dynamic Programming Example:Computing Fibonacci Numbers 210
Finding the Longest Common Substring 213
The Knapsack Problem:A Recursive Solution 216
The Knapsack Problem:A Dynamic Programming Solution 217
Greedy Algorithms 219
A First Greedy Algorithm Example:The Coin-Changing Problem 219
A Greedy Algorithm Solution to the Knapsack Problem 220
Exercises 222
Index 225