手把手教你实现常用数据结构，代码不再黑盒

很多人学编程的时候，一看到链表、栈、队列这些名词就头大。书上讲得抽象，API 调用倒是会了，可一旦面试官问“你能自己写一个吗”，立马卡壳。其实，数据结构没那么玄乎，亲手实现一遍，理解自然就上来了。

从最简单的开始：手写一个动态数组

平时用 list 或 ArrayList 的时候，是不是觉得它能自动扩容很神奇？其实原理很简单。我们用 Java 写个简化版看看：

public class MyArrayList {
    private int[] data;
    private int size;
    private int capacity;

    public MyArrayList() {
        this.capacity = 10;
        this.size = 0;
        this.data = new int[capacity];
    }

    public void add(int value) {
        if (size == capacity) {
            resize();
        }
        data[size++] = value;
    }

    private void resize() {
        capacity *= 2;
        int[] newData = new int[capacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        return data[index];
    }
}

就这么几十行，一个能自动扩容的数组容器就有了。你会发现，所谓的“高级功能”，不过是一层一层叠加出来的逻辑。

链表也不难：自己连节点

链表的核心是“指针”——在现代语言里就是引用。比如写一个单向链表节点：

class ListNode {
    int val;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
}

插入操作只要改改指向就行。比如在头部插入新节点：

public void addFirst(int value) {
    ListNode newNode = new ListNode(value);
    newNode.next = head;
    head = newNode;
}

删节点也一样，找到前一个，把它的 next 指向目标的下一个，垃圾回收自然会清理掉中间那个。

栈和队列：用数组或链表就能搭出来

栈讲究后进先出，就像叠盘子。我们可以用动态数组来实现：

public class MyStack {
    private MyArrayList data;

    public MyStack() {
        data = new MyArrayList();
    }

    public void push(int x) {
        data.add(x);
    }

    public int pop() {
        if (data.size == 0) throw new RuntimeException("empty");
        return data.get(--data.size); // 简化处理
    }

    public int top() {
        return data.get(data.size - 1);
    }
}

队列呢？先进先出，像排队买奶茶。可以用链表实现，头删尾插：

public class MyQueue {
    private ListNode front, rear;

    public void offer(int x) {
        ListNode node = new ListNode(x);
        if (rear == null) {
            front = node;
            rear = node;
        } else {
            rear.next = node;
            rear = node;
        }
    }

    public int poll() {
        if (front == null) throw new RuntimeException("empty");
        int val = front.val;
        front = front.next;
        if (front == null) rear = null;
        return val;
    }
}

这些结构本身不复杂，关键是你得动手连一遍。光看别人写等于背菜谱，自己炒一次才知道火候怎么调。

为什么非要手写一遍？

你在公司写业务代码，确实天天调 API。但哪天系统卡了，你得知道 ArrayList 扩容一次要复制整个数组，频繁 add 就可能成性能瓶颈。或者缓存用 LRU，底层靠双向链表+哈希表，不懂原理根本调不好。

手写实现不是为了造轮子，而是为了拆轮子。就像学开车不用先学造汽车，但懂点发动机原理，油门踩起来才心里有数。

找个周末，花两个小时，从数组开始，一个一个敲。别抄，试着自己想接口怎么设计，边界怎么处理。等你写完，再看集合框架源码，会发现很多命名和判断都似曾相识——因为你已经做过一遍了。