# 6. DLLists and Arrays ## 6. DLLists In Chapter 2.2, we built the `SLList` class, which was better than our earlier naked recursive `IntList` data structure. In this section, we'll wrap up our discussion of linked lists, and also start learning the foundations of arrays that we'll need for an array based list we'll call an `AList`. Along the way, we'll also reveal the secret of why we used the awkward name `SLList` in the previous chapter. **addLast** Consider the `addLast(int x)` method from the previous chapter. ```java public void addLast(int x) { size += 1; IntNode p = sentinel; while (p.next != null) { p = p.next; } p.next = new IntNode(x, null); } ``` The issue with this method is that it is slow. For a long list, the `addLast` method has to walk through the entire list, much like we saw with the `size` method in chapter 2.2. Similarly, we can attempt to speed things up by adding a `last` variable, to speed up our code, as shown below: ```java public class SLList { private IntNode sentinel; private IntNode last; private int size; public void addLast(int x) { last.next = new IntNode(x, null); last = last.next; size += 1; } ... } ``` **Exercise 2.3.1:** Consider the box and pointer diagram representing the `SLList` implementation above, which includes the last pointer. Suppose that we'd like to support `addLast`, `getLast`, and `removeLast` operations. Will the structure shown support rapid `addLast`, `getLast`, and `removeLast` operations? If not, which operations are slow? ![sllist\_last\_pointer.png](https://joshhug.gitbooks.io/hug61b/content/chap2/fig23/sllist_last_pointer.png) **Answer 2.3.1:** `addLast` and `getLast` will be fast, but `removeLast` will be slow. That's because we have no easy way to get the second-to-last node, to update the `last` pointer, after removing the last node. **SecondToLast** The issue with the structure from exercise 2.3.1 is that a method that removes the last item in the list will be inherently slow. This is because we need to first find the second to last item, and then set its next pointer to be null. Adding a `secondToLast` pointer will not help either, because then we'd need to find the third to last item in the list in order to make sure that `secondToLast` and `last` obey the appropriate invariants after removing the last item. **Exercise 2.3.2:** Try to devise a scheme for speeding up the `removeLast` operation so that it always runs in constant time, no matter how long the list. Don't worry about actually coding up a solution, we'll leave that to project 1. Just come up with an idea about how you'd modify the structure of the list (i.e. the instance variables). We'll describe the solution in Improvement #7. **Improvement #7: Looking Back** The most natural way to tackle this issue is to add a previous pointer to each `IntNode`, i.e. ```java public class IntNode { public IntNode prev; public int item; public IntNode next; } ``` In other words, our list now has two links for every node. One common term for such lists is the "Doubly Linked List", which we'll call a `DLList` for short. This is in contrast to a single linked list from chapter 2.2, a.k.a. an `SLList`. The addition of these extra pointers will lead to extra code complexity. Rather than walk you through it, you'll build a doubly linked list on your own in project 1. The box and pointer diagram below shows more precisely what a doubly linked list looks like for lists of size 0 and size 2, respectively. ![dllist\_basic\_size\_0.png](https://joshhug.gitbooks.io/hug61b/content/chap2/fig23/dllist_basic_size_0.png) ![dllist\_basic\_size\_2.png](https://joshhug.gitbooks.io/hug61b/content/chap2/fig23/dllist_basic_size_2.png) **Improvement #8: Sentinel Upgrade** Back pointers allow a list to support adding, getting, and removing the front and back of a list in constant time. There is a subtle issue with this design where the `last` pointer sometimes points at the sentinel node, and sometimes at a real node. Just like the non-sentinel version of the `SLList`, this results in code with special cases that is much uglier than what we'll get after our 8th and final improvement. (Can you think of what `DLList` methods would have these special cases?) One fix is to add a second sentinel node to the back of the list. This results in the topology shown below as a box and pointer diagram. ![dllist\_double\_sentinel\_size\_0.png](https://joshhug.gitbooks.io/hug61b/content/chap2/fig23/dllist_double_sentinel_size_0.png) ![dllist\_double\_sentinel\_size\_2.png](https://joshhug.gitbooks.io/hug61b/content/chap2/fig23/dllist_double_sentinel_size_2.png) An alternate approach is to implement the list so that it is circular, with the front and back pointers sharing the same sentinel node. ![dllist\_circular\_sentinel\_size\_0.png](https://joshhug.gitbooks.io/hug61b/content/chap2/fig23/dllist_circular_sentinel_size_0.png) ![dllist\_circular\_sentinel\_size\_2.png](https://joshhug.gitbooks.io/hug61b/content/chap2/fig23/dllist_circular_sentinel_size_2.png) Both the two-sentinel and circular sentinel approaches work and result in code that is free of ugly special cases, though I personally find the circular approach to be cleaner and more aesthetically beautiful. We will not discuss the details of these implementations, as you'll have a chance to explore one or both in project 1. **Generic DLLists** Our DLLists suffer from a major limitation: they can only hold integer values. For example, suppose we wanted to create a list of Strings: ```java DLList d2 = new DLList("hello"); d2.addLast("world"); ``` The code above would crash, since our `DLList` constructor and `addLast` methods only take an integer argument. Luckily, in 2004, the creators of Java added **generics** to the language, which will allow you to, among other things, create data structures that hold any reference type. The syntax is a little strange to grasp at first. The basic idea is that right after the name of the class in your class declaration, you use an arbitrary placeholder inside angle brackets: `<>`. Then anywhere you want to use the arbitrary type, you use that placeholder instead. For example, our `DLList` declaration before was: ```java public class DLList { private IntNode sentinel; private int size; public class IntNode { public IntNode prev; public int item; public IntNode next; ... } ... } ``` A generic `DLList` that can hold any type would look as below: ```java public class DLList { private IntNode sentinel; private int size; public class IntNode { public IntNode prev; public BleepBlorp item; public IntNode next; ... } ... } ``` Here, `BleepBlorp` is just a name I made up, and you could use most any other name you might care to use instead, like `GloopGlop`, `Horse`, `TelbudorphMulticulus` or whatever. Now that we've defined a generic version of the `DLList` class, we must also use a special syntax to instantiate this class. To do so, we put the desired type inside of angle brackets during declaration, and also use empty angle brackets during instantiation. For example: ```java DLList d2 = new DLList<>("hello"); d2.addLast("world"); ``` Since generics only work with reference types, we cannot put primitives like `int` or `double` inside of angle brackets, e.g. ``. Instead, we use the reference version of the primitive type, which in the case of `int` case is `Integer`, e.g. ```java DLList d1 = new DLList<>(5); d1.insertFront(10); ``` There are additional nuances about working with generic types, but we will defer them to a later chapter of this book, when you've had more of a chance to experiment with them on your own. For now, use the following rules of thumb: * In the .java file **implementing** a data structure, specify your generic type name only once at the very top of the file after the class name. * In other .java files, which use your data structure, specify the specific desired type during declaration, and use the empty diamond operator during instantiation. * If you need to instantiate a generic over a primitive type, use `Integer`, `Double`, `Character`, `Boolean`, `Long`, `Short`, `Byte`, or `Float` instead of their primitive equivalents. Minor detail: You may also declare the type inside of angle brackets when instantiating, though this is not necessary, so long as you are also declaring a variable on the same line. In other words, the following line of code is perfectly valid, even though the `Integer` on the right hand side is redundant. ```java DLList d1 = new DLList(5); ``` At this point, you know everything you need to know to implement the `LinkedListDeque` project on project 1, where you'll refine all of the knowledge you've gained in chapters 2.1, 2.2, and 2.3. ## 6. Arrays So far, we've seen how to harness recursive class definitions to create an expandable list class, including the `IntList`, `SLList`, and `DLList`. In the next two sections of this book, we'll discuss how to build a list class using arrays. This section of this book assumes you've already worked with arrays and is not intended to be a comprehensive guide to their syntax. #### Array Basics To ultimately build a list that can hold information, we need some way to get memory boxes. Prevously, we saw how we could get memory boxes with variable declarations and class instantiations. For example: * `int x;` gives us a 32 bit memory box that stores ints. * `Walrus w1;` gives us a 64 bit memory box that stores Walrus references. * `Walrus w2 = new Walrus(30, 5.6);` gets us 3 total memory boxes. One 64 bit box that stores Walrus references, one 32 bit box that stores the int size of the Walrus, and a 64 bit box that stores the double tuskSize of the Walrus. Arrays are a special type of object that consists of a numbered sequence of memory boxes. This is unlike class instances, which have named memory boxes. To get the ith item of an array, we use bracket notation as we saw in HW0 and Project 0, e.g. `A[i]` to get the `i`th element of A. Arrays consist of: * A fixed integer length, N * A sequence of N memory boxes (N = length) where all boxes are of the same type, and are numbered 0 through N - 1. Unlike classes, arrays do not have methods. **Naive ALists** In this section, we'll build a new class called `AList` that can be used to store arbitrarily long lists of data, similar to our `DLList`. Unlike the `DLList`, the `AList` will use arrays to store data instead of a linked list. **Linked List Performance Puzzle** Suppose we wanted to write a new method for `DLList` called `int get(int i)`. Why would `get` be slow for long lists compared to `getLast`? For what inputs would it be especially slow? You may find the figure below useful for thinking about your answer. ![dllist\_circular\_sentinel\_size\_2.png](https://joshhug.gitbooks.io/hug61b/content/chap2/fig23/dllist_circular_sentinel_size_2.png) **Linked List Performance Puzzle Solution** It turns out that no matter how clever you are, the `get` method will usually be slower than `getBack` if we're using the doubly linked list structure described in section 2.3. This is because, since we only have references to the first and last items of the list, we'll always need to walk through the list from the front or back to get to the item that we're trying to retrieve. For example, if we want to get item #417 in a list of length 10,000, we'll have to walk across 417 forward links to get to the item we want. In the very worst case, the item is in the very middle and we'll need to walk through a number of items proportional to the length of the list (specifically, the number of items divided by two). In other words, our worst case execution time for `get` is linear in the size of the entire list. This in contrast to the runtime for `getBack`, which is constant, no matter the size of the list. Later in the course, we'll formally define runtimes in terms of big O and big Theta notation. For now, we'll stick to an informal understanding. **Our First Attempt: The Naive Array Based List** Accessing the `i`th element of an array takes constant time on a modern computer. This suggests that an array-based list would be capable of much better performance for `get` than a linked-list based solution, since it can simply use bracket notation to get the item of interest. If you'd like to know **why** arrays have constant time access, check out this [Quora post](https://www.quora.com/Why-does-accessing-an-array-element-take-constant-time). **removeLast** The last operation we need to support is `removeLast`. Before we start, we make the following key observation: Any change to our list must be reflected in a change in one or more memory boxes in our implementation. This might seem obvious, but there is some profundity to it. The list is an abstract idea, and the `size`, `items`, and `items[i]` memory boxes are the concrete representation of that idea. Any change the user tries to make to the list using the abstractions we provide (`addLast`, `removeLast`) must be reflected in some changes to these memory boxes in a way that matches the user's expectations. Our invariants provide us with a guide for what those changes should look like. #### Appendix: Extra Information on Arrays There are three valid notations for array creation. Try running the code below and see what happens. Click [here](http://pythontutor.com/iframe-embed.html#code=public%20class%20ArrayCreationDemo%20%7B%0A%20%20public%20static%20void%20main\(String%5B%5D%20args%29%20%7B%0A%20%20%20%20int%5B%5D%20x%3B%0A%20%20%20%20int%5B%5D%20y%3B%0A%20%20%20%20x%20%3D%20new%20int%5B3%5D%3B%0A%20%20%20%20y%20%3D%20new%20int%5B%5D%7B1,%202,%203,%204,%205%7D%3B%0A%20%20%20%20int%5B%5D%20z%20%3D%20%7B9,%2010,%2011,%2012,%2013%7D%3B%0A%09%7D%0A%7D\&codeDivHeight=400\&codeDivWidth=350\&cumulative=false\&curInstr=0\&heapPrimitives=false\&origin=opt-frontend.js\&py=java\&rawInputLstJSON=%5B%5D\&textReferences=false) for an interactive visualization. * `x = new int[3];` * `y = new int[]{1, 2, 3, 4, 5};` * `int[] z = {9, 10, 11, 12, 13};` All three notations create an array. The first notation, used to create `x`, will create an array of the specified length and fill in each memory box with a default value. In this case, it will create an array of length 3, and fill each of the 3 boxes with the default `int` value `0`. The second notation, used to create `y`, creates an array with the exact size needed to accommodate the specified starting values. In this case, it creates an array of length 5, with those five specific elements. The third notation, used to declare **and** create `z`, has the same behavior as the second notation. The only difference is that it omits the usage of `new`, and can only be used when combined with a variable declaration. None of these notations is better than any other. **Array Access and Modification** The following code showcases all of the key syntax we'll use to work with arrays. Try stepping through the code below and making sure you understand what happens when each line executes. To do so, click [here](https://goo.gl/bertuh) for an interactive visualization. With the exception of the final line of code, we've seen all of this syntax before. ```java int[] z = null; int[] x, y; x = new int[]{1, 2, 3, 4, 5}; y = x; x = new int[]{-1, 2, 5, 4, 99}; y = new int[3]; z = new int[0]; int xL = x.length; String[] s = new String[6]; s[4] = "ketchup"; s[x[3] - x[1]] = "muffins"; int[] b = {9, 10, 11}; System.arraycopy(b, 0, x, 3, 2); ``` The final line demonstrates one way to copy information from one array to another. `System.arraycopy` takes five parameters: * The array to use as a source * Where to start in the source array * The array to use as a destination * Where to start in the destination array * How many items to copy For Python veterans, `System.arraycopy(b, 0,x, 3, 2)` is the equivalent of `x[3:5] = b[0:2]` in Python. An alternate approach to copying arrays would be to use a loop. `arraycopy` is usually faster than a loop, and results in more compact code. The only downside is that `arraycopy` is (arguably) harder to read. Note that Java arrays only perform bounds checking at runtime. That is, the following code compiles just fine, but will crash at runtime. ```java int[] x = {9, 10, 11, 12, 13}; int[] y = new int[2]; int i = 0; while (i < x.length) { y[i] = x[i]; i += 1; } ``` Try running this code locally in a java file or in the [visualizer](https://goo.gl/YHufJ6). What is the name of the error that you encounter when it crashes? Does the name of the error make sense? **2D Arrays in Java** What one might call a 2D array in Java is actually just an array of arrays. They follow the same rules for objects that we've already learned, but let's review them to make sure we understand how they work. Syntax for arrays of arrays can be a bit confusing. Consider the code `int[][] bamboozle = new int[4][]`. This creates an array of integer arrays called `bamboozle`. Specifically, this creates exactly four memory boxes, each of which can point to an array of integers (of unspecified length). Try running the code below line-by-lines, and see if the results match your intuition. For an interactive visualization, click [here](http://goo.gl/VS4cOK). ```java int[][] pascalsTriangle; pascalsTriangle = new int[4][]; int[] rowZero = pascalsTriangle[0]; pascalsTriangle[0] = new int[]{1}; pascalsTriangle[1] = new int[]{1, 1}; pascalsTriangle[2] = new int[]{1, 2, 1}; pascalsTriangle[3] = new int[]{1, 3, 3, 1}; int[] rowTwo = pascalsTriangle[2]; rowTwo[1] = -5; int[][] matrix; matrix = new int[4][]; matrix = new int[4][4]; int[][] pascalAgain = new int[][]{{1}, {1, 1}, {1, 2, 1}, {1, 3, 3, 1}}; ``` **Exercise 2.4.1:** After running the code below, what will be the values of x\[0]\[0] and w\[0]\[0]? Check your work by clicking [here](http://goo.gl/fCZ9Dr). ```java int[][] x = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; int[][] z = new int[3][]; z[0] = x[0]; z[1] = x[1]; z[2] = x[2]; z[0][0] = -z[0][0]; int[][] w = new int[3][3]; System.arraycopy(x[0], 0, w[0], 0, 3); System.arraycopy(x[1], 0, w[1], 0, 3); System.arraycopy(x[2], 0, w[2], 0, 3); w[0][0] = -w[0][0]; ``` **Arrays vs. Classes** Both arrays and classes can be used to organize a bunch of memory boxes. In both cases, the number of memory boxes is fixed, i.e. the length of an array cannot be changed, just as class fields cannot be added or removed. The key differences between memory boxes in arrays and classes: * Array boxes are numbered and accessed using `[]` notation, and class boxes are named and accessed using dot notation. * Array boxes must all be the same type. Class boxes can be different types. One particularly notable impact of these difference is that `[]` notation allows us to specify which index we'd like at runtime. For example, consider the code below: ```java int indexOfInterest = askUserForInteger(); int[] x = {100, 101, 102, 103}; int k = x[indexOfInterest]; System.out.println(k); ``` If we run this code, we might get something like: ``` $ javac arrayDemo $ java arrayDemo What index do you want? 2 102 ``` By contrast, specifying fields in a class is not something we do at runtime. For example, consider the code below: ```java String fieldOfInterest = "mass"; Planet p = new Planet(6e24, "earth"); double mass = p[fieldOfInterest]; ``` If we tried compiling this, we'd get a syntax error. ``` $ javac classDemo FieldDemo.java:5: error: array required, but Planet found double mass = earth[fieldOfInterest]; ^ ``` The same problem occurs if we try to use dot notation: ```java String fieldOfInterest = "mass"; Planet p = new Planet(6e24, "earth"); double mass = p.fieldOfInterest; ``` Compiling, we'd get: ``` $ javac classDemo FieldDemo.java:5: error: cannot find symbol double mass = earth.fieldOfInterest; ^ symbol: variable fieldOfInterest location: variable earth of type Planet ``` This isn't a limitation you'll face often, but it's worth pointing out, just for the sake of good scholarship. For what it's worth, there is a way to specify desired fields at runtime called *reflection*, but it is considered very bad coding style for typical programs. You can read more about reflection [here](https://docs.oracle.com/javase/tutorial/reflect/member/fieldValues.html). **You should never use reflection in any 61B program**, and we won't discuss it in our course. In general, programming languages are partially designed to limit the choices of programmers to make code simpler to reason about. By restricting these sorts of features to the special Reflections API, we make typical Java programs easier to read and interpret. **Appendix: Java Arrays vs. Other Languages** Compared to arrays in other languages, Java arrays: * Have no special syntax for "slicing" (such as in Python). * Cannot be shrunk or expanded (such as in Ruby). * Do not have member methods (such as in Javascript). * Must contain values only of the same type (unlike Python).