Data Structures and Algorithms with Bringing classic computing approaches to the Web

As an experienced javascript developer moving to server-side programming, you need to implement classic data structures and algorithms associated with conventional object-oriented languages like C# and Java. This practical guide shows you how to work hands-on with a variety of storage mechanisms—including linked lists, stacks, queues, and graphs—within the constraints of the javascript environment. Determine which data structures and algorithms are most appropriate for the problems you’re trying to solve, and understand the tradeoffs when using them in a javascript program. An overview of the javascript features used throughout the book is also included. This book covers: Arrays and lists: the most common data structures Stacks and queues: more complex list-like data structures Linked lists: how they overcome the shortcomings of arrays Dictionaries: storing data as key-value pairs Hashing: good for quick insertion and retrieval Sets: useful for storing unique elements that appear only once Binary Trees: storing data in a hierarchical manner Graphs and graph algorithms: ideal for modeling networks Algorithms: including those that help you sort or search data Advanced algorithms: dynamic programming and greedy algorithms Copyright 4 Table of Contents 5 Preface 11 Why Study Data Structures and Algorithms 11 What You Need for This Book 12 Organization of the Book 13 Conventions Used in This Book 14 Using Code Examples 14 Safari庐 Books Online 15 How to Contact Us 15 Acknowledgments 16 Chapter聽1.聽The JavaScript Programming Environment and Model 17 The JavaScript Environment 17 JavaScript Programming Practices 18 Declaring and Intializing Variables 19 Arithmetic and Math Library Functions in JavaScript 19 Decision Constructs 20 Repetition Constructs 22 Functions 23 Variable Scope 24 Recursion 26 Objects and Object-Oriented Programming 26 Summary 28 Chapter聽2.聽Arrays 29 JavaScript Arrays Defined 29 Using Arrays 29 Creating Arrays 30 Accessing and Writing Array Elements 31 Creating Arrays from Strings 31 Aggregate Array Operations 32 Accessor Functions 33 Searching for a Value 33 String Representations of Arrays 34 Creating New Arrays from Existing Arrays 34 Mutator Functions 35 Adding Elements to an Array 35 Removing Elements from an Array 36 Adding and Removing Elements from the Middle of an Array 37 Putting Array Elements in Order 38 Iterator Functions 39 Non鈥揂rray-Generating Iterator Functions 39 Iterator Functions That Return a New Array 41 Two-Dimensional and Multidimensional Arrays 43 Creating Two-Dimensional Arrays 43 Processing Two-Dimensional Array Elements 44 Jagged Arrays 46 Arrays of Objects 46 Arrays in Objects 47 Exercises 49 Chapter聽3.聽Lists 51 A List ADT 51 A List Class Implementation 52 Append: Adding an Element to a List 53 Remove: Removing an Element from a List 53 Find: Finding an Element in a List 54 Length: Determining the Number of Elements in a List 54 toString: Retrieving a List鈥檚 Elements 54 Insert: Inserting an Element into a List 55 Clear: Removing All Elements from a List 55 Contains: Determining if a Given Value Is in a List 56 Traversing a List 56 Iterating Through a List 57 A List-Based Application 58 Reading Text Files 58 Using Lists to Manage a Kiosk 59 Exercises 63 Chapter聽4.聽Stacks 65 Stack Operations 65 A Stack Implementation 66 Using the Stack Class 69 Multiple Base Conversions 69 Palindromes 70 Demonstrating Recursion 72 Exercises 73 Chapter聽5.聽Queues 75 Queue Operations 75 An Array-Based Queue Class Implementation 76 Using the Queue Class: Assigning Partners at a Square Dance 79 Sorting Data with Queues 83 Priority Queues 86 Exercises 88 Chapter聽6.聽Linked Lists 89 Shortcomings of Arrays 89 Linked Lists Defined 90 An Object-Based Linked List Design 91 The Node Class 91 The Linked List Class 92 Inserting New Nodes 92 Removing Nodes from a Linked List 94 Doubly Linked Lists 97 Circularly Linked Lists 101 Other Linked List Functions 102 Exercises 102 Chapter聽7.聽Dictionaries 105 The Dictionary Class 105 Auxiliary Functions for the Dictionary Class 107 Adding Sorting to the Dictionary Class 109 Exercises 110 Chapter聽8.聽Hashing 113 An Overview of Hashing 113 A Hash Table Class 114 Choosing a Hash Function 114 A Better Hash Function 117 Hashing Integer Keys 119 Storing and Retrieving Data in a Hash Table 122 Handling Collisions 123 Separate Chaining 123 Linear Probing 125 Exercises 127 Chapter聽9.聽Sets 129 Fundamental Set Definitions, Operations, and Properties 129 Set Definitions 129 Set Operations 130 The Set Class Implementation 130 More Set Operations 132 Exercises 136 Chapter聽10.聽Binary Trees and Binary Search Trees 137 Trees Defined 137 Binary Trees and Binary Search Trees 139 Building a Binary Search Tree Implementation 140 Traversing a Binary Search Tree 142 BST Searches 145 Searching for the Minimum and Maximum Value 146 Searching for a Specific Value 147 Removing Nodes from a BST 148 Counting Occurrences 150 Exercises 153 Chapter聽11.聽Graphs and Graph Algorithms 155 Graph Definitions 155 Real-World Systems Modeled by Graphs 157 The Graph Class 157 Representing Vertices 157 Representing Edges 158 Building a Graph 159 Searching a Graph 161 Depth-First Search 161 Breadth-First Search 164 Finding the Shortest Path 165 Breadth-First Search Leads to Shortest Paths 165 Determining Paths 166 Topological Sorting 167 An Algorithm for Topological Sorting 168 Implementing the Topological Sorting Algorithm 168 Exercises 173 Chapter聽12.聽Sorting Algorithms 175 An Array Test Bed 175 Generating Random Data 177 Basic Sorting Algorithms 177 Bubble Sort 178 Selection Sort 181 Insertion Sort 183 Timing Comparisons of the Basic Sorting Algorithms 184 Advanced Sorting Algorithms 186 The Shellsort Algorithm 187 The Mergesort Algorithm 192 The Quicksort Algorithm 197 Exercises 202 Chapter聽13.聽Searching Algorithms 203 Sequential Search 203 Searching for Minimum and Maximum Values 206 Using Self-Organizing Data 209 Binary Search 212 Counting Occurrences 216 Searching Textual Data 218 Exercises 221 Chapter聽14.聽Advanced Algorithms 223 Dynamic Programming 223 A Dynamic Programming Example: Computing Fibonacci Numbers 224 Finding the Longest Common Substring 227 The Knapsack Problem: A Recursive Solution 230 The Knapsack Problem: A Dynamic Programming Solution 231 Greedy Algorithms 233 A First Greedy Algorithm Example: The Coin-Changing Problem 233 A Greedy Algorithm Solution to the Knapsack Problem 234 Exercises 236 Index 237 About the Author 246 As an experienced JavaScript developer moving to server-side programming, you need to implement classic data structures and algorithms associated with conventional object-oriented languages like C# and Java. This practical guide shows you how to work hands-on with a variety of storage mechanisms—including linked lists, stacks, queues, and graphs—within the constraints of the JavaScript environment.Determine which data structures and algorithms are most appropriate for the problems you’re trying to solve, and understand the tradeoffs when using them in a JavaScript program. An overview of the JavaScript features used throughout the book is also included.This book covers:Arrays and lists: the most common data structuresStacks and queues: more complex list-like data structuresLinked lists: how they overcome the shortcomings of arraysDictionaries: storing data as key-value pairsHashing: good for quick insertion and retrievalSets: useful for storing unique elements that appear only onceBinary Trees: storing data in a hierarchical mannerGraphs and graph algorithms: ideal for modeling networksAlgorithms: including those that help you sort or search dataAdvanced algorithms: dynamic programming and greedy algorithms Annotation As an experienced JavaScript developer moving to server-side programming, you need to implement classic data structures and algorithms associated with conventional object-oriented languages like C♯ and Java. This practical guide shows you how to work hands-on with a variety of storage mechanismsincluding linked lists, stacks, queues, and graphswithin the constraints of the JavaScript environment. Determine which data structures and algorithms are most appropriate for the problems youre trying to solve, and understand the tradeoffs when using them in a JavaScript program. An overview of the JavaScript features used throughout the book is also included. This book covers:Arrays and lists: the most common data structuresStacks and queues: more complex list-like data structuresLinked lists: how they overcome the shortcomings of arraysDictionaries: storing data as key-value pairsHashing: good for quick insertion and retrievalSets: useful for storing unique elements that appear only onceBinary Trees: storing data in a hierarchical mannerGraphs and graph algorithms: ideal for modeling networksAlgorithms: including those that help you sort or search dataAdvanced algorithms: dynamic programming and greedy algorithms This practical guide shows you how to work hands-on with a variety of storage mechanisms - including linked lists, stacks, queues, and graphs - within the constraints of the JavaScript environment.