【C/C++ 数据结构 线性表】 数据结构 解析 链表中哨兵节点(伪节点)的作用

简介: 【C/C++ 数据结构 线性表】 数据结构 解析 链表中哨兵节点(伪节点)的作用

哨兵节点 的作用

哨兵节点(也称为虚拟头节点、哑节点或哨兵)是一个预先创建的节点,通常不用于存储实际数据,而是作为链表的起始点。使用哨兵节点可以简化链表的某些操作,特别是插入和删除。

哨兵节点的主要优点和用途包括:

  1. 简化边界情况:例如,在没有哨兵节点的链表中,向链表的头部插入或从头部删除元素需要特殊处理。但如果有哨兵节点,这些操作就可以与在链表中间的操作统一处理,从而简化代码。
  2. 避免空指针:哨兵节点确保链表永远不为空,这可以减少处理空指针的需要。
  3. 提供统一的插入和删除点:有时,哨兵节点可以包含特定的标记或值,以便在排序链表中进行比较或执行其他操作。
  4. 双向链表中的双哨兵:在双向链表中,可能会有两个哨兵节点:一个在头部,另一个在尾部。这进一步简化了双向链表的操作。

尽管哨兵节点提供了上述优点,但它也会稍微增加链表的内存开销。在实际应用中,选择是否使用哨兵节点取决于具体的需求和设计考虑。

标准库是否有使用此方式?

让我们分别看一下C++标准库的std::list和Qt的QList

  1. std::list:
  • std::list是一个双向链表。在其内部实现中,它确实使用了一个哨兵节点来简化操作。这个哨兵节点使得链表始终是循环的,头部和尾部都连接到这个哨兵节点。这样,插入和删除操作都可以统一处理,不需要特殊处理链表的头部和尾部。
  • 由于这是std::list的内部实现细节,所以这个哨兵节点对用户是不可见的。
  1. QList:
  • QList的实现与std::list不同。QList不是一个链表,而是一个动态数组,类似于std::vector。它在内部使用一个数组来存储元素,并在需要时动态地重新分配内存。
  • 由于QList是基于数组的,所以它不使用哨兵节点。但是,QList有其他的优化和特性,例如隐式共享(copy-on-write)。

总的来说,std::list使用哨兵节点来简化其双向链表的操作,而QList作为一个动态数组并不使用哨兵节点。

std::list的具体实现可能因编译器和版本而异,但我可以为你提供一个简化的实现来说明如何使用哨兵节点。

哨兵节点的具体实现

以下是一个简化的std::list实现,使用哨兵节点:

template <typename T>
class SimpleList {
private:
    struct Node {
        T data;
        Node* prev;
        Node* next;
        Node(const T& d, Node* p = nullptr, Node* n = nullptr) : data(d), prev(p), next(n) {}
    };
    Node* sentinel;  // 哨兵节点
    size_t size;
public:
    SimpleList() : size(0) {
        sentinel = new Node(T());
        sentinel->prev = sentinel;
        sentinel->next = sentinel;
    }
    ~SimpleList() {
        clear();
        delete sentinel;
    }
    void push_back(const T& value) {
        Node* newNode = new Node(value, sentinel->prev, sentinel);
        sentinel->prev->next = newNode;
        sentinel->prev = newNode;
        size++;
    }
    void push_front(const T& value) {
        Node* newNode = new Node(value, sentinel, sentinel->next);
        sentinel->next->prev = newNode;
        sentinel->next = newNode;
        size++;
    }
    void pop_back() {
        if (size == 0) return;
        Node* toDelete = sentinel->prev;
        toDelete->prev->next = sentinel;
        sentinel->prev = toDelete->prev;
        delete toDelete;
        size--;
    }
    void pop_front() {
        if (size == 0) return;
        Node* toDelete = sentinel->next;
        toDelete->next->prev = sentinel;
        sentinel->next = toDelete->next;
        delete toDelete;
        size--;
    }
    void clear() {
        while (size > 0) {
            pop_front();
        }
    }
    // ... 其他成员函数 ...
};

在上述代码中,SimpleList使用一个哨兵节点sentinel,它始终存在并且不存储实际数据。这个哨兵节点使得链表始终是循环的,头部和尾部都连接到这个哨兵节点。这样,插入和删除操作都可以统一处理,不需要特殊处理链表的头部和尾部。

这只是一个简化的实现,真实的std::list实现会更复杂,包括更多的优化和功能。

结语

在我们的编程学习之旅中,理解是我们迈向更高层次的重要一步。然而,掌握新技能、新理念,始终需要时间和坚持。从心理学的角度看,学习往往伴随着不断的试错和调整,这就像是我们的大脑在逐渐优化其解决问题的“算法”。

这就是为什么当我们遇到错误,我们应该将其视为学习和进步的机会,而不仅仅是困扰。通过理解和解决这些问题,我们不仅可以修复当前的代码,更可以提升我们的编程能力,防止在未来的项目中犯相同的错误。

我鼓励大家积极参与进来,不断提升自己的编程技术。无论你是初学者还是有经验的开发者,我希望我的博客能对你的学习之路有所帮助。如果你觉得这篇文章有用,不妨点击收藏,或者留下你的评论分享你的见解和经验,也欢迎你对我博客的内容提出建议和问题。每一次的点赞、评论、分享和关注都是对我的最大支持,也是对我持续分享和创作的动力。

目录
相关文章
|
10天前
|
存储 算法 程序员
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
18 4
|
9天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
9天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
9天前
|
存储 算法 C++
【数据结构与算法】:带你手搓顺序表(C/C++篇)
【数据结构与算法】:带你手搓顺序表(C/C++篇)
|
9天前
|
存储 编译器 程序员
【C++高阶】C++继承学习手册:全面解析继承的各个方面
【C++高阶】C++继承学习手册:全面解析继承的各个方面
14 1
|
9天前
数据结构 链表(第7、8天)
数据结构 链表(第7、8天)
|
12天前
|
存储 C++
C++的list-map链表与映射表
这篇教程介绍了C++中`list`链表和`map`映射表的基本使用。`list`链表可通过`push_front()`、`push_back()`、`pop_front()`和`pop_back()`进行元素的添加和删除,使用迭代器遍历并支持在任意位置插入或删除元素。`map`是一个键值对的集合,元素自动按键值排序,可使用下标操作符或`insert()`函数插入元素,通过迭代器遍历并修改键值对,同时提供`count()`方法统计键值出现次数。教程中包含多个示例代码以帮助理解和学习。
15 2
|
4天前
|
C++ Python
UE C++ 链表
UE C++ 链表
|
5天前
|
编译器 C++
C++对C的改进和拓展\域解析符、形参默认值、函数重载
C++对C的改进和拓展\域解析符、形参默认值、函数重载
5 0
|
7天前
|
存储 算法 Linux
【内核链表】数据结构——深入理解内核链表的概念和操作&笔记
【内核链表】数据结构——深入理解内核链表的概念和操作&笔记

推荐镜像

更多