Hi. In this section we're going to look at more operations on list. In the previous lesson, we learned how to construct lists and we looked at some of the basic operations available on them. In this lesson, we're going to see how to insert elements into a list, how we can access a particular element of a list, and learn about the data layout of the lists and how that impacts how we work with lists. To be able to answer these questions, we need to know how a list is laid out in memory. Now list is one of two things, it's either the empty list which we call nil, or it's a pair which contains a head and a tail. The head holds an element and the tail holds the rest of the list. A pair in Scala is written as two colons, so we have some examples here. Our first example is the simplest list, which is the empty list, just nil. Next example is a list containing one element, we have a pair and there are two colons and the pair has a head which was an element, in this case one and the tail, which is the rest of the list, which in this case is nil, the empty list. Then we can keep using this construction to calculate longer lists. For example here we have a pair holding one as the element and the tail is another list. Then this rest of the list consists of a pair holding element two, the rest that list and that goes down, we have a pair holding three and then finally, the list ends at nil. This recursive construction allows us to construct lists of arbitrary length. One very important point about lists in Scala is that they are immutable. This means you can't change the elements within the list or the structure of the list once is created. If you want a different list than you have to create another one, however, you can reuse parts of a list in constructing that new list. Later on we'll learn a motivation for immutability. Right now we're going to see how we can work with this restriction. Look at the following example, we have this list here contacts1 which contains Alice and Bob are contacts. Now from this we can create another list with a new contact let's call them Carol, added to the front. And we can do it like so, using a new pair which includes the original contacts1 list as the tail of that list. Note that we haven't changed contact1 at all to do this. However, we have constructed a new list with a head Carol, and a tail, our original contacts list. This shows how we can reuse parts of a list structure to construct a new list. It can be helpful to illustrate this graphically, so here we have the original list containing Alice and Bob, represented with the graphical notation we used earlier. What this tells us is that the list consists of first a pair which holds Alice as its element and here's the rest of the list, and the rest of that list is a pair, which holds Bob as its elements, and then nil as the tail. Now when we construct a new list with Carol, what we do is create a pair which points to Carol as the head and the tail the rest of the list is just a list we had originally. This shows us how we can reuse part of existing lists to construct new lists. It's important to realize that constructing a new list by prepending an element to an existing list is a constant time operation, this means it takes the same amount of time, no matter the length of the list that we prepending to. We don't copy the tail of the list, we just reuse it. There are lots of other data structures that do this and they used fairly extensively in the Scala standard library, these types of data structures are called persistent data structures because you never change the previous state of them. Calling the list constructor, which we saw when we first started learning about lists, is actually equivalent to prepending of the elements onto the empty list nil, as shown on the slide. Note that the double colon operator is right associative. This means it goes from right to left, we build the list starting with the empty list Nil and adding elements to the front of that first Bob, then Alice in this case. If we want to write this in method call style, were do as shown here, have nil and we call the double colon method on it with Bob as a parameter and then call the double colon method with Alice as a parameter, this is a general rule in Scala. Operators that end with colon in the name are right associative, that is they work from right to left. This is in contrast to normal operators such as plus that go from left to right. Now that we've learned how to build lists, let's look at how we do the opposite, take them apart or decompose them. We can do this with pattern matching and as usual, the syntax of pattern matching matches the syntax we use to construct a list. Say for example, if we want to look for the empty list, we can use the case nil as shown here. If we want to look for a list that contains an element and a tail, we would use the pair syntax. We can extend this syntax to look for more elements in a list, for example, if we want to get the second element from a list, we could use the pattern shown here, looking for first element and a pair and the second element, then a pair and then perhaps the empty list if we're expecting the list to only have two elements. Note the underscore case here, this is what's called a wildcard pattern it matches anything which could be an empty lists, a list with one contact or a list with more than two contacts, anything that the previous pattern didn't match. Let's think about what would happen if instead of using the wildcard pattern we had written pattern and such as case nil here. In this case we wouldn't be handling all of the possible inputs, we wouldn't, for example, handle a list with more than two elements. One thing that's really nice about Scala is that the compiler will actually detect this and give us a warning, this type of warnings is called exhaustivity checking, it's telling us that we're not matching all of the possible cases. This is very handy for preventing bugs in our code. Instead of using pattern matching, we can also access the elements of a list using the head method, the tail method, or access them by index. Here's some examples. First, we construct a list fruits here, which contains three elements, apples, oranges, and pears. If we call the head method on fruits, we get back the first element in the list, in this case apples. Calling the tail method gets us the rest of the list, the list oranges and pears. Getting the head of the tail, gets us the first element in the tail of the list, oranges. We can also access elements by index using this function call notation. Index zero is the first element in the list, apples and index two is the last element in the list, pears. Note that these operations can raise an exception if you, for example, try to get a head or tail of an empty list or access an index that does not exist. Also note that accessing elements by index is in general not efficient, we'll talk about this on the next slide. The table on the slide summarizes the performance characteristics of some of the methods on list. This tells us that prepending elements were list using the double colon method takes a constant amount of time no matter the length of the list, so does accessing the head or the tail of a list. Random access, however, that is accessing by index takes time as proportion to the length of the list and the index, so does calling the size method to get the number of elements in the list. That is it for this section, to summarize some of the key points. Lists are linear immutable sequences, we can construct them using the double colon operator and we can deconstruct them using the same syntax with pattern matching. They're not efficient for random access, but they are very efficient when we want to access elements one at a time starting from the head.
