创建一个链表 //在 i 个位序前插入整数 X //删除位序为 i 的元素 // 查找位序为 i 的元素

链表是一种基于指针的数据结构，它由若干个节点（Node）组成，每个节点包含一个数据域和一个指向下一个节点的指针域。链表的头指针指向第一个节点，尾节点的指针域指向 NULL。

下面是一个简单的链表结构体定义：

struct Node {
    int value;          // 数据域
    Node* next;         // 指针域，指向下一个节点
};

创建链表的过程就是动态分配节点的过程，可以使用 new 运算符动态分配节点。下面的代码演示了如何创建一个包含 5 个节点的链表：

Node* head = nullptr;
Node* tail = nullptr;
for (int i = 0; i < 5; i++) {
    Node* node = new Node;
    node->value = i;
    node->next = nullptr;
    if (head == nullptr) {
        head = node;
        tail = node;
    } else {
        tail->next = node;
        tail = node;
    }
}

这段代码中，我们首先定义了两个指针 head 和 tail，分别指向链表的头和尾。然后使用 for 循环创建 5 个节点，每个节点的 value 域赋值为 i，next 域初始化为 nullptr。接着判断 head 是否为 nullptr，如果是，则将 head 和 tail 指向第一个节点；否则将新节点插入到尾节点的后面，并更新 tail 指针。

在 i 个位序前插入整数 X，需要先找到第 i-1 个节点，然后将新节点插入到它的后面。如果 i=0，则需要把新节点作为链表的头节点。下面的代码演示了如何在第 3 个位置插入值为 10 的节点：

int i = 3;
int x = 10;
Node* node = new Node;
node->value = x;
if (i == 0) {
    node->next = head;
    head = node;
} else {
    Node* p = head;
    for (int j = 0; j < i-1 && p != nullptr; j++) {
        p = p->next;
    }
    if (p != nullptr) {
        node->next = p->next;
        p->next = node;
    }
}

这段代码中，我们首先创建一个新节点，并将它的 value 域赋值为 x。然后判断 i 是否为 0，如果是，则将新节点作为头节点，否则需要找到第 i-1 个节点，将新节点插入到它的后面。我们使用一个指针 p 遍历链表，直到找到第 i-1 个节点或者链表末尾。如果找到了第 i-1 个节点，则将新节点插入到它的后面，否则不做任何操作。

删除位序为 i 的元素也类似，需要先找到第 i-1 个节点，然后将它的 next 指针指向第 i+1 个节点。下面的代码演示了如何删除第 3 个节点：

int i = 3;
if (i == 0) {
    Node* p = head;
    head = head->next;
    delete p;
} else {
    Node* p = head;
    for (int j = 0; j < i-1 && p != nullptr; j++) {
        p = p->next;
    }
    if (p != nullptr && p->next != nullptr) {
        Node* q = p->next;
        p->next = q->next;
        delete q;
    }
}

这段代码中，我们首先判断 i 是否为 0，如果是，则直接删除头节点。否则需要找到第 i-1 个节点，将它的 next 指针指向第 i+1 个节点，并删除第 i 个节点。如果找到了第 i-1 个节点和第 i 个节点，则执行删除操作，否则不做任何操作。

查找位序为 i 的元素也类似，需要遍历链表，找到第 i 个节点，然后返回它的 value 域。下面的代码演示了如何查找第 3 个节点的值：

int i = 3;
Node* p = head;
for (int j = 0; j < i && p != nullptr; j++) {
    p = p->next;
}
if (p != nullptr) {
    int x = p->value;
    cout << "第 " << i << " 个节点的值为 " << x << endl;
} else {
    cout << "第 " << i << " 个节点不存在" << endl;
}

这段代码中，我们首先使用一个指针 p 遍历链表，直到找到第 i 个节点或者链表末尾。如果找到了第 i 个节点，则返回它的 value 域，否则输出错误信息。