链表介绍

链表是一种数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。链表的基本特性包括：

1. 动态大小：链表的大小可以根据需要动态调整，不像数组那样需要事先定义固定大小。
2. 节点连接：每个节点通过指针连接到下一个节点，从而形成一个链状结构。
3. 灵活插入和删除：在链表中插入和删除节点通常比数组更高效，因为这些操作不需要移动其他元素。

链表的类型

1. 单向链表（Singly Linked List）：每个节点包含一个指针，指向链表中的下一个节点。最后一个节点的指针指向 null，表示链表的结束。

2. 双向链表（Doubly Linked List）：每个节点包含两个指针，一个指向前一个节点，一个指向下一个节点。这样可以在两个方向上遍历链表。

3. 循环链表（Circular Linked List）：链表的最后一个节点指向第一个节点，形成一个循环结构。它可以是单向或双向的。

4. 双向循环链表（Doubly Circular Linked List）：结合了双向链表和循环链表的特性，既可以在两个方向上遍历，又形成了一个循环结构。

链表的基本操作

1. 插入：在链表的任意位置插入新节点。
2. 删除：从链表中删除指定节点。
3. 查找：在链表中查找指定值的节点。
4. 遍历：访问链表中所有节点，通常用来打印或处理数据。
5. 更新：修改链表中某个节点的数据。

C++ 实现链表

下面是一个包含基本操作的链表实现代码：

#include <iostream>

class Node {
public:
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
private:
    Node* head;
public:
    LinkedList() : head(nullptr) {}

    // 插入节点到链表头部
    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 deleteValue(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 traverse() {
        Node* temp = head;
        while (temp) {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        }
        std::cout << "nullptr" << std::endl;
    }

    ~LinkedList() {
        while (head) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }
};

int main() {
    LinkedList list;

    // 插入数据
    list.insertAtHead(1);
    list.insertAtHead(2);
    list.insertAtTail(3);
    list.insertAtTail(4);

    // 遍历链表
    std::cout << "Linked List: ";
    list.traverse();

    // 查找数据
    std::cout << "Searching for 3: " << (list.search(3) ? "Found" : "Not Found") << std::endl;

    // 删除数据
    list.deleteValue(2);
    std::cout << "After deleting 2, Linked List: ";
    list.traverse();

    return 0;
}

代码说明

1. Node 类：定义了链表节点的结构。
2. LinkedList 类：
   • insertAtHead(int val)：在链表头部插入新节点。
   • insertAtTail(int val)：在链表尾部插入新节点。
   • deleteValue(int val)：删除链表中第一个匹配值的节点。
   • search(int val)：查找链表中是否存在指定值的节点。
   • traverse()：遍历并打印链表所有节点的数据。
   • 析构函数~LinkedList()：释放链表占用的内存。

编译代码

使用 C++ 编译器（如 g++）编译这个文件。打开终端或命令提示符，执行以下命令：

g++ -o linked_list linked_list.cpp -o linked_list

指定输出文件的名称为 linked_list。
linked_list.cpp 是你保存的代码文件名。

代码输出结果

Linked List: 2 -> 1 -> 3 -> 4 -> nullptr
Searching for 3: Found
After deleting 2, Linked List: 1 -> 3 -> 4 -> nullptr

链表与其他数据结构的优缺点

优点

1. 动态大小：链表可以动态分配内存，避免了固定大小数组的限制。
2. 高效插入和删除：在链表中插入和删除节点比数组高效（O(1)时间复杂度），特别是在头部或中间位置。
3. 无需预定义大小：链表不需要定义固定的大小，可以根据需要扩展。

缺点

1. 内存开销：每个节点需要额外的指针，导致比数组占用更多的内存。
2. 随机访问困难：链表不支持直接索引，必须从头部开始逐一遍历（O(n)时间复杂度）。
3. 访问速度慢：由于节点分散在内存中，链表的遍历比数组慢。

总结

链表是一种灵活且高效的动态数据结构，适用于需要频繁插入和删除操作的应用场景。尽管它的内存开销和访问速度可能不如数组，但它的动态特性和高效的插入/删除操作使其在某些情况下非常有用。了解链表的基本操作和特性，可以帮助在不同的应用场景中选择合适的数据结构。