数组 → 链表 → 栈 → 队列 → 哈希 → 树 → 堆 → 图 → 高级结构

1. 动态数组 Array

Python

Python 自带 list，本质是动态数组。

class DynamicArray:

    def __init__(self):
        self.capacity = 10
        self.size = 0
        self.data = [None] * self.capacity


    def resize(self):
        self.capacity *= 2
        new_data = [None] * self.capacity

        for i in range(self.size):
            new_data[i] = self.data[i]

        self.data = new_data


    def append(self, value):

        if self.size == self.capacity:
            self.resize()

        self.data[self.size] = value
        self.size += 1


    def get(self,index):

        if index < 0 or index >= self.size:
            return None

        return self.data[index]

---

C

#include<stdio.h>
#include<stdlib.h>


typedef struct{

    int *data;

    int size;

    int capacity;

}Array;



Array* createArray(){

    Array *arr = malloc(sizeof(Array));

    arr->capacity=10;
    arr->size=0;

    arr->data=
        malloc(sizeof(int)*arr->capacity);

    return arr;
}



void append(Array* arr,int value){

    if(arr->size==arr->capacity){

        arr->capacity*=2;

        arr->data=
        realloc(arr->data,
        sizeof(int)*arr->capacity);
    }


    arr->data[arr->size++]=value;
}

---

2. 单链表 Linked List

Python

class Node:

    def __init__(self,val):

        self.val=val
        self.next=None



class LinkedList:

    def __init__(self):

        self.head=None


    def insert(self,val):

        node=Node(val)

        node.next=self.head

        self.head=node



    def delete(self,val):

        cur=self.head
        pre=None


        while cur:

            if cur.val==val:

                if pre:
                    pre.next=cur.next
                else:
                    self.head=cur.next

                return


            pre=cur
            cur=cur.next

---

C

typedef struct Node{

    int val;

    struct Node* next;

}Node;



Node* createNode(int val){

    Node* node=
    malloc(sizeof(Node));

    node->val=val;
    node->next=NULL;

    return node;
}



void insert(Node** head,int val){

    Node* node=createNode(val);

    node->next=*head;

    *head=node;
}



void delete(Node** head,int val){

    Node* cur=*head;

    Node* pre=NULL;


    while(cur){

        if(cur->val==val){

            if(pre)
                pre->next=cur->next;
            else
                *head=cur->next;


            free(cur);

            return;
        }


        pre=cur;
        cur=cur->next;
    }
}

---

3. 双向链表

Python

class Node:

    def __init__(self,val):

        self.val=val

        self.prev=None

        self.next=None

面试重点：

• LRU Cache 必须手写双向链表
• HashMap + Double Linked List

---

4. 栈 Stack

Python

class Stack:

    def __init__(self):

        self.data=[]


    def push(self,x):

        self.data.append(x)


    def pop(self):

        return self.data.pop()


    def top(self):

        return self.data[-1]

---

C

#define SIZE 100


typedef struct{

    int data[SIZE];

    int top;

}Stack;



void init(Stack* s){

    s->top=-1;
}



void push(Stack* s,int x){

    s->data[++s->top]=x;

}



int pop(Stack* s){

    return s->data[s->top--];

}

---

5. 队列 Queue

Python

from collections import deque


q=deque()


q.append(1)

x=q.popleft()

---

C 循环队列

#define SIZE 100


typedef struct{


int data[SIZE];

int front;

int rear;


}Queue;



void enqueue(
Queue*q,int x)
{

q->data[q->rear]=x;

q->rear=
(q->rear+1)%SIZE;

}



int dequeue(Queue*q){

int x=q->data[q->front];

q->front=
(q->front+1)%SIZE;

return x;

}

---

6. 哈希表 HashMap

Python

hashmap={}


hashmap["a"]=1


if "a" in hashmap:

    print(hashmap["a"])

---

C 手写链地址法

#define SIZE 100


typedef struct Node{

char key[20];

int value;

struct Node* next;


}Node;



Node* table[SIZE];



int hash(char* key){

int sum=0;

while(*key)
{
sum+=*key++;
}

return sum%SIZE;

}



void insert(char* key,int value){

int h=hash(key);


Node* node=
malloc(sizeof(Node));


strcpy(node->key,key);

node->value=value;


node->next=table[h];

table[h]=node;

}

---

7. 二叉树 Binary Tree

Python

class TreeNode:


    def __init__(self,val):

        self.val=val

        self.left=None

        self.right=None

遍历：

前序

def preorder(root):

    if not root:
        return

    print(root.val)

    preorder(root.left)

    preorder(root.right)

---

C

typedef struct TreeNode{


int val;


struct TreeNode* left;


struct TreeNode* right;


}TreeNode;



TreeNode* create(int val){

TreeNode* node=
malloc(sizeof(TreeNode));


node->val=val;

node->left=NULL;

node->right=NULL;


return node;

}

---

8. 二叉搜索树 BST

Python

def insert(root,val):

    if not root:

        return TreeNode(val)


    if val < root.val:

        root.left=insert(root.left,val)

    else:

        root.right=insert(root.right,val)


    return root

---

9. 堆 Heap

AI Infra 面试非常重要：

用途：

• TopK
• 调度
• vLLM continuous batching

Python

import heapq


heap=[]


heapq.heappush(heap,5)

heapq.heappush(heap,2)


x=heapq.heappop(heap)

---

手写小根堆

class MinHeap:


    def __init__(self):

        self.heap=[]


    def push(self,x):

        self.heap.append(x)

        self.up(len(self.heap)-1)



    def pop(self):

        ans=self.heap[0]

        self.heap[0]=self.heap[-1]

        self.heap.pop()

        self.down(0)

        return ans

---

10. 图 Graph

邻接表

Python

graph={}


graph[0]=[1,2]

graph[1]=[3]

DFS:

def dfs(node):

    if node in visited:

        return


    visited.add(node)


    for nxt in graph[node]:

        dfs(nxt)

---

BFS:

from collections import deque


q=deque([start])


while q:

    node=q.popleft()

---

11. 并查集 Union Find

AI Infra 高频：

用途：

• 集群连通
• GPU拓扑
• 图连通问题

Python:

class UnionFind:


    def __init__(self,n):

        self.parent=list(range(n))


    def find(self,x):

        if self.parent[x]!=x:

            self.parent[x]=self.find(
                self.parent[x]
            )

        return self.parent[x]


    def union(self,a,b):

        pa=self.find(a)

        pb=self.find(b)


        if pa!=pb:

            self.parent[pa]=pb

---

12. Trie 字典树

LLM相关：

用途：

• tokenizer
• 前缀搜索

Python:

class TrieNode:


    def __init__(self):

        self.children={}

        self.end=False



class Trie:


    def __init__(self):

        self.root=TrieNode()



    def insert(self,word):

        node=self.root


        for c in word:

            if c not in node.children:

                node.children[c]=TrieNode()


            node=node.children[c]


        node.end=True

---