第3课数据结构_数组_链表
热度🔥:89 免费课程
授课语音
数组和链表
1. 介绍
数组（Array） 用于存储固定数量的相同类型的元素。元素在内存中是连续存储的，通过索引访问，提供了高效的随机访问能力和简单的实现，适用于需要快速访问且不需要频繁动态调整大小的场景。
链表（Linked List） 每个节点包含数据和指向下一个节点的指针（在双链表中，还包含指向前一个节点的指针）。节点在内存中不一定是连续的，提供了灵活的大小调整和高效的插入删除操作，适用于动态数据集合和需要频繁插入删除的情况，但访问速度较慢且内存开销较大。
1.1 内存结构
- 数组：内存连续性，数组的元素在内存中是连续存储的，地址计算简单且快速；固定大小，数组的大小在创建时定义，之后无法调整（动态数组可以在运行过程中动态扩容）。
- 链表：内存分散，链表的节点在内存中可能是非连续的，每个节点包含指向其他节点的指针；动态大小，链表的大小可以动态调整，可以随时增加或删除节点。
1.2 访问时间
- 数组：随机访问，支持常数时间复杂度 O(1) 的随机访问。可以通过索引直接访问任何元素，效率高。
- 链表：顺序访问，访问某个元素时需要从头节点开始逐个遍历，时间复杂度为 O(n)。不支持直接随机访问。
1.3 插入和删除
- 数组：插入，在数组的中间或开头插入元素时，需要移动后续的元素，时间复杂度为 O(n)。在数组末尾插入元素通常为 O(1)，但前提是数组有足够的空间。删除，在数组的中间或开头删除元素时，需要移动后续的元素，时间复杂度为 O(n)。在末尾删除元素通常为 O(1)。
- 链表：插入，在链表中插入元素时，只需调整指针，时间复杂度为 O(1)（在已知位置的情况下），在链表的末尾插入元素也可以在常数时间内完成（假设已知末尾）。删除，在链表中删除元素时，只需调整指针，时间复杂度为 O(1)（在已知位置的情况下）。
1.4 内存使用
- 数组：空间效率，数组的内存使用是连续的，额外内存开销较少。每个元素占用固定的内存空间。
- 链表：空间开销，每个节点需要额外的内存来存储指针（在双链表中，还需要存储前驱指针），因此内存开销较大。
1.5 性能
- 数组：优点，在随机访问和遍历方面表现优异，因为元素存储在连续内存中，访问速度快。缺点，插入和删除操作效率较低，尤其是在数组中间部分。
- 链表：优点，插入和删除操作效率较高，尤其在链表的开头或中间部分。大小动态调整灵活。缺点，访问操作较慢，需要顺序遍历节点，额外内存开销较大。
1.6 适用场景
- 数组：适合需要频繁随机访问的应用，如静态数据集合、缓存数据、固定大小的数据集合。
- 链表：适合需要频繁插入和删除的应用，如动态数据集合、栈和队列的实现、数据量动态变化的情况。
1.7 数组 vs 链表
| 特性 | 数组 | 链表 |
|---|---|---|
| 存储结构 | 连续内存空间 | 不连续的内存空间，每个元素都有指针指向下一个元素 |
| 访问速度 | 支持快速随机访问，时间复杂度为 O(1) | 随机访问较慢，时间复杂度为 O(n) |
| 插入和删除 | 插入和删除操作较慢，时间复杂度为 O(n) | 插入和删除操作较快，时间复杂度为 O(1)（在已知位置时） |
| 内存分配 | 需要在创建时指定大小，大小不可动态调整 | 动态分配内存，大小可以在运行时调整 |
| 空间效率 | 可能浪费内存（如果未使用的空间较多） | 只使用实际存储的数据，没有预留空间 |
| 遍历效率 | 遍历速度快，缓存友好 | 遍历速度较慢，可能导致缓存不友好 |
| 实现复杂性 | 实现简单 | 实现复杂，需要管理指针 |
| 使用场景 | 适合需要快速访问和较少插入删除的场景 | 适合频繁插入和删除的场景 |
2. 代码案例
2.1 数组实现 (Array)
// ======================数组==========================
#include <iostream>
#include <stdexcept>
#include <vector>
class Array {
private:
int size; // 数组的大小
std::vector<int> array; // 存储数组元素的容器
public:
// 构造函数：初始化数组
Array(int size) {
this->size = size;
array.resize(size, -1); // 使用 -1 初始化数组
}
// 设置数组指定索引位置的值
void set(int index, int value) {
if (index >= 0 && index < size) {
array[index] = value;
} else {
throw std::out_of_range("索引超出范围");
}
}
// 获取数组指定索引位置的值
int get(int index) {
if (index >= 0 && index < size) {
return array[index];
} else {
throw std::out_of_range("索引超出范围");
}
}
// 删除数组指定索引位置的值
void deleteAt(int index) {
if (index >= 0 && index < size) {
array[index] = -1; // 使用 -1 表示删除
} else {
throw std::out_of_range("索引超出范围");
}
}
// 返回数组的字符串表示
std::string toString() {
std::string result = "[";
for (int i = 0; i < size; ++i) {
result += std::to_string(array[i]);
if (i < size - 1) result += ", ";
}
result += "]";
return result;
}
};
2.2 单链表实现 (Singly Linked List)
// ======================单链表==========================
#include <iostream>
class Node {
public:
int data; // 节点的数据
Node* next; // 指向下一个节点的指针
// 构造函数：创建节点
Node(int data) : data(data), next(nullptr) {}
};
class SinglyLinkedList {
private:
Node* head; // 链表的头节点
public:
// 构造函数：初始化空链表
SinglyLinkedList() : head(nullptr) {}
// 向链表的末尾添加一个新节点
void append(int data) {
Node* newNode = new Node(data);
if (head == nullptr) {
head = newNode; // 如果链表为空，新节点成为头节点
} else {
Node* last = head;
while (last->next != nullptr) {
last = last->next; // 遍历到链表的最后一个节点
}
last->next = newNode; // 将新节点链接到链表的末尾
}
}
// 删除链表中第一个匹配指定数据的节点
void deleteNode(int data) {
Node* current = head;
if (current == nullptr) return;
// 如果要删除的是头节点
if (current->data == data) {
head = current->next;
delete current;
return;
}
Node* prev = nullptr;
while (current != nullptr && current->data != data) {
prev = current;
current = current->next;
}
// 如果找到要删除的节点
if (current != nullptr) {
prev->next = current->next; // 跳过要删除的节点
delete current;
}
}
// 查找链表中第一个匹配指定数据的节点，并返回节点数据
int get(int data) {
Node* current = head;
while (current != nullptr) {
if (current->data == data) {
return current->data;
}
current = current->next;
}
return -1; // 未找到数据
}
// 打印链表的所有节点
void printList() {
Node* current = head;
if (current == nullptr) {
std::cout << "链表为空" << std::endl;
return;
}
while (current != nullptr) {
std::cout << current->data << " -> ";
current = current->next;
}
std::cout << "None" << std::endl;
}
// 析构函数：释放链表的内存
~SinglyLinkedList() {
Node* current = head;
while (current != nullptr) {
Node* next = current->next;
delete current;
current = next;
}
}
};
2.3 双向链表实现 (Doubly Linked List)
// ======================双链表==========================
#include <iostream>
class DoublyNode {
public:
int data; // 节点的数据
DoublyNode* next; // 指向下一个节点的指针
DoublyNode* prev; // 指向前一个节点的指针
// 构造函数：创建双向节点
DoublyNode(int data) : data(data), next(nullptr), prev(nullptr) {}
};
class DoublyLinkedList {
private:
DoublyNode* head; // 链表的头节点
public:
// 构造函数：初始化空双向链表
DoublyLinkedList() : head(nullptr) {}
// 向双向链表的末尾添加一个新节点
void append(int data) {
DoublyNode* newNode = new DoublyNode(data);
if (head == nullptr) {
head = newNode; // 如果链表为空，新节点成为头节点
head->next = head;
head->prev = head;
} else {
DoublyNode* last = head->prev;
last->next = newNode;
newNode->prev = last;
newNode->next = head;
head->prev = newNode;
}
}
// 删除双向链表中第一个匹配指定数据的节点
void deleteNode(int data) {
if (head == nullptr) return;
DoublyNode* current = head;
while (true) {
if (current->data == data) {
if (current == head) {
if (current->next == current) { // 只有一个节点
head = nullptr;
} else {
head = current->next;
head->prev = current->prev;
current->prev->next = head;
}
} else {
current->prev->next = current->next;
current->next->prev = current->prev;
}
delete current;
return;
}
current = current->next;
if (current == head) break; // 循环链表
}
}
// 查找双向链表中第一个匹配指定数据的节点，并返回节点数据
int get(int data) {
if (head == nullptr) return -1;
DoublyNode* current = head;
while (true) {
if (current->data == data) {
return current->data;
}
current = current->next;
if (current == head) break;
}
return -1; // 未找到数据
}
// 打印双向链表的所有节点
void printList() {
if (head == nullptr) {
std::cout << "链表为空" << std::endl;
return;
}
DoublyNode* current = head;
do {
std::cout << current->data << " <-> ";
current = current->next;
} while (current != head);
std::cout << "(head)" << std::endl;
}
// 析构函数：释放链表的内存
~DoublyLinkedList() {
if (head == nullptr) return;
DoublyNode* current = head;
do {
DoublyNode* next = current->next;
delete current;
current = next;
} while (current != head);
}
};
2.4 动态数组实现 (Dynamic Array)
// ======================动态数组==========================
#include <iostream>
#include <vector>
class DynamicArray {
private:
std::vector<int> array; // 存储数组元素的容器
public:
// 构造函数：初始化空的动态数组
DynamicArray() {}
// 向动态数组的末尾添加一个新元素
void append(int value) {
array.push_back(value);
}
// 获取动态数组指定索引位置的值
int get(int index) {
if (index >= 0 && index < array.size()) {
return array[index];
} else {
throw std::out_of_range("索引超出范围");
}
}
// 删除动态数组指定索引位置的元素
void deleteAt(int index) {
if (index >= 0 && index < array.size()) {
array.erase(array.begin() + index);
} else {
throw std::out_of_range("索引超出范围");
}
}
// 返回动态数组的字符串表示
std::string toString() {
std::string result = "[";
for (size_t i = 0; i < array.size(); ++i) {
result += std::to_string(array[i]);
if (i < array.size() - 1) result += ", ";
}
result += "]";
return result;
}
};
2.5 示例使用 (Main Function)
// 示例使用
int main() {
// 数组示例
Array arr(5); // 创建一个大小为 5 的数组
arr.set(0, 10);
arr.set(1, 20);
std::cout << "数组: " << arr.toString() << std::endl;
std::cout << "索引 1 处的值: " << arr.get(1) << std::endl;
arr.deleteAt(1);
std::cout << "删除后的数组: " << arr.toString() << std::endl;
// 单链表示例
SinglyLinkedList sll;
sll.append(1);
sll.append(2);
sll.append(3);
std::cout << "单链表: ";
sll.printList();
std::cout << "查找值为 2 的节点: " << sll.get(2) << std::endl;
sll.deleteNode(2);
std::cout << "删除后的单链表: ";
sll.printList();
// 双向链表示例
DoublyLinkedList dcll;
dcll.append(10);
dcll.append(20);
dcll.append(30);
std::cout << "双向链表: ";
dcll.printList();
std::cout << "查找值为 20 的节点: " << dcll.get(20) << std::endl;
dcll.deleteNode(20);
std::cout << "删除后的双向链表: ";
dcll.printList();
// 动态数组示例
DynamicArray da;
da.append(5);
da.append(15);
da.append(25);
std::cout << "动态数组: " << da.toString() << std::endl;
std::cout << "索引 1 处的值: " << da.get(1) << std::endl;
da.deleteAt(1);
std::cout << "删除后的动态数组: " << da.toString() << std::endl;
return 0;
}
解释：
- 数组实现 (
Array): 用std::vector来实现动态数组，提供set,get,deleteAt方法。 - 单链表 (
SinglyLinkedList): 使用Node类和next指针实现单链表的基本操作。 - 双向链表 (
DoublyLinkedList): 使用DoublyNode类和next,prev指针实现双向链表的基本操作。 - 动态数组 (
DynamicArray): 使用std::vector来模拟动态数组。
系列课程：
📱 下载客户端
小程序
安卓APP
iOS APP
📚 视频课程
- Java入门教程 86
- C++入门教程 45
- Go入门教程 38
- JavaScript入门教程 35
- Python入门教程 33
- SQL入门教程 29
- 数据结构与算法 30
- 设计模式入门 23
- C语言入门教程 25
- Redis入门教程 31