CS61B(4): References, Recursion, and Lists

Posted on | In , |

This is the lecture note of CS61B - Lecture 4.

In this lecture, we will learn about primitive types and reference types in Java, and use these concepts to construct our first data strucure - Linked Data Structures.

Q1: What's your answer of the following question? Will the change to b affects a?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
class Walrus {
    int weight;
    double tuskSize;

    public Walrus(int w, double t) {
        weight = w;
        tuskSize = t;
    }
}
*/

Walrus a = new Walrus(1000, 8.3);
Walrus b;
b = a;
b.weight = 5;
System.out.println(a);
System.out.println(b);

The answer is yes! And the output is as follows:

1
2
weight: 5, tusk size: 8.30
weight: 5, tusk size: 8.30

Q2: Think about another question, will the change to x affect y?

1
2
3
4
5
6
int x = 5;
int y;
y = x;
x = 2;
System.out.println("x is: " + x);
System.out.println("y is: " + y);

The answer is no, and x is 2 and y is 5.

You may wonder why. To clear up your confusion, let's explore data types in Java world.

Primitive Types

Your computer stores information in memory. And whatever the information you want to store, ultimately it will be encoded as a sequence of ones and zeros.

Actually, sometimes, two different things will be stored as the same bits sequence. For example, number 72 stored as 01001000, and letter H stored as 01001000, too.

So how computer interprets them correctly? The answer is the data type tells Java interpreter how to interpret it.

There are 8 primitive types in Java: byte, short, int, long, float, double, boolean, char.

Reference Types

We already know that there are 8 primitive types in Java. Everything else, including array and string, is a reference type.

The Golden Rule of Equals

This is a very important rule and can help us answer the above puzzles.

  • Given variables x and y, then y = x means copies all bits from x into y.

And reference types also obey this rule. If x and y are reference types, after y = x, x and y will refer to the same object.

Exercise

Try to do the following exercise and make sure you understand everyting so far.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Does the call to doStuff(walrus, x) have an affect on walrus and/or main’s x?

public static void main(String[] args) {
    Walrus walrus = new Walrus(3500, 10.5);
    int x = 9;
    doStuff(walrus, x);
    System.out.println(walrus);
    System.out.println(x);
}

public static void doStuff(Walrus W, int x) {
    W.weight = W.weight - 100;
    x = x - 5;
}

The answer is "walrus will lose 100 lbs, but main’s x will not change".

Linked Data Structures

If you have used Python before, you must be familiar with list. Java has list too.

A list is going to be able to grow arbitrarily large, which is different from array. But you may wonder why list can have arbitrary size. To answer this question, you need to know its data structure under the hood, i.e. Linked List.

We will learn it by building it from scratch. Our goal is to build a linked list as follows,

Create Linked List

You can build it intuitively, even though it is awkward.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class IntList {
    public int first;
    public IntList rest;

    public static void main(String[] args) {
        IntList L = new IntList();
        L.first = 5;
        L.rest = null;

        L.rest = new IntList();
        L.rest.first = 10;
    
        L.rest.rest = new IntList();
        L.rest.rest.first = 15;
    }
}

We can make things slightly better by using constructor.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class IntList {
    public int first;
    public IntList rest;

    public IntList(int f, IntList r) {
        first = f;
        rest = r;
    }

    public static void main(String[] args) {
        IntList L = new IntList(15, null);
        L = new IntList(10, L);
        L = new IntList(5, L);
    }
}

Define size( ) Method

In Python, we use len(list) to get the size of list. In Java, we use L.size(). How can we implement it?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/** Return the size of the list using ... recursion! */
public int size() {
    if (rest == null) {
        return 1;
    }
    return 1 + this.rest.size();
}

/** Return the size of the list using ... iteration! */
public int iterativeSize() {
    IntList p = this;
    int totalSize = 0;

    while (p != null) {
        p = p.rest;
        totalSize++;
    }

    return totalSize;
}

Define get( ) Method

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/** Return the i-th item of the list using ... recursion! */
public int get(int i) {
    if (i == 0) {
        return first;
    }
    return rest.get(i - 1);
}

/** Return the i-th item of the list using ... iteration! */
public int iterativeGet(int i) {
    IntList p = this;

    while (i != 0) {
        p = p.rest;
        i -= 1;
    }

    return p.first;
}

Final code

The following is the overall code we built in this lecture. It reveals the structure of linked list although it is hard to use. In the next lecture, we will improve our implementation of linked list. See you next time 🤠

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public class IntList {
    public int first;
    public IntList rest;

    public IntList(int f, IntList r) {
        first = f;
        rest = r;
    }

    /** Return the size of the list using ... recursion! */
    public int size() {
        if (rest == null) {
            return 1;
        }
        return 1 + this.rest.size();
    }

    /** Return the size of the list using ... iteration! */
    public int iterativeSize() {
        IntList p = this;
        int totalSize = 0;

        while (p != null) {
            p = p.rest;
            totalSize++;
        }

        return totalSize;
    }

    /** Returns the i-th item of the IntList. */
    public int get(int i) {
        if (i == 0) {
            return first;
        }
        return rest.get(i - 1);
    }

    /** Return the i-th item of the list using ... iteration! */
    public int iterativeGet(int i) {
        IntList p = this;

        while (i != 0) {
            p = p.rest;
            i -= 1;
        }

        return p.first;
    }

    public static void main(String[] args) {
        IntList L = new IntList(15, null);
        L = new IntList(10, L);
        L = new IntList(5, L);

        System.out.println(L.size());
        System.out.println(L.iterativeSize());

        System.out.println(L.get(1));
        System.out.println(L.iterativeGet(2));
    }
}