说明

  • 初学数据结构时,不理解教程中为什么要在链表首部定义一个空数据的头结点,不明白其优缺点,认为可有可无,有时考虑节省内存空间而省略该节点,但是定义头结点是有意义和作用的。
  • 头结点示意图:无头结点
    有头结点

缺点

  • 多定义了一个结点,多占用了一个结点的内存。
  • 改善方式:可以采用linux kernel中的list实现方式(结点中只包含结点指针不包含结点数据),减少头节点的内存占用。

优点

  • 链表(不管是单链表还是双链表)删除或者插入节点时,如果没有头结点,处理有两种情况,以下是删除操作的两种情况:
  1. 操作的对象不是第一个结点,只需要将前一个节点的next 指向后一个节点。
  2. 操作的对象是第一个结点,相对于第一种情况,由于没有前节点,所以不能按照第一种情况的方式处理,需要更改链表的头指针指向下一个节点。
  • 如果有头结点,只存在一种情况:不是第一个结点,因此按照上面第一种情况进行处理就好了,这样代码更通用,处理更简单高效。
  • 以下是无头节点单链表删除节点的示例代码:
//单链表删除结点
void deleteNode(listNode *node){
    listNode *head, *prev, *current;
    
    if (!head){
        return;    
    }
    
    //无头结点则需要额外做如下处理
    if (head == node){
        head = head->next;
        return;
    }
    
    prev = head;
    current = header->next;
    while (current){
        if (current == node){
            prev->next = current->next;
            delete current;
        } else {
            prev = current;
            current = current->next;
        }
    }
}
  • 以上代码看起来有头结点和没头结点的差别不大,但是实际复杂情况下有没有头结点的处理差别会更明显,会导致初次接触者理不清,加上头结点能减轻某些场景下的复杂度,是空间换时间的策略体现。
GitHub 加速计划 / li / linux-dash
10.39 K
1.2 K
下载
A beautiful web dashboard for Linux
最近提交(Master分支:2 个月前 )
186a802e added ecosystem file for PM2 4 年前
5def40a3 Add host customization support for the NodeJS version 4 年前
Logo

旨在为数千万中国开发者提供一个无缝且高效的云端环境,以支持学习、使用和贡献开源项目。

更多推荐