数据结构的的书说链表需要1个特殊的头节点,但是std::list并没有这么一个元素啊!

Ruckus优科

list需要一个所谓的头节点，这个头节点是链表的开始，它指向链表的第一个元素，本身不存储任何东西。这个我能理解。
但是我看std::list并没有一个这么所谓的头节点。

而且，我觉得，知道第一个节点就能访问链表了，这个所谓的头节点好像就是一种多余的存在啊。
求解释

heguangwu

c++ stl库文件可读性不是很好，但理论是不会错的，虽然我也没有看过代码，所谓的头结点其实就是一个指针而已

alwaysR9

头节点存放或者不存放数据都可以，这看实现者自己的定义；
头节点不存放数据可以令一些链表操作更方便，比如删除连表中某个节点x：
假设头节点不存放数据：

p = head;
q = head->next;
while (q) {
        if (q == x) {
                 p->next = q->next;
                 delete x;
                 break;
        }
        p = q;
        q = q->next;
}
return;

如果头节点存放数据，那删除节点的操作需要单独处理头节点：

if (x == head) {
        head = head->next;
        delete x;
        return;
}
p = head;
q = head->next;
while (q) {
        if (q == x) {
                 p->next = q->next;
                 delete x;
                 break;
        }
        p = q;
        q = q->next;
}
return;

不用纠结头节点是否需要存数据，按照自己的想法定义就好

windoze

你看的那是什么数据结构的书啊？链表这种东西都搞得这么复杂？

你有个指针指向第一个节点不就行了，还要什么“特殊的头结点”？

dorodaloo

windoze 发表于 2015-12-03 22:14
你看的那是什么数据结构的书啊？链表这种东西都搞得这么复杂？

你有个指针指向第一个节点不就行了，还要 ...

windoze
是不会错的

action08

head本身是存在内容的，要么为nil
也是个指针

action08

代码语义翻译一下，链表的指针不是用pq
这里数据结构推荐用n next，p previous，代码看起来规范些，当然编译器无所谓

windoze

回复 7# action08

pn……猛一看还以为说三极管……

hanxin83

我也看过类似的说法, 只不过说是"可以有"而不是"需要".
有这个空的头节点, 只是为了避免:
1. 插入节点, 每次都要额外判断一下"链表是不是空".
2. 删除节点, 每次都要额外判断一下"是不是删了头节点".

没有当然也是很好的, 我应届生毕业出来的时候弄个空的头节点还被人说是奇技淫巧呢~~~~