singly linked list optimally defined over operations in C?

Question

I have implemented my singly linked list in C and I tried to do it with the most efficient code as possible. Is there any place for improvement?

This post is the second version.

First version of this question

Third version of this question

These are the operations I defined:

• append (insert at the end -- 2 versions, with one more efficient O(1))
• prepend (insert at the beginning)
• insert (insert between the head and tail)
• delete (delete nodes)
• swap (swap nodes values)
• clear (delete all nodes)
• print (print elements)
• reverse (reverse elements)
• search (get the index of element if it exists)
• size (get size of the list)
• isEmpty (check if the list is empty)
• rotate (rotate clockwise by k)

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

typedef struct Node {
    int data;             
    struct Node* next;      
} Node;

Node* head = NULL;
Node* prev = NULL;

Node* create_node(int elm) {
    Node* node = malloc(sizeof * node);
    if (!node) exit(EXIT_FAILURE);
    node->data = elm;
    node->next = NULL;
    return node;
}

Node* node_k(int i) {
    int k = 0;
    Node* node = head;
    while (k != i) {
        k += 1;
        node = node->next;
    }
    return node;
}

void append_sll_1(int elm) { //O(1)
    Node* cur = create_node(elm);
    if (!head) {
        head = cur;
        prev = head;
    }
    else {
        prev->next = cur;
        prev = cur;
    }
}

void append_sll_2(int elm) { //O(n)
    Node* temp = create_node(elm);
    if (!head) {
        head = temp;
    }
    else {
        Node* last = head;
        while (last->next != NULL) {
            last = last->next;
        }
        last->next = temp;

    }
}

void prepend(int elm) {
    Node* updated_head = create_node(elm);
    if (!head) {
        head = updated_head;
    }
    else {
        updated_head->next = head;
        head = updated_head;
    }
}

void insert_sll(int elm, int i) {
    int k = 1; // we don't prepend, so K > 0
    Node* cur = create_node(elm);
    if (!head) {
        head = cur;
    }
    else {
        Node* last = head;
        while (k != i - 1) { //  1 < i < n | 1:prepend, n:append
            k += 1;
            last = last->next;
        }
        cur->next = last->next;
        last->next = cur;
    }
}

void delete_sll(int elm) {
    Node* node = head;
    if (head->data == elm) {
        head = head->next;
        free(node);
    }
    else {
        while (node->data != elm) {
            prev = node;
            node = node->next;
        }
        prev->next = node->next;
        free(node);
    }
}

int is_empty_sll() { //O(1)
    return head == NULL;
}

int size_sll() { //O(n) 
    int count = 0;
    Node* last = head;
    while (last) {
        count += 1;
        last = last->next;
    }
    return count;
}

int search_sll(int elm) { //O(n)
    int i = 0;
    Node* last = head;
    while (last->data != elm) {
        i += 1;
        last = last->next;
    }
    return i;
}

void swap_sll(int i, int j) {//O(n) --swap value of position i with j
    Node* node_i = node_k(i);
    Node* node_j = node_k(j);
    int temp = node_i->data;
    node_i->data = node_j->data;
    node_j->data = temp;
}

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

void reverse_sll() {
    prev = head;
    Node* cur = head->next;
    Node* next_node = cur;
    while (next_node) {
        next_node = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next_node;
    }
    head->next = next_node;
    head = prev;
}

void clear_sll() { //O(n)
    while (head) {
        Node* temp = head;
        head = head->next;
        free(temp);
    }
    printf("List Cleared!\n");
}

void rotate_sll(int k) {
    int size = size_sll();
    Node* tail = head;
    while (tail->next != NULL) {
        tail = tail->next;
    }
    tail->next = head;
    Node* k_node = node_k(k);

    for (int i = 0; i < size; i++) {
        printf("%d ", k_node->data);
        k_node = k_node->next;
    }
}

// void sort_sll() {//

// }

int main() {
    append_sll_1(1);
    append_sll_1(2);
    append_sll_1(4);
    insert_sll(3, 3);
    prepend(0);
    print_sll();
    printf("size: %d\n", size_sll());
    printf("index of 3 is: %d\n", search_sll(3));
    delete_sll(2);
    print_sll();
    swap_sll(0, 1);
    print_sll();
    reverse_sll();
    print_sll();
    clear_sll();
    print_sll();
    return 0;
}

Do you have any improvement ideas? I tried to make it as simple and code friendly as possible for future learners, it would help if you find it a stable implementation to upvote it. There are many implementations online, and many of them are just very confusing to follow, whereas this one, you can just take a paper and pen, and everything becomes clear in front of your eyes.

Answer 1

node_k(int i) {
    int k = 0;
    Node* node = head;
    while (k != i) {
        k += 1;
        ...

This is a curious approach.

From the identifier I infer we want the K-th node. Yet the public API's signature talks about i instead. Recommend you dispense with i and just use k-- until it hits zero.

That is to say, what appears in the signature is part of the Public API, and what we say there matters.

---

void append_sll_1 ...
void append_sll_2 ...

You really need to spell out the pros and cons of these two approaches. When would the O(n) version be better than the O(1) access version?

---

In node_k and insert_sll you have termination criteria that just seem kind of reckless, such as this

        while (k != i - 1) {

You are making very strong assumptions about the input value i, without validating it. On a 32-bit machine you might go through 4 billion iterations before exiting (or null deref). On a 64-bit machine, substantially longer. At least give us an assert.

---

void delete_sll(int elm) {
        ...
        while (node->data != elm) {

How could this possibly be correct? Suppose the element does not appear in the singly linked list? What do we expect all those node dereferences will result in?

Similarly for search_sll and node_k.

Do we even have unit tests for these functions??

---

I like the simplicity of swap_sll, but I will just point out that we have an opportunity to compare the magnitude of i and j, and start chasing pointers a bit further into it. Big-oh complexity will still be the same, for random i, j less than n. I suppose we're relying on L1 cache to save us, here.

---

In main we find some code that is apparently trying to achieve good code coverage. This is nice, but it would be more useful if it was a self-evaluating unit test. That is, the test suite should be able to evaluate that the correct answer was produced and that invariants continue to be preserved. As written, it appears we are trying to establish that we never core dumped.

---

Overall?

There is a paucity of documentation for the public API. Exceptional conditions are not called out.

I am willing to believe that this codebase probably implements certain operations correctly, subject to caller contracts. It impresses me as risky code, given that

1. The human readable documentation does not spell out the contracts, and
2. There is no error checking for preconditions being met.

I would not be willing to accept or delegate maintenance tasks for this code base.

Answer 2

Most difficult to recover from is the lack of documentation:
What exactly is required behaviour?
(Try to define that for insert_sll(int elm, int i):
Insert before or after? What if the list was shorter? What if i is negative?)
You may want to "protect" functions granting access to Nodes, as these compromise structural integrity.

implemented my singly linked list is precise in using singular:
You can have exactly one list, key identical to payload.

While C doesn't support object oriented coding, that should not keep you from OO modelling, and implementing accordingly:
Define a list type, have it keep a key comparison function (int equality above).

The handling of head is inconsistent:
Sometimes empty list does get handled, sometimes not, starting with node_k().

The handling of prev is inconsistent:
Sometimes it does get updated, sometimes not.

reverse_sll() leaves prev equal to head.
[contrary to my previous statement clear_sll() does set head to NULL.]
rotate_sll() leaves the list circular: the next operation may take a long time.

node_k() and prepend() aren't decorated with _sll:
While I don't think the intention is for node_k() not to be part of the API, you could exclude a static Node *prepend().

Out of 5 conditional statements, all branches of 2½ begin or end the same:
Don't Repeat Yourself.

/** append an allocated Node containing elm.*/
void append_sll_1(int elm) { //O(1)
    Node* cur = create_node(elm);
    if (!head) {
        head = cur;
    }
    else {
        prev->next = cur;
    }
    prev = cur;
}

/** prepend an allocated Node containing elm. */
void prepend(int elm) {
    Node* updated_head = create_node(elm);
    if (head) {                    /* could as well be unconditional */
        updated_head->next = head;
    }
    head = updated_head;
}