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.

• slepic: Is it intended that your list is a global singleton? This was pointed out to you in the previous version review that it is most likely not desired. Do you care? Anyway, no, your implementation is not stable. It has so many bugs that I am tempted to vote to close as not working as intended...
• pacmaninbw: When you post a follow up question, it is best to include a link to the previous question. As @slepic indicated you did not address some of the major issues from the previous question.
• V_head: I will address them and update everything back, thank you or your remarks. Yes, I want to keep the global variables.
• chux: @user21078706 Why does public function node_k() not have protection from iterating past the end of the list?
• V_head: Please see the update, this post is already have been taken as starting point to fix many issues

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.

• V_head: Ah sorry, I forgot to add that my code for now is just really assuming the user to enter only correct data, I agree, I should assert or if else conditionals.

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 21⁄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;
}

• V_head: Yes, prev sometimes get updated sometimes not, because prev doesn't have a particular function like head which should always be pointing to the first node. I believe head usage is consistent.
• greybeard: So what to expect after a call to reverse_sll() and a subsequent one to append_sll_1(13)? (Had I been aware of the 1st iteration of this question, I would have written something different. Or voted to close as not working.)
• V_head: You are right, I will update the code soon.
• greybeard: Please heed What should I not do when someone answers my question?
• V_head: Ok, I will post a separate post. Thanks