链表

链表是线性数据结构，其中元素存储在节点中，每个节点包含数据和指向下一个节点的指针/引用。与数组不同，链表元素不存储在连续的内存位置中。

链表提供动态内存分配和高效的插入/删除操作，使其非常适用于数据大小未知或频繁变化的应用程序。

单向链表

单向链表是最简单的类型，其中每个节点都指向序列中的下一个节点：

单向链表实现

#include <iostream>
using namespace std;

// Node structure
struct Node {
    int data;
    Node* next;
    
    Node(int value) : data(value), next(nullptr) {}
};

class LinkedList {
private:
    Node* head;

public:
    LinkedList() : head(nullptr) {}
    
    // Insert at beginning
    void insertAtBeginning(int value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
    }
    
    // Insert at end
    void insertAtEnd(int value) {
        Node* newNode = new Node(value);
        if (head == nullptr) {
            head = newNode;
            return;
        }
        
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
    
    // Delete by value
    void deleteValue(int value) {
        if (head == nullptr) return;
        
        if (head->data == value) {
            Node* temp = head;
            head = head->next;
            delete temp;
            return;
        }
        
        Node* current = head;
        while (current->next != nullptr && current->next->data != value) {
            current = current->next;
        }
        
        if (current->next != nullptr) {
            Node* temp = current->next;
            current->next = current->next->next;
            delete temp;
        }
    }
    
    // Display list
    void display() {
        Node* temp = head;
        while (temp != nullptr) {
            cout << temp->data << " -> ";
            temp = temp->next;
        }
        cout << "NULL" << endl;
    }
    
    // Search for value
    bool search(int value) {
        Node* temp = head;
        while (temp != nullptr) {
            if (temp->data == value) {
                return true;
            }
            temp = temp->next;
        }
        return false;
    }
    
    // Destructor
    ~LinkedList() {
        while (head != nullptr) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }
};

int main() {
    LinkedList list;
    
    // Insert elements
    list.insertAtEnd(10);
    list.insertAtEnd(20);
    list.insertAtEnd(30);
    list.insertAtBeginning(5);
    
    cout << "Linked List: ";
    list.display();
    
    // Search
    cout << "Search 20: " << (list.search(20) ? "Found" : "Not Found") << endl;
    cout << "Search 25: " << (list.search(25) ? "Found" : "Not Found") << endl;
    
    // Delete
    list.deleteValue(20);
    cout << "After deleting 20: ";
    list.display();
    
    return 0;
}

双向链表

双向链表的节点具有指向下一个和上一个节点的指针，允许双向遍历：

双向链表实现

#include <iostream>
using namespace std;

struct DoublyNode {
    int data;
    DoublyNode* next;
    DoublyNode* prev;
    
    DoublyNode(int value) : data(value), next(nullptr), prev(nullptr) {}
};

class DoublyLinkedList {
private:
    DoublyNode* head;
    DoublyNode* tail;

public:
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}
    
    // Insert at beginning
    void insertAtBeginning(int value) {
        DoublyNode* newNode = new DoublyNode(value);
        if (head == nullptr) {
            head = tail = newNode;
        } else {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
    }
    
    // Insert at end
    void insertAtEnd(int value) {
        DoublyNode* newNode = new DoublyNode(value);
        if (tail == nullptr) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
    }
    
    // Display forward
    void displayForward() {
        DoublyNode* temp = head;
        cout << "Forward: ";
        while (temp != nullptr) {
            cout << temp->data << " <-> ";
            temp = temp->next;
        }
        cout << "NULL" << endl;
    }
    
    // Display backward
    void displayBackward() {
        DoublyNode* temp = tail;
        cout << "Backward: ";
        while (temp != nullptr) {
            cout << temp->data << " <-> ";
            temp = temp->prev;
        }
        cout << "NULL" << endl;
    }
    
    // Delete by value
    void deleteValue(int value) {
        DoublyNode* temp = head;
        while (temp != nullptr && temp->data != value) {
            temp = temp->next;
        }
        
        if (temp == nullptr) return; // Value not found
        
        if (temp->prev) {
            temp->prev->next = temp->next;
        } else {
            head = temp->next;
        }
        
        if (temp->next) {
            temp->next->prev = temp->prev;
        } else {
            tail = temp->prev;
        }
        
        delete temp;
    }
    
    ~DoublyLinkedList() {
        while (head != nullptr) {
            DoublyNode* temp = head;
            head = head->next;
            delete temp;
        }
    }
};

int main() {
    DoublyLinkedList list;
    
    list.insertAtEnd(10);
    list.insertAtEnd(20);
    list.insertAtEnd(30);
    list.insertAtBeginning(5);
    
    list.displayForward();
    list.displayBackward();
    
    list.deleteValue(20);
    cout << "After deleting 20:" << endl;
    list.displayForward();
    
    return 0;
}

链表 - C++ 学习中心

链表

单向链表

单向链表实现

双向链表

双向链表实现

优缺点

优点

缺点