数据结构基础：数组与链表（定义+底层原理+面试必问）

大家好欢迎继续学习《算法面试60讲2026最新版·全真题带解析》专栏上一篇我们搞懂了算法面试的考点分布、评分标准和避坑指南明确了基础数据结构是算法面试的核心占比35-40分今天这一篇我们就从最基础、最高频的两个数据结构——数组与链表开始系统学习帮你夯实算法面试的第一块基石。数组和链表是算法面试中“出场率最高”的基础数据结构不管是校招还是社招不管是算法岗还是后端、前端岗都会重点考察。很多复杂的算法和数据结构如图、栈、队列本质上都是基于数组或链表实现的所以吃透这两个知识点能为后续学习打下坚实的基础。今天这篇内容我们不搞复杂理论只聚焦“面试考点”从定义、底层原理、核心区别到面试必问真题一步步讲透让你看完就能掌握应对面试不慌。一、数组Array面试高频基础必吃透1. 数组的定义面试必背数组是一种连续存储的线性数据结构它将相同类型的元素按照一定的顺序存储在一块连续的内存空间中。简单来说就是“把相同类型的元素排成一排放在连续的内存里”。举个通俗的例子我们平时用的“手机通讯录”把所有联系人按顺序存在一起每个联系人占用固定大小的空间这就是数组的思想。面试重点记住“连续存储”“相同类型”这两个核心关键词这是数组与其他数据结构如链表的核心区别也是面试官常问的考点。2. 数组的底层原理面试高频追问数组的底层核心是“连续内存空间”正因为内存连续所以它有两个非常鲜明的特点也是面试必问的重点访问速度快因为内存连续我们可以通过“下标索引”直接定位到目标元素时间复杂度为O(1)。比如数组nums[0]可以直接通过内存地址计算瞬间找到对应元素不需要遍历。插入、删除效率低如果要在数组中间插入或删除一个元素需要移动后续所有元素腾出空间或填补空缺时间复杂度为O(n)。比如在数组[1,2,3,4]中插入5到索引1的位置需要把2、3、4依次后移一位再插入5操作繁琐。补充数组的容量是固定的初始化时确定如果需要扩容需要重新申请一块更大的连续内存把原数组的元素复制过去这也是数组的一个局限性。3. 数组面试必问真题基础题必练数组的面试题以基础题为主校招重点考察社招也会作为基础题铺垫以下3道真题覆盖高频考点建议动手写一遍代码真题1两数之和LeetCode 1简单题目给定一个整数数组nums和一个目标值target请你在该数组中找出和为目标值的两个整数并返回它们的数组下标。核心思路两种解法对比掌握面试时可灵活选择解法1暴力法双重循环遍历数组判断两个元素之和是否等于target时间复杂度O(n²)空间复杂度O(1)适合零基础入门面试时可先说出这种解法再优化。解法2哈希表优化遍历数组时用哈希表存储元素和其下标判断target - 当前元素是否在哈希表中时间复杂度O(n)空间复杂度O(n)面试最优解法体现优化能力。代码示例Javapublic int[] twoSum(int[] nums, int target) { // 哈希表存储元素和下标 MapInteger, Integer map new HashMap(); for (int i 0; i nums.length; i) { int complement target - nums[i]; // 判断补数是否在哈希表中 if (map.containsKey(complement)) { return new int[]{map.get(complement), i}; } map.put(nums[i], i); } // 题目假设存在唯一解此处可忽略异常处理 throw new IllegalArgumentException(No two sum solution); }真题2数组去重高频基础题题目给定一个排序数组nums原地删除重复出现的元素使每个元素只出现一次返回删除后的数组长度。核心思路双指针法面试高频技巧用慢指针指向当前不重复的元素快指针遍历数组遇到不重复的元素就移动慢指针并赋值时间复杂度O(n)空间复杂度O(1)。真题3数组反转面试必练题目给定一个数组将数组中的元素反转要求原地反转不使用额外的数组空间。核心思路双指针法左右两个指针分别指向数组的开头和结尾交换两个指针的元素然后向中间移动直到两个指针相遇时间复杂度O(n)空间复杂度O(1)。二、链表Linked List面试难点铺垫重点掌握1. 链表的定义面试必背链表是一种非连续存储的线性数据结构它由一个个“节点”组成每个节点包含两个部分数据域存储元素和指针域存储下一个节点的地址。节点之间通过指针连接形成一条链式结构内存空间可以不连续。举个通俗的例子我们平时用的“铁链”每一节铁链都是一个节点一节连一节不需要连续排列这就是链表的思想。面试重点链表的核心是“非连续存储”“节点指针”与数组的“连续存储”形成鲜明对比这是面试中常考的区别题。2. 链表的底层原理面试高频追问链表的底层核心是“节点指针”内存不连续因此它的特点与数组完全相反也是面试必问的重点访问速度慢因为内存不连续无法通过下标直接访问元素必须从链表的头节点开始依次遍历直到找到目标元素时间复杂度为O(n)。插入、删除效率高如果要插入或删除一个节点只需要修改对应节点的指针不需要移动其他节点时间复杂度为O(1)前提是找到要插入/删除的节点找节点的时间还是O(n)。补充链表的容量是动态的不需要初始化容量只要有内存空间就可以不断添加节点没有扩容的烦恼。3. 链表的常见类型面试必知面试中链表主要考察3种类型重点掌握前两种单链表最基础的链表每个节点只有一个指针指向后一个节点尾节点的指针指向null面试最常考。双链表每个节点有两个指针一个指向后一个节点一个指向前一个节点访问前后节点更方便部分社招会考察。循环链表尾节点的指针不指向null而是指向头节点形成一个循环考察较少了解即可。4. 链表面试必问真题基础题必练链表的面试题比数组稍难重点考察指针操作以下3道真题是校招/社招的高频题必须掌握真题1链表反转LeetCode 206简单必练题目反转一个单链表返回反转后的头节点。核心思路两种解法重点掌握迭代法面试高频解法1迭代法用三个指针prev、curr、next依次反转每个节点的指针时间复杂度O(n)空间复杂度O(1)面试最优解法。解法2递归法递归遍历链表从尾节点开始反转时间复杂度O(n)空间复杂度O(n)理解即可面试时可作为补充。代码示例Java迭代法public ListNode reverseList(ListNode head) { ListNode prev null; // 前驱节点 ListNode curr head; // 当前节点 while (curr ! null) { ListNode next curr.next; // 保存下一个节点 curr.next prev; // 反转当前节点的指针 prev curr; // 前驱节点后移 curr next; // 当前节点后移 } return prev; // 反转后prev是新的头节点 } // 链表节点定义面试时可直接写出 class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val val; } ListNode(int val, ListNode next) { this.val val; this.next next; } }真题2判断链表是否有环LeetCode 141简单题目给定一个单链表判断链表中是否有环。核心思路快慢指针法面试高频技巧快指针每次走两步慢指针每次走一步如果链表有环快慢指针一定会相遇如果没有环快指针会先到达null。真题3合并两个有序链表LeetCode 21简单题目将两个升序链表合并为一个新的升序链表返回合并后的链表头节点。核心思路双指针法分别指向两个链表的头节点比较两个节点的值将较小的节点接入新链表依次移动指针直到其中一个链表遍历完毕再将剩余节点接入新链表。三、数组与链表核心区别面试必问背会直接用数组和链表的区别是算法面试中最基础、最常考的题目直接背会以下对比面试时可以直接回答不用临场思考对比维度数组链表内存存储连续内存空间非连续内存空间节点指针访问效率高O(1)下标直接访问低O(n)需遍历插入/删除效率低O(n)需移动元素高O(1)仅修改指针容量固定需手动扩容动态无需扩容适用场景频繁访问、少量插入/删除频繁插入/删除、少量访问以上就是数组与链表的核心知识点涵盖定义、底层原理、面试真题和核心区别都是面试必考点建议大家重点掌握代码实现尤其是双指针法数组和链表都常用这是面试中的“加分项”。记住数组和链表是算法的基础吃透这两个知识点后续学习栈、队列、图等复杂数据结构会轻松很多。下一篇我们将学习《栈与队列原理、实现及面试高频应用场景》继续夯实基础敬请期待