Insert a number into a linked list in ascending order

Discussion in 'C++' started by askmatlab@gmail.com, Jan 24, 2007.

  1. Guest

    Hello all:

    I would like to insert a number into a linked list in ascending order.

    Is the following function correct?

    void insert(Node **node, int v)
    {
    Node *tmp = (Node *)malloc(sizeof(Node));
    while(*node && (*node)->value < v) node = &(*node)->next;
    tmp->value = v;
    tmp->next = *node;
    *node = tmp;
    }

    If this is correct, how to answer the following case:

    Given a linked-list as follows:
    NodeA(2) -> NodeB(4) -> NodeC(7) -> NULL.

    Insert 5.

    Then the new linked-list will become as follows if I understand
    correctly.

    NodeA(2) -> NodeB(4) -> NodeC(7) -> NULL
    NodeD(5) -> NodeC(7)


    Please correct me.

    Thank you
    -Daniel
     
    , Jan 24, 2007
    #1
    1. Advertising

  2. wrote:
    > I would like to insert a number into a linked list in ascending order.
    >
    > Is the following function correct?


    Probably not, since you're not getting the right result with it :-/

    >
    > void insert(Node **node, int v)
    > {
    > Node *tmp = (Node *)malloc(sizeof(Node));


    I suggest you *move* 'tmp->value = v;' statement here. And why are
    you usuing 'malloc'? It's so much simpler with 'new':

    Node *tmp = new Node;

    And does your 'Node' class have a constructor? It should, probably.

    > while(*node && (*node)->value < v) node = &(*node)->next;


    > tmp->value = v;
    > tmp->next = *node;


    You're not making the "previous" node in the sequence aware of the
    insertion. It has to be aware if you want your sequence to run
    correctly. (I suppose you have a singly linked list here)

    Node *prev = NULL;
    while (*node && (*node)->value < v) {
    prev = *node;
    node = &(*node)->next;
    }

    if (prev)
    prev->next = tmp;
    tmp->next = *node;

    > *node = tmp;
    > }
    >
    > If this is correct, how to answer the following case:
    >
    > Given a linked-list as follows:
    > NodeA(2) -> NodeB(4) -> NodeC(7) -> NULL.
    >
    > Insert 5.


    What if you insert 1?

    >
    > Then the new linked-list will become as follows if I understand
    > correctly.
    >
    > NodeA(2) -> NodeB(4) -> NodeC(7) -> NULL
    > NodeD(5) -> NodeC(7)
    >
    >
    > Please correct me.


    See above. I didn't test it, though.

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Jan 24, 2007
    #2
    1. Advertising

  3. On Jan 24, 3:44 pm, wrote:
    > Hello all:
    >
    > I would like to insert a number into a linked list in ascending order.
    >
    > Is the following function correct?
    >
    > void insert(Node **node, int v)
    > {
    > Node *tmp = (Node *)malloc(sizeof(Node));
    > while(*node && (*node)->value < v) node = &(*node)->next;
    > tmp->value = v;
    > tmp->next = *node;
    > *node = tmp;
    >
    > }


    Does not seem right, you forgot to attach the new node to the previous
    one.

    Given the follownig:

    struct Node {
    Node* next;
    int value;
    }

    The algorithm would be something like:

    void insert(Node* node, int v) {
    Node* n = new Node; // use malloc if you want
    while (node != 0 && node->next != 0 && node->next->value < v)
    node = node->next;
    n->value = v;
    n->next = node->next;
    node->next = n;
    }

    I think, I have not tried it.

    --
    Erik Wikström
     
    =?iso-8859-1?q?Erik_Wikstr=F6m?=, Jan 24, 2007
    #3
  4. Daniel Guest

    Hello Victor:

    Thank you for your comments and this is the reorganized code:

    This is the new code following your comments:

    void insert(Node **node, int v) {

    Node *tmp = new Node(v);
    Node *prev = NULL;

    while (*node && (*node)->value < v) {
    prev = *node;
    node = &(*node)->next;
    }

    if (prev) // the while loop runs at least once.
    {
    prev->next = tmp;
    tmp->next = *node;
    }
    else // never enter into the while loop
    {
    tmp->next = *node;
    *node = tmp;
    }

    } // end of function insert

    Hopefully, this time it is correct.


    Thank you again:)
     
    Daniel, Jan 24, 2007
    #4
  5. Daniel Guest

    Hello Erik:

    The original code was written by me and I got it somewhere.

    > Given the follownig:
    >
    > struct Node {
    > Node* next;
    > int value;
    >
    > }The algorithm would be something like:
    >
    > void insert(Node* node, int v) {
    > Node* n = new Node; // use malloc if you want
    > while (node != 0 && node->next != 0 && node->next->value < v)
    > node = node->next;
    > n->value = v;
    > n->next = node->next;
    > node->next = n;
    >
    > }I think, I have not tried it.



    This solution doesn't work if you have a linked-list as follows:

    NodeA(7) -> NULL;
    insert 6 to this linked-list.

    Based on your solution, the produced Linked-List will be
    NodeA(7) -> NodeB(6) -> NULL;


    I have posted a new solution and wish it is right.

    Thank you for your comments.
    -Daniel
     
    Daniel, Jan 24, 2007
    #5
  6. Daniel T. Guest

    In article <>,
    wrote:

    > Hello all:
    >
    > I would like to insert a number into a linked list in ascending order.
    >
    > Is the following function correct?
    >
    > void insert(Node **node, int v)
    > {
    > Node *tmp = (Node *)malloc(sizeof(Node));
    > while(*node && (*node)->value < v) node = &(*node)->next;
    > tmp->value = v;
    > tmp->next = *node;
    > *node = tmp;
    > }


    What happened when you tested it? For example, what happens with the
    following main? (You may need to #include <cassert> )

    int main()
    {
    Node* n = 0;
    insert( &n, 2 );
    assert( n->value == 2 );
    assert( n->next == 0 );

    insert( &n, 4 );
    assert( n->value == 2 );
    assert( n->next->value == 4 );
    assert( n->next->next == 0 );

    insert( &n, 7 );
    assert( n->value == 2 );
    assert( n->next->value == 4 );
    assert( n->next->next->value == 7 );
    assert( n->next->next->next == 0 );

    insert( &n, 5 );
    assert( n->value == 2 );
    assert( n->next->value == 4 );
    assert( n->next->next->value == 5 );
    assert( n->next->next->next->value == 7 );
    assert( n->next->next->next->next == 0 );

    }

    > If this is correct, how to answer the following case:
    >
    > Given a linked-list as follows:
    > NodeA(2) -> NodeB(4) -> NodeC(7) -> NULL.
    >
    > Insert 5.
    >
    > Then the new linked-list will become as follows if I understand
    > correctly.
    >
    > NodeA(2) -> NodeB(4) -> NodeC(7) -> NULL
    > NodeD(5) -> NodeC(7)


    You answer it however you think it should be answered. Does the problem
    require the insert function to maintain a sorted list? What should the
    insert function do if the list passed in wasn't sorted in the first
    place?

    Ask your instructor to please show his students how to test their code
    so they will know, before turning it in, if it is correct.

    I've tutored several people going to several different colleges, and it
    always amazes me that not one of the teachers seem to bother teaching
    their students how to test code for conformance to the spec.
     
    Daniel T., Jan 24, 2007
    #6
  7. Daniel T. Guest

    "Victor Bazarov" <> wrote:

    > > If this is correct, how to answer the following case:
    > >
    > > Given a linked-list as follows:
    > > NodeA(2) -> NodeB(4) -> NodeC(7) -> NULL.
    > >
    > > Insert 5.

    >
    > What if you insert 1?


    int main()
    {
    Node* n = 0;
    insert( &n, 4 );
    assert( n->value == 4 );
    assert( n->next == 0 );

    insert( &n, 1 );
    assert( n->value == 1 );
    assert( n->next->value == 4 );
    assert( n->next->next == 0 );
    }

    None of the asserts fire with his original code.

    Granted, the use of malloc in a c++ program is odd, and he would
    probably be better off with some member-functions. However, his initial
    code passed every test I could think of.
     
    Daniel T., Jan 24, 2007
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?Utf-8?B?Sm9l?=
    Replies:
    2
    Views:
    624
    =?Utf-8?B?RGVhc3Vu?=
    Nov 19, 2004
  2. Replies:
    0
    Views:
    301
  3. Replies:
    2
    Views:
    297
  4. PRadyut
    Replies:
    2
    Views:
    490
    Barry Schwarz
    Jun 10, 2005
  5. sudhir
    Replies:
    8
    Views:
    828
    Kenny McCormack
    Dec 6, 2005
Loading...

Share This Page