Why start a loop at 2?

Question

While I'm doing an exercise about the linked lists in c, It has a question to insert a new node in the middle of the list. I finished, but then I didn't understand why I had to start at 2.

For example, if I start I = 0
linked list = 1,2,3,4,5
The value I want to insert is 6 at position 2. So I expect my linked list will be = 1,6,2,3,4,5. But the actual output will be 1,2,3,6,4,5.

Here is my code.

void Inserting(Node* head)
{
    int n;
    int i;
    Node* Cur_Node = head;
    Display(Cur_Node);
    Node* NewNode = (Node*)malloc(sizeof(Node));
    NewNode->next == NULL;
    printf("What value your want to add : ");
    scanf("%d",&(NewNode->number));
    if (Cur_Node == NULL && NewNode == NULL)
    {
        return 0;
    }
    printf("Where do you want to put : ");
    scanf("%d",&n);
    for(int i=2; i < n; i++) 
    {
        if(Cur_Node->next != NULL) {
        Cur_Node = Cur_Node->next;
        }
    }
    NewNode->next = Cur_Node->next;
    Cur_Node->next = NewNode;

}

Answer 1

Draw it

The only way to answer these kinds of questions is to get out a piece of paper and a pencil and draw yourself a linked list. Here’s an example:

        ┌───┐   ┌───┐   ┌───┐   
head ──►│ 2 ├──►│ 3 ├──►│ 7 ├──► NULL
        └───┘   └───┘   └───┘   

Suppose you want to create a new node and add it to the list in the 3rd position:

                    ┌───┐
       new_node ──► │ 5 ├──► 
                    └───┘

How would you do that?

        ┌───┐   ┌───┐   ┌───┐   
head ──►│ 2 ├──►│ 3 ├──►│ 7 ├──► NULL
        └───┘   └───┘   └───┘   
                          ▲   
                    ┌───┐ │
       new_node ──► │ 5 ├─┘ 
                    └───┘

Then:

        ┌───┐   ┌───┐   ┌───┐   
head ──►│ 2 ├──►│ 3 │   │ 7 ├──► NULL
        └───┘   └─┬─┘   └───┘   
                  │       ▲   
                  ▼ ┌───┐ │
       new_node  ──►│ 5 ├─┘ 
                    └───┘

Rearranging the picture a little:

        ┌───┐   ┌───┐   ┌───┐   ┌───┐   
head ──►│ 2 ├──►│ 3 ├──►│ 5 ├──►│ 7 ├──► NULL
        └───┘   └───┘   └───┘   └───┘   
                          ▲   
                          │
       new_node ──────────┘ 

Notice how things must work in a specific order?

Why start at 2?

Now, look again at the way we had to insert the node. Which node is the one we must have a pointer to to insert the new node: the one before or the one after the position we want the new node to go?

How do we count down to get to that node?

(What should we do if the count is too large?)

Functions and Input

The purpose of a function is to do a single thing. In this case, your function should not be asking for and getting user input. Its sole purpose should be to update the list by inserting a new node in a specific spot.

Do all the I/O elsewhere, then call the function.

void insert_item_at( int index, int number );

Answer 2

I guess because you are comparing i < n instead of i <= n. The i is not used inside the loop, it is there just for counting the position in the list. You can start at any number that it does not matter, as long you compensate where you finish.

Answer 3

As the loop variable is not used in the loop body, you can do the following if you want the loop to go the the previous to previous n element.

    for (int i = 0; i < n - 2; i++) { ... }

but that will make the compiler to evaluate the expression i < n - 2, that implies two variables and one constant. When you change to this one:

    for (int i = 2; i < n; i++) { ... }

the loop executes exactly the same number of times, but this time the loop test (which is executed once at every iteration) involves only a comparison between two variables only, no addition is executed and probably will run a bit faster than the previous one (also it is probable that the optimization made by the loop writer is also done, behind the scenes, by the compiler optimizer)

Note:

I have not checked if the loop limits are correct for the solution of this problem, but as written, the above loops are both equivalent, when the control variable is indeed not used inside the loop body.