本文開坑伯克利 CS 61B（算法與數據結構）2024年春季課程學習筆記，Lecture 1 & Lecture 2 的內容為課程介紹與 Java 基礎，因此直接跳過。本文內容為介紹基本數據類型與引用數據類型的區別，以及手動實現整數列表。

1. 基本數據類型 & 引用數據類型

在 Java 中，所有數據類型可以分為兩大類：Primitive Types（基本數據類型） 和 Reference Types（引用數據類型）。基本數據類型是 Java 語言內置的、最基礎的數據類型，它們直接存儲值，而不是對象的引用。

Java 提供了8種基本數據類型，分別是：byte、short、int、long、float、double、char、boolean。基本數據類型直接存儲值，存儲在棧內存中，訪問速度快，因為棧內存的讀寫效率高于堆內存。

引用數據類型是指存儲在堆內存中的對象的引用。它們通過對象的引用（內存地址）來訪問對象的實際數據。引用數據類型包括：類（Class）、接口（Interface）、數組（Array）、枚舉（Enum）、包裝類（Wrapper Classes）。

看下面這個例子：

package CS61B.Lecture3;public class PollQuestions {public static void main(String[] args) {Walrus a = new Walrus(1000, 8.3);Walrus b;b = a;b.weight = 5;System.out.println(a);  // Weight: 5, TuskSize: 8.30System.out.println(b);  // Weight: 5, TuskSize: 8.30int x = 5;int y;y = x;y = 2;System.out.println(x);  // 5System.out.println(y);  // 2}public static class Walrus {public int weight;public double tuskSize;public Walrus(int weight, double tuskSize) {this.weight = weight;this.tuskSize = tuskSize;}public String toString() {return String.format("Weight: %d, TuskSize: %.2f", weight, tuskSize);}}
}

對于基本數據類型，執行 y = x 實際上是將 x 在內存中所存放的值復制給 y，兩個變量互相獨立。

而 Walrus 類的對象為引用數據類型，當聲明任何引用類型的變量時，無論對象類型是什么，Java 都精確地分配一個64位大小的空間，這些位可以設置為 null（全為零）或該類的特定實例的64位地址（由 new 返回）。

我們創建了一個 Walrus 對象，并將其引用賦值給變量 a。此時，a 指向堆內存中的一個 Walrus 對象，而之后又聲明了一個變量 b，并將 a 的引用復制給 b。此時，a 和 b 都指向同一個 Walrus 對象（內存地址相同）。換句話說，a 和 b 是同一個對象的兩個引用。

通過 IDEA 的 Java Visualizer 插件進行調試可以直觀地看到不同數據在內存中的情況：

對于函數的參數傳遞同樣會完成復制值的操作，例如以下代碼的 doStuff 方法接收的參數 w 執行了 w = walrus 操作，而 walrus 變量為一個 Walrus 類的對象地址，因此 w 接收到的是從 walrus 那復制過來的地址，而不像 x 接收到的是從 a 復制過來的值：

package CS61B.Lecture3;public class ParameterPassing {public static void main(String[] args) {Walrus walrus = new Walrus(3500, 10.5);int a = 9;doStuff(walrus, a);System.out.println(walrus);  // Weight: 2500, TuskSize: 10.50System.out.println(a);  // 9}public static void doStuff(Walrus w, int x) {w.weight -= 1000;x -= 5;}public static class Walrus {public int weight;public double tuskSize;public Walrus(int weight, double tuskSize) {this.weight = weight;this.tuskSize = tuskSize;}public String toString() {return String.format("Weight: %d, TuskSize: %.2f", weight, tuskSize);}}
}

2. 數組與列表

數組不是基本數據類型，因此也需要用 new 進行初始化：

int[] a = new int[]{0, 1, 2, 3}

數組的大小在創建時必須指定，并且一旦創建，其大小不能改變，數組的值存儲在堆內存中，但數組變量（引用）存儲在棧內存中，也就是上述代碼中的變量 a。

列表的大小可以動態變化，可以根據需要添加或刪除元素，列表本身是一個對象，存儲在堆內存中，其內部通過動態數組或其他數據結構（如鏈表）來存儲元素。

我們先手動實現一個整數列表：

package CS61B.Lecture3;public class IntList {public int val;public IntList next;public IntList(int val) {this.val = val;this.next = null;}public static void main(String[] args) {IntList L = new IntList(5);L.next = new IntList(3);L.next.next = new IntList(10);while (L != null) {System.out.print(L.val + " ");L = L.next;}  // 5 3 10}
}

其可視化效果如下：

同樣我們還能構建一個反向列表，即元素在首部插入：

package CS61B.Lecture3;public class IntList {public int val;public IntList next;public IntList(int val, IntList next) {this.val = val;this.next = next;}public static void main(String[] args) {IntList L = new IntList(5, null);L = new IntList(3, L);L = new IntList(10, L);while (L != null) {System.out.print(L.val + " ");L = L.next;}  // 10 3 5}
}

最后我們可以實現求解列表長度以及獲取某個元素的方法：

package CS61B.Lecture3;public class IntList {public int val;public IntList next;public IntList(int val, IntList next) {this.val = val;this.next = next;}// 使用遞歸求解列表長度public int sizeRecursive() {if (this.next == null) {return 1;} else return 1 + this.next.sizeRecursive();}// 使用遍歷求解列表長度public int sizeIterative() {int res = 0;IntList p = this;  // 創建一個指向當前地址的變量while (p != null) {res++;p = p.next;}return res;}// 使用遞歸求解列表第i個元素public int getVal(int i) {if (i >= this.sizeRecursive()) {System.out.println(String.format("Index %d is out of range!", i));return 0;}if (i == 0) return this.val;else return this.next.getVal(i - 1);}public static void main(String[] args) {IntList L = new IntList(5, null);L.next = new IntList(3, null);L.next.next = new IntList(10, null);System.out.println(L.sizeRecursive());  // 3System.out.println(L.sizeIterative());  // 3System.out.println(L.getVal(2));  // 10while (L != null) {System.out.print(L.val + " ");L = L.next;}  // 5 3 10}
}