CODEWITHSUNDEEP
c++
chris
chris

Reputation:

linked list push front

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

I have a piece of code here, however I don't really understand it, what is the line head->next->prev=head do ? could anyone please explain, thanks

Upvotes: 0

Views: 3528

Answers (2)

Loki Astari
Loki Astari

Reputation: 264551

If the list looks like this:

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

Now: Add the new item

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 *
                                                                 ***************

Notice the second item in the chain. The Prev member is still NULL.
So to add the link from the second item back to the head.

head->next->prev=head;

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

So you can think of the line:

    head->next->prev=head;

    // This is equivelant too:

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

Upvotes: 13

Alex Martelli
Alex Martelli

Reputation: 882083

Presumably head=new dnode<dataType> (item,NULL,head); set the new head->next to the previous head, so head->next->prev=head; is fixing the prev field of said previous head (was previously NULL, is now the hew head).

Upvotes: 1

Related Questions