singly linked list insertion

This is a discussion on singly linked list insertion within the C++ Programming forums, part of the General Programming Boards category; Please help me understand this code. Thanks. It is trying to do insert in a sorted linked list. void SLList: ...

  1. #1
    Unregistered
    Guest

    Exclamation singly linked list insertion

    Please help me understand this code. Thanks.

    It is trying to do insert in a sorted linked list.

    void SLList: sortedInsert(int element)
    {
    //Find the place to insert

    IntegerNode *p, *q;

    for (p = myHead, q =0; //why do we need q? Don't we already
    //have a null pointer in the last node?
    (p != 0) && (element <= p->data( ); ) //can we omit the update
    //instruction?

    {q= p; //What does it mean? I don't know what
    //would happen in q=p
    p = p->next();
    }
    ...}
    Thank you for being help.

  2. #2
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    p points to the current node.
    q points to the parent node.

    can you omit the increment?

    yes you can.... this is a legal for statement too.... for(;;) {...}

    besides this.... p = p->next(); is the increment. this assigns p to point at the next node.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  3. #3
    Unregistered
    Guest
    Thank you.

    I still don't underestand the role of q here. I think it is used to have a null pointer in the last node. Is this correct?

    Now supppose we don't know how many nodes in this list, will q always equals to 0? What happens when q = p?


    Thanks a lot!

  4. #4
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    in this snippet q isnt used but it could be very useful as it points to the parent node of the current node.
    Code:
    void SLList: sortedInsert(int element) 
    { 
    IntegerNode *Current,*Parent;
    for (Current = myHead, // make current point to head of list
    Parent=NULL; // head of list has no parent. 
    (Current != NULL) // make sure that there is something pointed to
     && (element <= Current->data( ); ) // comparison
    {
    Parent=Current; // now both pointers point to same node... current
    Current = Current->next(); // move onto next node in list.
    }
    }
    now you can find where to insert all you need implement is how to insert. This is where knowing the address of the parent of the current node is necessary.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  5. #5
    Unregistered
    Guest
    Thank you. Your code makes things clear.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with Insertion sort on a single linked list
    By goron350 in forum C++ Programming
    Replies: 4
    Last Post: 07-11-2005, 08:38 PM
  2. reversing a singly linked list
    By galmca in forum C Programming
    Replies: 6
    Last Post: 02-07-2005, 09:25 AM
  3. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 08:27 PM
  4. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21