# Lecture 10 -- Memory Addresses and Arrays ## Motivating Questions Is there a way to get list elements all in consecutive spaces in memory? ## Conceptual Study Questions - If we create a new array of size `z` at address `@1XXX`, then create a new `Course` object, at what address would the `Course` be stored? - What's the difference between an array and an arraylist? ## Memory Addresses Up until now, we've drawn our memory diagrams using arrows to connect names to objects. In reality, objects live within locations (addresses) in the memory of your computer. The heap looks something like this, where `@XXXX` is the notation for memory address XXXX. In this course, we'll use 4-digit numbers for addresses. The starting number for a chunk of memory is arbitrary, but it is important that the addresses are consecutive. **Heap** | | | | -------- | -------- | | @1001 | null | | @1002 | null | | @1003 | null | | @1004 | null | | @1005 | null | | @1006 | null | | @1007 | null | Let's take a look at how these addresses get populated. Consider the following program: ```=java= public void Example() { MutableList<Integer> L = new MutableList<>(); L.addFirst(6); L.addFirst(2); Boa teenBoa= new Boa(“Scout”, 10, “chips”); L.addFirst(3); } ``` Each time the program processes a `new` command, it puts the new object in the next available memory address. If you would have drawn an arrow to an object, you write the address instead. Here's the diagram for the above program **Environment:** - L --> @1001 - teenBoa --> @1004 **Heap:** | | | | -------- | -------- | | @1001 | MutableList(start = @1005) | | @1002 | Node(data = 6, next = null) | | @1003 | Node(data = 2, next = @1002) | | @1004 | Boa(name = “Scout”, length = 10, eats = “chips”) | | @1005 | Node(data = 3, next = @1003) | | @1006 | null | | @1007 | null | What are the contents of the list `L` in order? Start from `L` in the environment. That says that the list is in address `@1001`. The object in `@1001` says that the first node in the list is in location `@1005` (value 3). The next node is in `@1003` (value 2), and the next Node from there is in `@1002` (value 6). Thus, `L` references the list `[3, 2, 6]`. It is worth noting that the `Node` objects for the list aren't in consecutive memory locations. The objects can end up scattered all over memory, depending on what other objects have been created in the heap intertwined with populating the list. Let's look at another example, this time from another perspective. Imagine that the following heap contents resulted from creating the list `[8, 3, 6, 4]`. What was the program that generated this heap layout, in terms of calls to `addFirst` and `addLast`? **Heap:** | | | | -------- | -------- | @1012 | MutableList(start:@1017) @1013 | Node(item:6, next:@1016) @1014 | Node(item:3, next:@1013) @1015 | Course(name = “CSCI1410”, enrollment = 200) @1016 | Node(item:4, next:null) @1017 | Node(item:8, next:@1014) @1018 | null The key to answering this is remembering that the objects get put into the heap in the order that they were created. That means that the program created objects in the following order: ```=java new MutableList() new Node(6, ...) new Node(3, ...) new Course(...) new Node(4, ...) new Node(8, ...) ``` What remains is to determine whether the `new Node` statements came from `addFirst` or `addLast` calls. For that, we look at the order in the final list `[8, 3, 6, 4]`. ```=java L = new MutableList() L.addFirst(6) // could also be addLast L.addFirst(3) // since 3 comes before 6 new Course(...) L.addLast(4) // since 4 comes after 6 L.addFirst(8) // since 8 is at the front of the list ``` ## Finding items by position Now, let's say we wanted to write a method to find the element at a particular position in the list (this is the `get` method that you wrote in homework 2). Since the Nodes could be anywhere in memory, we have to follow the references (arrows) from Node to Node, counting off until we get to the one we want. The memory diagram helps show why `get` must be linear. ## An alternative memory layout Imagine instead that the list `[8, 3, 6, 4]` (and the `Course` object were laid out in the heap as follows (imagine `ConsecList` were a new kind of list object in which the elements were stored in order in consecutive memory locations): **Heap:** | | | | -------- | -------- | @1012 | ConsecList @1013 | 8 @1014 | 3 @1015 | 6 @1016 | 4 @1017 | Course(name = “CSCI1410”, enrollment = 200) @1018 | null Now, a method to get an element based on position doesn't need to search along the list. We could *compute* the address where each position is located from the address of the `ConsecList` object. For example: - the result of `get(0)` is in `@1013`, which is `@1012 + 1` - the result of `get(1)` is in `@1014`, which is `@1012 + 2` - the result of `get(2)` is in `@1015`, which is `@1012 + 3` - the result of `get(3)` is in `@1016`, which is `@1012 + 4` From here, we can see the general formula would be `get(p)` is in `ConsecList_address + 1 + p`. The `+ 1` advances from the address for the list to the address of the first element; the `+ p` counts off the elements. Now Java doesn't let us do arithmetic on addresses as we've done here (though languages like C and C++ do). However, there is a data structure called an *array* that does work like this. ## Arrays Arrays are built in to every programming language (sometimes they are called "vectors" instead). An array is a sequence of consecutive memory addresses. Languages come with notations for accessing specific positions in the array. Here's an example: ```=java= import java.util.Arrays; public class Main { public static void main(String[] args) { // square brackets after a type means “array with given type” String[] words = new String[4]; // 4 is the # of slots words[2] = "on"; // store “on” in the third slot (count from 0) new Course("CSCI1410", 200); words[0] = "meet"; // store “meet” in the first slot System.out.println(Arrays.toString(words)); // need the above notation to convert an array to a string } ``` Line 6 shows the type and notation to create an array. The type notation for an array consists of the type of the content followed by square brackets (e.g., `String[]`). To create an array, we use similar notation, but with a number inside the square brackets. That number indicates how many memory locations to set aside for the array. Notation like `words[2]` (lines 7 and 8) is used to either look up the content in a specific position, or to store data in a specific position. Here's the address-based memory diagram for the above program: **Environment:** words --> @1012 **Heap:** | | | | -------- | -------- | @1012 | Array String[4] @1013 | “meet” @1014 | null @1015 | “on” @1016 | null @1017 | Course(CSCI1410, 200) Locations `@1013` through `@1016` are reserved for the array, which is why the allocated `Course` has gone into address `@1018`. ## Introduction to ArrayLists The `ConsecList` class that we sketched out earlier in these notes are a kind of list that store their elements in arrays, rather than in a series of `Node` objects. This kind of list is actually called an `ArrayList` in Java. An `ArrayList` has all of the usual list operations (such as `addFirst`). In contrast, arrays don't come with methods: they simply have a `length` and the ability to access elements as shown in the above code sample. Let's build our own class for arraylists to see how they work. To avoid conflict with Java's built-in `ArrayList` class, we'll call ours `ArrList`. For this example, we'll make array lists containing strings (rather than generic types -- we'll get to that later). ```=java= public class ArrList { String[] theArray; // the underlying array that stores the elements // constructor with an array size specified public ArrList(int initSize) { this.theArray = new String[initSize]; } // constructor with a default array size of 8 public ArrList() { this.theArray = new String[8]; } } ``` This code shows two constructors: one takes the number of locations for the underlying array from the programmer, while the other uses a built-in default. Java's `ArrayList`s work similarly -- if you make a new `ArrayList` without specifying the number of locations, Java creates the array with a default size. It remains to add methods such as `addFirst` and `addLast` to our `ArrList` class. We'll work on those in the next lecture.