单元2

下面是一个简洁的 C++ 程序示例，展示了**顺序表（使用 vector）和链表（使用自定义单向链表）**的基本操作对比，包括插入、删除和访问元素：

🧪 顺序表 vs 链表：C++ 示例对比

✅ 顺序表（使用 std::vector）

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> seqList;

    // 插入元素
    seqList.push_back(10);
    seqList.push_back(20);
    seqList.push_back(30);

    // 删除元素（删除第二个）
    seqList.erase(seqList.begin() + 1);

    // 访问元素
    for (int i = 0; i < seqList.size(); ++i) {
        cout << "顺序表元素[" << i << "] = " << seqList[i] << endl;
    }

    return 0;
}

✅ 链表（自定义单向链表）

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

void insert(Node*& head, int val) {
    Node* newNode = new Node(val);
    newNode->next = head;
    head = newNode;
}

void deleteNode(Node*& head, int val) {
    Node* curr = head;
    Node* prev = nullptr;
    while (curr) {
        if (curr->data == val) {
            if (prev) prev->next = curr->next;
            else head = curr->next;
            delete curr;
            return;
        }
        prev = curr;
        curr = curr->next;
    }
}

void printList(Node* head) {
    int index = 0;
    while (head) {
        cout << "链表元素[" << index++ << "] = " << head->data << endl;
        head = head->next;
    }
}

int main() {
    Node* head = nullptr;

    // 插入元素（头插法）
    insert(head, 30);
    insert(head, 20);
    insert(head, 10);

    // 删除元素（删除值为 20 的节点）
    deleteNode(head, 20);

    // 打印链表
    printList(head);

    return 0;
}

📊 对比总结

特性顺序表（vector）链表（自定义）
插入效率中间插入需移动元素，较慢修改指针即可，效率高
删除效率删除需移动元素修改指针即可
随机访问支持 O(1) 下标访问需遍历，O(n)
内存结构连续内存，缓存友好分散内存，灵活扩展
实现复杂度简单（STL支持）需手动管理指针

单链表中，做插入数据的操作时，是否需要同时做两处数据的操作？ 也就是修改前一个数据的后置链接指向，并增加新数据，例如在数据A和B之间插入C，首先要生成新的数据C，其后驱指针指向B，再修改前一个数据A的后驱指针，删除其与B的链接，建立与C的链接。 此外删除操作也是类似的的需要修改两处，该规则适用于双链表和循环链表。