← 返回首页

第一章-数组和链表

第一章：数组和链表 (Arrays and Linked Lists)

学习内容

数组和链表是两种最基本的数据结构，它们是许多其他数据结构和算法的基础。

数组 (Array)

数组是一种线性数据结构，它用一组连续的内存来存储一组元素。

#### 特点



#### 基本操作
1. 访问元素：通过索引访问，时间复杂度 O(1)
2. 更新元素：通过索引更新，时间复杂度 O(1)
3. 插入元素：在任意位置插入元素，时间复杂度 O(n)
4. 删除元素：删除任意位置元素，时间复杂度 O(n)

链表 (Linked List)

链表是一种线性数据结构，其中的元素不是存储在连续的位置上，而是通过指针连接。

#### 特点



#### 基本操作
1. 遍历：从头节点开始，依次访问每个节点，时间复杂度 O(n)
2. 搜索：查找特定值的节点，时间复杂度 O(n)
3. 插入：在指定位置插入新节点，时间复杂度 O(1)
4. 删除：删除指定节点，时间复杂度 O(1)

重点和难点

重点


1. 理解数组和链表的基本概念和特点
2. 掌握数组和链表的基本操作
3. 理解数组和链表在内存中的存储方式

难点


1. 数组和链表在不同场景下的选择
2. 链表的指针操作容易出错
3. 环形链表的检测和处理

练习题

数组相关


1. 删除排序数组中的重复项 (Remove Duplicates from Sorted Array)
- 题目：给定一个排序数组，你需要原地删除重复出现的元素，使得每个元素只出现一次。
- 解题思路：使用双指针技巧，一个指针用于遍历数组，另一个指针用于记录不重复元素的位置。
- 注意点：确保原地修改数组，不使用额外空间。

2. 移动零 (Move Zeroes)
- 题目：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
- 解题思路：使用双指针，一个指针指向当前可以放置非零元素的位置，另一个指针遍历数组。
- 注意点：必须在不复制数组的情况下原地对数组进行操作。

链表相关


1. 反转链表 (Reverse Linked List)
- 题目：反转一个单链表。
- 解题思路：迭代或递归方式实现。迭代方式需要三个指针：前一个节点、当前节点、下一个节点。
- 注意点：注意处理边界情况，如空链表或只有一个节点的情况。

2. 合并两个有序链表 (Merge Two Sorted Lists)
- 题目：将两个升序链表合并为一个新的升序链表并返回。
- 解题思路：使用双指针分别指向两个链表的头节点，比较节点值大小，依次连接较小的节点。
- 注意点：处理两个链表长度不一致的情况。

解题思路总结

双指针技巧


双指针是数组和链表问题中常用的技巧：

何时使用数组 vs 链表



学习时间

建议学习时间：1-2小时