Page
1
JavaScript Data Structures and Algorithms An Introduction to Understanding and Implementing Core Data Structure and Algorithm Fundamentals — Sammie Bae
Page
2
JavaScript Data Structures and Algorithms An Introduction to Understanding and Implementing Core Data Structure and Algorithm Fundamentals Sammie Bae
Page
3
JavaScript Data Structures and Algorithms ISBN-13 (pbk): 978-1-4842-3987-2 ISBN-13 (electronic): 978-1-4842-3988-9 https://doi.org/10.1007/978-1-4842-3988-9 Library of Congress Control Number: 2019930417 Copyright © 2019 by Sammie Bae This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. Trademarked names, logos, and images may appear in this book. Rather than use a trademark symbol with every occurrence of a trademarked name, logo, or image we use the names, logos, and images only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. While the advice and information in this book are believed to be true and accurate at the date of publication, neither the authors nor the editors nor the publisher can accept any legal responsibility for any errors or omissions that may be made. The publisher makes no warranty, express or implied, with respect to the material contained herein. Managing Director, Apress Media LLC: Welmoed Spahr Acquisitions Editor: Louise Corrigan Development Editor: Chris Nelson Coordinating Editor: Nancy Chen Cover designed by eStudioCalamar Distributed to the book trade worldwide by Springer Science+Business Media New York, 233 Spring Street, 6th Floor, New York, NY 10013. Phone 1-800-SPRINGER, fax (201) 348-4505, e-mail orders-ny@springer- sbm.com, or visit www.springeronline.com. Apress Media, LLC is a California LLC and the sole member (owner) is Springer Science + Business Media Finance Inc (SSBM Finance Inc). SSBM Finance Inc is a Delaware corporation. For information on translations, please e-mail rights@apress.com, or visit www.apress.com/ rights-permissions. Apress titles may be purchased in bulk for academic, corporate, or promotional use. eBook versions and licenses are also available for most titles. For more information, reference our Print and eBook Bulk Sales web page at www.apress.com/bulk-sales. Any source code or other supplementary material referenced by the author in this book is available to readers on GitHub via the book’s product page, located at www.apress.com/9781484239872. For more detailed information, please visit www.apress.com/source-code. Printed on acid-free paper Sammie Bae Hamilton, ON, Canada
Page
4
This book is dedicated to Dr. Hamid R. Tizhoosh for inspiring me in my studies and to my mother, Min Kyoung Seo, for her kindness and support.
Page
5
v Table of Contents Chapter 1: Big-O Notation ����������������������������������������������������������������������������������������� 1 Big-O Notation Primer ������������������������������������������������������������������������������������������������������������������� 1 Common Examples ������������������������������������������������������������������������������������������������������������������ 2 Rules of Big-O Notation ����������������������������������������������������������������������������������������������������������������� 4 Coefficient Rule: “Get Rid of Constants” ���������������������������������������������������������������������������������� 5 Sum Rule: “Add Big-Os Up” ����������������������������������������������������������������������������������������������������� 6 Product Rule: “Multiply Big-Os” ���������������������������������������������������������������������������������������������� 7 Polynomial Rule: “Big-O to the Power of k”����������������������������������������������������������������������������� 8 Summary��������������������������������������������������������������������������������������������������������������������������������������� 8 Exercises ��������������������������������������������������������������������������������������������������������������������������������������� 9 Answers ��������������������������������������������������������������������������������������������������������������������������������� 11 Chapter 2: JavaScript: Unique Parts ����������������������������������������������������������������������� 13 JavaScript Scope ������������������������������������������������������������������������������������������������������������������������ 13 Global Declaration: Global Scope ������������������������������������������������������������������������������������������� 13 Declaration with var: Functional Scope ��������������������������������������������������������������������������������� 13 Declaration with let: Block Scope ������������������������������������������������������������������������������������������ 15 About the Author �����������������������������������������������������������������������������������������������������xv About the Technical Reviewer �������������������������������������������������������������������������������xvii Acknowledgments ��������������������������������������������������������������������������������������������������xix Introduction ������������������������������������������������������������������������������������������������������������xxi
Page
6
vi Equality and Types ���������������������������������������������������������������������������������������������������������������������� 16 Variable Types ������������������������������������������������������������������������������������������������������������������������ 16 Truthy/Falsey Check �������������������������������������������������������������������������������������������������������������� 17 === vs == ���������������������������������������������������������������������������������������������������������������������������� 18 Objects ���������������������������������������������������������������������������������������������������������������������������������� 18 Summary������������������������������������������������������������������������������������������������������������������������������������� 20 Chapter 3: JavaScript Numbers ������������������������������������������������������������������������������ 21 Number System �������������������������������������������������������������������������������������������������������������������������� 21 JavaScript Number Object ���������������������������������������������������������������������������������������������������������� 23 Integer Rounding ������������������������������������������������������������������������������������������������������������������� 23 Number�EPSILON ������������������������������������������������������������������������������������������������������������������� 24 Maximums ����������������������������������������������������������������������������������������������������������������������������� 24 Minimums ������������������������������������������������������������������������������������������������������������������������������ 25 Size Summary ����������������������������������������������������������������������������������������������������������������������� 26 Number Algorithms ���������������������������������������������������������������������������������������������������������������� 26 Prime Factorization ��������������������������������������������������������������������������������������������������������������� 28 Random Number Generator �������������������������������������������������������������������������������������������������������� 29 Exercises ������������������������������������������������������������������������������������������������������������������������������������� 29 Summary������������������������������������������������������������������������������������������������������������������������������������� 34 Chapter 4: JavaScript Strings ��������������������������������������������������������������������������������� 35 JavaScript String Primitive ��������������������������������������������������������������������������������������������������������� 35 String Access ������������������������������������������������������������������������������������������������������������������������� 35 String Comparison ����������������������������������������������������������������������������������������������������������������� 36 String Search ������������������������������������������������������������������������������������������������������������������������� 36 String Decomposition ������������������������������������������������������������������������������������������������������������ 38 String Replace ����������������������������������������������������������������������������������������������������������������������� 38 Regular Expressions ������������������������������������������������������������������������������������������������������������������� 38 Basic Regex ��������������������������������������������������������������������������������������������������������������������������� 39 Commonly Used Regexes ������������������������������������������������������������������������������������������������������ 39 Encoding ������������������������������������������������������������������������������������������������������������������������������������� 41 Base64 Encoding ������������������������������������������������������������������������������������������������������������������� 42 Table of ConTenTs
Page
7
vii String Shortening ������������������������������������������������������������������������������������������������������������������������ 43 Encryption ����������������������������������������������������������������������������������������������������������������������������������� 45 RSA Encryption ���������������������������������������������������������������������������������������������������������������������� 46 Summary ������������������������������������������������������������������������������������������������������������������������������� 50 Chapter 5: JavaScript Arrays���������������������������������������������������������������������������������� 53 Introducing Arrays ����������������������������������������������������������������������������������������������������������������������� 53 Insertion �������������������������������������������������������������������������������������������������������������������������������� 53 Deletion ��������������������������������������������������������������������������������������������������������������������������������� 54 Access ����������������������������������������������������������������������������������������������������������������������������������� 54 Iteration ��������������������������������������������������������������������������������������������������������������������������������������� 54 for (Variables; Condition; Modification) ��������������������������������������������������������������������������������� 55 for ( in ) ���������������������������������������������������������������������������������������������������������������������������������� 56 for ( of ) ���������������������������������������������������������������������������������������������������������������������������������� 56 forEach( ) �������������������������������������������������������������������������������������������������������������������������������� 56 Helper Functions ������������������������������������������������������������������������������������������������������������������������� 57 �slice(begin,end) �������������������������������������������������������������������������������������������������������������������� 57 � splice(begin,size,element1,element2…) ������������������������������������������������������������������������������ 58 � concat() ��������������������������������������������������������������������������������������������������������������������������������� 59 � length Property ��������������������������������������������������������������������������������������������������������������������� 59 Spread Operator �������������������������������������������������������������������������������������������������������������������� 60 Exercises ������������������������������������������������������������������������������������������������������������������������������������� 60 JavaScript Functional Array Methods ����������������������������������������������������������������������������������������� 67 Map���������������������������������������������������������������������������������������������������������������������������������������� 67 Filter �������������������������������������������������������������������������������������������������������������������������������������� 68 Reduce ���������������������������������������������������������������������������������������������������������������������������������� 68 Multidimensional Arrays ������������������������������������������������������������������������������������������������������������� 68 Exercises ������������������������������������������������������������������������������������������������������������������������������������� 71 Summary������������������������������������������������������������������������������������������������������������������������������������� 81 Table of ConTenTs
Page
8
viii Chapter 6: JavaScript Objects �������������������������������������������������������������������������������� 83 JavaScript Object Property ��������������������������������������������������������������������������������������������������������� 83 Prototypal Inheritance ����������������������������������������������������������������������������������������������������������������� 84 Constructor and Variables ����������������������������������������������������������������������������������������������������������� 85 Summary������������������������������������������������������������������������������������������������������������������������������������� 86 Exercises ������������������������������������������������������������������������������������������������������������������������������������� 87 Chapter 7: JavaScript Memory Management ��������������������������������������������������������� 89 Memory Leaks ���������������������������������������������������������������������������������������������������������������������������� 89 Reference to an Object ���������������������������������������������������������������������������������������������������������� 89 Leaking DOM ������������������������������������������������������������������������������������������������������������������������� 90 Global window Object ������������������������������������������������������������������������������������������������������������ 91 Limiting Object References ��������������������������������������������������������������������������������������������������� 92 The delete Operator ��������������������������������������������������������������������������������������������������������������� 92 Summary������������������������������������������������������������������������������������������������������������������������������������� 93 Exercises ������������������������������������������������������������������������������������������������������������������������������������� 93 Chapter 8: Recursion ���������������������������������������������������������������������������������������������� 99 Introducing Recursion ����������������������������������������������������������������������������������������������������������������� 99 Rules of Recursion �������������������������������������������������������������������������������������������������������������������� 100 Base Case ���������������������������������������������������������������������������������������������������������������������������� 100 Divide-and-Conquer Method ����������������������������������������������������������������������������������������������� 101 Classic Example: Fibonacci Sequence �������������������������������������������������������������������������������� 101 Fibonacci Sequence: Tail Recursion ������������������������������������������������������������������������������������ 102 Pascal’s Triangle ������������������������������������������������������������������������������������������������������������������ 103 Big-O for Recursion ������������������������������������������������������������������������������������������������������������������� 105 Recurrence Relations ���������������������������������������������������������������������������������������������������������� 105 Master Theorem ������������������������������������������������������������������������������������������������������������������ 106 Recursive Call Stack Memory ��������������������������������������������������������������������������������������������������� 107 Summary����������������������������������������������������������������������������������������������������������������������������������� 109 Exercises ����������������������������������������������������������������������������������������������������������������������������������� 109 Table of ConTenTs
Page
9
ix Chapter 9: Sets ����������������������������������������������������������������������������������������������������� 117 Introducing Sets ������������������������������������������������������������������������������������������������������������������������ 117 Set Operations �������������������������������������������������������������������������������������������������������������������������� 117 Insertion ������������������������������������������������������������������������������������������������������������������������������ 118 Deletion ������������������������������������������������������������������������������������������������������������������������������� 118 Contains ������������������������������������������������������������������������������������������������������������������������������� 118 Other Utility Functions��������������������������������������������������������������������������������������������������������������� 119 Intersection �������������������������������������������������������������������������������������������������������������������������� 119 isSuperSet ��������������������������������������������������������������������������������������������������������������������������� 119 Union ����������������������������������������������������������������������������������������������������������������������������������� 120 Difference ���������������������������������������������������������������������������������������������������������������������������� 120 Summary����������������������������������������������������������������������������������������������������������������������������������� 121 Exercises ����������������������������������������������������������������������������������������������������������������������������������� 122 Chapter 10: Searching and Sorting ���������������������������������������������������������������������� 125 Searching ���������������������������������������������������������������������������������������������������������������������������������� 125 Linear Search ���������������������������������������������������������������������������������������������������������������������� 125 Binary Search ���������������������������������������������������������������������������������������������������������������������� 127 Sorting �������������������������������������������������������������������������������������������������������������������������������������� 129 Bubble Sort �������������������������������������������������������������������������������������������������������������������������� 129 Selection Sort ���������������������������������������������������������������������������������������������������������������������� 131 Insertion Sort ����������������������������������������������������������������������������������������������������������������������� 132 Quicksort ����������������������������������������������������������������������������������������������������������������������������� 134 Quickselect �������������������������������������������������������������������������������������������������������������������������� 137 Mergesort ���������������������������������������������������������������������������������������������������������������������������� 138 Count Sort ���������������������������������������������������������������������������������������������������������������������������� 140 JavaScript’s Built-in Sort ����������������������������������������������������������������������������������������������������� 141 Summary����������������������������������������������������������������������������������������������������������������������������������� 142 Exercises ����������������������������������������������������������������������������������������������������������������������������������� 143 Table of ConTenTs
Page
10
x Chapter 11: Hash Tables ��������������������������������������������������������������������������������������� 151 Introducing Hash Tables ������������������������������������������������������������������������������������������������������������ 151 Hashing Techniques ������������������������������������������������������������������������������������������������������������������ 152 Prime Number Hashing ������������������������������������������������������������������������������������������������������� 152 Probing �������������������������������������������������������������������������������������������������������������������������������� 154 Rehashing/Double-Hashing ������������������������������������������������������������������������������������������������� 155 Hash Table Implementation ������������������������������������������������������������������������������������������������������� 156 Using Linear Probing ����������������������������������������������������������������������������������������������������������� 156 Using Quadratic Probing ������������������������������������������������������������������������������������������������������ 158 Using Double-Hashing with Linear Probing ������������������������������������������������������������������������� 160 Summary����������������������������������������������������������������������������������������������������������������������������������� 161 Chapter 12: Stacks and Queues ���������������������������������������������������������������������������� 163 Stacks ��������������������������������������������������������������������������������������������������������������������������������������� 163 Peek ������������������������������������������������������������������������������������������������������������������������������������� 165 Insertion ������������������������������������������������������������������������������������������������������������������������������ 165 Deletion ������������������������������������������������������������������������������������������������������������������������������� 166 Access ��������������������������������������������������������������������������������������������������������������������������������� 166 Search ��������������������������������������������������������������������������������������������������������������������������������� 167 Queues �������������������������������������������������������������������������������������������������������������������������������������� 167 Peek ������������������������������������������������������������������������������������������������������������������������������������� 169 Insertion ������������������������������������������������������������������������������������������������������������������������������ 169 Deletion ������������������������������������������������������������������������������������������������������������������������������� 169 Access ��������������������������������������������������������������������������������������������������������������������������������� 170 Search ��������������������������������������������������������������������������������������������������������������������������������� 171 Summary����������������������������������������������������������������������������������������������������������������������������������� 171 Exercises ����������������������������������������������������������������������������������������������������������������������������������� 172 Chapter 13: Linked Lists ��������������������������������������������������������������������������������������� 179 Singly Linked Lists �������������������������������������������������������������������������������������������������������������������� 179 Insertion ������������������������������������������������������������������������������������������������������������������������������ 180 Deletion by Value ����������������������������������������������������������������������������������������������������������������� 181 Table of ConTenTs
Page
11
xi Deletion at the Head ������������������������������������������������������������������������������������������������������������ 182 Search ��������������������������������������������������������������������������������������������������������������������������������� 183 Doubly Linked Lists ������������������������������������������������������������������������������������������������������������������� 184 Insertion at the Head ����������������������������������������������������������������������������������������������������������� 185 Insertion at the Tail �������������������������������������������������������������������������������������������������������������� 185 Deletion at the Head ������������������������������������������������������������������������������������������������������������ 186 Deletion at the Tail ��������������������������������������������������������������������������������������������������������������� 187 Search ��������������������������������������������������������������������������������������������������������������������������������� 188 Summary����������������������������������������������������������������������������������������������������������������������������������� 189 Exercises ����������������������������������������������������������������������������������������������������������������������������������� 190 Chapter 14: Caching ��������������������������������������������������������������������������������������������� 193 Understanding Caching ������������������������������������������������������������������������������������������������������������� 193 Least Frequently Used Caching ������������������������������������������������������������������������������������������������� 194 Least Recently Used Caching ���������������������������������������������������������������������������������������������������� 199 Summary����������������������������������������������������������������������������������������������������������������������������������� 203 Chapter 15: Trees �������������������������������������������������������������������������������������������������� 205 General Tree Structure �������������������������������������������������������������������������������������������������������������� 205 Binary Trees ������������������������������������������������������������������������������������������������������������������������������ 206 Tree Traversal ���������������������������������������������������������������������������������������������������������������������������� 207 Pre-order Traversal �������������������������������������������������������������������������������������������������������������� 207 In-Order Traversal ���������������������������������������������������������������������������������������������������������������� 209 Post-order Traversal ������������������������������������������������������������������������������������������������������������ 211 Level-Order Traversal ���������������������������������������������������������������������������������������������������������� 212 Tree Traversal Summary ������������������������������������������������������������������������������������������������������ 214 Binary Search Trees ������������������������������������������������������������������������������������������������������������������ 214 Insertion ������������������������������������������������������������������������������������������������������������������������������ 216 Deletion ������������������������������������������������������������������������������������������������������������������������������� 218 Search ��������������������������������������������������������������������������������������������������������������������������������� 220 Table of ConTenTs
Page
12
xii AVL Trees ����������������������������������������������������������������������������������������������������������������������������������� 221 Single Rotation �������������������������������������������������������������������������������������������������������������������� 221 Double Rotation ������������������������������������������������������������������������������������������������������������������� 225 Balancing the Tree ��������������������������������������������������������������������������������������������������������������� 228 Insertion ������������������������������������������������������������������������������������������������������������������������������ 229 Putting It All Together: AVL Tree Example ����������������������������������������������������������������������������� 231 Summary����������������������������������������������������������������������������������������������������������������������������������� 234 Exercises ����������������������������������������������������������������������������������������������������������������������������������� 234 Chapter 16: Heaps ������������������������������������������������������������������������������������������������ 245 Understanding Heaps ���������������������������������������������������������������������������������������������������������������� 245 Max-Heap ���������������������������������������������������������������������������������������������������������������������������� 246 Min-Heap ����������������������������������������������������������������������������������������������������������������������������� 247 Binary Heap Array Index Structure �������������������������������������������������������������������������������������������� 248 Percolation: Bubbling Up and Down ������������������������������������������������������������������������������������ 250 Implementing Percolation���������������������������������������������������������������������������������������������������� 253 Max-Heap Example ������������������������������������������������������������������������������������������������������������� 254 Min-Heap Complete Implementation ���������������������������������������������������������������������������������������� 258 Max-Heap Complete Implementation ��������������������������������������������������������������������������������������� 259 Heap Sort ���������������������������������������������������������������������������������������������������������������������������������� 261 Ascending-Order Sort (Min-Heap) ��������������������������������������������������������������������������������������� 261 Descending-Order Sort (Max-Heap) ������������������������������������������������������������������������������������ 264 Summary����������������������������������������������������������������������������������������������������������������������������������� 267 Exercises ����������������������������������������������������������������������������������������������������������������������������������� 268 Chapter 17: Graphs ����������������������������������������������������������������������������������������������� 273 Graph Basics ����������������������������������������������������������������������������������������������������������������������������� 273 Undirected Graphs �������������������������������������������������������������������������������������������������������������������� 277 Adding Edges and Vertices �������������������������������������������������������������������������������������������������� 279 Removing Edges and Vertices ��������������������������������������������������������������������������������������������� 280 Directed Graphs ������������������������������������������������������������������������������������������������������������������������ 282 Table of ConTenTs
Page
13
xiii Graph Traversal ������������������������������������������������������������������������������������������������������������������������� 285 Breadth-First Search ����������������������������������������������������������������������������������������������������������� 286 Depth-First Search �������������������������������������������������������������������������������������������������������������� 289 Weighted Graphs and Shortest Path ����������������������������������������������������������������������������������������� 293 Graphs with Weighted Edges ����������������������������������������������������������������������������������������������� 293 Dijkstra’s Algorithm: Shortest Path �������������������������������������������������������������������������������������� 294 Topological Sort ������������������������������������������������������������������������������������������������������������������������ 298 Summary����������������������������������������������������������������������������������������������������������������������������������� 300 Chapter 18: Advanced Strings ������������������������������������������������������������������������������ 303 Trie (Prefix Tree) ������������������������������������������������������������������������������������������������������������������������ 303 Boyer–Moore String Search ������������������������������������������������������������������������������������������������������ 307 Knuth–Morris–Pratt String Search �������������������������������������������������������������������������������������������� 311 Rabin–Karp Search ������������������������������������������������������������������������������������������������������������������� 316 The Rabin Fingerprint ���������������������������������������������������������������������������������������������������������� 316 Applications in Real Life ������������������������������������������������������������������������������������������������������ 319 Summary����������������������������������������������������������������������������������������������������������������������������������� 320 Chapter 19: Dynamic Programming ��������������������������������������������������������������������� 321 Motivations for Dynamic Programming������������������������������������������������������������������������������������� 321 Rules of Dynamic Programming ����������������������������������������������������������������������������������������������� 323 Overlapping Subproblems ��������������������������������������������������������������������������������������������������� 323 Optimal Substructure ���������������������������������������������������������������������������������������������������������� 323 Example: Ways to Cover Steps �������������������������������������������������������������������������������������������� 323 Classical Dynamic Programming Examples ������������������������������������������������������������������������������ 325 The Knapsack Problem �������������������������������������������������������������������������������������������������������� 325 Longest Common Subsequence ������������������������������������������������������������������������������������������ 328 Coin Change ������������������������������������������������������������������������������������������������������������������������ 330 Edit (Levenshtein) Distance ������������������������������������������������������������������������������������������������� 334 Summary����������������������������������������������������������������������������������������������������������������������������������� 338 Table of ConTenTs
Page
14
xiv Chapter 20: Bit Manipulation �������������������������������������������������������������������������������� 339 Bitwise Operators ��������������������������������������������������������������������������������������������������������������������� 339 AND �������������������������������������������������������������������������������������������������������������������������������������� 340 OR ���������������������������������������������������������������������������������������������������������������������������������������� 340 XOR �������������������������������������������������������������������������������������������������������������������������������������� 341 NOT �������������������������������������������������������������������������������������������������������������������������������������� 341 Left Shift ������������������������������������������������������������������������������������������������������������������������������ 342 Right Shift ���������������������������������������������������������������������������������������������������������������������������� 342 Zero-Fill Right Shift ������������������������������������������������������������������������������������������������������������� 343 Number Operations ������������������������������������������������������������������������������������������������������������������� 343 Addition ������������������������������������������������������������������������������������������������������������������������������� 343 Subtraction �������������������������������������������������������������������������������������������������������������������������� 344 Multiplication ����������������������������������������������������������������������������������������������������������������������� 345 Division �������������������������������������������������������������������������������������������������������������������������������� 347 Summary����������������������������������������������������������������������������������������������������������������������������������� 349 Index ��������������������������������������������������������������������������������������������������������������������� 351 Table of ConTenTs
Page
15
xv About the Author Sammie Bae is a data engineer at Yelp and previously worked for the data platform engineering team at NVIDIA. He developed a deep interest in JavaScript during an internship at SMART Technologies (acquired by Foxconn), where he developed Node.js-based JavaScript APIs for serial port communication between electronic board drivers and a web application. Despite how relevant JavaScript is to the modern software engineering industry, currently no books besides this one teach algorithms and data structures using JavaScript. Sammie understands how difficult these computer science concepts are and aims to provide clear and concise explanations in this book.
Page
16
xvii About the Technical Reviewer Phil Nash is a developer evangelist for Twilio, serving developer communities in London and all over the world. He is a Ruby, JavaScript, and Swift developer; Google Developers Expert; blogger; speaker; and occasional brewer. He can be found hanging out at meetups and conferences, playing with new technologies and APIs, or writing open source code.
Page
17
xix Acknowledgments Thank you, Phil Nash, for the valuable feedback that helped me improve the technical content of this book with clear explanations and concise code. Special thanks to the Apress team. This includes James Markham, Nancy Chen, Jade Scard, and Chris Nelson. Finally, I want to thank Steve Anglin for reaching out to me to publish with Apress.
Page
18
xxi Introduction The motivation for writing this book was the lack of resources available about data structures and algorithms written in JavaScript. This was strange to me because today many of the job opportunities for software development require knowledge of JavaScript; it is the only language that can be used to write the entire stack, including the front-end, mobile (native and hybrid) platforms, and back-end. It is crucial for JavaScript developers to understand how data structures work and how to design algorithms to build applications. Therefore, this book aims to teach data structure and algorithm concepts from computer science for JavaScript rather than for the more typical Java or C++. Because JavaScript follows the prototypal inheritance pattern, unlike Java and C++ (which follow the inheritance pattern), there are some changes in writing data structures in JavaScript. The classical inheritance pattern allows inheritance by creating a blueprint- like form that objects follow during inheritance. However, the prototypal inheritance pattern means copying the objects and changing their properties. This book first covers fundamental mathematics for Big-O analysis and then lays out the basic JavaScript foundations, such as primitive objects and types. Then, this book covers implementations and algorithms for fundamental data structures such as linked lists, stacks, trees, heaps, and graphs. Finally, more advanced topics such as efficient string search algorithms, caching algorithms, and dynamic programming problems are explored in great detail.
Page
19
1 © Sammie Bae 2019 S. Bae, JavaScript Data Structures and Algorithms, https://doi.org/10.1007/978-1-4842-3988-9_1 CHAPTER 1 Big-O Notation O(1) is holy. —Hamid Tizhoosh Before learning how to implement algorithms, you should understand how to analyze the effectiveness of them. This chapter will focus on the concept of Big-O notation for time and algorithmic space complexity analysis. By the end of this chapter, you will understand how to analyze an implementation of an algorithm with respect to both time (execution time) and space (memory consumed). Big-O Notation Primer The Big-O notation measures the worst-case complexity of an algorithm. In Big-O notation, n represents the number of inputs. The question asked with Big-O is the following: “What will happen as n approaches infinity?” When you implement an algorithm, Big-O notation is important because it tells you how efficient the algorithm is. Figure 1-1 shows some common Big-O notations.
Page
20
2 The following sections illustrate these common time complexities with some simple examples. Common Examples O(1) does not change with respect to input space. Hence, O(1) is referred to as being constant time. An example of an O(1) algorithm is accessing an item in the array by its index. O(n) is linear time and applies to algorithms that must do n operations in the worst-case scenario. An example of an O(n) algorithm is printing numbers from 0 to n-1, as shown here: 1 function exampleLinear(n) { 2 for (var i = 0 ; i < n; i++ ) { Figure 1-1. Common Big-O complexities Chapter 1 Big-O NOtatiON