2.1 LIST
数组：
Java 中的数组大小是固定的，我们可以构建自己的list类型中学习java的关健特性。
- 为什么构建list？
- 因为list是有序的，不定长的，方便增删查改
8 种原始类型：
字节、短、int、long、float、double、boolean 和 char。
java会根据类型去映射不同的二进制代码。（映射位宽和字节码）
如：当你声明某个类型的变量时:
Java 会找到一个连续的块，其比特恰好足够容纳该类型的事物。
例如，如果你声明一个 int，你得到一个 32 位的块。如果你声明一个字节，你得到一个 8 位的块。Java 中的每种数据类型包含不同的位数。
除了预留内存外，Java 解释器还在内部表中创建一个条目，将每个变量名映射到盒子中第一个位的位置。(类似索引的存在)
而他不允许在没有默认值的情况下让人输入。
对象实例化：
数据存放在地址而不是内存中。
为了区分地址和内存：
- 地址 地址全为0时，用null表示
- 箭头 就，指向地址
海象之谜是因为引用同一个地址的数值。参数传递也是这样的。
传参：（也是=的黄金法则）
如果是基本类型，拷贝值；
如果是引用类型，所以拷贝地址。
裸结构list：
一个基本的创建list结构：
public class IntList {
public int first;
public IntList rest;
public IntList(int f, IntList r) {
first = f;
rest = r;
}
}其中，f代表的是值，r则是指针。当r=null时，则为尾部节点。
尾部构造：
IntList list = new IntList(15, null); // 尾节点
list = new IntList(10, list); // 通过不断地引用10会自动指向15
list = new IntList(5, list); // 5会自动指向10
// 最终：
// list → [5|→] → [10|→] → [15|null]计算大小：
public int size() {
if (rest == null) {
return 1;
}
return 1 + this.rest.size()//计算大小的函数;
}使用指针遍历大小的方法：
public int iterativeSize() {
IntList p = this;
int totalSize = 0;
while (p != null) {
totalSize += 1;
p = p.rest;
}
return totalSize;
}先指定当前需要计算的数组，之后再添加一个累加数。
一开始指向当前列表，设置总和为0。
如果指针为空，返回0；
如果指针部位空，总数加一，然后返回下一个值。
找到特定值的方法
public int get(int i) {
IntList current = this; // this 指向当前链表头
int index = 0;
while (current != null) {
if (index == i) {
return current.first; // 找到第 i 个元素
}
current = current.rest; // 移动到下一个节点
index++;
}
// 如果 i 无效，可以返回一个默认值或抛出异常
// 题目说"不管行为如何"，这里返回 -1 表示无效
return -1;
}找到第i位数并返回其值，所以先判断数组是否越界，之后再根据index是否和i相同来返回值。
2.2 改进
我们的 接下来的SLList 相比第 2.1 章的简单 IntList 有许多优势：
SLList的用户永远不会看到IntList类。- 使用更简单。
- 更高效的
addFirst方法。 - 封装避免
IntList用户的错误或不当行为。
- 比
IntList更快的查找方法。
1. 重命名
IntNode 类：
// 节点类（通常作为内部类或单独定义）
public class IntNode {
public int item; // 存储数据
public IntNode next; // 指向下一个节点
public IntNode(int i, IntNode n) {
item = i;
next = n;
}
}构建(在别人面前展示的）：
public class SLList {
// first 是一个引用，指向链表的第一个节点
public IntNode first;
// 构造函数：创建一个包含单个节点的链表
public SLList(int x) {
first = new IntNode(x, null); // 创建节点，next设为null
}
}这样的好处时让用户不知道节点的位置，是引用中的引用
addFirst 和 getFirst
public void addFirst(int x) {
first = new IntNode(x, first);
}在头部节点插入
public int getFirst() {
return first.item;
}返回第一条头部节点
addlast方法
public void addLast(int x) {
size += 1;
IntNode p = sentinel;
while (p.next != null) {
p = p.next;
}
p.next = new IntNode(x, null);
}封装究竟合味道？
他其实只是告诉一些人说，如果你看不懂内部逻辑代码，你就老老实实用这个封装好的避免出错。
本质上也没办法阻止别人看代码。
public class SLList {
public static class IntNode {
public int item;
public IntNode next;
public IntNode(int i, IntNode n) {
item = i;
next = n;
}
}
private IntNode first;
...折断的封装是封装属性，也就意味着int node无法访问其他的类似first的属性，会报错。
追踪变量
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;
}
...
}们可以在 SLList 类中添加一个大小变量， 跟踪当前大小，得到下面的代码。这种保存重要数据以加快检索的做法有时被称为缓存 。
这是一种空间换时间的方法
哨兵节点（有点像双链表了，但并没有）
设置这个可以不用每次都去考虑null的情况。这有什么好处呢？因为他能够方便简化代码，减少一些边界条件的判断并且同意操作逻辑。
所以我们可以用不变量来表示它的值。
缺点
- 在尾部增加节点时会随着数组规模变大而时间变得更久（因为每加一个尾节点就需要遍历一次）。
- 解决方法：
- 在最后添加一个记录大小的变量来加快代码速度。
public class SLList {
private IntNode sentinel;
private IntNode last;
private int size;
public void addLast(int x) {
last.next = new IntNode(x, null);
last = last.next;
size += 1; //这个
}- 经过改良，add也变得便捷起来。但是remove依旧是很慢的。
remove需要删掉最后一个数，以及倒数第二个数指针（倒数第二会拉着倒数第一的手，倒一dead时倒二还拉着呢。计算机改变倒二的值就需要从头再遍历一遍，所以很慢。）（说的有点啰嗦）
2.3 再改 dllist
其实就是介绍了双向链表啦。上边不是讲了slist的remove很慢吗（删除不仅得找到要删的那个节点，还得重新遍历一次找到前边指向该节点的节点），解决的方法就是–为每个intnode都添加一个前置指针。
public class IntNode {
public IntNode prev;
public int item;
public IntNode next;
}这样的话，就可以找到要删的那个节点的同时，通过指向前边的指针来找到它。只需要遍历一次就好了。
这其实就是dllist捏。
泛型
在上边的案例中，只能接受整数参数构造，我们可以通过任意引用类型的数据结构。
2.4 数组
1. 是啥
数组是一种特殊类型的对象。
要获得数组的第 i 个元素，我们使用括号表示法：
A[i]：来获得 A 的第 i 个元素。
2. 创建语法
x = new int[3];y = new int[]{1, 2, 3, 4, 5};int[] z = {9, 10, 11, 12, 13};
3. 使用的方法
System.arraycopy(b, 0, x, 3, 2)复制
- 作为源的数组
- 源数组从哪里开始
- 作为目的地使用的数组
- 目标数组的起点
- 要复制多少物品