adding list items or nodes in linked list

Inserting nodes. First… The code!

#include <iostream>

struct listItem
    {
    //creating a node
    int data;
    struct listItem *next;
    };

//function to insert items
void Insert(listItem *&head, int item)
    {
    listItem **curr = &head; // start at head
    while (*curr != NULL // while there is a node
            && (*curr)->data <= item ) //  and the node goes before the new node
        {
        curr = &(*curr)->next; // get next node
        }
    *curr = new listItem{item, *curr}; // insert the new node
    }

int main()
    {

    listItem * head = NULL; // empty linked list head

    Insert(head, 1); // test insert to empty list
    Insert(head, 0); // insert at head
    Insert(head, 3); // insert at end
    Insert(head, 2); // insert in the middle
    }

I’ve removed all of the unnecessary code to focus on the insertion logic. You should always do this with a stack overflow question. To keep the noise in the question down, create a simple program that illustrates the problem and does nothing else. Read minimal reproducible example for more information and inspiration.

The code is almost self explanatory: Loop through the list until we find where to insert the node and then insert the node, but there are two little tricks.

There’s the head node and there are next nodes. Both do the same job: Point to the next node in the list. Since they have different names, we need different code to deal with them. But what if we could make head and all of the next nodes have the same name? Then they can have the exact same code. That’s curr‘s job. Now it doesn’t matter if curr is head or a next. Most of the function’s code just… goes away. And code that doesn’t exist has no bugs.

The other problem with inserting into a singly linked list if you iterate to the node you need to insert ahead of, you’ve lost track of the node before it. To maintain the linkage you have to have the previous node’s next pointer (or the head). You can maintain a pointer to the previous node, but this doesn’t work with head since there is no head node, so you ruin the first trick and wind up with some nearly duplicated code. But if you abstract away the node and and store the address of head or the next pointer you have two pieces of information in one: The insertion point and the node after the insertion point. With

listItem **curr;

curr points to where we want to place the new node and *curr is the node after it. So

while (*curr != NULL // while there is a node
        && (*curr)->data <= item ) //  and the node goes before the new node
    {
    curr = &(*curr)->next; // get next node
    }

Works through the list until we find either the last node in the list, *curr is NULL, or the data at *curr goes after the node we want to insert, and then

*curr = new listItem{item, *curr};

creates a new node that is linked to the node that goes after and this new node is assigned to the pointer at the insertion point.

*curr, the pointer to the next item in the list, is set to point at a new listItem, just like any other use of new.

The twist is listItem is a very simple data structure and can take advantage of aggregate Initialization to initialize the listItem‘s members. The braces contain the values I want in the new listItem in the order they are declared in the structure. The first member variable, data, is set to item and the second, next, set to the current value of *curr, the next item in the list.

For a tiny instance of time you’ll have *curr and the next of the new listItem pointing at the same listItem then the = operator updates the *curr to point at the newly created listItem instead.

Draw it out on a piece of paper and you’ll see what’s happening.