JavaScript Data Structures and Algorithms An Introduction to Understanding and Implementing Core Data Structure and Algorithm… (Sammie Bae)（Z-Library）

JavaScript Data Structures and Algorithms An Introduction to Understanding and Implementing Core Data Structure and Algorithm Fundamentals — Sammie Bae

JavaScript Data Structures and Algorithms An Introduction to Understanding and Implementing Core Data Structure and Algorithm Fundamentals Sammie Bae

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

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.

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.

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.

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.

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.

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.

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