C++数据结构之链表的创建

C++中链表的创建一般可分为以下几个步骤：

1. 创建节点结构体
2. 创建链表类，定义私有变量头结点（head）和一些公有方法，如插入、删除和打印链表等
3. 实现链表的插入、删除和打印方法

下面将会对以上每个步骤进行详细讲解。

1. 创建节点结构体

节点结构体包含两个部分，一个是存储数据的变量，另一个是存储指向下一个节点的指针。代码如下：

struct Node {
    int val;  // 存储节点的数据
    Node *next; // 存储指向下一个节点的指针
};

2. 创建链表类

链表类一般包括两个私有变量：头结点head和链表长度size，以及一些公有方法，如插入、删除和打印链表等。代码如下：

class LinkedList {
private:
    Node *head; // 头结点指针
    int size; // 链表长度

public:
    LinkedList(); // 构造函数
    ~LinkedList(); // 析构函数
    void insert(int index, int val); // 在指定位置插入节点
    void remove(int index); // 删除指定位置的节点
    void printList(); // 打印整个链表
};

3. 实现链表的插入、删除和打印方法

插入节点

插入节点需要先找到要插入的位置，然后插入节点，修改指针的指向。代码如下：

void LinkedList::insert(int index, int val) {
    if (index < 0 || index > size) { // 判断插入位置是否合法
        return;
    }

    Node *node = new Node(); // 创建新节点
    node->val = val;
    node->next = nullptr;

    if (index == 0) { // 若插入位置为0，则更新head指针
        node->next = head;
        head = node;
    } else {
        Node *prev = head;
        for (int i = 0; i < index - 1; i++) { // 找到要插入位置的前一个节点
            prev = prev->next;
        }
        node->next = prev->next; // 插入节点
        prev->next = node;
    }

    size++; // 修改链表长度
}

删除节点

删除节点需要先找到要删除的位置，然后将前一个节点的指针指向下一个节点，最后删除要删除的节点。代码如下：

void LinkedList::remove(int index) {
    if (index < 0 || index >= size) { // 判断删除位置是否合法
        return;
    }

    Node *prev = head;
    if (index == 0) { // 若删除位置为0，则更新head指针
        head = prev->next;
    } else {
        for (int i = 0; i < index - 1; i++) { // 找到要删除位置的前一个节点
            prev = prev->next;
        }
    }

    Node *node = prev->next; // 要删除的节点指针
    prev->next = node->next; // 将前一个节点的指针指向下一个节点
    delete node; // 删除节点
    size--; // 修改链表长度
}

打印链表

打印链表需要遍历整个链表，依次输出每个节点的数据。代码如下：

void LinkedList::printList() {
    Node *curr = head;
    while (curr != nullptr) { // 遍历整个链表
        cout << curr->val << " -> ";
        curr = curr->next;
    }
    cout << "NULL" << endl; // 最后一个节点指向NULL
}

示例说明

1. 首先，我们创建一个空链表对象，然后插入若干元素，最后打印整个链表。代码如下：

LinkedList list;

list.insert(0, 1); // 在位置0插入元素1
list.insert(1, 2); // 在位置1插入元素2
list.insert(2, 3); // 在位置2插入元素3

list.printList(); // 打印链表结果为：1 -> 2 -> 3 -> NULL

1. 然后，我们从链表中删除一个元素，并再次打印链表。代码如下：

list.remove(1); // 删除位置1的元素

list.printList(); // 打印链表结果为：1 -> 3 -> NULL

以上就是C++中链表的创建和基本操作的完整攻略。