Singly linked list optimized for search & insert in O(1)

Question

I have tried to implement my singly linked list to be optimal in the sense that when inserting I don't have to search for the tail and then chain the new node to it, I just keep track of the tail and then insert, resulting in O(1). This is my insert:

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


typedef struct Node {
    int data;               // integer data
    struct Node* next;      // pointer to the next node
} Node;

Node* head = NULL;
Node* prev = NULL;
int count = 0;

void insert_end_sll(int elm) {
    count += 1;
    Node* cur = malloc(sizeof * cur);
    if (!cur) exit(EXIT_FAILURE);
    cur->data = elm;
    cur->next = NULL;
    if (!head) {
        head = cur;
        prev = head;
    }
    else {
        prev->next = cur;
        prev = cur;
    }
}

void print_sll() {
    Node* trav = head;
    while (trav) {
        printf("%d ", trav->data);
        trav = trav->next;
    }
}

int main() {
    insert_end_sll(1);
    insert_end_sll(2);
    insert_end_sll(3);
    print_sll();
    return 0;
}

Do you find any optimization still possible?

Answer 1

General Observations

If the code used calloc() rather than malloc(), there would be no need to initialize next to NULL since the memory returned by calloc() is cleared.

I would recommend separating the creation of the node from the insertion. This is more along the lines of the Single Responsibility Principle. The Single Responsibility Principle states:

that every module, class, or function should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by that module, class or function.

While the program does perform some action if the malloc() fails, it is generally better to provide error messages to the user telling them the program failed.

Node* new_node(int data)
{
    Node* return_value = calloc(1, sizeof(*return_value));
    if (!return_value)
    {
        fprintf(stderr, "malloc of node failed in new_node()\n");
        exit(EXIT_FAILURE);
    }

    return_value->data = data;

    return return_value;
}

There is a well defined set of operations on linked lists:

• Traversal : To traverse all the nodes one after another.
• Insertion : To add a node at the given position.
• Deletion : To delete a node.
• Searching : To search an element(s) by value.
• Updating : To update a node.
• Sorting: To arrange nodes in a linked list in a specific order.
• Merging: To merge two linked lists into one.
  If you implement one, you should implement all. Sometimes insertion and append are implemented as separate functions.

You might want to have a specialized list pointer to point to the head that maintains more information:

typedef struct listhead
{
    unsigned int count;
    Node first;
    Node Last;
} ListHead;

Avoid Global Variables

It is very difficult to read, write, debug and maintain programs that use global variables. Global variables can be modified by any function within the program and therefore require each function to be examined before making changes in the code. In C and C++ global variables impact the namespace and they can cause linking errors if they are defined in multiple files. The answers in this stackoverflow question provide a fuller explanation.

Each operation for the linked list should have a first parameter that is the head of the list.