美团一面

面试高频问题：“数组和链表有什么区别？”回答必须覆盖：存储结构、时间复杂度、缓存友好性、内存碎片、扩容机制、嵌入式适用场景。一、数组（Array）1. 存储结构连续内存固定大小（静态数组）可动态扩容（动态数组，如 malloc + 重新分配）下标访问：基址 + 偏移地址计算公式： addr = base + index * sizeof(T) 本质是一次加法运算 → O(1)2. 时间复杂度随机访问O(1)直接地址计算插入O(n)需要整体搬移删除O(n)后续元素前移扩容O(n)重新申请 + 拷贝3. 优点随机访问极快CPU Cache 友好（顺序存储）无额外指针开销内存碎片少4. 缺点插入删除...