Contents

• Preface

  Why Study Data Structures and AlgorithmsWhat You Need for This BookOrganization of the BookConventions Used in This BookUsing Code ExamplesSafari® Books OnlineHow to Contact UsContent UpdatesOctober 20, 2015Acknowledgments

• 1. The JavaScript Programming Environment and Model

  The JavaScript EnvironmentJavaScript Programming PracticesDeclaring and Initializing VariablesArithmetic and Math Library Functions in JavaScriptDecision ConstructsRepetition ConstructsFunctionsVariable ScopeRecursionObjects and Object-Oriented ProgrammingSummary

• 2. Arrays

  JavaScript Arrays DefinedUsing ArraysCreating ArraysAccessing and Writing Array ElementsCreating Arrays from StringsAggregate Array OperationsAccessor FunctionsSearching for a ValueString Representations of ArraysCreating New Arrays from Existing ArraysMutator FunctionsAdding Elements to an ArrayRemoving Elements from an ArrayAdding and Removing Elements from the Middle of an ArrayPutting Array Elements in OrderIterator FunctionsNon–Array-Generating Iterator FunctionsIterator Functions That Return a New ArrayTwo-Dimensional and Multidimensional ArraysCreating Two-Dimensional ArraysProcessing Two-Dimensional Array ElementsJagged ArraysArrays of ObjectsArrays in ObjectsExercises

• 3. Lists

  A List ADTA List Class ImplementationAppend: Adding an Element to a ListRemove: Removing an Element from a ListFind: Finding an Element in a ListLength: Determining the Number of Elements in a ListtoString: Retrieving a List’s ElementsInsert: Inserting an Element into a ListClear: Removing All Elements from a ListContains: Determining if a Given Value Is in a ListMoving To and Retrieving a List ElementIterating Through a ListIterating Through a ListA List-Based ApplicationReading Text FilesUsing Lists to Manage a KioskExercises

• 4. Stacks

  Stack OperationsA Stack ImplementationUsing the Stack ClassMultiple Base ConversionsPalindromesDemonstrating RecursionExercises

• 5. Queues

  Queue OperationsAn Array-Based Queue Class ImplementationUsing the Queue Class: Assigning Partners at a Square DanceSorting Data with QueuesPriority QueuesExercises

• 6. Linked Lists

  Shortcomings of ArraysLinked Lists DefinedAn Object-Based Linked List DesignThe Node ClassThe Linked List ClassInserting New NodesRemoving Nodes from a Linked ListDoubly Linked ListsCircularly Linked ListsOther Linked List FunctionsExercises

• 7. Dictionaries

  The Dictionary ClassAuxiliary Functions for the Dictionary ClassAdding Sorting to the Dictionary ClassExercises

• 8. Hashing

  An Overview of HashingA Hash Table ClassChoosing a Hash FunctionA Better Hash FunctionHashing Integer KeysStoring and Retrieving Data in a Hash TableHandling CollisionsSeparate ChainingLinear ProbingExercises

• 9. Sets

  Fundamental Set Definitions, Operations, and PropertiesSet DefinitionsSet OperationsThe Set Class ImplementationMore Set OperationsExercises

• 10. Binary Trees and Binary Search Trees

  Trees DefinedBinary Trees and Binary Search TreesBuilding a Binary Search Tree ImplementationTraversing a Binary Search TreeBST SearchesSearching for the Minimum and Maximum ValueSearching for a Specific ValueRemoving Nodes from a BSTCounting OccurrencesExercises

• 11. Graphs and Graph Algorithms

  Graph DefinitionsReal-World Systems Modeled by GraphsThe Graph ClassRepresenting EdgesBuilding a GraphSearching a GraphDepth-First SearchBreadth-First SearchFinding the Shortest PathBreadth-First Search Leads to Shortest PathsDetermining PathsTopological SortingAn Algorithm for Topological SortingImplementing the Topological Sorting AlgorithmExercises

• 12. Sorting Algorithms

  An Array Test BedGenerating Random DataBasic Sorting AlgorithmsBubble SortSelection SortInsertion SortTiming Comparisons of the Basic Sorting AlgorithmsAdvanced Sorting AlgorithmsThe Shellsort AlgorithmThe Mergesort AlgorithmThe Quicksort AlgorithmExercises

• 13. Searching Algorithms

  Commonly Used Functions in ExamplesSearching for Minimum and Maximum ValuesUsing Self-Organizing DataBinary SearchCounting OccurrencesSearching Textual DataExercises

• 14. Advanced Algorithms

  Dynamic ProgrammingA Dynamic Programming Example: Computing Fibonacci NumbersFinding the Longest Common SubstringThe Knapsack Problem: A Recursive SolutionThe Knapsack Problem: A Dynamic Programming SolutionGreedy AlgorithmsA First Greedy Algorithm Example: The Coin-Changing ProblemA Greedy Algorithm Solution to the Knapsack ProblemExercises

• Index