How to insert a new node in a singly linked list without using a temporary node?

Question

I just started to learn Data Structures and have been trying to implement a simple singly linked list in C going step by step. I have been following an online tutorial and while showing how to insert a node to the beginning of the list, it used double asterisks in the function parameters which I couldn't understand and the tutorial didn't explain in detail.

I then worked around this and implemented the function without double pointers (by using a temp node), but I would love to understand and learn how the implementation I saw worked and how I implement it myself.

I taught myself about pointers fairly recently so I cannot say that I'm comfortable with them. Actually that's one of the reasons for why I have started learning Data Structures, to practice them more. I normally understand how dereferencing a pointer works, but in this context I am not sure how and with what purpose it's been used in the function header.

I would be so grateful if you could explain the way the function below works.

Here is the function that I couldn't quite get. (source)

void push(node_t ** head, int val) {
    node_t * new_node;
    new_node = malloc(sizeof(node_t));

    new_node->val = val;
    new_node->next = *head;
    *head = new_node;
}

And here is my implementation:

/*
// Singly Linked List Implementation
// 2018/01/10
*/

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
        int val;
        struct node *next;
    } node_t;

void addNodeBegin (node_t *head, int val);
void addNodeEnd (node_t *head, int val);
void printLinkedList();
void freeList(struct node* head);

int main(void) {

    node_t *head = NULL;
    head = malloc(sizeof(node_t));

    if (head == NULL) { return 1; }

    head->val = 1;
    head->next = NULL;

    head->next = malloc(sizeof(node_t));
    head->next->val = 2;
    head->next->next = NULL;

    addNodeEnd(head, 5);
    addNodeBegin(head, 10);
    printLinkedList(head);

    freeList(head);

}

// Insert a node to the beginning of the linked list
void addNodeBegin (node_t *head, int val) {
    node_t *newNode = NULL;
    newNode = malloc(sizeof(node_t));
    newNode->val = val;

    newNode->next = head->next;
    head->next = newNode;

    node_t *tmp = NULL;
    tmp = malloc(sizeof(node_t));

    tmp->val = head->val;
    head->val = newNode->val;
    head->next->val = tmp->val;

    free(tmp);

}

// Insert a node to the end of the linked list
void addNodeEnd (node_t *head, int val) {
    node_t *current = head;

    while (current->next != NULL) {
        current = current->next;
    }

    current->next = malloc(sizeof(node_t));
    current->next->val = val;
    current->next->next = NULL;

}

// Print the linked list
void printLinkedList(node_t *head) {
    node_t *current = head;

    while (current != NULL) {
        printf("%d\n", current->val);
        current = current->next;
    }
}

// Remove the list (and free the occupied memory)
void freeList(struct node* head) {
   struct node* tmp;

   while (head != NULL) {
       tmp = head;
       head = head->next;
       free(tmp);
    }
}

Answer 1

Well, the simplest way of not doing something is not to do it.

Tracing what the values of things are through your implementation:

// Insert a node to the beginning of the linked list
void addNodeBegin (node_t *head, int val) { // assume head = [val1, ...]
    node_t *newNode = NULL;
    newNode = malloc(sizeof(node_t));
    newNode->val = val;                     // newNode=[val, null]

    newNode->next = head->next;             // newNode=[val, ...]
    head->next = newNode;                   // head = [val1, [val, ...]]

    node_t *tmp = NULL;
    tmp = malloc(sizeof(node_t));

    tmp->val = head->val;                   // tmp = [val1, undefined]
    head->val = newNode->val;               // head = [val, [val, ...]]
    head->next->val = tmp->val;             // head = [val, [val1, ...]]

    free(tmp);

}

Firstly, the only thing temp is doing is storing a copy of head->val, so you could store the value directly instead by setting newNode->val before overwriting head->val:

// Insert a node to the beginning of the linked list
void addNodeBegin (node_t *head, int val) { // assume head = [val1, ...]
    node_t *newNode = malloc(sizeof(node_t)); // no need to set to NULL first
    newNode->val = head->val;               // newNode=[val1, undefined]
    newNode->next = head->next;             // newNode=[val1, ...]
    head->next = newNode;                   // head = [val1, [val1, ...]]
    head->val = val;                        // head = [val, [val1, ...]]
}

Secondly, this is doing something different to adding a node at the beginning of a list. It is inserting a node after the beginning, then swapping the values between the first and second nodes. This will matter as very commonly singly linked lists have multiple heads, either for performance reasons or to implement specific algorithms, so operations shouldn't change the tail of the list when they prepend to it. It also means you have to have two different operations - appending to an empty list (NULL) and appending to a non-empty list.

The example implementation of push() takes a pointer to the pointer to the head of the list, creates a new node and mutates that pointer to point to the new node. This seems harder to use than necessary, as it requires taking the address of the pointer to the head.

node_t* head = NULL;

push ( &head, 1 );
push ( &head, 2 );
push ( &head, 3 );
push ( &head, 4 );

node_t* head2 = head;

push ( &head2, 5 );

Personally I'd just return the pointer to the new node:

node_t* cons (int val, node_t* next) {
    node_t * new_node = malloc(sizeof(node_t));

    new_node->val = val;
    new_node->next = next;

    return new_node;
}

node_t* head = cons(4, cons(3, cons(2, cons(1, NULL))));
node_t* head2 = cons(5, head); 

'Cons' is short for construct, a traditional name for the construction of singly linked lists in this manner.