数据结构Data Structure

链表Linked List

认知

背景

Java 的基础数组 无法扩展，必须在创建时确定尺寸。

需要一个可以自行扩展的数据结构

什么是

能够自行扩展尺寸的数组

内存简图

原始内存

简化内存图

重点关注堆空间，堆空间变量为方块

指针变量化为箭头

栈空间变量不是重点，化为小圆圈

链表结构设计

理念

火车车头

对象

车头 勾着 第一节车厢

火车车厢

对象

车厢 存储着 一个数据

同时 勾着 下一结车厢

数量

一个链表 需要

1 个 车头 以及

0 ~ n 个 车厢

结构

链表样例

车头勾着车厢，车厢勾着下一结车厢，末尾车厢不勾

内存

简化内存

链表添加元素

在末尾车厢后面，再勾一个新车厢

内存

简化内存

空链表

有车头，没车厢

内存

简化内存

随堂练习

稳健性Robustness

背景

public 的方法就是对外公开的

谁都可以调用, 而且可能会不按照你预期调用

什么是

健壮性 / 鲁棒性 / 稳定性 / 稳健性

有能力处理运行时错误, 处理错误的输入

不管怎么运行都不崩溃

可能破坏稳健性的诱因

类型错误

void add(int value)

增加一个新的结点在链表末端, 值为 value

错误情况

1!
list.add("10"); 

分析

Java 的编译器 会在编译时 检测问题

如果有, 就飘红

范围错误

int get(int index)

返回第 index 个元素的值

错误情况

1 2 
list.get(7);list.get(-1);

分析

如果 list 只有 3 个元素

Java 编译器不会帮你检查

需要自己进行验证, 保证数值范围合理

边界情况

void add(int value)

增加一个新的结点在链表末端, 值为 value

错误情况

1 2 3 4 5 6 7 8 9 10 11 12 
public class LinkedList {    ...    public void add(int value) {        Node node = new Node(value);        Node current = first;        while(current.getNext() != null) {            current = current.getNext();        }        current.setNext(node);    }    ...}

分析

如果当前 list 没有结点...

边界情况下, 处理代码可能有所不同

需要自己进行边界检测, 保证边界情况运行正常

特殊情况总结

类型错误

编译器帮你处理

范围错误

需要处理

边界情况

需要处理

随堂练习

特殊情况分析 训练

特殊情况排查方法

先写一般情况的代码

分析特殊情况

分析现有代码能否接住特殊情况

不能，就要写 if 分支

随堂练习

String description()

早推出Early Exits

使用前

1 2 3 4 5 6 7 8 9 10 11 
public int get(int index) {    if (index >= 0 && index < size()) {        Node current = first;        for (int i = 0; i < index; i++) {            current = current.getNext();        }        return current.getValue();    } else {        return -1;    }}

使用后

1 2 3 4 5 6 7 8 9 10 11 12 
public int get(int index) {    //  早退出    if (index < 0 || index >= size()) {        return -1;    }     Node current = first;    for (int i = 0; i < index; i++) {        current = current.getNext();    }    return current.getValue();}

封装Encapsulation

内部功能抽离

方案

如果有了这个方法

Node getNode(int index)

那么 下面的几个方法 实现起来会很方便

int get(int index)
void insert(int index, int value)

private 方法

为内部服务的方法，本不应该曝光出去

1*2 3 
private Node getNode(int index) {    ...}

封装模型

对象模型

使用 private

使用 private 可对属性和方法进行访问保护

禁止外界直接访问属性和方法

private 的仅供内部使用

封装

外界只能看到 public 对外暴露的

不知道 也不该知道 里面有什么

不管 也不该管 里面怎么搞的

内部优化

可以添加不影响外部的 private 属性或方法

样例

1 2 3 
public int lastValue(){    return getNode(size() - 1).getValue();}

问题

为了求 size 已经跑到最后一个节点了，

getNode 时又跑了一遍

优化

1 2 3+4 5 6*7 8 9 10 11+12 13 14 
public class LinkedList {    ...    private int size;    ...    public int lastValue() {        return getNode(size - 1).getValue();    }    ...    public void add(int value) {        ...        size ++;    }    ...}

泛型Generics

案例

问题

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 
public class IceCreamBox {    private int id;    private IceCream iceCream;    private double weight;     public void put(IceCream iceCream) {        this.iceCream = iceCream;    }     public boolean isEmpty() {        return iceCream == null;    }     public IceCream takeOut() {        IceCream iceCream = this.iceCream;        this.iceCream = null;        return iceCream;    }     // getters and setters}

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 
public class MilkTeaBox {    private int id;    private MilkTea milkTea;    private double weight;     public void put(MilkTea milkTea) {        this.milkTea = milkTea;    }     public boolean isEmpty() {        return milkTea == null;    }     public MilkTea takeOut() {        MilkTea milkTea = this.milkTea;        this.milkTea = null;        return milkTea;    }     // getters and setters}

代码大面积重叠

解决方案

1*2 3*4 5 6*7*8 9 10 11*12 13 14*15*16*17*18 19 20 21 
public class Box <T> {    private int id;    private T content;    private double weight;     public void put(T content) {        this.content = content;    }     public boolean isEmpty() {        return content == null;    }     public T takeOut() {        T content = this.content;        this.content = null;        return content;    }     // getters and setters}

使用

1 2 3 4 5 6 7 
public class Driver {    public static void main(String[] args) {        Box<MilkTea> milkTeaBox = new Box<>();        MilkTea milkTea = new MilkTea();        milkTeaBox.put(milkTea);    }}

什么是

将类型中的类型 作为变量

Type Arguments

机制

new 时，传递泛型值，从而确定这个类到底是什么样

再使用，之后 会有方法的对应的类型提示

语法

声明

1 
public class Box <T>

赋值

1 
new Box<IceCream>();

使用

1 
private T content;

命名规则

一般用一个大写字母, 也可以用单词, 大写开头

赋值规则

不可以赋值基础类型

包装类Wrapper Classes

背景

有些情况下, 一些语法只能接收对象类型

1!
new Node<int>();

需要一种结构把基础类型 转成 对象类型

样例

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
public class Int {    private int value;     public Int(int value) {        this.value = value;    }     public int getValue() {        return value;    }     public void setValue(int value) {        this.value = value;    }}

1 2 3 4 5 6 7 8 9 10 
public class Main {    public static void main(String[] args) {        new Main().run();    }     public void run(){        Int anInt = new Int(3);         int value = anInt.getValue();    }}

装箱 和 拆箱Boxing and Unboxing

装箱

1 
new Int(3);

拆箱

1 
anInt.getValue();

配套泛型使用

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
public class Main {    public static void main(String[] args) {        new Main().run();    }     public void run(){        Node<Int> intNode = new Node<Int>();        Int intObject = new Int(10);    // 装箱 - 把基础类型放到包装对象里        intNode.setValue(intObject);     // 把对象放到业务代码里         Int intObjectOut = intNode.getValue(); // 从业务对象里取出对象        int intValue = intObjectOut.getValue(); // 拆箱 - 把包装对象拆出基础类型        Console.println(intValue);    }}

系统包装类

boolean Boolean
byte    Byte
char    Character
float   Float
int     Integer
long    Long
short   Short
double  Double

自动装箱拆箱

自动装箱

1 2 
Integer a = new Integer(3);Integer a = 3;

自动拆箱

1 2 
int value = a.intValue();int value = a;

列表List

是什么

系统的动态数组。

有两个

样例

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 
public class Main {    public static void main(String[] args) {        new Main().run();    }     public void run(){        LinkedList<Integer> list = new LinkedList<Integer>();        list.add(6);        list.add(7);        list.add(3);        list.add(8);        list.add(4);         for (int i = 0; i < list.size(); i++) {            int value = list.get(i);            Console.println(value);        }    }}

列表内包含对象

1 2 3 4 5 6 7 8 
public class Point {    private int x;    private int y;    public String description() {        return "(" + x + ", " + y + ")"    }    // ... 省略 getter setter 构造器}

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 
public class Main {    public static void main(String[] args) {        new Main().run();    }     public void run(){        LinkedList<Point> points = new LinkedList<Point>();        points.add(new Point(0, 0));        points.add(new Point(3, 0));        points.add(new Point(3, 4));         for (int i = 0; i < points.size(); i++) {            Point point = points.get(i);            Console.println(point.description());        }    }}

For Each遍历专用 for 语句

案例

使用前

1 2 3 4 
for (int i = 0; i < list.size(); i++) {    Integer value = list.get(i);    Console.println(value);}

使用后

1-2-3+4 5 
for (int i = 0; i < list.size(); i++) {    Integer value = list.get(i);for (Integer value : list) {    Console.println(value);}

语法

for (元素类型 元素变量 : 集合变量) {
    ...
}

for 语句对比

一般 for 可以进行高级控制

标准 for 可以获得当前位置

遍历 for 只能遍历所有元素

数组也可以用

1 2 3 4 
int[] values = {6, 7, 3, 8, 4};for (int value : values) {    Console.println(value);}