Don't understand the error in appending a new item to a Linked List (At Beginning and End)

Question

As mentioned I don't seem to be able to understand the error in my code, what is it that I'm doing wrong in this particular piece of code:

The Node is written as such:

struct Node {
    int data;
    struct Node *link;
};

This is the append to the beginning:

void Shift(struct Node **head, int new_data) {
    struct Node *New;
    
    New = (struct Node *)malloc(sizeof(struct Node));
    if (New == NULL) {
        printf("It is Null\n");
    }
    New->data = new_data;
    New->link = head;
}

This is the append to the end:

void Shift(struct Node *head, int new_data) {
    
    while (head !=  NULL) {
        head = head->link;
    }
    struct Node *New;
    New = (struct Node *)malloc(sizeof(struct Node));
    if (New == NULL) {
        printf("It is Null\n");
    }
    New->link = NULL;
    New->data = new_data;
    

If anyone knows what's up, please tell me what to add and why. Thanks in advance!!

I've looked it up and it said that I had to do head->link = new, but it results in a never ending cascade of number...

Answer 1

There are multiple problems:

• you do not return if memory allocation fails.

• the first version (inserting at the beginning of the list) does not handle head properly: it is a pointer to the head node pointer of the list so New->link must be set to *head and *head must be updated to become the new head: *head = New;.

• the second version skips the nodes until head is a null pointer, causing undefined behavior if you link the new node as its next node. You should instead loop until you have the last node of the list and link the New node as its next node.

• the second version should also take a double pointer struct Node **head so the head of the list can be updated if the list was empty.

Here are modified versions:

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

struct Node {
    int data;
    struct Node *link;
};

void Shift(struct Node **head, int new_data) {
    struct Node *New = malloc(sizeof(struct Node));
    if (New == NULL) {
        printf("Shift: Memory allocation error\n");
        return;
    }
    New->data = new_data;
    New->link = *head;
    *head = New;
}

void Append(struct Node **head, int new_data) {
    struct Node *New = malloc(sizeof(struct Node));
    if (New == NULL) {
        printf("Append: Memory allocation error\n");
        return;
    }
    New->data = new_data;
    New->next = NULL;
    if (*head) {
        struct Node *last = *head;
        while (last->next)
            last = last->next;
        last->next = New;
    } else {
        *head = New;
    }
}

The Append function can be simplified into this more compact version that may be more difficult to understand:

void Append(struct Node **head, int new_data) {
    struct Node *New = malloc(sizeof(struct Node));
    if (New == NULL) {
        printf("Append: Memory allocation error\n");
        return;
    }
    New->data = new_data;
    New->next = NULL;
    while (*head) {
        head = &(*head)->next;
    }
    *head = New;
}