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

大家好，欢迎继续学习《算法面试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)（面试最优解法，体现优化能力）。

代码示例（Java）：

public int[] twoSum(int[] nums, int target) { // 哈希表存储元素和下标 Map<Integer, 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，简单）

题目：将两个升序链表合并为一个新的升序链表，返回合并后的链表头节点。

核心思路：双指针法，分别指向两个链表的头节点，比较两个节点的值，将较小的节点接入新链表，依次移动指针，直到其中一个链表遍历完毕，再将剩余节点接入新链表。

三、数组与链表核心区别（面试必问，背会直接用）

数组和链表的区别，是算法面试中最基础、最常考的题目，直接背会以下对比，面试时可以直接回答，不用临场思考：

以上就是数组与链表的核心知识点，涵盖定义、底层原理、面试真题和核心区别，都是面试必考点，建议大家重点掌握代码实现，尤其是双指针法（数组和链表都常用），这是面试中的“加分项”。

记住：数组和链表是算法的基础，吃透这两个知识点，后续学习栈、队列、图等复杂数据结构，会轻松很多。

下一篇，我们将学习《栈与队列：原理、实现及面试高频应用场景》，继续夯实基础，敬请期待～