CS 61B, Data Structures
Matt's Notes
Welcome! Here are some notes from our sections together!
Click on any link below to view.
Dis 00. Template.
January 00, 2018.
Dis 04. Inheritance.
February 6, 2018.
Click here to view slides from this discussion.
Dis 03. LinkedLists and Arrays.
January 30, 2018.
Our Story of LinkedLists
We started out with the raw IntList. This was a nice a simple data structure that we could use to store individual integers in a series of connected links.

Next came the Singly Linked List, which allowed us to encapsulate our raw IntList. The advantage of encapsulation is that it allows us to provide for our users methods for performing operations on our data structure so that they do not need to be knowledgeable about the underlying intricacies of our implementation in our to use it; they can simply refer to an API or list of our methods and their descriptions and they can use our data structure like a black box.

Following that, we introduced Sentinels into our Singly Linked List. This was a "dummy" node that had an unimportant item that was always included. The purpose of a sentinel is to remove the need for null checks, since those can be messy in our code or it may be easy to miss a couple situations. Thus, instead of checking if an instance is null, we can check if it has returned back to the sentinel.

Finally, we allowed ourselves to have referenes in both directions, so that we could access both the previous and the next. This was the Doubly Linked List.

Problem Solving Strategies
Whenever you are asked to write a signficant amount of code by hand, first make a concrete example for yourself so that you understand what the problem is asking you to do, so that you get a feel for the operations that may be involved, and so that you have something to check against once you actually start writing code in a bit.

Next, break down the problem into functional parts or steps that you know how to do. If you are stuck, write out the parts of the code that are most obvious to you, even if you have to leave conditions or other things blank. For example, if we have to do an operation repeatedly, you know that there would have to be a loop or a recursive call, so you can set up the components for that first while you're still thinking (loop conditions, incrementations, base cases, etc.). Try to get the general situation working first, and then worry about the edge cases once you're done. Often times, those can be addressed by adding a simple if case at the top of your code later.

Arrays vs LinkedLists
Finally, we informally made observations about the arrays and linkedlists that we worked with today. We'll cover these in more detail later when we study runtime analysis. But for now, we saw that it was easier to get items out of an array, but that it was harder to "resize" them since they are of fixed length and so that would actually require us to make a new array and to copy everything over. LinkedLists on the other hand, require that we traverse the list in order to access a particular item, but it only requires us to switch around a few pointers to insert or delete items.
Dis 02. Static and IntLists.
January 23, 2018.
Architecture of a Class
Typical class definitions contain three sections of code.

First we have fields, which consist of class variables and instance variables that are useful for storing attributes, state, characteristics, data, etc. Class variables have the keyword static and thus each only hold one value that is shared among all object instances of the class. Instance variables are non-static declarations that contain unique values for every object instance made.

Next are the constructors, which are necessarily invoked when the user of your class wants to make a new object instance. The code inside constructors should be responsible for accepting some arguments, and storing those inputs into the fields.

Finally we have methods or functions. These may accept input, and may interact with and modify the fields before potentially returning some result.

Here is an example of these three components in action.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21  
public class Waffle {

    // Fields
    private boolean isDelicious;
    private int numStrawberries;

    // Constructors
    public Waffle(boolean isDelicious, int numStrawberries) {
        this.isDelicious = isDelicious;
        this.numStrawberries = numStrawberries;
    }

    // Methods
    public boolean isDelicious() {
        return isDelicious;
    }

    public void addStrawberries(int num) {
        this.numStrawberries += num;
    }
}
Static Methods and Variables
Fields can be labeled as static (class variables), and methods can also be labeled as static.

For static fields, there is only one variable that is shared among all instances of the class, and thus consequently, all object instances see the same value for that field (again, because there is a single variable shared among all; there is not one variable per instance). To call upon a static field, we use dot notation on the class name rather than on a particular instance.

For static methods, an object instance is not required for the function to be called. As a consequence, it cannot access non-static fields. If you'd like, you can call static methods on an object instance, but in that case Java will lookup the class of the instance and call it as we've just described.

IntLists
You'll often see statements such as L.rest.rest = L.rest.rest.rest;, but sometimes it seems like the way you follow the "rests" seem different for the left and right sides of the equals sign. Why is that?

Think about what the equals sign means. For example, let's look at an assignment statement such as this: String var = "object";. What this the box and pointer diagram look like?



We can see that var corresponds to a variable box in the diagram, and that the right hand side of the assignment statement was a String object.

In the same way, the left side of the statement L.rest.rest = L.rest.rest.rest; is a variable box in the diagram, and the right hand side is an IntList object. Therefore, when we count the number of "rests" for the left hand side, we stop counting in time so that we are left with the last "rest" variable box so that we can reassign it. When we count for the right hand side, we follow the final "rest" to an Object, and assign the left hand side to reference it.

Walk through this simple example and make sure you understand how this statement works and why.



Destructive vs. Non-Destructive
When writing a destructive function, you want to destroy the original and so you should not be creating new objects. Thus, destructive functions do not use the new keyword.

On the other hand, non-destructive functions want to preserve the original and return a new version. Thus, non-destructive functions should use the new keyword to create fresh objects as the necessary modifications are applied.
Dis 01. Introduction to Reading and Writing Java!
January 16, 2018.
Java programs begin execution starting from a main method public static void main (String[] args) {...}.

Primitives vs. Non-Primitives
We keep track of data using variables. Variables come in two flavors: primitives and non-primitives. Primitives in Java include only the following: byte, short, int, long, float, double, boolean, char. All other kinds of variables are non-primitives. Variables representing primitives store the appropriate raw value, while variables representing non-primitives store references to the actual data.

The creators of Java made this design decision for the language due to efficiency justifications. Imagine that you're in at an interview for your dream job. The manager really loves you and is almost ready to hire you, but first, they'd like to ensure that everything you've said about yourself is true. And so, the manager would like to verify with your best friend that you have indeed been truthful. But now the question is, would it be appropriate for you to clone your best friend so that the manager can chat with them? Probably not...your friend might not appreciate that very much. It makes much more sense to provide the manager with a reference to your friend, a phone number perhaps. This is why Java handles "complicated" (non-primitive) variables using references.

This goes hand-in-hand with what Professor Hug calls the Golden Rule of Equals. When we are drawing box and pointer diagrams, when a variable's contents are asked of, we provide whatever is inside that variable's corresponding box. This means that for primitives we copy the raw value, while for non-primitives we copy the arrow that we have drawn, such that our copied arrow points to the same destination. Given this distinction, if a function takes in both a primitive and a non-primitive as arguments, and it mangles both during the function call, when the function is over, which of the two (or both?) were actually changed? See the example below to find out:



Iteration and Recursion
Often times, we want to write code that does something over and over again. We have two techniques for doing this: iteration and recursion.

Iteration involves using a loop. In Java, one kind of loop is the while loop. To evaluate it, we follow these steps in order:
  1. Evaluate the loop condition. If it is false the loop is over and execution continues starting after the closing curly bracket of the loop.
  2. If it is true, then we start at the top of the loop's body of code and execute those lines in order until we reach its end.
  3. At this point, we go back to step 1 and check the condition again.
It is important to note that even if the condition becomes false in the middle of executing the loop body, the loop does not magically quite immediately. The loop can only quit in between executions of its body (unless there is a break statement, an Exception is thrown, etc.). Another kind of loop is the for loop. This kind of loop was introduced because programmers noticed that loops in general typically contained the initialization of some counter variable, the check of some condition against that counter variable, and the modification of this counter variable as iterations occur. For loops simply bundle these three elements together into a visually convenient place. We evaluate for loops following these steps in order:
  1. Initialize the counter variable.
  2. Evaluate the loop condition. If it is false the loop is over and execution continues starting after the closing curly bracket of the loop.
  3. If it is true, then we start at the top of the loop's body of code and execute those lines in order until we reach its end.
  4. Adjust the counter value according to the specified fashion. Usually an incrementation or decrementation.
  5. At this point, we go back to step 2 and check the condition again.
The other option we have is recursion. This occurs anytime we have a function and that function's body of code contains a statement in which it calls upon itself again. To prevent infinite recursion, we want our recursive functions to contain base cases, which are if statements that provide direct results of the simplest situations, and in all other cases our recursive calls should aim to move our complicated situation closer and closer to one of our base cases.

With the classic Fibonacci exercise (#3 on the worksheet), we saw how there may be many ways to solve the same problem and to arrive at the correct answer. Therefore, simply solving a problem one way is cute and all, but in the real world, that doesn't mean you're done--we want to find the "best" solution. What does "best" mean? It means code that is not only correct, but also fast, memory efficient, and clear to other human readers. In other words, in this class we will learn to consider time efficiency, space efficiency, and style/documentation.