C++ 单链表实现：创建、遍历、插入、删除和合并

本教程将带您了解如何使用 C++ 类来创建单链表并实现基本操作，包括创建、遍历、插入、删除和合并两个有序单链表。此外，文章还涵盖了双链表和循环链表的实现原理。

1. 设计 C++ 类及相关方法，用于维护单链表

#include <iostream>

class Node {
public:
    int data;
    Node* next;
};

class LinkedList {
public:
    Node* head;

    LinkedList() {
        head = nullptr;
    }

    void insert(int value) {
        Node* newNode = new Node();
        newNode->data = value;
        newNode->next = nullptr;

        if (head == nullptr) {
            head = newNode;
        } else {
            Node* curr = head;
            while (curr->next != nullptr) {
                curr = curr->next;
            }
            curr->next = newNode;
        }
    }

    void remove(int value) {
        if (head == nullptr) {
            std::cout << "List is empty" << std::endl;
            return;
        }

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

        Node* curr = head;
        Node* prev = nullptr;
        while (curr != nullptr && curr->data != value) {
            prev = curr;
            curr = curr->next;
        }

        if (curr == nullptr) {
            std::cout << "Element not found" << std::endl;
            return;
        }

        prev->next = curr->next;
        delete curr;
    }

    void display() {
        if (head == nullptr) {
            std::cout << "List is empty" << std::endl;
            return;
        }

        Node* curr = head;
        while (curr != nullptr) {
            std::cout << curr->data << " ";
            curr = curr->next;
        }
        std::cout << std::endl;
    }
};

2. 写出建立单链表，并向单链表中输入数据的函数

LinkedList createLinkedList() {
    LinkedList list;
    int n;
    std::cout << "Enter the number of elements: ";
    std::cin >> n;

    for (int i = 0; i < n; i++) {
        int value;
        std::cout << "Enter element " << i+1 << ": ";
        std::cin >> value;
        list.insert(value);
    }

    return list;
}

3. 实现单链表的建立、遍历、查找、新元素插入、及元素删除，写出输入及输出的内容

int main() {
    LinkedList list = createLinkedList();

    std::cout << "Linked List: ";
    list.display();

    int searchValue;
    std::cout << "Enter element to search: ";
    std::cin >> searchValue;
    Node* searchResult = list.search(searchValue);
    if (searchResult != nullptr) {
        std::cout << "Element found" << std::endl;
    } else {
        std::cout << "Element not found" << std::endl;
    }

    int insertValue;
    std::cout << "Enter element to insert: ";
    std::cin >> insertValue;
    list.insert(insertValue);

    std::cout << "Linked List after insertion: ";
    list.display();

    int removeValue;
    std::cout << "Enter element to remove: ";
    std::cin >> removeValue;
    list.remove(removeValue);

    std::cout << "Linked List after removal: ";
    list.display();

    return 0;
}

4. 将两个有序单链表合并为一个有序单链表 (扩展内容)

LinkedList mergeSortedLinkedLists(LinkedList list1, LinkedList list2) {
    LinkedList mergedList;

    Node* curr1 = list1.head;
    Node* curr2 = list2.head;

    while (curr1 != nullptr && curr2 != nullptr) {
        if (curr1->data < curr2->data) {
            mergedList.insert(curr1->data);
            curr1 = curr1->next;
        } else {
            mergedList.insert(curr2->data);
            curr2 = curr2->next;
        }  
    }

    while (curr1 != nullptr) {
        mergedList.insert(curr1->data);
        curr1 = curr1->next;
    }

    while (curr2 != nullptr) {
        mergedList.insert(curr2->data);
        curr2 = curr2->next;
    }

    return mergedList;
}

5. 双链表及循环链表的实现 (扩展内容)

双链表

class Node {
public:
    int data;
    Node* prev;
    Node* next;
};

class DoublyLinkedList {
public:
    Node* head;

    DoublyLinkedList() {
        head = nullptr;
    }

    void insert(int value) {
        Node* newNode = new Node();
        newNode->data = value;
        newNode->prev = nullptr;
        newNode->next = nullptr;

        if (head == nullptr) {
            head = newNode;
        } else {
            Node* curr = head;
            while (curr->next != nullptr) {
                curr = curr->next;
            }
            curr->next = newNode;
            newNode->prev = curr;
        }
    }

    void remove(int value) {
        if (head == nullptr) {
            std::cout << "List is empty" << std::endl;
            return;
        }

        if (head->data == value) {
            Node* temp = head;
            head = head->next;
            if (head != nullptr) {
                head->prev = nullptr;
            }
            delete temp;
            return;
        }

        Node* curr = head;
        while (curr != nullptr && curr->data != value) {
            curr = curr->next;
        }

        if (curr == nullptr) {
            std::cout << "Element not found" << std::endl;
            return;
        }

        curr->prev->next = curr->next;
        if (curr->next != nullptr) {
            curr->next->prev = curr->prev;
        }
        delete curr;
    }

    void display() {
        if (head == nullptr) {
            std::cout << "List is empty" << std::endl;
            return;
        }

        Node* curr = head;
        while (curr != nullptr) {
            std::cout << curr->data << " ";
            curr = curr->next;
        }
        std::cout << std::endl;
    }
};

循环链表

class CircularLinkedList {
public:
    Node* head;

    CircularLinkedList() {
        head = nullptr;
    }

    void insert(int value) {
        Node* newNode = new Node();
        newNode->data = value;
        newNode->prev = nullptr;
        newNode->next = nullptr;

        if (head == nullptr) {
            head = newNode;
            head->next = head;
            head->prev = head;
        } else {
            Node* last = head->prev;
            last->next = newNode;
            newNode->prev = last;
            newNode->next = head;
            head->prev = newNode;
        }
    }

    void remove(int value) {
        if (head == nullptr) {
            std::cout << "List is empty" << std::endl;
            return;
        }

        if (head->data == value) {
            Node* temp = head;
            head->prev->next = head->next;
            head->next->prev = head->prev;
            head = head->next;
            delete temp;
            return;
        }

        Node* curr = head;
        while (curr != nullptr && curr->data != value) {
            curr = curr->next;
        }

        if (curr == nullptr) {
            std::cout << "Element not found" << std::endl;
            return;
        }

        curr->prev->next = curr->next;
        curr->next->prev = curr->prev;
        delete curr;
    }

    void display() {
        if (head == nullptr) {
            std::cout << "List is empty" << std::endl;
            return;
        }

        Node* curr = head;
        do {
            std::cout << curr->data << " ";
            curr = curr->next;
        } while (curr != head);
        std::cout << std::endl;
    }
};

本教程展示了如何使用 C++ 类来创建单链表并实现基本操作，包括创建、遍历、插入、删除和合并两个有序单链表。此外，文章还涵盖了双链表和循环链表的实现原理。希望本教程能够帮助您更好地理解链表数据结构。