需要header节点

Question

我们说头链表是由一个叫做头节点的特殊节点组成的链表，它标志着列表的开始，但我不明白这个头节点的真正重要性是什么。请帮帮我?

Answer 1

有了前哨节点，您就不必处理某些边缘情况。

最大的是null检查:您总是知道在列表的顶部会有一个节点，您可以在后面插入节点，所以您不必检查head是否为null。(出于类似的原因，它也有助于拥有一个尾节点)

考虑以下两种情况：

具有头部和尾部节点：

addNewDataAtHead( data ):
    newNode = new Node(data);
    newNode.next = head.next;
    newNode.prev = head;
    head.next.prev = newNode;
    head.next = newNode;

没有：

addNewDataAtHead( data ):
    newNode = new Node(data);
    if (head == null):
        head = newNode;
    newNode.next = head;
    head.prev = newNode;
    head =  newNode;

第一个的意图要清晰得多，因为它就像在其他任何地方插入一样。第二种情况要求您检查是否有特殊情况。

Answer 2

有一种链表，可以极大地简化添加、插入和删除代码，而只需很少的存储空间和最少的遍历列表的额外工作。

这是因为一个空列表看起来像这样：

        +-------+    +-------+
head -> | dummy | -> | dummy | -> null
null <- | head  | <- | tail  | <- tail
        +-------+    +-------+

不用担心是否要追加(或插入)一个空列表，或者删除操作是否会创建一个空列表，这要简单得多。

初始化变得稍微复杂一些，左边是原始的，右边是根据下面的所有代码修改的。这通常不会造成问题，因为列表创建只发生一次，但插入和删除操作却经常发生。

def init ():                            def init ():
    head = null                             head = new node
    tail = null                             tail = new node
                                            head->next = tail
                                            head->prev = null
                                            tail->prev = head
                                            tail->next = null

比较经典的append (insert更复杂，因为您可能需要在head之前、中间或tail之后插入)和简化的append：

def append (node):                      def append (node):
    node->next = null                       node->next = tail
    if head == null:                        node->prev = tail->prev
        head = node                         tail->prev = node
        tail = node
        node->prev = null
    else:
        tail->next = node
        node->prev = tail
        tail = node

删除操作也大大简化了，因为对于经典的链表，有很多检查来确保您不会取消引用空指针：

def delete (node):                      def delete (node):
    if node == head and node == tail:       if node != head and node != tail:
        head = null                             node->prev->next = node->next
        tail = null                             node->next->prev = node->prev
    elsif node == head:                         free node
        head = head->next
        head->prev = null
    elsif node == tail:
        tail = tail->prev
        tail->next = null
    else:
        node->prev->next = node->next
        node->next->prev = node->prev
    free node

当然，用于遍历列表的代码需要排除虚拟节点，但这是一个微不足道的更改：

def traverse (head):                    def traverse (head):
    node = head                             node = head->next
    while node != null:                     while node != tail:
        do something with node                  do something with node
        node = node->next                       node = node->next

就我自己而言，我不太喜欢这样的代码，因为它可能表明人们太懒了，无法理解数据结构和算法是如何工作的。我更喜欢更复杂的代码，因为它显示了一个人可以思考的迹象。在任何情况下，这都是你倾向于只写一次的东西。