需要头节点

Question

我们说一个头链表是由一个称为头节点的特殊节点组成的，它标记了列表的开始，但我不明白这个头节点的真正重要性。 请帮我吗？

Answer 1

哨兵节点阻止你处理某些边缘情况。

最大的是空检查：你总是知道在列表顶部会有一个节点可以插入节点，所以你不必处理检查head是否为空。 （也可以帮助有类似的原因，尾节点）

考虑两种情况：

有了头和尾节点：

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 

比较经典的追加（插入变得更为复杂，因为你可能需要head之前插入，在中间，或tail后）与简化的一个：

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 

The co德遍历列表需要排除当然，虚拟节点，但这是一个微不足道的变化：

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 

---

我自己，我不是这样的代码的大风扇，因为它可能表明人们都懒得了解数据结构和算法是如何工作的。我宁愿拥有更复杂的代码，因为它表明人们可以思考问题。无论如何，这只是你一次只写的东西。