Java 基础与设计题

从这节课开始,面试不再问「你会不会某个算法」,而是问「你能不能用地道的 Java 亲手造一个数据结构」。内容干净地分成两半。前半是面试官真会追问的 OOP 基本功:抽象类与接口的区别、单继承与多继承(以及它规避掉的菱形问题)、泛型如何悄悄改变你的设计决策。后半是实操——从零实现 Stack 和 Queue,每个各做两遍:一遍用链表,一遍用定容数组。数组版会牵出循环缓冲区的「满 vs 空」难题和均摊扩容的 follow-up,这两处正是候选人要么听起来很资深、要么被刷掉的分水岭。

List、ArrayList、LinkedList:接口 vs 实现

从笔记的开头讲起,因为它给后面所有内容定了框架。List 是一个接口——一份契约,只说「有序、可按下标访问的集合」,不说怎么实现。ArrayList 和 LinkedList 是这份契约的两种实现,性能画像正好相反:ArrayList 是可变数组(按下标随机访问 O(1),尾部追加均摊 O(1),但中间插删 O(n),因为要整体搬移);LinkedList 是一串节点(两端增删 O(1),但走到下标 i 要 O(n))。这些取舍我们在 第 4 课拆过;在这里它们支撑一个设计选择——链表天然适合当 Stack/Queue 的骨架,正因为所有动作都发生在两端。

「一份契约,多种实现」这个分裂,就是本课 OOP 半场的全部主题。接下来两节讲的,不过是 Java 表达它的两件工具。

抽象类 vs 接口

最常见的 Java 基础题,笔记给了完整对照。抽象类是 is-a 层级里一个搭到一半的父类:它能持有字段(final 和非 final、static 和非 static)、定义构造器,并且能把抽象方法(无方法体,子类必须补全)和具体方法混在一起。接口是一份纯粹的能力契约:历史上只有抽象方法签名和 static final 常量,而且——面试官最爱确认你知不知道的细节——从 Java 8 起还能带 default 和 static 方法,这正是语言在不破坏所有实现类的前提下给既有接口加方法的办法。

要说出口的决策规则:当子类型共享状态或默认行为、且构成一个真正的 is-a 家族时(每个 Shape 都是一个 shape),用抽象类;当你描述的是一种能让互不相关的类型自愿加入的能力时(任何 Comparable、Iterable、Drawable,无关它的类层级),用接口。还有一个值得点名的不对称:抽象类可以 implements 接口,但接口永远不能实现抽象类——契约在部分实现之上,永远不在其下。

单继承 vs 多继承(以及菱形问题)

为什么 Java 一个类能 implements 任意多个接口,却只能 extends 一个类?笔记一句话点破,这正是关键:implement 接口会逼你自己写方法体,所以多继承永远没有歧义。如果两个接口都声明了 foo(),实现类照样只提供一个 foo()——要跑的实现始终只有一份。

extends 类就不同了。假如 class C extends A, B 合法,而 A 和 B 各自带了具体的 foo(),那么 c.foo() 就真的无法判定了——到底继承哪个父类的实现? 这就是经典的菱形问题(A 在顶,B 和 C 继承它,D 在底同时继承两者)。Java 的设计决定简单直接:干脆禁止这种局面——至多一个父类,就永远不存在两份相互竞争的继承方法体需要消歧。接口从构造上就绕开了它,因为在 default 方法出现前,它根本不带任何方法体。

泛型:<T> 为什么改变设计

本课每个结构都是泛型——MyStack<T>、MyQueue<T>,底层是泛型 Node<T>。泛型给你类型安全(编译器不让你把 String push 进 Integer 栈)并免去取出时的强转。但它改变了一个常把人绊倒的设计决策:你不能再拿 null 当「空」的哨兵了。一个空时返回 null 的 pop(),在 T 本身可以为 null 的那一刻就歧义了——一个合法 push 了 null 值的调用者,和一个碰到空栈的调用者,拿到的是同一个信号。两种干净的修法(下面都会用到):维护一个显式的 size 字段并检查它,或者抛异常(NoSuchElementException / EmptyStackException),而不是让 null 背两层含义。

数组版还会暴露一个运行时的坑:你不能写 new T[capacity]。泛型在运行时会被擦除,数组没有真实的元素类型可供实例化;地道写法是 (T[]) new Object[capacity],再压掉那个 unchecked 警告。重点是知道为什么——type erasure——而不是记住这句咒语。

用链表实现 Stack(FILO)

生产环境里的条件反射是 Deque<Integer> stack = new ArrayDeque<>();——在真实代码里这也确实是对的。但这不是面试官想要的;题目问的是「造出这个结构」,不是「说出库里的类名」。Stack 是后进先出,而单链表让它变得极简:只留一个 head 指针,所有事都在那儿干。push 把新节点接到旧栈顶之上;pop 把栈顶摘下来。两者都是 O(1),而且没有容量上限。

public class MyStack<T> {
    private static class Node<T> {   // 单链表节点
        T val;
        Node<T> next;
        Node(T val) { this.val = val; }
    }

    private Node<T> head;               // 栈顶

    public boolean push(T x) {
        Node<T> node = new Node<>(x);
        node.next = head;                // 把新节点接到旧栈顶之上
        head = node;                     // 它成为新栈顶
        return true;
    }

    public T pop() {
        if (head == null) return null;  // 坑:T 可为 null 时,这个 null 有歧义
        Node<T> node = head;
        head = head.next;
        node.next = null;                // 好习惯:断开被摘掉的节点
        return node.val;
    }

    public T peek() {
        return head == null ? null : head.val;
    }
}

注意返回前的 node.next = null——刻意切断被摘节点的链接。它不花任何代价,却能防止一个悬空引用把一整条对象链吊着不回收;笔记把这标为「好习惯」,在面试里它读起来也确实像。留下的软肋是 pop()/peek() 空时返回 null——做 demo 可以,但要把泛型 null 的坑说出口,并给出 size 字段或异常的替代方案。

用链表实现 Queue(FIFO)

Queue 是先进先出,所以单个 head 指针不够——你在一端入队、从另一端出队。解法是两个引用:一个 head 用来出队,一个 tail 用来入队,这样两个操作都保持 O(1)(带尾指针的单链表就够了;双链表——「右边进、左边出」——让接线对称,也是笔记画的那种)。必须精确处理的两种情况是:offer 时的空队列(第一个节点同时是 head 和 tail),以及 poll 时的最后一个元素(排空到空时必须把 两个指针都置回 null,否则残留的 tail 会在下一次 offer 时作祟)。

public class MyQueue<T> {
    private static class Node<T> {   // 双链表节点
        T val;
        Node<T> next, prev;
        Node(T val) { this.val = val; }
    }

    private Node<T> head;    // 出队端
    private Node<T> tail;    // 入队端

    public void offer(T val) {          // 从 tail 入队
        Node<T> node = new Node<>(val);
        if (head == null) {           // 空队列:node 同时是两端
            head = tail = node;
        } else {
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
    }

    public T poll() {                  // 从 head 出队
        if (head == null) return null;
        Node<T> node = head;
        if (head == tail) {          // 只剩一个元素:两端都要重置
            head = tail = null;
        } else {
            head = head.next;
            head.prev = null;
            node.next = null;         // 断开被摘掉的节点
        }
        return node.val;
    }

    public T peek() {
        if (head == null) throw new NoSuchElementException();
        return head.val;
    }
}

这里有两点要说出口。poll 里的 head == tail 分支是整个正确性的关键——忘了把 tail 置空,下一次 offer 就会接到一个已经脱离的节点上。另外 peek 现在抛异常而不是返回 null:这正是对前面泛型 null 陷阱的刻意回应。抛异常(或用 size 字段把关)才能让「空」和「存了个 null」不塌缩成同一个值。

用定容数组实现 Queue(循环缓冲区)

现在是数组版,好玩的问题都在这儿。把存活区间建模成半开区间 [head, tail):head 指向队首元素,tail 是下一个写入槽。offer 先写值再推进 tail;poll 先读值再推进 head。麻烦在数组末尾——朴素的 tail++ 会在队首还有空位时冲出边界。解法是循环数组:每次推进都用 % arr.length 回绕,缓冲区就能复用队首腾出来的槽。

这个回绕带来了经典歧义:操作若干次后,head == tail 既可能表示队列全空,也可能表示队列全满——指针本身说不清是哪种。两种标准解法:浪费一格(永不让 tail 追上 head),或者——更干净、也是我们用的——维护一个显式的 size 计数器和 capacity 比。size == 0 为空,size == arr.length 为满,不用猜。

public class ArrayQueue<T> {
    private T[] arr;
    private int head;    // 队首元素下标
    private int tail;    // 下一个写入位——存活区间是 [head, tail)
    private int size;

    @SuppressWarnings("unchecked")
    public ArrayQueue(int capacity) {
        arr = (T[]) new Object[capacity];   // 不能写 new T[]——泛型运行时被擦除
        head = tail = size = 0;
    }

    public boolean offer(T val) {
        if (size == arr.length) return false;   // 满
        arr[tail] = val;                          // 先赋值……
        tail = (tail + 1) % arr.length;         // ……再推进,回绕
        size++;
        return true;
    }

    public T poll() {
        if (size == 0) return null;             // 空
        T val = arr[head];                        // 先读值……
        arr[head] = null;                        // 释放引用,便于 GC
        head = (head + 1) % arr.length;         // ……再推进
        size--;
        return val;
    }

    public T peek() {
        if (size == 0) throw new NoSuchElementException();
        return arr[head];
    }
}

值得念出口的机械细节:offer 先赋值后自增,poll 先读值后自增。把这个顺序记牢,半开区间 [head, tail) 的不变式就能穿过每一次回绕。size 字段一身兼两职——既消解满/空歧义,又让 offer/poll/peek 都轻松 O(1)。

用定容数组实现 Stack

数组版 Stack 是简单的那个弟弟——没有回绕,因为 Stack 只在一端伸缩。把存活区间建模成 [0, head),其中 head 既是元素个数、也是下一个写入下标。push 在 head 赋值再自增;pop 先自减再读;peek 看 arr[head - 1]。全是 O(1),而且只有一个边界变量要推理。

public class ArrayStack<T> {
    private final T[] arr;
    private int head;    // 元素个数;有效范围是 [0, head)

    @SuppressWarnings("unchecked")
    public ArrayStack(int capacity) {   // 注意:构造器名要跟自己的类同名,不是 ArrayQueue
        arr = (T[]) new Object[capacity];
        head = 0;
    }

    public boolean push(T val) {
        if (head == arr.length) return false;   // 满
        arr[head++] = val;                        // 先赋值,再抬高栈顶
        return true;
    }

    public T pop() {
        if (head == 0) throw new EmptyStackException();
        T val = arr[--head];                      // 先退一步,再读
        arr[head] = null;                        // 释放引用
        return val;
    }

    public T peek() {
        if (head == 0) throw new EmptyStackException();
        return arr[head - 1];
    }
}

前置自减与后置自增就是整个诀窍:arr[head++] 把值 push 进当前栈顶槽再把标记上移,而 arr[--head] 先把标记下移、再读现在暴露出来的元素。(笔记里空时抛的是裸 NullPointerException;地道的信号是 EmptyStackException——java.util.Stack 自己抛的就是它——这样空栈的 bug 读起来才像空栈的 bug。)

Follow-up:扩容与均摊代价

对任何定容结构最自然的反问:「装满了怎么办?」答案是扩大底层数组——通常翻倍——分配一个更大的数组、把元素拷过去、再换上。循环队列这里有一处微妙:不能盲目 Arrays.copyOf,因为存活元素可能回绕越过了末尾;要从 head 起把它们展开进一个全新的、不回绕的数组,再重置 head = 0、tail = size。

@SuppressWarnings("unchecked")
private void resize(int newCapacity) {
    T[] bigger = (T[]) new Object[newCapacity];
    for (int i = 0; i < size; i++)
        bigger[i] = arr[(head + i) % arr.length];   // 把回绕展开成整齐布局
    arr = bigger;
    head = 0;
    tail = size;                                     // 重新变成 [0, size),不再回绕
}

单次扩容确实昂贵——O(n) 拷贝全部元素,如果你在哈希表里做这件事,那就是同一笔「rehash 很贵」的开销。但——值得落地的一句——均摊代价并不高。因为你是翻倍而不是每次加一,一次大小为 n 的拷贝只在 n 次廉价 O(1) 操作之后发生,把拷贝的工作摊到这些操作上,平均每次操作是 O(1)。这正是 ArrayList 尾插和 第 6 课 里 HashMap 扩容背后的论证——说出「单次贵、均摊 O(1)」,你就答到了面试官钓的那个点上。

刷题清单