• 問題引入
  

上圖中，賦給b海象的weight會改變a海象的weight，但x的賦值又不會改變y的賦值

Bits

要解釋上圖的問題，我們應該從Java的底層入手

相同的二進制編碼，卻因為數(shù)據(jù)類型不同，輸出不同的值

變量的聲明

基本類型

Java does not write anything into the reserved box when a variable is declared. In other words, there are no default values. As a result, the Java compiler prevents you from using a variable until after the box has been filled with bits using the = operator. For this reason, I have avoided showing any bits in the boxes in the figure above.

引用類型

When we declare a variable of any reference type (Walrus, Dog, Planet, array, etc.), Java allocates a box of 64 bits, no matter what type of object.

96位大于64位，這似乎有些矛盾：
在Java中：the 64 bit box contains not the data about the walrus, but instead the address of the Walrus in memory.

Gloden rule

練習

答案：B
解析：

• 在調用方法（函數(shù)）時，doStuff方法中的int x與main方法中的int x 實際上處于兩個不同的scope（調用方法時會new 一個scope，并將main方法中的x變量的位都傳遞給doStuff方法中的x變量，即值傳遞），所以x = x - 5實際上只作用于doStuff方法中的x，而不是main方法中的x。
• 但對于引用類型來說，引用類型儲存的是引用的地址，所以在進行值傳遞時傳遞的是對象的地址，所以doStuff方法中的int x與main方法中的walrus實際上指向相同的一個對象，這使得doStuff中執(zhí)行的語句會作用于main方法中walrus指向的對象，所以反作用于main方法中的walrus

IntLists

使用遞歸求鏈表中元素的個數(shù)

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

Exercise: You might wonder why we don’t do something like if (this == null) return 0;. Why wouldn’t this work?

Answer: Think about what happens when you call size. You are calling it on an object, for example L.size(). If L were null, then you would get a NullPointer error!

不使用遞歸求元素個數(shù)

/** Return the size of the list using no recursion! */
public int iterativeSize() {IntList p = this;int totalSize = 0;while (p != null) {totalSize += 1;p = p.rest;}return totalSize;
}

求第n個元素

SLList

接下來我們對IntList進行改進，使鏈表看上去不那么naked

有了節(jié)點類，現(xiàn)在我們補充上鏈表類

public class SLList {public IntNode first;public SLList(int x) {first = new IntNode(x, null);}
}

對比SLList和IntList，我們發(fā)現(xiàn)，在使用SLList時無需強調null

IntList L1 = new IntList(5, null);
SLList L2  = new SLList(5);

addFirst() and getFirst()

  /** Adds an item to the front of the list. */public void addFirst(int x) {first = new IntNode(x, first);}/** Retrieves the front item from the list. */public int getFirst() {return first.item;
}

private and nested class

public class SLList {public class IntNode {public int item;public IntNode next;public IntNode(int i, IntNode n) {item = i;next = n;}}private IntNode first;public SLList(int x) {first = new IntNode(x, null);}/** Adds an item to the front of the list. */public void addFirst(int x) {first = new IntNode(x,first);}/** Retrieves the front item from the list. */public int getFirst() {return first.item;}
}

addLast() and Size()

/** Adds an item to the end of the list. */
public void addLast(int x) {IntNode p = first;/* Advance p to the end of the list. */while (p.next != null) {p = p.next;}p.next = new IntNode(x, null);
}

/** Returns the size of the list starting at IntNode p. */
private static int size(IntNode p) {if (p.next == null) {return 1;}return 1 + size(p.next);
}

優(yōu)化低效的Size()方法

在改變鏈表的Size時直接記錄下，就可以不需要在Size()方法中遍歷鏈表了

public class SLList {... /* IntNode declaration omitted. */private IntNode first;private int size;public SLList(int x) {first = new IntNode(x, null);size = 1;}public void addFirst(int x) {first = new IntNode(x, first);size += 1;}public int size() {return size;}...
}

空鏈表（ The Empty List)

創(chuàng)建空鏈表很簡單（對于SLList），但會導致addLast()方法報錯

public SLList() {first = null;size = 0;
}

public void addLast(int x) {size += 1;IntNode p = first;while (p.next != null) {p = p.next;}p.next = new IntNode(x, null);
}

p指向null，故p.next會出現(xiàn)空指針異常

addLast()改進（使用分支）

public void addLast(int x) {size += 1;if (first == null) {first = new IntNode(x, null);return;}IntNode p = first;while (p.next != null) {p = p.next;}p.next = new IntNode(x, null);
}

addLast()改進（更robust的做法）

對于存在很多特殊情況需要討論的數(shù)據(jù)結構，上面的方法就顯得十分低效。
故我們需要考慮將其改進為一個具有普適性的方法：將first改為sentinal.next
sentinal將會永遠存在于鏈表的上位

package lists.sslist;public class SLList {public class IntNode {public int item;public IntNode next;public IntNode(int i, IntNode n) {item = i;next = n;}}private IntNode sentinel;private int size;public SLList() {sentinel = new IntNode(63,null);size = 0;}public SLList(int x) {sentinel = new IntNode(63,null);sentinel.next = new IntNode(x, null);size = 1;}/** Adds an item to the front of the list. */public void addFirst(int x) {sentinel.next = new IntNode(x, sentinel.next);size += 1;}/** Retrieves the front item from the list. */public int getFirst() {return sentinel.next.item;}/** Returns the number of items in the list. */public int size() {return size;}/** Adds an item to the end of the list. */public void addLast(int x) {IntNode p = sentinel;/* Advance p to the end of the list. */while (p.next != null) {p = p.next;}p.next = new IntNode(x, null);}/** Crashes when you call addLast on an empty SLList. Fix it. */public static void main(String[] args) {SLList x = new SLList();x.addLast(5);}
}