C++如何實現單鏈表

C++如何實現單鏈表

單鏈表（Singly Linked List）是一種常見的數據結構，它由一系列節點組成，每個節點包含數據和指向下一個節點的指針。單鏈表的優點是插入和刪除操作的時間復雜度為O(1)，但訪問元素的時間復雜度為O(n)。本文將介紹如何使用C++實現一個簡單的單鏈表。

1. 單鏈表的基本結構

首先，我們需要定義一個節點結構體，它包含兩個成員：數據域和指針域。數據域用于存儲節點的數據，指針域用于指向下一個節點。

struct Node {
    int data;       // 數據域
    Node* next;     // 指針域，指向下一個節點

    // 構造函數
    Node(int val) : data(val), next(nullptr) {}
};

2. 單鏈表的類定義

接下來，我們定義一個單鏈表類，它包含一個指向鏈表頭節點的指針，并提供一些基本的操作，如插入、刪除、查找等。

class SinglyLinkedList {
private:
    Node* head;  // 指向鏈表頭節點的指針

public:
    // 構造函數
    SinglyLinkedList() : head(nullptr) {}

    // 析構函數
    ~SinglyLinkedList() {
        while (head) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }

    // 在鏈表頭部插入節點
    void insertAtHead(int val) {
        Node* newNode = new Node(val);
        newNode->next = head;
        head = newNode;
    }

    // 在鏈表尾部插入節點
    void insertAtTail(int val) {
        Node* newNode = new Node(val);
        if (!head) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next) {
            temp = temp->next;
        }
        temp->next = newNode;
    }

    // 刪除鏈表中的某個節點
    void deleteNode(int val) {
        if (!head) return;

        // 如果要刪除的是頭節點
        if (head->data == val) {
            Node* temp = head;
            head = head->next;
            delete temp;
            return;
        }

        Node* temp = head;
        while (temp->next && temp->next->data != val) {
            temp = temp->next;
        }

        if (temp->next) {
            Node* nodeToDelete = temp->next;
            temp->next = temp->next->next;
            delete nodeToDelete;
        }
    }

    // 查找鏈表中是否包含某個值
    bool search(int val) {
        Node* temp = head;
        while (temp) {
            if (temp->data == val) {
                return true;
            }
            temp = temp->next;
        }
        return false;
    }

    // 打印鏈表中的所有元素
    void printList() {
        Node* temp = head;
        while (temp) {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        }
        std::cout << "nullptr" << std::endl;
    }
};

3. 單鏈表的操作示例

現在，我們可以使用上面定義的SinglyLinkedList類來創建一個單鏈表，并進行一些基本操作。

int main() {
    SinglyLinkedList list;

    // 在鏈表頭部插入節點
    list.insertAtHead(3);
    list.insertAtHead(2);
    list.insertAtHead(1);

    // 在鏈表尾部插入節點
    list.insertAtTail(4);
    list.insertAtTail(5);

    // 打印鏈表
    list.printList();  // 輸出: 1 -> 2 -> 3 -> 4 -> 5 -> nullptr

    // 刪除節點
    list.deleteNode(3);
    list.printList();  // 輸出: 1 -> 2 -> 4 -> 5 -> nullptr

    // 查找節點
    if (list.search(4)) {
        std::cout << "4 is found in the list." << std::endl;
    } else {
        std::cout << "4 is not found in the list." << std::endl;
    }

    return 0;
}

4. 總結

本文介紹了如何使用C++實現一個簡單的單鏈表。我們首先定義了節點結構體，然后實現了單鏈表類，并提供了插入、刪除、查找和打印等基本操作。通過這些操作，我們可以輕松地管理鏈表中的數據。

單鏈表雖然簡單，但在實際應用中非常有用，特別是在需要頻繁插入和刪除操作的場景中。希望本文能幫助你理解單鏈表的基本概念和實現方法。