Lab 2 Notes

CS61B UCBerkeley

Lab2 Navigation

Debugging Basics

• Breakpoints
• Stepping over
• Stepping into
• Stepping out
• Resuming

Application: IntLists

IntList myList = IntList.list(0, 1, 2, 3);
    // Creates the IntList 0 -> 1 -> 2 -> 3 -> null

 IntList myList = new IntList(0, null);
    myList.rest = new IntList(1, null);
    myList.rest.rest = new IntList(2, null);
    myList.rest.rest.rest = new IntList(3, null);
    // One line of using IntList.list() can do the job of four lines!

Destructive vs. Non-Destructive

Let's consider a method dSquareList that will destuctively square every item in a list (similar to what we saw in discussion):

IntList origL = Intlist.list(1, 2, 3)
    dSquareList(origL);
    // origL is now (1, 4, 9)
Here is one implementation of dSquareList():
    public static void dSquareList(IntList L) {
        while (L != null) {
            L.first = L.first * L.first;
            L = L.rest;
        }
    }

This is a classic example of a destructive method. It iterates through the list and squares each item, causing the values linked by L to change. In other words, after calling this method once on L, every element in L will be squared.

NOTE: The choice to return void rather than the original pointer to L was an arbitrary decision. Different languages and libraries use different conventions (and people get quite grumpy about which is the "right" one).

Examining the code above, we see that the origL variable contains a reference to the created IntList. This origL variable never changes. Although the L variable in dSquareList() gets reassigned all day long, because all parameter passing in method calls are pass-by-copy (remember pass-by-bits from lecture?), the origL variable is still safe and properly points to the first element. In other words, even as we continually call L = L.rest, origL always points to the beginning of the IntList.

The reason that dSquareList is destructive is because we change the values of the original input IntList. As we go along, we square each value, and the action of changing the internal data persists (unlike the reassignment of L, which doesn't effectively last after the method finishes).

By the end of the method, L is null, and origL is still pointing at the beginning of the IntList, but every value in the IntList that origL points to is now squared.

Now, look at squareListIterative() and squareListRecursive(). These methods are both non-destructive. That is, the underlying IntList passed into the methods does not get modified, and instead a fresh new copy is modified and returned.

public static IntList squareListIterative(IntList L) {
        if (L == null) {
            return null;
        }
        IntList res = new IntList(L.first * L.first, null);
        IntList ptr = res;
        L = L.rest;
        while (L != null) {
            ptr.rest = new IntList(L.first * L.first, null);
            L = L.rest;
            ptr = ptr.rest;
        }
        return res;
    }

Pay attention to res, it has changed when ptr changed. This is because an object has been created in heap, so they pointed to the same object before ptr=ptr.rest which changed the pointer of ptr. This method is non-destructive because origL always pointed to the same thing and never has been changed.

Implementing Destructive vs. Non-destructive Methods

   /**
    * Returns a list consisting of the elements of A followed by          *the elements of B.  May modify items of A. Don't use 'new'.
    */
    public static IntList dcatenate(IntList A, IntList B){
       if(A == null) {
            return B;
        }else if(B == null){
            return A;
        }
        IntList L = A;
        while(A.rest != null){
            A = A.rest;
        }
        A.rest = B;
        return L;
    }

    /**
     * Returns a list consisting of the elements of A followed by       *  the elements of B.  May NOT modify items of A.  Use 'new'.
     */
    public static IntList catenateRecursive(IntList A, IntList B){
        if(A == null){
            return B;
        }
        return new IntList(A.first, catenateRecursive(A.rest, B));
    }

    public static IntList catenateIterative(IntList A, IntList B){
        if (A == null) {
            return B;
        }
        IntList res = new IntList(A.first, null);
        IntList ptr = res;
        A = A.rest;
        while (A != null) {
            ptr.rest = new IntList(A.first, null);
            A = A.rest;
            ptr = ptr.rest;
        }
        ptr.rest = B;
        return res;
    }

In ctenateIterative(), I was wondering why A=A.rest doesn't modify A.

disscusion 2 Bonus Problems: Squaring a List

Write the following methods to destructively and non-destructively square a linked list. Destructively squaring means modifying the items in the IntList passed as an argument. Nondestructively means all values in the original list are unaffected by the function.

/** Destructively squares each element of the given IntList L.
* Don’t use ’new’; modify the original IntList.
* Should be written iteratively. */
public static IntList SquareDestructiveIterate(IntList L) {
    IntList B = L;
    while(L != null){
        B.first = B.first * B.first;
        B = B.rest;
    }
    return L;
}

/** Non-destructively squares each element of the given IntList L.
* Don’t modify the given IntList.
* Should be written recursively*/
public static IntList SquareNonDestructiveRecursive(IntList L) {
    if(L == null){
        return null; 
    }
    return new IntList(L.first * L.first, SquareNonDestructive(L.rest));
}

Even more bonus problems: Write SquareDestructive recursively. Write SquareNonDestructive iteratively

public static IntList SquareDestructiveRecursive(IntList L){
    if(L == null){
        return null;
    }
    L.first *= L.first;
    return SquareDestructiveRecursive(L.rest);
}

public static IntList SquareNonestructiveIterate(IntList L){
    if (L == null) {
        return null;
    }
    IntList res = new IntList(L.first*L.first, null);
    IntList ptr = res;
    L = L.rest;
    while (L != null) {
        ptr.rest = new IntList(L.first*L.first, null);
        L = L.rest;
        ptr = ptr.rest;
    }
        return res;
}

From this practice, I lack a deeper understanding of the passing of parameters in Java and I can't write recursive or iterative method really quickly. Here are some extra information I found helpful:
java参数传递（超经典）
java到底是值传递还是引用传递？
在java方法中改变传递的参数的值
java 参数传递探究
Java中的参数传递方式
Java参数引用传递引发的惨案（又一次Java的String的“非对象”特性的踩坑经历）

刚在写一个用例，需要在方法中改变传递的参数的值，可是java中只有传值调用，没有传址调用。所以在java方法中改变参数的值是行不通的。但是可以改变引用变量的属性值。

可以仔细理解一下下面几句话：

• 对于基本类型参数，在方法体内对参数进行重新赋值，并不会改变原有变量的值。
• 对于引用类型参数，在方法体内对参数进行重新赋予引用，并不会改变原有变量所持有的引用。
• 方法体内对参数进行运算，不影响原有变量的值。
• 方法体内对参数所指向对象的属性进行操作，将改变原有变量所指向对象的属性值。

也就是说，对于基本数据类型，实现的是传值，只是个形参，不会改变原有值。对于引用数据类型，对这个引用进行操作，其实也是相当于对形参的操作，不会改变原来的引用。但是，当对这个引用的属性进行操作的时候，可以改变这个引用的属性的值。

三句话总结一下：

• 对象就是传引用
• 原始类型就是传值
• String，Integer,Double等immutable类型因为没有提供自身修改的函数，每次操作都是新生成一个对象，所以要特殊对待。可以认为是传值。

Integer 和 String一样。保存value的类变量是Final属性，无法被修改，只能被重新赋值／生成新的对象。 当Integer做为方法参数传递进方法内时，对其的赋值都会导致原Integer 的引用被指向了方法内的栈地址，失去了对原类变量地址的指向.对赋值后的Integer对象做得任何操作，都不会影响原来对象。

Let's see an example from the above links:

public class Argument {
    public static class User{
      public String name;
    }
    public static void main(String[] args) {
        User user = new User();
        user.name="AA";
        change(user);
        System.out.print(user.name); //输出BB
    }
    public static void change(User user){
        user.name="BB";
    }
}

上面就是改变了引用的属性user.name,所以可以改变这个引用的属性的值.

Let's see another example:

public class Argument {
    public static void main(String[] args) {
        String value = "小明";
        change(value);
        System.out.print(value); //output: 小明
    }
    public static void change(String value){
        String str="小红";
        value=str;
    }
}

在未进入change方法前，value 的指向的地址为 453

进入方法后 形参 value 的指向的地址依然为 453 说明形参复制了实参的地址

其中str变量的指向的地址为 454

value=str;这行很关键，出现以上错觉的原因就是String的赋值，java里赋值的做法是将地址赋值给变量，因为value指向的地址453，现在将它赋值后，指向的地址将变成str的地址454，只是指向的地址进行了改变，对于地址453上存的值便没有发生改变，change方法的形参在change生命周期结束后便回收了，而在方法change外面的value的指向地址便没有发生改变还是指向453，所以value的值不会改变。

类似C中的两个指针，一个是change外面的value，一个是change里面的value，一开始他们指向同一个地址453，后来change里面的value指向了454，便没有对453上面存储的值进行改变，所以外面的value的值不会发生改变。