Thread: Two Question About Inserting Node In the Linked List

  1. #1
    Registered User
    Join Date
    Jul 2012
    Location
    Ankara
    Posts
    52

    Two Question About Inserting Node In the Linked List

    When I tried to build the following code, although the compiler didn't give an error or a warning, I met with the following picture:

    Two Question About Inserting Node In the Linked List-1-png

    Then, I noticed that in the book, there is a newline character(\n) inside the function scanf as follows:

    Code:
    scanf("\n%c",&item);              // QUESTION 1
    Because I didn't write '\n' inside the function scanf, I met above picture. But why? I don't understand that the work is done by '\n' inside the function scanf. Can you explain this situtation?


    *****************************************(1)


    The other thing that I don't understand that the process of adding node. Normally if we first add character B, then if we secondly add character A, we see that;

    (Shortly after the function insert)

    Two Question About Inserting Node In the Linked List-b-png

    ---------------------------

    Then if we add character C, does it have to be in this manner:

    (Shortly after the function insert)

    Two Question About Inserting Node In the Linked List-c-png


    So does it have to be output the following:
    (1) A -- > C -- > B -- > NULL

    But, when program runs, The output is in this way:
    (2) A -- > B -- > C -- > NULL

    I think it mustn't be as above figure (2). It must be figure (1). Because, in the code there are no parts of code about adding to last of list. There are just parts of code about adding new node at beginning of list, and adding new node between previousPtr and currentPtr. I focused the while statement in the function insert, but result in my head didn't change. If you want to see my processing steps as above picture, look at the next my post here.(At DOWN)


    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    
    struct listNode{
        char data;
        struct listNode *nextPtr;
    };
    
    
    typedef struct listNode ListNode;
    typedef ListNode* ListNodePtr;
    
    
    void insert(ListNodePtr *sPtr,char value);
    void instructions(void);
    void printList(ListNodePtr currentPtr);
    
    
    int main()
    {
        ListNodePtr startPtr=NULL;
        char item;
        int choice;
    
    
        instructions();
        printf("> ");
        scanf("%d",&choice);
    
    
        while(choice != 2){
            switch(choice){
                case 1:
                    printf("Enter a character: ");
                    scanf("\n%c",&item);              // QUESTION 1
                    insert(&startPtr,item);
                    printList(startPtr);
                    break;
                default:
                    printf("\nIncorrect choice.\n");
                    instructions();
                    break;
            }
            printf("> ");
            scanf("%d",&choice);
        }
        printf("End of run.\n");
        return 0;
    }
    
    
    void insert(ListNodePtr *sPtr,char value)
    {
        ListNodePtr newPtr,currentPtr,previousPtr;
    
    
        newPtr = malloc(sizeof(ListNode));
    
    
        if(newPtr != NULL) {
            newPtr->data = value;
            newPtr->nextPtr=NULL;
    
    
            previousPtr = NULL;
            currentPtr = *sPtr;
    
    
            while(currentPtr != NULL && value > currentPtr->data) { 
                previousPtr = currentPtr;
                currentPtr = currentPtr->nextPtr;
            }
    
    
            if(previousPtr == NULL){
                newPtr->nextPtr = *sPtr;
                *sPtr = newPtr;
            }
            else {
                previousPtr->nextPtr = newPtr;
                newPtr->nextPtr = currentPtr;
            }
        }
        else{
            printf("%c not inserted. No memory available.\n",value);
        }
    }
    
    
    void printList(ListNodePtr currentPtr)
    {
        if(currentPtr == NULL){
            printf("List is empty.\n\n");
        }
        else {
            printf("The list is:\n");
    
    
            while(currentPtr != NULL){
                printf("%c --> ",currentPtr->data);
                currentPtr = currentPtr->nextPtr;
            }
            printf("NULL\n\n");
        }
    }
    
    
    void instructions(void)
    {
        printf("\nEnter a choice :\n"
               "1 - Insert an element into the list.\n"
               "2 - End of run.\n");
    }
    *****************************************(2)

  2. #2
    Registered User
    Join Date
    Jul 2012
    Location
    Ankara
    Posts
    52
    step 1:
    Two Question About Inserting Node In the Linked List-step-1-png



    step 2:
    Two Question About Inserting Node In the Linked List-step-2-png



    step 3:
    Two Question About Inserting Node In the Linked List-step-3-b-png
    Two Question About Inserting Node In the Linked List-step-3-c-png

    *****************************************(3)

  3. #3
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    With scanf maybe it has to do with the input buffer but i am not aware of that.

    As for the inserting.When we have a single-linked list it is common to insert a node at the start of the list or at the end of the list.Now if you want the list to be sorted,then yuo have to modify the insert function in order to achieve that.
    What i mean is that is someone uses only the insert at end function and be given the input C,A,B,A then the list is like this
    Code:
    C-->A-->B-->A-->NULL
    if you use only the insert at start philosophy then the link is like this
    Code:
    A-->B-->A-->C-->NULL
    Then if you want the list to be sorted-as in li(whether you use the insertAtStart or the insertAtEnd or both) then the list would be like this
    Code:
    A-->A-->B-->C-->NULL

  4. #4
    Registered User
    Join Date
    Jul 2012
    Location
    Ankara
    Posts
    52
    With scanf maybe it has to do with the input buffer but i am not aware of that.
    Ok.

    Code:
    void insert(ListNodePtr *sPtr,char value){
        ListNodePtr newPtr,currentPtr,previousPtr;
    
    
    
    
        newPtr = malloc(sizeof(ListNode));
    
    
    
    
        if(newPtr != NULL) {
            newPtr->data = value;
            newPtr->nextPtr=NULL;
    
    
    
    
            previousPtr = NULL;
            currentPtr = *sPtr;
    
    
    
    
            while(currentPtr != NULL && value > currentPtr->data) { 
                previousPtr = currentPtr;
                currentPtr = currentPtr->nextPtr;
            }
    
    
    
    
            if(previousPtr == NULL){
                newPtr->nextPtr = *sPtr;
                *sPtr = newPtr;
            }
            else {
                previousPtr->nextPtr = newPtr;
                newPtr->nextPtr = currentPtr;
            }
        }
        else{
            printf("%c not inserted. No memory available.\n",value);
        }
    }
    When I compile in my head above the codes which I shared, I can't get the correct order of the book says: A->B->C->NULL.
    I get that: A->C->B->NULL. So I showed how I compiled in my head with above pictures in my previous post. Then, what step did I make a mistake that I found A->C->B->NULL?
    Two Question About Inserting Node In the Linked List

  5. #5
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Note that it is usually extremely inefficient to insert at the end of a single linked list unless you are maintaining a pointer to the end of the list. Otherwise, you iterate over the whole list every time you want to insert which is pretty terrible.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  6. #6
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    @hefese i run your code and gave input B A C and got A->B->C->NULL.Maybe i did not understand well with what input you have trouble.

    @claudiu. It is true that the complexity of search is O(n) in a single linked list.However if it does not make much difference if you insert at start or at end.What i am trying to say is that the complexity of search still remains bad,except of the case that you want to access the last nodes of your list

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by std10093
    However if it does not make much difference if you insert at start or at end.
    It does make a big difference since inserting at the start does not require the traversal of the linked list, whereas inserting at the end does (unless you maintain a pointer to the end, as was already noted).
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Quote Originally Posted by laserlight View Post
    It does make a big difference since inserting at the start does not require the traversal of the linked list, whereas inserting at the end does (unless you maintain a pointer to the end, as was already noted).
    I meant for the search function.I agree for the insert function (did not realize that claudiu was reffering to this)

  9. #9
    Registered User
    Join Date
    Jul 2012
    Location
    Ankara
    Posts
    52
    @claduia
    I guess I understand you say, but I couldn't relate my problem.

    @std10093
    The code is run smoothly. But when I consider the code, I see that the output should be A->C->B->NULL. But the output is A->B->C->NULL as you say and as the book says.

    I showed with pictures in my previous post how I get the output imaginary from my head. Where is the problem that compilation imaginary from my head?

    Quote Originally Posted by hefese View Post
    step 1:
    Two Question About Inserting Node In the Linked List-step-1-png



    step 2:
    Two Question About Inserting Node In the Linked List-step-2-png



    step 3:
    Two Question About Inserting Node In the Linked List-step-3-b-png
    Two Question About Inserting Node In the Linked List-step-3-c-png

    *****************************************(3)
    The output which compilation imaginary from my head is A->C->B->NULL
    Last edited by hefese; 08-07-2012 at 10:20 AM.

  10. #10
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Your imagination fails at step 3.Let's see why
    a-correct
    b-the while loop in line 25 of function insert moves the pointer a little different of what you said.
    • We are immetediately after a on step 3.So the condition of while is true,because currentPtr points to starting node(with A as data).Then the value(C) is > than the data of current node(A) so the condition is true.Inside the body of the loop,prevPtr points to where currentPtr points,thus prevPtr points to node A,and currentPtr points to the next node of A,which is B.End of body loop.
    • Check the condition again.True it is,because currentPtr points to B,and value (C) is greater than the data of current node(B).So enter the body loop.Move prevPtr to point to where currentPtr points,thus prevPtr points to B.Then move currentPtr to point to the next node of B.But be has no next node,so currentPtr points to NULL.End of body loop.
    • prevPtr point to B,not to NULL,so we go to the else in line 37,and now the nextPtr of where the prevPtr points to will be linked(will be pointing to ) where the newPtr points to.In other words node's B link is going to be attached at node C(the new node).Then the link of where newPtr points to(this is node C) is going to point where currentPtr points to,which is NULL(this step is not necessary at this point)


    If questions,ask !

  11. #11
    Registered User
    Join Date
    Jul 2012
    Location
    Ankara
    Posts
    52
    No, I don't have a question more. I understand that you write. It's clear that even if I focused while statement, nevertheless I didn't examine well. Thank you for your reply, taking the time.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. A question about node deletion in a linked list
    By nonlinearly in forum C Programming
    Replies: 2
    Last Post: 11-16-2011, 03:19 AM
  2. problem inserting node in middle of list
    By c_weed in forum C++ Programming
    Replies: 3
    Last Post: 12-22-2010, 09:14 PM
  3. Replies: 7
    Last Post: 11-04-2010, 01:18 PM
  4. Linked List, node creation question
    By Alec0905 in forum C++ Programming
    Replies: 5
    Last Post: 10-03-2010, 09:45 AM
  5. Replies: 3
    Last Post: 12-06-2008, 07:54 PM

Tags for this Thread