链表(linked_list)的理解以及实现

链表的概念：

链表是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过“引用”相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。 

可以看出：链表物理结构不是连续的

链表与数组：

链表(带头双向循环链表)与数组(顺序表)在功能，结构上的不同：

链表的分类：

类型分类：

• 单链表（Singly Linked List）:

   - 每个节点包含数据和指向下一个节点的指针。

   - 单向链表，只能从表头向表尾遍历。

• 双链表（Doubly Linked List）:

   - 每个节点包含数据和两个指针，分别指向前一个节点和后一个节点。

   - 双向链表，可以从任一节点开始向前或向后遍历。

• 循环链表（Circular Linked List）:

   - 单链表或双链表的变体，最后一个节点的指针指向表头或前一个节点。

   - 循环单链表：最后一个节点指向表头。

   - 循环双链表：最后一个节点的后指针指向表头，表头的前指针指向最后一个节点。

• 双向循环链表（Doubly Circular Linked List）:

   - 双链表的循环版本，第一个节点的前指针和最后一个节点的后指针都指向表头。

• 栈式链表（Stack Implementation Using Linked List）:

   - 使用链表实现的栈，遵循后进先出（LIFO）原则。

   - 通常使用单链表实现，新元素总是添加到链表的头部。

• 队列式链表（Queue Implementation Using Linked List）:

   - 使用链表实现的队列，遵循先进先出（FIFO）原则。

   - 通常使用双链表实现，新元素添加到链表的尾部，移除元素从头部。

• 有序链表（Ordered Linked List）:

   - 链表中的节点按照特定的顺序（如数值大小）进行排序。

• 无序链表（Unordered Linked List）:

   - 链表中的节点没有特定的顺序。

• 动态链表（Dynamic Linked List）:

   - 可以在运行时动态地添加或删除节点。

• 静态链表（Static Linked List）:

    - 节点的数量在创建时就固定了，不能动态地添加或删除节点。

• 哈希链表（Hash Linked List）:

    - 哈希表的实现方式之一，通过链表解决哈希冲突。

• 索引链表（Indexed Linked List）:

    - 链表中包含指向特定节点的索引，可以快速访问链表中的元素。

结构分类：

其中：较为常见的整体结构还是单向，环形，双向连表：

 

链表的结构⾮常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构：

 

• ⽆头单向⾮循环链表：结构简单，⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦结构，如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多
• 带头双向循环链表：结构最复杂，⼀般⽤在单独存储数据。实际中使⽤的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使⽤代码实现以后会发现结构会带来很多优势，实现反⽽简单了

  ---

实现图解：

在实现链表的过程中，主要还是还是数据得插入删除

插入：

删除： 

单链表的实现：

在此主要实现带头单向不循环链表

在这里，带头带的其实就是哨兵位，哨兵位是一种特殊的节点，通常被添加到链表的开始或末尾，以简化某些操作，比如避免对空链表的特殊情况处理。哨兵节点通常不存储有效的数据，或者存储一个默认值

#include <iostream>
#include <stdexcept> // 用于抛出异常
 
// 定义节点模板结构体
template <typename T>
struct Node {
    T data; // 存储数据
    Node<T>* next; // 指向下一个节点的指针
 
    // 构造函数
    Node(T val = T())
        : data(val)
        , next(nullptr)
    {}
};
 
// 定义带头结点的单向不循环链表类
template <typename T>
class LinkedListWithHead {
private:
    Node<T>* head; // 头结点，哨兵节点
 
public:
    // 构造函数
    LinkedListWithHead()
    {
        head = new Node<T>(); // 创建哨兵节点
    }
 
    // 析构函数
    ~LinkedListWithHead()
    {
        Node<T>* current = head->next;
        while (current != nullptr)
        {
            Node<T>* next = current->next;
            delete current;
            current = next;
        }
        delete head; // 释放哨兵节点
    }
 
    // 在链表末尾添加新节点
    void append(const T& value)
    {
        Node<T>* newNode = new Node<T>(value);
        Node<T>* last = head;
        while (last->next != nullptr)
        {
            last = last->next;
        }
        last->next = newNode;
    }
 
    // 在链表头部添加新节点
    void prepend(const T& value)
    {
        Node<T>* newNode = new Node<T>(value);
        newNode->next = head->next;
        head->next = newNode;
    }
 
    // 根据值删除节点
    void remove(const T& value)
    {
        Node<T>* current = head;
        while (current->next != nullptr && current->next->data != value)
        {
            current = current->next;
        }
        if (current->next != nullptr)
        {
            Node<T>* toDelete = current->next;
            current->next = current->next->next;
            delete toDelete;
        }
        else
        {
            throw std::runtime_error("Value not found in the list.");
        }
    }
 
    // 查找节点是否存在
    bool contains(const T& value) const
    {
        Node<T>* current = head->next;
        while (current != nullptr)
        {
            if (current->data == value)
            {
                return true;
            }
            current = current->next;
        }
        return false;
    }
 
    // 打印链表中的所有元素
    void print() const
    {
        Node<T>* current = head->next;
        while (current != nullptr)
        {
            std::cout << current->data << " -> ";
            current = current->next;
        }
        std::cout << "null" << std::endl;
    }
};
 

• remove 方法：删除链表中第一个匹配值的节点。如果找不到该值，则抛出一个 std::runtime_error 异常。
• contains 方法：检查链表中是否存在具有给定值的节点，并返回一个布尔值。

请注意，remove 方法中，我们首先遍历链表直到找到要删除的节点。如果找到，我们将其从链表中移除并释放内存。如果链表中没有该值，我们抛出一个异常。contains 方法则是遍历链表检查是否存在具有给定值的节点。

双向链表的实现：

在此主要实现带头双向循环链表：

实现一个带头结点的双向循环链表涉及到创建一个链表，其中每个节点除了包含数据外，还有两个指针分别指向前一个节点和后一个节点。头结点是一个哨兵节点，它的 next 和 prev 指针都指向链表的第一个实际数据节点，而链表的最后一个数据节点的 next 指向头结点，prev 指向最后一个数据节点自身。

下面是C++模板实现带头结点的双向循环链表的示例代码：

#pragma once
#include <iostream>
#include <stdexcept> // 用于抛出异常
 
// 定义节点模板结构体
template <typename T>
struct Node {
    T data;
    Node<T>* prev;
    Node<T>* next;
 
    // 构造函数，为data提供默认参数值
    Node(T val = T()) : data(val), prev(nullptr), next(nullptr) {}
};
 
// 定义带头结点的双向循环链表类
template <typename T>
class CircularDoublyLinkedList {
private:
    Node<T>* head; // 头结点，哨兵节点
 
public:
    // 构造函数
    CircularDoublyLinkedList() {
        head = new Node<T>(); // 创建哨兵节点
        head->next = head->prev = head; // 哨兵节点形成循环
    }
 
    // 析构函数
    ~CircularDoublyLinkedList() {
        Node<T>* current = head->next;
        while (current != head) {
            Node<T>* temp = current;
            current = current->next;
            delete temp;
        }
        delete head; // 释放哨兵节点
    }
 
    // 在链表末尾添加新节点
    void append(const T& value) {
        Node<T>* newNode = new Node<T>(value);
        newNode->prev = head->prev;
        newNode->next = head;
        head->prev->next = newNode;
        head->prev = newNode;
    }
 
    // 删除链表中的指定节点
    void remove(Node<T>* node) {
        if (node == head) {
            head = head->next; // 哨兵节点指向下一个节点
        }
        node->prev->next = node->next;
        node->next->prev = node->prev;
        delete node;
    }
 
    // 打印链表中的所有元素
    void print() const {
        Node<T>* current = head->next;
        if (head->next == head) {
            std::cout << "List is empty." << std::endl;
            return;
        }
        do {
            std::cout << current->data << " ";
            current = current->next;
        } while (current != head->next);
        std::cout << std::endl;
    }
 
    // 根据值查找节点，如果找到则返回节点指针，否则返回nullptr
    Node<T>* find(const T& value) const {
        Node<T>* current = head->next;
        if (head->next == head) {
            return nullptr; // 链表为空
        }
        do {
            if (current->data == value) return current;
            current = current->next;
        } while (current != head->next);
        return nullptr;
    }
 
    // 根据值删除节点
    void removeByValue(const T& value) {
        Node<T>* nodeToDelete = find(value);
        if (nodeToDelete != nullptr) {
            remove(nodeToDelete);
        }
    }
};
 

在这个实现中，定义了 Node 结构体和 CircularDoublyLinkedList 类。CircularDoublyLinkedList 类包括添加节点到头部和末尾、删除节点、打印链表、查找节点以及根据值删除节点的方法。链表使用哨兵节点简化了头部和末尾的操作。

请注意，remove 方法接受一个 Node 指针作为参数，它将该节点从链表中移除并释放内存。removeByValue 方法使用 find 方法来查找具有给定值的节点，如果找到了就调用 remove 方法来删除它。