Data Structures and Algorithms with JavaScript PDF
Document Details
Uploaded by NoteworthyDjinn9264
2014
Michael McMillan
Tags
Related
- Data Structures and Algorithms Study Guide (Sorsogon State University)
- DATA STRUCTURES AND ALGORITHMS-2015 Edition.pdf
- 1 Introduction to Data Structures and Algorithms.pdf
- Data Structures and Algorithms Made Easy_ Data Structures and Algorithmic Puzzles.pdf
- Data Structures and Algorithms in Java (6th ed.) [Goodrich, Tamassia Goldwasser 2014].pdf
- DSA Notes - Data Structures and Algorithms PDF
Summary
This is a textbook about data structures and algorithms using JavaScript, by Michael McMillan, published in 2014. It covers topics like arrays, lists, and stacks. The book provides a comprehensive introduction to these foundational computer science concepts.
Full Transcript
For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in...
For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in Data Structures and Algorithms with JavaScript Michael McMillan For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in Data Structures and Algorithms with JavaScript by Michael McMillan Copyright © 2014 Michael McMillan. All rights reserved. Printed in the United States of America. Published by O’Reilly Media, Inc., 1005 Gravenstein Highway North, Sebastopol, CA 95472. O’Reilly books may be purchased for educational, business, or sales promotional use. Online editions are also available for most titles (http://my.safaribooksonline.com). For more information, contact our corporate/ institutional sales department: 800-998-9938 or [email protected]. Editors: Brian MacDonald and Meghan Blanchette Cover Designer: Karen Montgomery Production Editor: Melanie Yarbrough Interior Designer: David Futato Copyeditor: Becca Freed Illustrators: Rebecca Demarest and Cynthia Clarke Proofreader: Amanda Kersey Fehrenbach Indexer: Ellen Troutman-Zaig March 2014: First Edition Revision History for the First Edition: 2014-03-06: First release See http://oreilly.com/catalog/errata.csp?isbn=9781449364939 for release details. Nutshell Handbook, the Nutshell Handbook logo, and the O’Reilly logo are registered trademarks of O’Reilly Media, Inc. Data Structures and Algorithms with JavaScript, the image of an amur hedgehog, and related trade dress are trademarks of O’Reilly Media, Inc. Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and O’Reilly Media, Inc. was aware of a trademark claim, the designations have been printed in caps or initial caps. While every precaution has been taken in the preparation of this book, the publisher and authors assume no responsibility for errors or omissions, or for damages resulting from the use of the information contained herein. ISBN: 978-1-449-36493-9 [LSI] For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in Table of Contents Preface....................................................................... ix 1. The JavaScript Programming Environment and Model............................ 1 The JavaScript Environment 1 JavaScript Programming Practices 2 Declaring and Intializing 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 10 Summary 12 2. Arrays.................................................................... 13 JavaScript Arrays Defined 13 Using Arrays 13 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 17 String Representations of Arrays 18 Creating New Arrays from Existing Arrays 18 Mutator Functions 19 Adding Elements to an Array 19 Removing Elements from an Array 20 iii For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in 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 25 Two-Dimensional and Multidimensional Arrays 27 Creating Two-Dimensional Arrays 27 Processing Two-Dimensional Array Elements 28 Jagged Arrays 30 Arrays of Objects 30 Arrays in Objects 31 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 Traversing a List 40 Iterating Through a List 41 A List-Based Application 42 Reading Text Files 42 Using Lists to Manage a Kiosk 43 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 iv | Table of Contents For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in 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 72 6. Linked Lists................................................................ 73 Shortcomings of Arrays 73 Linked Lists Defined 74 An Object-Based Linked List Design 75 The Node Class 75 The Linked List Class 76 Inserting New Nodes 76 Removing Nodes from a Linked List 78 Doubly Linked Lists 81 Circularly Linked Lists 85 Other Linked List Functions 86 Exercises 86 7. Dictionaries............................................................... 89 The Dictionary Class 89 Auxiliary Functions for the Dictionary Class 91 Adding Sorting to the Dictionary Class 93 Exercises 94 8. Hashing................................................................... 97 An Overview of Hashing 97 A Hash Table Class 98 Choosing a Hash Function 98 A Better Hash Function 101 Hashing Integer Keys 103 Storing and Retrieving Data in a Hash Table 106 Handling Collisions 107 Separate Chaining 107 Linear Probing 109 Exercises 111 9. Sets..................................................................... 113 Fundamental Set Definitions, Operations, and Properties 113 Set Definitions 113 Set Operations 114 The Set Class Implementation 114 Table of Contents | v For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in More Set Operations 116 Exercises 120 10. Binary Trees and Binary Search Trees......................................... 121 Trees Defined 121 Binary Trees and Binary Search Trees 123 Building a Binary Search Tree Implementation 124 Traversing a Binary Search Tree 126 BST Searches 129 Searching for the Minimum and Maximum Value 130 Searching for a Specific Value 131 Removing Nodes from a BST 132 Counting Occurrences 134 Exercises 137 11. Graphs and Graph Algorithms............................................... 139 Graph Definitions 139 Real-World Systems Modeled by Graphs 141 The Graph Class 141 Representing Vertices 141 Representing Edges 142 Building a Graph 143 Searching a Graph 145 Depth-First Search 145 Breadth-First Search 148 Finding the Shortest Path 149 Breadth-First Search Leads to Shortest Paths 149 Determining Paths 150 Topological Sorting 151 An Algorithm for Topological Sorting 152 Implementing the Topological Sorting Algorithm 152 Exercises 157 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 170 vi | Table of Contents For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in The Shellsort Algorithm 171 The Mergesort Algorithm 176 The Quicksort Algorithm 181 Exercises 186 13. Searching Algorithms...................................................... 187 Sequential Search 187 Searching for Minimum and Maximum Values 190 Using Self-Organizing Data 193 Binary Search 196 Counting Occurrences 200 Searching Textual Data 202 Exercises 205 14. Advanced Algorithms...................................................... 207 Dynamic Programming 207 A Dynamic Programming Example: Computing Fibonacci Numbers 208 Finding the Longest Common Substring 211 The Knapsack Problem: A Recursive Solution 214 The Knapsack Problem: A Dynamic Programming Solution 215 Greedy Algorithms 217 A First Greedy Algorithm Example: The Coin-Changing Problem 217 A Greedy Algorithm Solution to the Knapsack Problem 218 Exercises 220 Index....................................................................... 221 Table of Contents | vii For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in Preface Over the past few years, JavaScript has been used more and more as a server-side com‐ puter programming language owing to platforms such as Node.js and SpiderMonkey. Now that JavaScript programming is moving out of the browser, programmers will find they need to use many of the tools provided by more conventional languages, such as C++ and Java. Among these tools are classic data structures such as linked lists, stacks, queues, and graphs, as well as classic algorithms for sorting and searching data. This book discusses how to implement these data structures and algorithms for server-side JavaScript programming. JavaScript programmers will find this book useful because it discusses how to implement data structures and algorithms within the constraints that JavaScript places them, such as arrays that are really objects, overly global variables, and a prototype-based object system. JavaScript has an unfair reputation as a “bad” programming language, but this book demonstrates how you can use JavaScript to develop efficient and effective data structures and algorithms using the language’s “good parts.” Why Study Data Structures and Algorithms I am assuming that many of you reading this book do not have a formal education in computer science. If you do, then you already know why studying data structures and algorithms is important. If you do not have a degree in computer science or haven’t studied these topics formally, you should read this section. The computer scientist Nicklaus Wirth wrote a computer programming textbook titled Algorithms + Data Structures = Programs (Prentice-Hall). That title is the essence of computer programming. Any computer program that goes beyond the trivial “Hello, world!” will usually require some type of structure to manage the data the program is written to manipulate, along with one or more algorithms for translating the data from its input form to its output form. ix For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in For many programmers who didn’t study computer science in school, the only data structure they are familiar with is the array. Arrays are great for some problems, but for many complex problems, they are simply not sophisticated enough. Most experienced programmers will admit that for many programming problems, once they come up with the proper data structure, the algorithms needed to solve the problem are easier to design and implement. An example of a data structure that leads to efficient algorithms is the binary search tree (BST). A binary search tree is designed so that it is easy to find the minimum and maximum values of a set of data, yielding an algorithm that is more efficient than the best search algorithms available. Programmers unfamiliar with BSTs will instead prob‐ ably use a simpler data structure that ends up being less efficient. Studying algorithms is important because there is always more than one algorithm that can be used to solve a problem, and knowing which ones are the most efficient is im‐ portant for the productive programmer. For example, there are at least six or seven ways to sort a list of data, but knowing that the Quicksort algorithm is more efficient than the selection sort algorithm will lead to a much more efficient sorting process. Or that it’s fairly easy to implement a sequential or linear search algorithm for a list of data, but knowing that the binary sort algorithm can sometimes be twice as efficient as the se‐ quential search will lead to a better program. The comprehensive study of data structures and algorithms teaches you not only which data structures and which algorithms are the most efficient, but you also learn how to decide which data structures and which algorithms are the most appropriate for the problem at hand. There will often be trade-offs involved when writing a program, es‐ pecially in the JavaScript environment, and knowing the ins and outs of the various data structures and algorithms covered in this book will help you make the proper decision for any particular programming problem you are trying to solve. What You Need for This Book The programming environment we use in this book is the JavaScript shell based on the SpiderMonkey JavaScript engine. Chapter 1 provides instructions on downloading the shell for your environment. Other shells will work as well, such as the Node.js Java‐ Script shell, though you will have to make some translations for the programs in the book to work in Node. Other than the shell, the only thing you need is a text editor for writing your JavaScript programs. x | Preface For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in Organization of the Book Chapter 1 presents an overview of the JavaScript language, or at least the features of the JavaScript language used in this book. This chapter also demonstrates through use the programming style used throughout the other chapters. Chapter 2 discusses the most common data structure in computer programming: the array, which is native to JavaScript. Chapter 3 introduces the first implemented data structure: the list. Chapter 4 covers the stack data structure. Stacks are used throughout computer science in both compiler and operating system implementations. Chapter 5 discusses queue data structures. Queues are an abstraction of the lines you stand in at a bank or the grocery store. Queues are used extensively in simulation software where data has to be lined up before it is processed. Chapter 6 covers Linked lists. A linked list is a modification of the list data structure, where each element is a separate object linked to the objects on either side of it. Linked lists are efficient when you need to perform multiple insertions and dele‐ tions in your program. Chapter 7 demonstrates how to build and use dictionaries, which are data structures that store data as key-value pairs. One way to implement a dictionary is to use a hash table, and Chapter 8 discusses how to build hash tables and the hash algorithms that are used to store data in the table. Chapter 9 covers the set data structure. Sets are often not covered in data structure books, but they can be useful for storing data that is not supposed to have duplicates in the data set. Binary trees and binary search trees are the subject of Chapter 10. As mentioned earlier, binary search trees are useful for storing data that needs to be stored orig‐ inally in sorted form. Chapter 11 covers graphs and graph algorithms. Graphs are used to represent data such as the nodes of a computer network or the cities on a map. Chapter 12 moves from data structures to algorithms and discusses various algo‐ rithms for sorting data, including both simple sorting algorithms that are easy to implement but are not efficient for large data sets, and more complex algorithms that are appropriate for larger data sets. Chapter 13 also covers algorithms, this time searching algorithms such as sequential search and binary search. The last chapter of the book, Chapter 14, discusses a couple more advanced algo‐ rithms for working with data—dynamic programming and greedy algorithms. Preface | xi For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in These algorithms are useful for solving hard problems where a more traditional algorithm is either too slow or too hard to implement. We examine some classic problems for both dynamic programming and greedy algorithms in the chapter. Conventions Used in This Book The following typographical conventions are used in this book: Italic Indicates new terms, URLs, email addresses, filenames, and file extensions. Constant width Used for program listings, as well as within paragraphs to refer to program elements such as variable or function names, databases, data types, environment variables, statements, and keywords. Constant width bold Shows commands or other text that should be typed literally by the user. Constant width italic Shows text that should be replaced with user-supplied values or by values deter‐ mined by context. Using Code Examples Supplemental material (code examples, exercises, etc.) is available for download at https://github.com/oreillymedia/data_structures_and_algorithms_using_javascript. This book is here to help you get your job done. In general, if example code is offered with this book, you may use it in your programs and documentation. You do not need to contact us for permission unless you’re reproducing a significant portion of the code. For example, writing a program that uses several chunks of code from this book does not require permission. Selling or distributing a CD-ROM of examples from O’Reilly books does require permission. Answering a question by citing this book and quoting example code does not require permission. Incorporating a significant amount of ex‐ ample code from this book into your product’s documentation does require permission. We appreciate, but do not require, attribution. An attribution usually includes the title, author, publisher, and ISBN. For example: “Data Structures and Algorithms Using Java‐ Script by Michael McMillian (O’Reilly). Copyright 2014 Michael McMillan, 978-1-449-36493-9.” If you feel your use of code examples falls outside fair use or the permission given above, feel free to contact us at [email protected]. xii | Preface For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in Safari® Books Online Safari Books Online is an on-demand digital library that delivers expert content in both book and video form from the world’s leading authors in technology and business. Technology professionals, software developers, web designers, and business and crea‐ tive professionals use Safari Books Online as their primary resource for research, prob‐ lem solving, learning, and certification training. Safari Books Online offers a range of product mixes and pricing programs for organi‐ zations, government agencies, and individuals. Subscribers have access to thousands of books, training videos, and prepublication manuscripts in one fully searchable database from publishers like O’Reilly Media, Prentice Hall Professional, Addison-Wesley Pro‐ fessional, Microsoft Press, Sams, Que, Peachpit Press, Focal Press, Cisco Press, John Wiley & Sons, Syngress, Morgan Kaufmann, IBM Redbooks, Packt, Adobe Press, FT Press, Apress, Manning, New Riders, McGraw-Hill, Jones & Bartlett, Course Technol‐ ogy, and dozens more. For more information about Safari Books Online, please visit us online. How to Contact Us Please address comments and questions concerning this book to the publisher: O’Reilly Media, Inc. 1005 Gravenstein Highway North Sebastopol, CA 95472 800-998-9938 (in the United States or Canada) 707-829-0515 (international or local) 707-829-0104 (fax) We have a web page for this book, where we list errata, examples, and any additional information. You can access this page at http://oreil.ly/data_structures_algorithms_JS. To comment or ask technical questions about this book, send email to bookques [email protected]. For more information about our books, courses, conferences, and news, see our website at http://www.oreilly.com. Find us on Facebook: http://facebook.com/oreilly Follow us on Twitter: http://twitter.com/oreillymedia Watch us on YouTube: http://www.youtube.com/oreillymedia Preface | xiii For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in Acknowledgments There are always lots of people to thank when you’ve finished writing a book. I’d like to thank my acquisition editor, Simon St. Laurent, for believing in this book and getting me started writing it. Meghan Blanchette worked hard to keep me on schedule, and if I went off schedule, it definitely wasn’t her fault. Brian MacDonald worked extremely hard to make this book as understandable as possible, and he helped make several parts of the text much clearer than I had written them originally. I also want to thank my technical reviewers for reading all the text as well as the code, and for pointing out places where both my prose and my code needed to be clearer. My colleague and illustrator, Cynthia Fehrenbach, did an outstanding job translating my chicken scratchings into crisp, clear illustrations, and she deserves extra praise for her willingness to redraw several illustrations at the very last minute. Finally, I’d like to thank all the people at Mozilla for designing an excellent JavaScript engine and shell and writing some excellent documentation for using both the language and the shell. xiv | Preface For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in CHAPTER 1 The JavaScript Programming Environment and Model This chapter describes the JavaScript programming environment and the programming constructs we’ll use in this book to define the various data structures and algorithms examined. The JavaScript Environment JavaScript has historically been a programming language that ran only inside a web browser. However, in the past few years, there has been the development of JavaScript programming environments that can be run from the desktop, or similarly, from a server. In this book we use one such environment: the JavaScript shell that is part of Mozilla’s comprehensive JavaScript environment known as SpiderMonkey. To download the JavaScript shell, navigate to the Nightly Build web page. Scroll to the bottom of the page and pick the download that matches your computer system. Once you’ve downloaded the program, you have two choices for using the shell. You can use it either in interactive mode or to interpret JavaScript programs stored in a file. To use the shell in interactive mode, type the command js at a command prompt. The shell prompt, js>, will appear and you are ready to start entering JavaScript ex‐ pressions and statements. The following is a typical interaction with the shell: js> 1 1 js> 1+2 3 js> var num = 1; js> num*124 124 1 For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in js> for (var i = 1; i < 6; ++i) { print(i); } 1 2 3 4 5 js> You can enter arithmetic expressions and the shell will immediately evaluate them. You can write any legal JavaScript statement and the shell will immediately evaluate it as well. The interactive shell is great for exploring JavaScript statements to discover how they work. To leave the shell when you are finished, type the command quit(). The other way to use the shell is to have it interpret complete JavaScript programs. This is how we will use the shell throughout the rest of the book. To use the shell to intepret programs, you first have to create a file that contains a JavaScript program. You can use any text editor, making sure you save the file as plain text. The only requirement is that the file must have a.js extension. The shell has to see this extension to know the file is a JavaScript program. Once you have your file saved, you interpret it by typing the js command followed by the full filename of your program. For example, if you saved the for loop code fragment that’s shown earlier in a file named loop.js, you would enter the following: c:\js>js loop.js which would produce the following output: 1 2 3 4 5 After the program is executed, control is returned to the command prompt. JavaScript Programming Practices In this section we discuss how we use JavaScript. We realize that programmers have different styles and practices when it comes to writing programs, and we want to de‐ scribe ours here at the beginning of the book so that you’ll understand the more complex code we present in the rest of the book. This isn’t a tutorial on using JavaScript but is just a guide to how we use the fundamental constructs of the language. 2 | Chapter 1: The JavaScript Programming Environment and Model For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in Declaring and Intializing Variables JavaScript variables are global by default and, strictly speaking, don’t have to be declared before using. When a JavaScript variable is initialized without first being declared, it becomes a global variable. In this book, however, we follow the convention used with compiled languages such as C++ and Java by declaring all variables before their first use. The added benefit to doing this is that declared variables are created as local vari‐ ables. We will talk more about variable scope later in this chapter. To declare a variable in JavaScript, use the keyword var followed by a variable name, and optionally, an assignment expression. Here are some examples: var number; var name; var rate = 1.2; var greeting = "Hello, world!"; var flag = false; Arithmetic and Math Library Functions in JavaScript JavaScript utilizes the standard arithmetic operators: + (addition) - (subtraction) * (multiplication) / (division) % (modulo) JavaScript also has a math library you can use for advanced functions such as square root, absolute value, and the trigonometric functions. The arithmetic operators follow the standard order of operations, and parentheses can be used to modify that order. Example 1-1 shows some examples of performing arithmetic in JavaScript, as well as examples of using several of the mathematical functions. Example 1-1. Arithmetic and math functions in JavaScript var x = 3; var y = 1.1; print(x + y); print(x * y); print((x+y)*(x-y)); var z = 9; print(Math.sqrt(z)); print(Math.abs(y/x)); The output from this program is: JavaScript Programming Practices | 3 For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in 4.1 3.3000000000000003 7.789999999999999 3 0.3666666666666667 If you don’t want or need the precision shown above, you can format a number to a fixed precision: var x = 3; var y = 1.1; var z = x * y; print(z.toFixed(2)); // displays 3.30 Decision Constructs Decision constructs allow our programs to make decisions on what programming statements to execute based on a Boolean expression. The two decision constructs we use in this book are the if statement and the switch statement. The if statement comes in three forms: The simple if statement The if-else statement The if-else if statement Example 1-2 shows how to write a simple if statement. Example 1-2. The simple if statement var mid = 25; var high = 50; var low = 1; var current = 13; var found = -1; if (current < mid) { mid = (current-low) / 2; } Example 1-3 demonstrates the if-else statement. Example 1-3. The if-else statement var mid = 25; var high = 50; var low = 1; var current = 13; var found = -1; if (current < mid) { mid = (current-low) / 2; } 4 | Chapter 1: The JavaScript Programming Environment and Model For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in else { mid = (current+high) / 2; } Example 1-4 illustrates the if-else if statement. Example 1-4. The if-else if statement var mid = 25; var high = 50; var low = 1; var current = 13; var found = -1; if (current < mid) { mid = (current-low) / 2; } else if (current > mid) { mid = (current+high) / 2; } else { found = current; } The other decision structure we use in this book is the switch statement. This statement provides a cleaner, more structured construction when you have several simple deci‐ sions to make. Example 1-5 demonstrates how the switch statement works. Example 1-5. The switch statement putstr("Enter a month number: "); var monthNum = readline(); var monthName; switch (monthNum) { case "1": monthName = "January"; break; case "2": monthName = "February"; break; case "3": monthName = "March"; break; case "4": monthName = "April"; break; case "5": monthName = "May"; break; case "6": monthName = "June"; break; case "7": JavaScript Programming Practices | 5 For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in monthName = "July"; break; case "8": monthName = "August"; break; case "9": monthName = "September"; break; case "10": monthName = "October"; break; case "11": monthName = "November"; break; case "12": monthName = "December"; break; default: print("Bad input"); } Is this the most efficient way to solve this problem? No, but it does a great job of dem‐ onstrating how the switch statement works. One major difference between the JavaScript switch statement and switch statements in other programming languages is that the expression that is being tested in the state‐ ment can be of any data type, as opposed to an integral data type, as required by languages such as C++ and Java. In fact, you’ll notice in the previous example that we use the month numbers as strings, rather than converting them to numbers, since we can com‐ pare strings using the switch statement in JavaScript. Repetition Constructs Many of the algorithms we study in this book are repetitive in nature. We use two repetition constructs in this book—the while loop and the for loop. When we want to execute a set of statements while a condition is true, we use a while loop. Example 1-6 demonstrates how the while loop works. Example 1-6. The while loop var number = 1; var sum = 0; while (number < 11) { sum += number; ++number; } print(sum); // displays 55 6 | Chapter 1: The JavaScript Programming Environment and Model For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in When we want to execute a set of statements a specified number of times, we use a for loop. Example 1-7 uses a for loop to sum the integers 1 through 10. Example 1-7. Summing integers using a for loop var number = 1; var sum = 0; for (var number = 1; number < 11; number++) { sum += number; } print(sum); // displays 55 for loops are also used frequently to access the elements of an array, as shown in Example 1-8. Example 1-8. Using a for loop with an array var numbers = [3, 7, 12, 22, 100]; var sum = 0; for (var i = 0; i < numbers.length; ++i) { sum += numbers[i]; } print(sum); // displays 144 Functions JavaScript provides the means to define both value-returning functions and functions that don’t return values (sometimes called subprocedures or void functions). Example 1-9 demonstrates how value-returning functions are defined and called in JavaScript. Example 1-9. A value-returning function function factorial(number) { var product = 1; for (var i = number; i >= 1; --i) { product *= i; } return product; } print(factorial(4)); // displays 24 print(factorial(5)); // displays 120 print(factorial(10)); // displays 3628800 Example 1-10 illustrates how to write a function that is used not for its return value, but for the operations it performs. JavaScript Programming Practices | 7 For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in Example 1-10. A subprocedure or void function in JavaScript function curve(arr, amount) { for (var i = 0; i < arr.length; ++i) { arr[i] += amount; } } var grades = [77, 73, 74, 81, 90]; curve(grades, 5); print(grades); // displays 82,78,79,86,95 All function parameters in JavaScript are passed by value, and there are no reference parameters. However, there are reference objects, such as arrays, which are passed to functions by reference, as was demonstrated in Example 1-10. Variable Scope The scope of a variable refers to where in a program a variable’s value can be accessed. The scope of a variable in JavaScript is defined as function scope. This means that a variable’s value is visible within the function definition where the variable is declared and defined and within any functions that are nested within that function. When a variable is defined outside of a function, in the main program, the variable is said to have global scope, which means its value can be accessed by any part of a program, including functions. The following short program demonstrates how global scope works: function showScope() { return scope; } var scope = "global"; print(scope); // displays "global" print(showScope()); // displays "global" The function showScope() can access the variable scope because scope is a global vari‐ able. Global variables can be declared at any place in a program, either before or after function definitions. Now watch what happens when we define a second scope variable within the show Scope() function: function showScope() { var scope = "local"; return scope; } var scope = "global"; print(scope); // displays "global" print(showScope()); // displays "local" 8 | Chapter 1: The JavaScript Programming Environment and Model For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in The scope variable defined in the showScope() function has local scope, while the scope variable defined in the main program is a global variable. Even though the two variables have the same name, their scopes are different, and their values are different when accessed within the area of the program where they are defined. All of this behavior is normal and expected. However, it can all change if you leave off the keyword var in the variable definitions. JavaScript allows you to define variables without using the var keyword, but when you do, that variable automatically has global scope, even if defined within a function. Example 1-11 demonstrates the ramifications of leaving off the var keyword when defining variables. Example 1-11. The ramification of overusing global variables function showScope() { scope = "local"; return scope; } scope = "global"; print(scope); // displays "global" print(showScope()); // displays "local" print(scope); // displays "local" In Example 1-11, because the scope variable inside the function is not declared with the var keyword, when the string "local" is assigned to the variable, we are actually chang‐ ing the value of the scope variable in the main program. You should always begin every definition of a variable with the var keyword to keep things like this from happening. Earlier, we mentioned that JavaScript has function scope. This means that JavaScript does not have block scope, unlike many other modern programming languages. With block scope, you can declare a variable within a block of code and the variable is not accessible outside of that block, as you typically see with a C++ or Java for loop: for (int i = 1; i 6 add(6,4) -> 10 add(10,5) -> 15 add(15,6) -> 21 add(21,7) -> 28 add(28,8) -> 36 add(36,9) -> 45 add(45,10) -> 55 We can also use reduce() with strings to perform concatenation: function concat(accumulatedString, item) { return accumulatedString + item; } var words = ["the ", "quick ","brown ", "fox "]; var sentence = words.reduce(concat); print(sentence); // displays "the quick brown fox" JavaScript also provides a reduceRight() function, which works similarly to re duce(), only working from the righthand side of the array to the left, instead of from left to right. The following program uses reduceRight() to reverse the elements of an array: function concat(accumulatedString, item) { return accumulatedString + item; } var words = ["the ", "quick ","brown ", "fox "]; var sentence = words.reduceRight(concat); print(sentence); // displays "fox brown quick the" Iterator Functions That Return a New Array There are two iterator functions that return new arrays: map() and filter(). The map() function works like the forEach() function, applying a function to each element of an array. The difference between the two functions is that map() returns a new array with the results of the function application. Here is an example: function curve(grade) { return grade += 5; } var grades = [77, 65, 81, 92, 83]; var newgrades = grades.map(curve); print(newgrades); // 82, 70, 86, 97, 88 Here is an example using strings: Iterator Functions | 25 For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in function first(word) { return word; } var words = ["for","your","information"]; var acronym = words.map(first); print(acronym.join("")); // displays "fyi" For this last example, the acronym array stores the first letter of each word in the words array. However, if we want to display the elements of the array as a true acronym, we need to get rid of the commas that will be displayed if we just display the array elements using the implied toString() function. We accomplish this by calling the join() func‐ tion with the empty string as the separator. The filter() function works similarly to every(), but instead of returning true if all the elements of an array satisfy a Boolean function, the function returns a new array consisting of those elements that satisfy the Boolean function. Here is an example: function isEven(num) { return num % 2 == 0; } function isOdd(num) { return num % 2 != 0; } var nums = []; for (var i = 0; i < 20; ++i) { nums[i] = i+1; } var evens = nums.filter(isEven); print("Even numbers: "); print(evens); var odds = nums.filter(isOdd); print("Odd numbers: "); print(odds); This program returns the following output: Even numbers: 2,4,6,8,10,12,14,16,18,20 Odd numbers: 1,3,5,7,9,11,13,15,17,19 Here is another interesting use of filter(): function passing(num) { return num >= 60; } var grades = []; for (var i = 0; i < 20; ++i) { grades[i] = Math.floor(Math.random() * 101); 26 | Chapter 2: Arrays For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in } var passGrades = grades.filter(passing); print("All grades: ); print(grades); print("Passing grades: "); print(passGrades); This program displays: All grades: 39,43,89,19,46,54,48,5,13,31,27,95,62,64,35,75,79,88,73,74 Passing grades: 89,95,62,64,75,79,88,73,74 Of course, we can also use filter() with strings. Here is an example that applies the spelling rule “i before e except after c”: function afterc(str) { if (str.indexOf("cie") > -1) { return true; } return false; } var words = ["recieve","deceive","percieve","deceit","concieve"]; var misspelled = words.filter(afterc); print(misspelled); // displays recieve,percieve,concieve Two-Dimensional and Multidimensional Arrays JavaScript arrays are only one-dimensional, but you can create multidimensional arrays by creating arrays of arrays. In this section we’ll describe how to create two-dimensional arrays in JavaScript. Creating Two-Dimensional Arrays A two-dimensional array is structured like a spreadsheet with rows and columns. To create a two-dimensional array in JavaScript, we have to create an array and then make each element of the array an array as well. At the very least, we need to know the number of rows we want the array to contain. With that information, we can create a two- dimensional array with n rows and one column: var twod = []; var rows = 5; for (var i = 0; i < rows; ++i) { twod[i] = []; } The problem with this approach is that each element of the array is set to undefined. A better way to create a two-dimensional array is to follow the example from JavaScript: Two-Dimensional and Multidimensional Arrays | 27 For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in The Good Parts (O’Reilly, p. 64). Crockford extends the JavaScript array object with a function that sets the number of rows and columns and sets each value to a value passed to the function. Here is his definition: Array.matrix = function(numrows, numcols, initial) { var arr = []; for (var i = 0; i < numrows; ++i) { var columns = []; for (var j = 0; j < numcols; ++j) { columns[j] = initial; } arr[i] = columns; } return arr; } Here is some code to test the definition: var nums = Array.matrix(5,5,0); print(nums); // displays 0 var names = Array.matrix(3,3,""); names = "Joe"; print(names); // display "Joe" We can also create a two-dimensional array and initialize it to a set of values in one line: var grades = [[89, 77, 78],[76, 82, 81],[91, 94, 89]]; print(grades); // displays 89 For small data sets, this is the easiest way to create a two-dimensional array. Processing Two-Dimensional Array Elements There are two fundamental patterns used to process the elements of a two-dimensional array. One pattern emphasizes accessing array elements by columns, and the other pat‐ tern emphasizes accessing array elements by rows. We will use the grades array created in the preceding code fragment to demonstrate how these patterns work. For both patterns, we use a set of nested for loops. For columnar processing, the outer loop moves through the rows, and the inner loop processes the columns. For the grades array, think of each row as a set of grades for one student. We can compute the average for each student’s grades by adding each grade on the row to a total variable and then dividing total by the total number of grades on that row. Here is the code for that process: var grades = [[89, 77, 78],[76, 82, 81],[91, 94, 89]]; var total = 0; var average = 0.0; for (var row = 0; row < grades.length; ++row) { for (var col = 0; col < grades[row].length; ++col) { total += grades[row][col]; 28 | Chapter 2: Arrays For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in } average = total / grades[row].length; print("Student " + parseInt(row+1) + " average: " + average.toFixed(2)); total = 0; average = 0.0; } The inner loop is controlled by the expression: col < grades[row].length This works because each row contains an array, and that array has a length property we can use to determine how many columns there are in the row. The grade average for each student is rounded to two decimals using the toFixed(n) function. Here is the output from the program: Student 1 average: 81.33 Student 2 average: 79.67 Student 3 average: 91.33 To perform a row-wise computation, we simply have to flip the for loops so that the outer loop controls the columns and the inner loop controls the rows. Here is the cal‐ culation for each test: var grades = [[89, 77, 78],[76, 82, 81],[91, 94, 89]]; var total = 0; var average = 0.0; for (var col = 0; col < grades.length; ++col) { for (var row = 0; row < grades[col].length; ++row) { total += grades[row][col]; } average = total / grades[col].length; print("Test " + parseInt(col+1) + " average: " + average.toFixed(2)); total = 0; average = 0.0; } The output from this program is: Test 1 average: 85.33 Test 2 average: 84.33 Test 3 average: 82.67 Two-Dimensional and Multidimensional Arrays | 29 For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in Jagged Arrays A jagged array is an array where the rows in the array may have a different number of elements. One row may have three elements, while another row may have five elements, while yet another row may have just one element. Many programming languages have problems handling jagged arrays, but JavaScript does not since we can compute the length of any row. To give you an example, imagine the grades array where students have an unequal number of grades recorded. We can still compute the correct average for each student without changing the program at all: var grades = [[89, 77],[76, 82, 81],[91, 94, 89, 99]]; var total = 0; var average = 0.0; for (var row = 0; row < grades.length; ++row) { for (var col = 0; col < grades[row].length; ++col) { total += grades[row][col]; } average = total / grades[row].length; print("Student " + parseInt(row+1) + " average: " + average.toFixed(2)); total = 0; average = 0.0; } Notice that the first student only has two grades, while the second student has three grades, and the third student has four grades. Because the program computes the length of the row in the inner loop, this jaggedness doesn’t cause any problems. Here is the output from the program: Student 1 average: 83.00 Student 2 average: 79.67 Student 3 average: 93.25 Arrays of Objects All of the examples in this chapter have consisted of arrays whose elements have been primitive data types, such as numbers and strings. Arrays can also consist of objects, and all the functions and properties of arrays work with objects. For example: function Point(x,y) { this.x = x; this.y = y; } function displayPts(arr) { for (var i = 0; i < arr.length; ++i) { 30 | Chapter 2: Arrays For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in print(arr[i].x + ", " + arr[i].y); } } var p1 = new Point(1,2); var p2 = new Point(3,5); var p3 = new Point(2,8); var p4 = new Point(4,4); var points = [p1,p2,p3,p4]; for (var i = 0; i < points.length; ++i) { print("Point " + parseInt(i+1) + ": " + points[i].x + ", " + points[i].y); } var p5 = new Point(12,-3); points.push(p5); print("After push: "); displayPts(points); points.shift(); print("After shift: "); displayPts(points); The output from this program is: Point 1: 1, 2 Point 2: 3, 5 Point 3: 2, 8 Point 4: 4, 4 After push: 1, 2 3, 5 2, 8 4, 4 12, -3 After shift: 3, 5 2, 8 4, 4 12, -3 The point 12, -3 is added to the array using push(), and the point 1, 2 is removed from the array using shift(). Arrays in Objects We can use arrays to store complex data in an object. Many of the data structures we study in this book are implemented as class objects with an underlying array used to store data. The following example demonstrates many of the techniques we use throughout the book. In the example, we create an object that stores the weekly observed high Arrays in Objects | 31 For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in temperature. The object has functions for adding a new temperature and computing the average of the temperatures stored in the object. Here is the code: function weekTemps() { this.dataStore = []; this.add = add; this.average = average; } function add(temp) { this.dataStore.push(temp); } function average() { var total = 0; for (var i = 0; i < this.dataStore.length; ++i) { total += this.dataStore[i]; } return total / this.dataStore.length; } var thisWeek = new weekTemps(); thisWeek.add(52); thisWeek.add(55); thisWeek.add(61); thisWeek.add(65); thisWeek.add(55); thisWeek.add(50); thisWeek.add(52); thisWeek.add(49); print(thisWeek.average()); // displays 54.875 You’ll notice the add() function uses the push() function to add elements to the data Store array, using the name add() rather than push(). Using a more intuitive name for an operation is a common technique when defining object functions. Not everyone will understand what it means to push a data element, but everyone knows what it means to add a data element. 32 | Chapter 2: Arrays For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in Exercises 1. Create a grades object that stores a set of student grades in an object. Provide a function for adding a grade and a function for displaying the student’s grade average. 2. Store a set of words in an array and display the contents both forward and backward. 3. Modify the weeklyTemps object in the chapter so that it stores a month’s worth of data using a two-dimensional array. Create functions to display the monthly aver‐ age, a specific week’s average, and all the weeks’ averages. 4. Create an object that stores individual letters in an array and has a function for displaying the letters as a single word. Exercises | 33 For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in CHAPTER 3 Lists Lists are one of the most common organizing tools people use in their day-to-day lives. We have to-do lists, grocery lists, top-ten lists, bottom-ten lists, and many other types. Our computer programs can also use lists, particularly if we only have a few items to store in list form. Lists are especially useful if we don’t have to perform searches on the items in the list or put them into some type of sorted order. When we need to perform long searches or complex sorts, lists become less useful, especially with more complex data structures. This chapter presents the creation of a simple list class. We start with the definition of a list abstract data type (ADT) and then demonstrate how to implement the ADT. We wrap up the chapter with some problems that are best solved with lists. A List ADT In order to design an ADT for a list, we have to provide a definition of the list, including its properties, as well as the operations performed on it and by it. A list is an ordered sequence of data. Each data item stored in a list is called an ele‐ ment. In JavaScript, the elements of a list can be of any data type. There is no predeter‐ mined number of elements that can be stored in a list, though the practical limit will be the amount of memory available to the program using the list. A list with no elements is an empty list. The number of elements stored in a list is called the length of the list. Internally, the number of elements in a list is kept in a listSize variable. You can append an element to the end of a list, or you can insert an element into a list after an existing element or at the beginning of a list. Elements are deleted from a list using a remove operation. You can also clear a list so that all of its current elements are removed. 35 For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in The elements of a list are displayed using either a toString() operation, which displays all the elements, or with a getElement() operation, which displays the value of the current element. Lists have properties to describe location. There is the front of a list and the end of a list. You can move from one element of a list to the next element using the next() operation, and you can move backward through a list using the prev() operation. You can also move to a numbered position in a list using the moveTo(n) operation, where n specifies the position to move to. The currPos property indicates the current position in a list. The List ADT does not specify a storage function for a list, but for our implementation will use an array named dataStore. Table 3-1 shows the complete List ADT. Table 3-1. ADT List listSize (property) Number of elements in list pos (property) Current position in list length (property) Returns the number of elements in list clear (function) Clears all elements from list toString (function) Returns string representation of list getElement (function) Returns element at current position insert (function) Inserts new element after existing element append (function) Adds new element to end of list remove (function) Removes element from list front (function) Sets current position to first element of list end (function) Sets current position to last element of list prev (function) Moves current position back one element next (function) Moves current position forward one element currPos (function) Returns the current position in list moveTo (function) Moves the current position to specified position A List Class Implementation A List class implementation can be taken straight from the List ADT we just defined. We’ll start with a definition of a constructor function, though it is not part of the ADT: function List() { this.listSize = 0; this.pos = 0; this.dataStore = []; // initializes an empty array to store list elements this.clear = clear; this.find = find; 36 | Chapter 3: Lists For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in this.toString = toString; this.insert = insert; this.append = append; this.remove = remove; this.front = front; this.end = end; this.prev = prev; this.next = next; this.length = length; this.currPos = currPos; this.moveTo = moveTo; this.getElement = getElement; this.length = length; this.contains = contains; } Append: Adding an Element to a List The first function we’ll implement is the append() function. This function appends a new element onto the list at the next available position, which will be equal to the value of the listSize variable: function append(element) { this.dataStore[this.listSize++] = element; } After the element is appended, listSize is incremented by 1. Remove: Removing an Element from a List Next, let’s see how to remove an element from a list. remove() is one of the harder functions to implement in the List class. First, we have to find the element in the list, and then we have to remove it and adjust the space in the underlying array to fill the hole left by removing an element. However, we can simplify the process by using the splice() mutator function. To start, let’s define a helper function, find(), for finding the element to remove: function find(element) { for (var i = 0; i < this.dataStore.length; ++i) { if (this.dataStore[i] == element) { return i; } } return -1; } A List Class Implementation | 37 For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in Find: Finding an Element in a List The find function simply iterates through dataStore looking for the specified ele‐ ment. If the element is found, the function returns the position where the element was found. If the element wasn’t found, the function returns -1, which is a standard value to return when an element can’t be found in an array. We can use this value for error checking in the remove() function. The remove() function uses the position returned by find() to splice the dataStore array at that place. After the array is modified, listSize is decremented by 1 to reflect the new size of the list. The function returns true if an element is removed, and false otherwise. Here is the code: function remove(element) { var foundAt = this.find(element); if (foundAt > -1) { this.dataStore.splice(foundAt,1); --this.listSize; return true; } return false; } Length: Determining the Number of Elements in a List The length() function returns the number of elements in a list: function length() { return this.listSize; } toString: Retrieving a List’s Elements Now is a good time to create a function that allows us to view the elements of a list. Here is the code for a simple toString() function: function toString() { return this.dataStore; } Strictly speaking, this function returns an array object and not a string, but its utility is in providing a view of the current state of an object, and just returning the array works adequately for this purpose. Let’s take a break from implementing our List class to see how well it works so far. Here is a short test program that exercises the functions we’ve created so far: var names = new List(); names.append("Cynthia"); names.append("Raymond"); 38 | Chapter 3: Lists For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in names.append("Barbara"); print(names.toString()); names.remove("Raymond"); print(names.toString()); The output from this program is: Cynthia,Raymond,Barbara Cynthia,Barbara Insert: Inserting an Element into a List The next function to discuss is insert(). What if, after removing Raymond from the preceding list, we decide we need to put him back where he was to begin with? An insertion function needs to know where to insert an element, so for now we will say that insertion occurs after a specified element already in the list. With this in mind, here is the definition of the insert() function: function insert(element, after) { var insertPos = this.find(after); if (insertPos > -1) { this.dataStore.splice(insertPos+1, 0, element); ++this.listSize; return true; } return false; } insert() uses the helper function find() to determine the correct insertion position for the new element by finding the element specified in the after argument. Once this position is found, we use shift() to insert the new element into the list. Then we increment listSize by 1 and return true to indicate the insertion was successful. Clear: Removing All Elements from a List Next, we need a function to clear out the elements of a list and allow new elements to be entered: function clear() { delete this.dataStore; this.dataStore = []; this.listSize = this.pos = 0; } The clear() function uses the delete operator to delete the dataStore array, and the next line re-creates the empty array. The last line sets the values of listSize and pos to 0 to indicate the start of a new list. A List Class Implementation | 39 For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in Contains: Determining if a Given Value Is in a List The contains() function is useful when you want to check a list to see if a particular value is part of the list. Here is the definition: function contains(element) { for (var i = 0; i < this.dataStore.length; ++i) { if (this.dataStore[i] == element) { return true; } } return false; } Traversing a List This final set of functions allows movement through a list, and the last function, getElement(), displays the current element in a list: function front() { this.pos = 0; } function end() { this.pos = this.listSize-1; } function prev() { if (this.pos > 0) { --this.pos; } } function next() { if (this.pos < this.listSize-1) { ++this.pos; } } function currPos() { return this.pos; } function moveTo(position) { this.pos = position; } function getElement() { return this.dataStore[this.pos]; } Let’s create a new list of names to demonstrate how these functions work: 40 | Chapter 3: Lists For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in var names = new List(); names.append("Clayton"); names.append("Raymond"); names.append("Cynthia"); names.append("Jennifer"); names.append("Bryan"); names.append("Danny"); Now let’s move to the first element of the list and display it: names.front(); print(names.getElement()); // displays Clayton Next, we move forward one element and display the element’s value: names.next(); print(names.getElement()); // displays Raymond Now we’ll move forward twice and backward once, displaying the current element to demonstrate how the prev() function works: names.next(); names.next(); names.prev(); print(names.getElement()); // displays Cynthia The behavior we’ve demonstrated in these past few code fragments is captured in the concept of an iterator. We explore iterators in the next section. Iterating Through a List An iterator allows us to traverse a list without referencing the internal storage mecha‐ nism of the List class. The functions front(), end(), prev(), next(), and currPos provide an implementation of an iterator for our List class. Some advantages to using iterators over using array indexing include: Not having to worry about the underlying data storage structure when accessing list elements Being able to update the list and not having to update the iterator, where an index becomes invalid when a new element is added to the list Providing a uniform means of accessing elements for different types of data stores used in the implemenation of a List class With these advantages in mind, here is how to use an iterator to traverse through a list: for(names.front(); names.currPos() < names.length(); names.next()) { print(names.getElement()); } Iterating Through a List | 41 For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in The for loop starts by setting the current position to the front of the list. The loop continues while the value of currPos is less than the length of the list. Each time through the loop, the current position is moved one element forward through the use of the next() function. We can also traverse a list backward using an iterator. Here is the code: for(names.end(); names.currPos() >= 0; names.prev()) { print(names.getElement()); } The loop starts at the last element of the list and moves backward using the prev() function while the current position is greater than or equal to 0. Iterators are used only to move through a list and should not be combined with any functions for adding or removing items from a list. A List-Based Application To demonstrate how to use lists, we are going to build a system that can be used in the simulation of a video-rental kiosk system such as Redbox. Reading Text Files In order to get the list of videos available in the kiosk into our program, we need to be able to read the data from a file. We first have to create a text file that contains the list of videos available using a text editor. We name the file films.txt. Here are the contents of the files (these movies are the top 20 movies as voted on by IMDB users as of October 5, 2013): 1. The Shawshank Redemption 2. The Godfather 3. The Godfather: Part II 4. Pulp Fiction 5. The Good, the Bad and the Ugly 6. 12 Angry Men 7. Schindler’s List 8. The Dark Knight 9. The Lord of the Rings: The Return of the King 10. Fight Club 11. Star Wars: Episode V - The Empire Strikes Back 12. One Flew Over the Cuckoo’s Nest 42 | Chapter 3: Lists For More Visit : www.LearnEngineering.in For More Visit : www.LearnEngineering.in 13. The Lord of the Rings: The Fellowship of the Ring 14. Inception 15. Goodfellas 16. Star Wars 17. Seven Samurai 18. The Matrix 19. Forrest Gump 20. City of God Now we need a code fragment to read the contents of the file into our program: var movies = read(films.txt).split("\n"); This line performs two tasks. First, it reads the contents of our movies text file into the program, read(films.txt); and second, it splits the file into individual lines by using the newline character as a delimiter. This output is then stored as an array in the mov ies variable. This line of code works up to a point, but it’s not perfect. When the elements of the text file are split into the array, the newline character is replaced with a space. While a single space seems innocuous enough, having an extra space in a string can cause havoc when you are doing string comparisons. So we need to add a loop that strips the space from each array element using the trim() function. This code will work better in a function, so let’s create a function to read data from a file and store it in an array: function createArr(file) { var arr = read(file).split("\n"); for (var i = 0; i < arr.length; ++i) { arr[i] = arr[i].trim(); } return arr; } Using Lists to Manage a Kiosk The next step is to take the movies array and store its contents in a list. Here is how we do it: var movieList = new List(); for (var i = 0; i < movies.length; ++i) { movieList.append(movies[i]); } Now we can write a function to display the movie list available at the kiosk:
