链表推前

Question

  void push_front(const dataType &item)
  {
     head=new dnode<dataType> (item,NULL,head);
     if (!empty())
        head->next->prev=head;
     else
        tail=head;
     numItems++;
  }

我这里有一段代码,但我真的不明白,这是什么行head->next->prev=head呢？谁能请解释一下,谢谢

Answer 1

如果列表如下所示:

      ***************
head->*Data:   XXX  *
      *Prev:   NULL *    ***************
      *Next:   --------> * Data:   YYY *
      *************** <----Prev:       *     ***************
                         * Next:   --------> * Data:   ZZZ *
                         ***************<------Prev:       *
                                             * Next:  NULL *
                                             ***************

现在:添加新项目

head = new dnode<dataType> (AAA,NULL,head);


      ***************
head->*Data:   AAA  *
      *Prev:   NULL *    ***************
      *Next:   --------> * Data:   XXX *
      ***************    * Prev:  NULL *     ***************
                         * Next:   --------> * Data:   YYY *
                         ***************<------Prev:       *     ***************
                                             * Next:   --------> * Data:   ZZZ *
                                             ***************<------Prev:       *
                                                                 * Next:  NULL *
                                                                 ***************

注意链中的第二项.Prev成员仍为NULL.
所以要将第二个项目的链接添加回头部.

head->next->prev=head;

      ***************
head->*Data:   AAA  *
      *Prev:   NULL *    ***************
      *Next:   --------> * Data:   XXX *
      ***************<-----Prev:       *     ***************
                         * Next:   --------> * Data:   YYY *
                         ***************<------Prev:       *     ***************
                                             * Next:   --------> * Data:   ZZZ *
                                             ***************<------Prev:       *
                                                                 * Next:  NULL *
                                                                 ***************

所以你可以想到这条线:

    head->next->prev=head;

    // This is equivelant too:

    oldHead       = head->next;
    oldHead->prev = head;