用C＋＋实现链表基础操作

链表是一种常见的数据结构，它可以动态地存储数据，可以方便地插入和删除节点。链表由一个个节点组成，每个节点包含数据和指向下一个节点的指针。

以下是C++实现链表的基础操作：

1. 定义节点结构体

struct Node {
    int data;
    Node* next;
};

2. 创建链表

Node* createList(int n) {
    Node* head = nullptr;
    Node* tail = nullptr;
    for (int i = 0; i < n; i++) {
        Node* newNode = new Node();
        cin >> newNode->data;
        newNode->next = nullptr;
        if (head == nullptr) {
            head = newNode;
            tail = newNode;
        }
        else {
            tail->next = newNode;
            tail = newNode;
        }
    }
    return head;
}

3. 遍历链表

void traverseList(Node* head) {
    Node* p = head;
    while (p != nullptr) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

4. 插入节点

void insertNode(Node*& head, int pos, int val) {
    Node* newNode = new Node();
    newNode->data = val;
    newNode->next = nullptr;

    if (head == nullptr) {
        head = newNode;
        return;
    }

    if (pos == 0) {
        newNode->next = head;
        head = newNode;
        return;
    }

    Node* p = head;
    int i = 0;
    while (p != nullptr && i < pos - 1) {
        p = p->next;
        i++;
    }

    if (p == nullptr) {
        cout << "Invalid position" << endl;
        return;
    }

    newNode->next = p->next;
    p->next = newNode;
}

5. 删除节点

void deleteNode(Node*& head, int pos) {
    if (head == nullptr) {
        cout << "Empty list" << endl;
        return;
    }

    if (pos == 0) {
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
    }

    Node* p = head;
    int i = 0;
    while (p != nullptr && i < pos - 1) {
        p = p->next;
        i++;
    }

    if (p == nullptr || p->next == nullptr) {
        cout << "Invalid position" << endl;
        return;
    }

    Node* temp = p->next;
    p->next = temp->next;
    delete temp;
}

6. 查找节点

int searchNode(Node* head, int val) {
    Node* p = head;
    int i = 0;
    while (p != nullptr) {
        if (p->data == val) {
            return i;
        }
        p = p->next;
        i++;
    }
    return -1;
}

7. 获取链表长度

int getListLength(Node* head) {
    int len = 0;
    Node* p = head;
    while (p != nullptr) {
        len++;
        p = p->next;
    }
    return len;
}