Think Data Structures - Algorithms and Information Retrieval in Java PDF

THINK DATA STRUCTURES - ALGORITHMS AND INFORMATION RETRIEVAL IN JAVA Allen B. Downey Olin College  Olin College Think Data Structures - Algorithms and Information Retrieval in Java Allen B. Downey This text is disseminated via the Open Education Resource (OER) LibreTe...

THINK DATA STRUCTURES - ALGORITHMS AND INFORMATION RETRIEVAL IN JAVA Allen B. Downey Olin College  Olin College Think Data Structures - Algorithms and Information Retrieval in Java Allen B. Downey This text is disseminated via the Open Education Resource (OER) LibreTexts Project (https://LibreTexts.org) and like the hundreds of other texts available within this powerful platform, it is freely available for reading, printing and "consuming." Most, but not all, pages in the library have licenses that may allow individuals to make changes, save, and print this book. Carefully consult the applicable license(s) before pursuing such effects. Instructors can adopt existing LibreTexts texts or Remix them to quickly build course-specific resources to meet the needs of their students. Unlike traditional textbooks, LibreTexts’ web based origins allow powerful integration of advanced features and new technologies to support learning. The LibreTexts mission is to unite students, faculty and scholars in a cooperative effort to develop an easy-to-use online platform for the construction, customization, and dissemination of OER content to reduce the burdens of unreasonable textbook costs to our students and society. The LibreTexts project is a multi-institutional collaborative venture to develop the next generation of open- access texts to improve postsecondary education at all levels of higher learning by developing an Open Access Resource environment. The project currently consists of 14 independently operating and interconnected libraries that are constantly being optimized by students, faculty, and outside experts to supplant conventional paper-based books. These free textbook alternatives are organized within a central environment that is both vertically (from advance to basic level) and horizontally (across different fields) integrated. The LibreTexts libraries are Powered by NICE CXOne and are supported by the Department of Education Open Textbook Pilot Project, the UC Davis Office of the Provost, the UC Davis Library, the California State University Affordable Learning Solutions Program, and Merlot. This material is based upon work supported by the National Science Foundation under Grant No. 1246120, 1525057, and 1413739. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation nor the US Department of Education. Have questions or comments? For information about adoptions or adaptions contact [email protected]. More information on our activities can be found via Facebook (https://facebook.com/Libretexts), Twitter (https://twitter.com/libretexts), or our blog (http://Blog.Libretexts.org). This text was compiled on 04/10/2024 TABLE OF CONTENTS Licensing Preface Prerequisites 1: Interfaces 1.2: Interfaces in Java 1.3: The List Interface 1.4: Exercise 1 2: Analysis of Algorithms 2.1: Selection Sort 2.2: Big O notation 2.3: Exercise 2 3: ArrayList 3.1: Classifying MyArrayList methods 3.2: Classifying add 3.3: Problem Size 3.4: Linked Data Structures 3.5: Exercise 3 3.6: A note on garbage collection 4: LinkedList 4.1: Classifying MyLinkedList methods 4.2: Comparing MyArrayList and MyLinkedList 4.3: Profiling 4.4: Interpreting results 4.5: Exercise 4 5: Doubly-linked list 5.1: Performance profiling results 5.2: Profiling LinkedList methods 5.3: Adding to the end of a LinkedList 5.4: Doubly-linked list 5.5: Choosing a Structure 6: Tree traversal 6.1: Search engines 6.2: Parsing HTML 6.3: Using jsoup 6.4: Iterating through the DOM 6.5: Depth-first search 6.6: Stacks in Java 1 https://eng.libretexts.org/@go/page/14075  6.7: Iterative DFS 7: Getting to Philosophy 7.1: Getting started 7.2: Iterables and Iterators 7.3: WikiFetcher 7.4: Exercise 5 8: Indexer 8.1: Data structure selection 8.2: TermCounter 8.3: Exercise 6 9: The Map interface 9.1: Implementing MyLinearMap 9.2: Exercise 7 9.3: Analyzing MyLinearMap 10: Hashing 10.1: Hashing 10.3: Hashing and mutation 10.4: Exercise 8 11: HashMap 11.1: Exercise 9 11.2: Analyzing MyHashMap 11.3: The tradeoffs 11.4: Profiling MyHashMap 11.5: Fixing MyHashMap 11.6: UML class diagrams 12: TreeMap 12.2: Binary search tree 12.3: Exercise 10 12.4: Implementing a TreeMap 13: Binary search tree 13.1: A simple MyTreeMap 13.2: Searching for values 13.3: Implementing put 13.4: In-order traversal 13.5: The logarithmic methods 13.6: Self-balancing trees 13.7: One more exercise 14: Persistence 14.1: Redis 14.2: Redis clients and servers 2 https://eng.libretexts.org/@go/page/14075  14.3: Making a Redis-backed index 14.4: Redis data types 14.5: Exercise 11 14.6: More suggestions if you want them 14.7: A few design hints 15: Crawling Wikipedia 15.1: The Redis-backed indexer 15.2: Analysis of lookup 15.3: Analysis of indexing 15.4: Graph traversal 15.5: Exercise 12 16: Boolean search 16.1: Crawler solution 16.2: Information retrieval 16.3: Boolean search 16.4: Exercise 13 16.5: Comparable and Comparator 16.6: Extensions 17: Sorting 17.1: Insertion sort 17.2: Exercise 14 17.3: Analysis of merge sort 17.4: Radix sort 17.5: Heap sort 17.6: Bounded heap 17.7: Space complexity Index Glossary Detailed Licensing 3 https://eng.libretexts.org/@go/page/14075 Licensing A detailed breakdown of this resource's licensing can be found in Back Matter/Detailed Licensing. 1 https://eng.libretexts.org/@go/page/95800 Preface The philosophy behind the book Data structures and algorithms are among the most important inventions of the last 50 years, and they are fundamental tools software engineers need to know. But in my opinion, most of the books on these topics are too theoretical, too big, and too “bottom up”: Too theoretical: Mathematical analysis of algorithms is based on simplifying assumptions that limit its usefulness in practice. Many presentations of this topic gloss over the simplifications and focus on the math. In this book I present the most practical subset of this material and omit or de-emphasize the rest. Too big: Most books on these topics are at least 500 pages, and some are more than 1000. By focusing on the topics I think are most useful for software engineers, I kept this book under 200 pages. Too “bottom up”: Many data structures books focus on how data structures work (the implementations), with less about how to use them (the interfaces). In this book, I go “top down”, starting with the interfaces. Readers learn to use the structures in the Java Collections Framework before getting into the details of how they work. Finally, some books present this material out of context and without motivation: it’s just one damn data structure after another! I try to liven it up by organizing the topics around an application — web search — that uses data structures extensively, and is an interesting and important topic in its own right. This application motivates some topics that are not usually covered in an introductory data structures class, including persistent data structures with Redis. I have made difficult decisions about what to leave out, but I have made some compromises. I include a few topics that most readers will never use, but that they might be expected to know, possibly in a technical interview. For these topics, I present both the conventional wisdom as well as my reasons to be skeptical. This book also presents basic aspects of software engineering practice, including version control and unit testing. Most chapters include an exercise that allows readers to apply what they have learned. Each exercise provides automated tests that check the solution. And for most exercises, I present my solution at the beginning of the next chapter. 1 https://eng.libretexts.org/@go/page/13099 Prerequisites This book is intended for college students in computer science and related fields, as well as professional software engineers, people training in software engineering, and people preparing for technical interviews. Before you start this book, you should know Java pretty well; in particular, you should know how to define a new class that extends an existing class or implements an interface. If your Java is rusty, here are two books you might start with: Downey and Mayfield, Think Java (O’Reilly Media, 2016), which is intended for people who have never programmed before. Sierra and Bates, Head First Java (O’Reilly Media, 2005), which is appropriate for people who already know another programming language. You should also be familiar with type parameters and generic types. For example, you should know how create an object with a type parameter, like ArrayList. If not, you can read about type parameters at thinkdast.com/types. You should be familiar with the Java Collections Framework (JCF), which you can read about at thinkdast.com/collections. In particular, you should know about the List interface and the classes ArrayList and LinkedList. Ideally you should be familiar with Apache Ant, which is an automated build tool for Java. You can read more about Ant at thinkdast.com/anttut. And you should be familiar with JUnit, which is a unit testing framework for Java. You can read more about it at thinkdast.com/junit. Working with the code The code for this book is in a Git repository at thinkdast.com/repo. Git is a “version control system” that allows you to keep track of the files that make up a project. A collection of files under Git’s control is called a “repository”. GitHub is a hosting service that provides storage for Git repositories and a convenient web interface. It provides several ways to work with the code: You can create a copy of the repository on GitHub by pressing the Fork button. If you don’t already have a GitHub account, you’ll need to create one. After forking, you’ll have your own repository on GitHub that you can use to keep track of code you write. Then you can “clone” the repository, which downloads a copy of the files to your computer. Alternatively, you could clone the repository without forking. If you choose this option, you don’t need a GitHub account, but you won’t be able to save your changes on GitHub. If you don’t want to use Git at all, you can download the code in a ZIP archive using the Download button on the GitHub page, or this link: thinkdast.com/zip. After you clone the repository or unzip the ZIP file, you should have a directory called ThinkDataStructures with a subdirectory called code. The examples in this book were developed and tested using Java SE Development Kit 7. If you are using an older version, some examples will not work. If you are using a more recent version, they should all work. Contributors and Attributions This book is an adapted version of a curriculum I wrote for the Flatiron School in New York City, which offers a variety of online classes related to programming and web development. They offer a class based on this material, which provides an online development environment, help from instructors and other students, and a certificate of completion. You can find more information at http://flatironschool.com. At the Flatiron School, Joe Burgess, Ann John, and Charles Pletcher provided guidance, suggestions, and corrections from the initial specification all the way through implementation and testing. Thank you all! I am very grateful to my technical reviewers, Barry Whitman, Patrick White, and Chris Mayfield, who made many helpful suggestions and caught many errors. Of course, any remaining errors are my fault, not theirs! Thanks to the instructors and students in Data Structures and Algorithms at Olin College, who read this book and provided useful feedback. 1 https://eng.libretexts.org/@go/page/13100 If you have comments or ideas about the text, please send them to: [email protected]. 2 https://eng.libretexts.org/@go/page/13100  CHAPTER OVERVIEW 1: Interfaces This book presents three topics: Data structures: Starting with the structures in the Java Collections Framework (JCF), you will learn how to use data structures like lists and maps, and you will see how they work. Analysis of algorithms: I present techniques for analyzing code and predicting how fast it will run and how much space (memory) it will require. Information retrieval: To motivate the first two topics, and to make the exercises more interesting, we will use data structures and algorithms to build a simple web search engine. Here’s an outline of the order of topics: We’ll start with the List interface and you will write classes that implement this interface two different ways. Then we’ll compare your implementations with the Java classes ArrayList and LinkedList. Next I’ll introduce tree-shaped data structures and you will work on the first application: a program that reads pages from Wikipedia, parses the contents, and navigates the resulting tree to find links and other features. We’ll use these tools to test the “Getting to Philosophy” conjecture (you can get a preview by reading thinkdast.com/getphil). We’ll learn about the Map interface and Java’s HashMap implementation. Then you’ll write classes that implement this interface using a hash table and a binary search tree. Finally, you will use these classes (and a few others I’ll present along the way) to implement a web search engine, including: a crawler that finds and reads pages, an indexer that stores the contents of Web pages in a form that can be searched efficiently, and a retriever that takes queries from a user and returns relevant results. Let’s get started. 1.1: Why are there two kinds of List? 1.2: Interfaces in Java 1.3: The List Interface 1.4: Exercise 1 This page titled 1: Interfaces is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Allen B. Downey (Green Tea Press). 1 1.1: Why are there two kinds of List? When people start working with the Java Collections Framework, they are sometimes confused about ArrayList and LinkedList. Why does Java provide two implementations of the List interface ? And how should you choose which one to use? We will answer these questions in the next few chapters. I’ll start by reviewing interfaces and the classes that implement them, and I’ll present the idea of “programming to an interface”. In the first few exercises, you’ll implement classes similar to ArrayList and LinkedList, so you’ll know how they work, and we’ll see that each of them has pros and cons. Some operations are faster or use less space with ArrayList; others are faster or smaller with LinkedList. Which one is better for a particular application depends on which operations it performs most often. This page titled 1.1: Why are there two kinds of List? is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Allen B. Downey (Green Tea Press). 1.1.1 https://eng.libretexts.org/@go/page/12722 1.2: Interfaces in Java A Java interface specifies a set of methods; any class that implements this interface has to provide these methods. For example, here is the source code for Comparable, which is an interface defined in the package java.lang: 1 public interface Comparable { 2 public int compareTo(T o); 3 } This interface definition uses a type parameter, T, which makes Comparable a generic type. In order to implement this interface , a class has to Specify the type T refers to, and Provide a method named compareTo that takes an object as a parameter and returns an int. For example, here’s the source code for java.lang.Integer: 1 public final class Integer extends Number implements Comparable { 2 public int compareTo(Integer anotherInteger) { 3 int thisVal = this.value; 4 int anotherVal = anotherInteger.value; 5 return (thisVal= array.length) { 03 // make a bigger array and copy over the elements 04 E[] bigger = (E[]) new Object[array.length * 2]; 05 System.arraycopy(array, 0, bigger, 0, array.length); 06 array = bigger; 07 } 08 array[size] = element; 09 size++; 10 return true; 11 } If there are no unused spaces in the array, we have to create a bigger array and copy over the elements. Then we can store the element in the array and increment size. 2.3.1 https://eng.libretexts.org/@go/page/12731 It might not be obvious why this method returns a boolean, since it seems like it always returns true. As always, you can find the answer in the documentation: thinkdast.com/colladd. It’s also not obvious how to analyze the performance of this method. In the normal case, it’s constant time, but if we have to resize the array, it’s linear. I’ll explain how to handle this in Section 3.2. Finally, let’s look at get; then you can get started on the exercises. 1 public T get(int index) { 2 if (index < 0 || index >= size) { 3 throw new IndexOutOfBoundsException(); 4 } 5 return array[index]; 6 } Actually, get is pretty simple: if the index is out of bounds, it throws an exception; otherwise it reads and returns an element of the array. Notice that it checks whether the index is less than size, not array.length, so it’s not possible to access the unused elements of the array. In MyArrayList.java, you’ll find a stub for set that looks like this: 1 public T set(int index, T element) { 2 // TODO: fill in this method. 3 return null; 4 } Read the documentation of set at thinkdast.com/listset, then fill in the body of this method. If you run MyArrayListTest again, testSet should pass. HINT Try to avoid repeating the index-checking code. Your next mission is to fill in indexOf. As usual, you should read the documentation at thinkdast.com/listindof so you know what it’s supposed to do. In particular, notice how it is supposed to handle null. I’ve provided a helper method called equals that compares an element from the array to a target value and returns true if they are equal (and it handles null correctly). Notice that this method is private because it is only used inside this class; it is not part of the List interface. When you are done, run MyArrayListTest again; testIndexOf should pass now, as well as the other tests that depend on it. Only two more methods to go, and you’ll be done with this exercise. The next one is an overloaded version of add that takes an index and stores the new value at the given index, shifting the other elements to make room, if necessary. Again, read the documentation at thinkdast.com/listadd, write an implementation, and run the tests for confirmation. HINT Avoid repeating the code that makes the array bigger. Last one: fill in the body of remove. The documentation is at thinkdast.com/listrem. When you finish this one, all tests should pass. Once you have your implementation working, compare it to mine, which you can read at thinkdast.com/myarraylist. This page titled 2.3: Exercise 2 is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Allen B. Downey (Green Tea Press). 2.3.2 https://eng.libretexts.org/@go/page/12731  CHAPTER OVERVIEW 3: ArrayList This chapter kills two birds with one stone: I present solutions to the previous exercise and demonstrate a way to classify algorithms using amortized analysis. 3.1: Classifying MyArrayList methods 3.2: Classifying add 3.3: Problem Size 3.4: Linked Data Structures 3.5: Exercise 3 3.6: A note on garbage collection This page titled 3: ArrayList is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Allen B. Downey (Green Tea Press). 1 3.1: Classifying MyArrayList methods For many methods, we can identify the order of growth by examining the code. For example, here’s the implementation of get from MyArrayList: 1 public E get(int index) { 2 if (index < 0 || index >= size) { 3 throw new IndexOutOfBoundsException(); 4 } 5 return array[index]; 6 } Everything in get is constant time, so get is constant time. No problem. Now that we’ve classified get, we can classify set, which uses it. Here is our implementation of set from the previous exercise: 1 public E set(int index, E element) { 2 E old = get(index); 3 array[index] = element; 4 return old; 5 } One slightly clever part of this solution is that it does not check the bounds of the array explicitly; it takes advantage of get, which raises an exception if the index is invalid. Everything in set, including the invocation of get, is constant time, so set is also constant time. Next we’ll look at some linear methods. For example, here’s my implementation of indexOf: 1 public int indexOf(Object target) { 2 for (int i = 0; iindex; i--) { 10 array[i] = array[i-1]; 11 } 12 // put the new one in the right place 13 array[index] = element; 14 } This two-parameter version, called add( int , E), uses the one-parameter version, called add(E), which puts the new element at the end. Then it shifts the other elements to the right, and puts the new element in the correct place. Before we can classify the two-parameter add( int , E), we have to classify the one-parameter add(E): 01 public boolean add(E element) { 02 if (size >= array.length) { 03 // make a bigger array and copy over the elements 04 E[] bigger = (E[]) new Object[array.length * 2]; 05 System.arraycopy(array, 0, bigger, 0, array.length); 06 array = bigger; 07 } 08 array[size] = element; 09 size++; 10 return true; 11 } The one-parameter version turns out to be hard to analyze. If there is an unused space in the array, it is constant time, but if we have to resize the array, it’s linear because System.arraycopy takes time proportional to the size of the array. So is add constant time or linear? We can classify this method by thinking about the average number of operations per add over a series of n adds. For simplicity, assume we start with an array that has room for 2 elements. The first time we call add, it finds unused space in the array, so it stores 1 element. The second time, it finds unused space in the array, so it stores 1 element. The third time, we have to resize the array, copy 2 elements, and store 1 element. Now the size of the array is 4. The fourth time stores 1 element. The fifth time resizes the array, copies 4 elements, and stores 1 element. Now the size of the array is 8. The next 3 adds store 3 elements. The next add copies 8 and stores 1. Now the size is 16. The next 7 adds store 7 elements. And so on. Adding things up: After 4 adds, we’ve stored 4 elements and copied 2. After 8 adds, we’ve stored 8 elements and copied 6. After 16 adds, we’ve stored 16 elements and copied 14. By now you should see the pattern: to do n adds, we have to store n elements and copy n − 2. So the total number of operations is n + n − 2 , which is 2n − 2. 3.2.1 https://eng.libretexts.org/@go/page/12737 To get the average number of operations per add, we divide the total by n; the result is 2 − 2/n. As n gets big, the second term, 2/n, gets small. Invoking the principle that we only care about the largest exponent of n, we can think of add as constant time. It might seem strange that an algorithm that is sometimes linear can be constant time on average. The key is that we double the length of the array each time it gets resized. That limits the number of times each element gets copied. Otherwise — if we add a fixed amount to the length of the array, rather than multiplying by a fixed amount — the analysis doesn’t work. This way of classifying an algorithm, by computing the average time in a series of invocations, is called amortized analysis. You can read more about it at thinkdast.com/amort. The key idea is that the extra cost of copying the array is spread, or “amortized”, over a series of invocations. Now, if add(E) is constant time, what about add( int , E)? After calling add(E), it loops through part of the array and shifts elements. This loop is linear, except in the special case where we are adding at the end of the list. So add( int , E) is linear. This page titled 3.2: Classifying add is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Allen B. Downey (Green Tea Press). 3.2.2 https://eng.libretexts.org/@go/page/12737 3.3: Problem Size The last example we’ll consider is removeAll; here’s the implementation in MyArrayList: 1 public boolean removeAll(Collection collection) { 2 boolean flag = true; 3 for (Object obj: collection) { 4 flag &= remove(obj); 5 } 6 return flag; 7 } Each time through the loop, removeAll invokes remove, which is linear. So it is tempting to think that removeAll is quadratic. But that’s not necessarily the case. In this method, the loop runs once for each element in collection. If collection contains m elements and the list we are removing from contains n elements, this method is in O(nm). If the size of collection can be considered constant, removeAll is linear with respect to n. But if the size of the collection is proportional to n, removeAll is quadratic. For example, if collection always contains 100 or fewer elements, removeAll is linear. But if collection generally contains 1% of the elements in the list, removeAll is quadratic. When we talk about problem size, we have to be careful about which size, or sizes, we are talking about. This example demonstrates a pitfall of algorithm analysis: the tempting shortcut of counting loops. If there is one loop, the algorithm is often linear. If there are two loops (one nested inside the other), the algorithm is often quadratic. But be careful! You have to think about how many times each loop runs. If the number of iterations is proportional to n for all loops, you can get away with just counting the loops. But if, as in this example, the number of iterations is not always proportional to n, you have to give it more thought. This page titled 3.3: Problem Size is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Allen B. Downey (Green Tea Press). 3.3.1 https://eng.libretexts.org/@go/page/12738 3.4: Linked Data Structures For the next exercise I provide a partial implementation of the List interface that uses a linked list to store the elements. If you are not familiar with linked lists, you can read about them at thinkdast.com/linkedlist, but this section provides a brief introduction. A data structure is “linked” if it is made up of objects, often called “nodes”, that contain references to other nodes. In a linked list, each node contains a reference to the next node in the list. Other linked structures include trees and graphs, in which nodes can contain references to more than one other node. Here’s a class definition for a simple node: 01 public class ListNode { 02 public Object data; 03 public ListNode next; 04 05 public ListNode() { 06 this.data = null; 07 this.next = null; 08 } 09 10 public ListNode(Object data) { 11 this.data = data; 12 this.next = null; 13 } 14 15 public ListNode(Object data, ListNode next) { 16 this.data = data; 17 this.next = next; 18 } 19 20 public String toString() { 21 return "ListNode(" + data.toString() + ")"; 22 } 23 } The ListNode object has two instance variables: data is a reference to some kind of Object, and next is a reference to the next node in the list. In the last node in the list, by convention, next is null. ListNode provides several constructors, allowing you to provide values for data and next, or initialize them to the default value, null. Figure 3.4.1: Object diagram of a linked list. You can think of each ListNode as a list with a single element, but more generally, a list can contain any number of nodes. There are several ways to make a new list. A simple option is to create a set of ListNode objects, like this: 1 ListNode node1 = new ListNode(1); 2 ListNode node2 = new ListNode(2); 3.4.1 https://eng.libretexts.org/@go/page/12739  3 ListNode node3 = new ListNode(3); And then link them up, like this: 1 node1.next = node2; 2 node2.next = node3; 3 node3.next = null; Alternatively, you can create a node and link it at the same time. For example, if you want to add a new node at the beginning of a list, you can do it like this: 1 ListNode node0 = new ListNode(0, node1); After this sequence of instructions, we have four nodes containing the Integers 0, 1, 2, and 3 as data, linked up in increasing order. In the last node, the next field is null. Figure 3.4.1 is an object diagram that shows these variables and the objects they refer to. In an object diagram, variables appear as names inside boxes, with arrows that show what they refer to. Objects appear as boxes with their type on the outside (like ListNode and Integer) and their instance variables on the inside. This page titled 3.4: Linked Data Structures is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Allen B. Downey (Green Tea Press). 3.4.2 https://eng.libretexts.org/@go/page/12739 3.5: Exercise 3 In the repository for this book, you’ll find the source files you need for this exercise: MyLinkedList.java contains a partial implementation of the List interface using a linked list to store the elements. MyLinkedListTest.java contains JUnit tests for MyLinkedList. Run ant MyArrayList to run MyArrayList.java, which contains a few simple tests. Then you can run ant MyArrayListTest to run the JUnit tests. Several of them should fail. If you examine the source code, you’ll find three TODO comments indicating the methods you should fill in. Before you start, let’s walk through some of the code. Here are the instance variables and the constructor for MyLinkedList: 1 public class MyLinkedList implements List { 2 private int size; // keeps track of the number of elements 3 private Node head; // reference to the first node 4 5 public MyLinkedList() { 6 head = null; 7 size = 0; 8 } 9 } As the comments indicate, size keeps track of how many elements are in MyLinkedList; head is a reference to the first Node in the list or null if the list is empty. Storing the number of elements is not necessary, and in general it is risky to keep redundant information, because if it’s not updated correctly, it creates opportunities for error. It also takes a little bit of extra space. But if we store size explicitly, we can implement the size method in constant time; otherwise, we would have to traverse the list and count the elements, which requires linear time. Because we store size explicitly, we have to update it each time we add or remove an element, so that slows down those methods a little, but it doesn’t change their order of growth, so it’s probably worth it. The constructor sets head to null , which indicates an empty list, and sets size to 0. This class uses the type parameter E for the type of the elements. If you are not familiar with type parameters, you might want to read this tutorial: thinkdast.com/types. The type parameter also appears in the definition of Node, which is nested inside MyLinkedList: 1 private class Node { 2 public E data; 3 public Node next; 4 5 public Node(E data, Node next) { 6 this.data = data; 7 this.next = next; 8 } 9 } Other than that, Node is similar to ListNode above. Finally, here’s my implementation of add: 01 public boolean add(E element) { 02 if (head == null) { 03 head = new Node(element); 04 } else { 05 Node node = head; 3.5.1 https://eng.libretexts.org/@go/page/12740  06 // loop until the last node 07 for ( ; node.next != null; node = node.next) {} 08 node.next = new Node(element); 09 } 10 size++; 11 return true; 12 } This example demonstrates two patterns you’ll need for your solutions: 1. For many methods, we have to handle the first element of the list as a special case. In this example, if we are adding the first element of a list, we have to modify head. Otherwise, we traverse the list, find the end, and add the new node. 2. This method shows how to use a for loop to traverse the nodes in a list. In your solutions, you will probably write several variations on this loop. Notice that we have to declare node before the loop so we can access it after the loop. Now it’s your turn. Fill in the body of indexOf. As usual, you should read the documentation, at thinkdast.com/listindof, so you know what it is supposed to do. In particular, notice how it’s supposed to handle null. As in the previous exercise, I provide a helper method called equals that compares an element from the array to a target value and checks whether they are equal — and it handles null correctly. This method is private because it is used inside this class but it is not part of the List interface. When you are done, run the tests again; testIndexOf should pass now, as well as the other tests that depend on it. Next, you should fill in the two-parameter version of add, which takes an index and stores the new value at the given index. Again, read the documentation at thinkdast.com/listadd, write an implementation, and run the tests for confirmation. Last one: fill in the body of remove. The documentation is here: thinkdast.com/listrem. When you finish this one, all tests should pass. Once you have your implementation working, compare it to the version in the solution directory of the repository. This page titled 3.5: Exercise 3 is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Allen B. Downey (Green Tea Press). 3.5.2 https://eng.libretexts.org/@go/page/12740 3.6: A note on garbage collection In MyArrayList from the previous exercise, the array grows if necessary, but it never shrinks. The array never gets garbage collected, and the elements don’t get garbage collected until the list itself is destroyed. One advantage of the linked list implementation is that it shrinks when elements are removed, and the unused nodes can get garbage collected immediately. Here is my implementation of the clear method: 1 public void clear() { 2 head = null; 3 size = 0; 4 } When we set head to null , we remove a reference to the first Node. If there are no other references to that Node (and there shouldn’t be), it will get garbage collected. At that point, the reference to the second Node is removed, so it gets garbage collected, too. This process continues until all nodes are collected. So how should we classify clear? The method itself contains two constant time operations, so it sure looks like it’s constant time. But when you invoke it, you make the garbage collector do work that’s proportional to the number of elements. So maybe we should consider it linear! This is an example of what is sometimes called a performance bug: a program that is correct in the sense that it does the right thing, but it doesn’t belong to the order of growth we expected. In languages like Java that do a lot of work, like garbage collection, behind the scenes, this kind of bug can be hard to find. This page titled 3.6: A note on garbage collection is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Allen B. Downey (Green Tea Press). 3.6.1 https://eng.libretexts.org/@go/page/12741  CHAPTER OVERVIEW 4: LinkedList This chapter presents solutions to the previous exercise and continues the discussion of analysis of algorithms. 4.1: Classifying MyLinkedList methods 4.2: Comparing MyArrayList and MyLinkedList 4.3: Profiling 4.4: Interpreting results 4.5: Exercise 4 This page titled 4: LinkedList is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Allen B. Downey (Green Tea Press). 1 4.1: Classifying MyLinkedList methods My implementation of indexOf is below. Read through it and see if you can identify its order of growth before you read the explanation. 01 public int indexOf(Object target) { 02 Node node = head; 03 for (int i=0; i= size) { 03 throw new IndexOutOfBoundsException(); 04 } 05 Node node = head; 06 for (int i=0; i