05 | 理论讲解：数组&链表-算法面试通关 50 讲

当前位置:　首页>> 技术小册>> 算法面试通关 50 讲

### 05 | 理论讲解：数组&链表

在算法面试中，数据结构是基础且核心的知识点，它们不仅是解决问题的工具，更是衡量候选人编程素养和逻辑思维能力的重要标尺。本章将深入剖析两种最基本也是最常用的数据结构——数组（Array）与链表（LinkedList），探讨它们的定义、特性、操作方式以及在实际面试问题中的应用。

#### 一、数组（Array）

##### 1.1 定义与特性

数组是一种基础的数据结构，用于在计算机内存中连续存储相同类型的数据。它允许通过索引（通常是整数）快速访问元素，索引通常从0开始。数组的主要特性包括：

- **固定大小**：一旦创建，数组的大小（即能存储的元素数量）就不能改变。这意味着如果需要存储更多元素，可能需要重新分配一个更大的数组，并将旧数组中的元素复制到新数组中，这个过程称为“扩容”。
- **随机访问**：由于数组在内存中是连续存储的，因此可以通过索引直接访问任意位置的元素，时间复杂度为O(1)。
- **类型一致性**：数组中的所有元素必须是相同的数据类型。

##### 1.2 操作

- **插入**：在数组中间或末尾插入元素时，若数组已满，则需要先扩容；否则，从插入点开始，后续元素均需向后移动一位以腾出空间，时间复杂度为O(n)（n为数组长度）。在数组开头插入元素，则所有元素均需向后移动，时间复杂度同样为O(n)。
- **删除**：删除数组中的元素，需要将该元素之后的所有元素向前移动一位来填补空缺，时间复杂度也为O(n)。
- **查找**：通过索引直接访问元素，时间复杂度为O(1)；若需通过值查找元素位置，则需遍历数组，时间复杂度为O(n)。
- **遍历**：按顺序访问数组中的每个元素，时间复杂度为O(n)。

##### 1.3 应用场景

- 当需要快速访问元素且元素数量固定或变化不大时，如记录班级学生的成绩。
- 缓存机制中，利用数组的随机访问特性快速获取数据。
- 实现静态栈和队列等数据结构。

#### 二、链表（LinkedList）

##### 2.1 定义与特性

链表是由一系列节点（Node）组成的集合，每个节点包含数据部分和指向列表中下一个节点的指针（或引用）。与数组不同，链表在内存中不必连续存储，因此它具有以下特性：

- **动态大小**：链表的大小可以根据需要动态增长或缩小，无需担心空间限制。
- **非随机访问**：由于节点在内存中不连续，因此不能通过索引直接访问链表中的元素，访问特定元素需要从头节点开始遍历链表，时间复杂度为O(n)。
- **类型灵活性**：虽然通常链表中的节点会包含相同类型的数据，但理论上链表的节点可以包含不同类型的数据或数据结构，增强了灵活性。

##### 2.2 类型

链表有多种类型，最常见的有单向链表（Singly Linked List）和双向链表（Doubly Linked List）：

- **单向链表**：每个节点只包含一个指向下一个节点的指针。
- **双向链表**：每个节点包含两个指针，一个指向前一个节点（前驱），另一个指向下一个节点（后继）。这使得从任意节点向前或向后遍历链表成为可能。

##### 2.3 操作

- **插入**：在链表中的某个位置插入新节点，需要找到该位置的前一个节点，然后调整指针的指向，时间复杂度为O(n)（最坏情况，即在最前端或最后端插入时，可能需要遍历整个链表）。
- **删除**：删除链表中的节点，同样需要找到该节点的前一个节点，然后调整指针指向，时间复杂度也为O(n)。
- **查找**：遍历链表以查找具有特定值的节点，时间复杂度为O(n)。
- **遍历**：按顺序访问链表中的每个节点，时间复杂度为O(n)。

##### 2.4 应用场景

- 当数据项集合的大小频繁变动时，如实现栈、队列等数据结构。
- 需要在数据项间进行大量插入和删除操作时，链表的高效性尤为明显。
- 链表的灵活性允许它作为更复杂数据结构（如图、树）的基础组件。

#### 三、数组与链表的比较

| 特性 | 数组 | 链表 |
|------|------|------|
| 存储方式 | 连续存储 | 非连续存储 |
| 大小变化 | 固定大小，需扩容 | 动态大小 |
| 访问速度 | 索引访问，O(1) | 顺序访问，O(n) |
| 插入/删除 | 可能需要移动元素，O(n) | 只需调整指针，平均O(1)，但寻找位置O(n) |
| 内存利用 | 紧凑，可能浪费空间（因扩容） | 不紧凑，但灵活 |
| 遍历 | 顺序遍历，O(n) | 顺序遍历，O(n) |
| 应用场景 | 快速访问，大小固定或变化不大 | 大小频繁变化，需要频繁插入删除 |

#### 四、面试技巧与实战

在算法面试中，理解并掌握数组与链表的基本操作和特性至关重要。面试官可能会通过以下类型的问题来考察你的能力：

- **基础操作题**：要求实现数组的插入、删除、查找等操作，或链表的反转、查找环等经典问题。
- **算法设计题**：利用数组或链表解决具体问题，如实现一个高效的缓存机制、排序算法（如归并排序中的合并过程通常使用数组）等。
- **优化题**：给定一个基于数组或链表的问题，要求优化时间复杂度或空间复杂度，如使用双指针技术解决链表中的某些问题。

应对这些面试题，建议：

- **深入理解**：不仅要知道如何操作数组和链表，更要理解它们背后的原理和适用场景。
- **动手实践**：通过编写代码实现各种操作，加深对数据结构的理解。
- **总结归纳**：将遇到的问题和解决方案进行分类和总结，形成自己的知识体系。
- **模拟面试**：与同伴进行模拟面试，通过实战演练提升应对能力。

总之，数组和链表作为最基础的数据结构，在算法面试中占据着举足轻重的地位。通过深入学习和实践，你将能够更加灵活地运用它们来解决各种问题。

该分类下的相关小册推荐：

数据结构与算法(上)

数据结构与算法之美

数据结构与算法(下)

数据结构与算法(中)

编程之道-算法面试(上)

业务开发实用算法精讲

编程之道-算法面试(下)