Simple singly linked list implementation in C

Question

I have implemented a LinkedList with the ability to add, get elements from a particular position and ability to show all the elements in the array in to the console (main purpose to implement this was to ensure that all the elements are being populated in the LinkedList correctly).

I would highly appreciate comments based on:

• The efficiency of my code
• Conceptual misinterpretations of a linked list, if any
• Violations of best practices
• Better way of achieving this

This is the code I have written:

#include <stdio.h>
#include <stdlib.h>
struct Element {
 int value;
 struct Element *nextElement;
};
struct LinkedList {
 struct Element *firstElement; 
};
void add(struct LinkedList *list, int value) {
 if(list->firstElement == NULL) {
 struct Element *newElement;
 newElement = malloc(sizeof(struct Element));
 newElement->value = value;
 newElement->nextElement = NULL;
 list->firstElement = newElement;
 } else {
 struct Element *lastElement;
 lastElement = list->firstElement;
 while(lastElement->nextElement != NULL) {
 lastElement = lastElement->nextElement; 
 }
 struct Element *newElement;
 newElement = malloc(sizeof(struct Element));
 newElement->value = value;
 newElement->nextElement = NULL;
 lastElement->nextElement = newElement;
 }
}
int getElement(struct LinkedList *list, int index) {
 int iteratedIndex = 0;
 int returnValue = 0;
 struct Element *temporaryElement = list->firstElement;
 while(temporaryElement != NULL) {
 if(iteratedIndex == index) {
 returnValue = temporaryElement->value;
 return returnValue;
 }
 iteratedIndex = iteratedIndex + 1;
 temporaryElement = temporaryElement->nextElement;
 }
 return 0;
}
void showAllElements(struct LinkedList *list) {
 struct Element *lastElement = list->firstElement;
 while(lastElement != NULL) {
 printf("%d\n", lastElement->value);
 lastElement = lastElement->nextElement;
 }
}
int main()
{
 struct LinkedList list = {NULL};
 add(&list, 5);
 add(&list, 10);
 add(&list, 15);
 showAllElements(&list);
 int value = getElement(&list, 0);
 printf("%d\n", value);
 return 0; 
}

Here's the output I got:

5
10
15
5

Which is correct, first three listing all the elements in the LinkedList and last one fetching the element in the 0th index.

Answer 1

Well, you have consistent indentation and your code compiles and runs cleanly as C99+ (not C90), that's a good start.

So, the data-types:

• Consider adding typedef-names equal to the struct tags. Makes it more pleasant to work with.
• LinkedList is just an Element*, so making it a typedef instead of its own struct-type should be preferred.
• Putting nextElement first is probably slightly more efficient. And it's certainly more common.
• Your names are curious. Call it Node and List, to be consistent with common usage, and the elements of a Node would be next and value (or data).
• Consider giving your list-functions a common prefix (C's alternative to C++ namespaces).

typedef struct Node {
 struct Node* next;
 int value;
} Node;
typedef node* List;

Let's move on to add, which is far too complicated.

• A single Node** simplifies things enormously.
• I also used a compound-literal for more comfortable initialization
• And you have to do something if allocation fails.
• Don't use sizeof with a type, use it with the appropriate expression. That's more resilient to change and less error-prone.

void add(List* head, int value) {
 while(*head)
 head = &head[0]->next;
 *head = malloc(sizeof **head);
 if(!*head) abort();
 **head = (Node){0, value};
}

Going to getElement:

• What's returnValue for, aside from additional typing?
• The other temporary can also be usefully eliminated.
• Not sure returning 0 for too-high indices is that good an idea, but one can do it.
• It's returning the value of an element, not the element itself.

int getValue(List* head, int index) {
 Node* node = *head;
 while(index && node)
 node = node->next, --index;
 return node ? node->value : 0;
}

showAllElements is the perfect place for a for-loop, so let's use that:

void showAllElements(List* head) {
 for(Node* p = *head; p; p = p->next)
 printf("%d\n", p->value);
}

return 0; is implicit in C99+ for main.

---

As a general point, either avoid adding things unto the end of your list instead of the front, take advantage of easy linear-time constant-space list-reversal, or manage an additional pointer to the last node.

See it working on coliru.

• codez: What is C99, C90? Also, can you please explain the code in a bit more detailed manner? I am having difficulties to understand. I'm new to C.
• Deduplicator: Pre-standard C is K&R-C, C90 (also known as C89 and incorrectly as ANSI C) is the first C-standard, C99 the second and C11 the current one. --- Should I explain anything specific? I might look it all over later and add some explanations wherever I assume you might have trouble, but that would be hit and miss at best...
• codez: Since C11 is the current one, could you please tell me what I need to do to make it to the C11 standard? Also I want code explanation, quite complex to understand.
• Deduplicator: Well, it works as C99 or later, including C11. Yes, I understand you want some more explanation, but what specifically don't you understand? I doubt you aren't understanding anything at all.
• codez: Nothing other than the typedef part. I'm less than a week old to C.

Answer 2

In terms for efficiency and concept, the implementation is fine. It lacks the more interesting functionality such as deleting and inserting items.

The most important missing element is deleting the linked list itself: when you allocate memory using malloc, it's important to add functions to clean that up at some point.

Code duplication

In addElement, the logic of creating a new element is duplicated twice. This could be easily avoided by moving that logic to another function, for example:

struct Element * createElement(int value) {
 struct Element *newElement;
 newElement = malloc(sizeof(struct Element));
 newElement->value = value;
 newElement->nextElement = NULL;
 return newElement;
}

On closer look, you didn't even really need an extra method, you could eliminate the duplicated logic by moving the element creation before the if condition:

void add(struct LinkedList *list, int value) {
 struct Element *newElement = createElement(value);
 if(list->firstElement == NULL) {
 list->firstElement = newElement;
 } else {
 // ...
 lastElement->nextElement = newElement;
 }
}

Naming

Most of the names are good and nicely descriptive. But there are a few exceptions:

• getElement: despite its name, this function returns an int, not an Element. So getValue would be better.
• lastElement as loop is not so great, as it's typically not referencing the last element. node would be a more common name for the purpose

Trivial simplifications

Some of the functions can be simplified very easily.

For example, in getElement you really don't need the returnValue variable. You assign to it right before you return it, and that's the only use. So avoid the pointless local variable. Every variable has the potential of getting misused. So if a variable has no good purpose to serve, then don't use it.

Another minor point is that instead of iteratedIndex = iteratedIndex + 1 you can write simply ++iteratedIndex.

• Deduplicator: 1. There's a better way to simplify add, getting rid of the if-statement too. 2. In addition to providing cleanup, checking for success of malloc is a good idea.
• codez: Talking about malloc, I believe the OS cleans up the memory allocated when the application is terminated? Or do you mean to clean up memory for when the LinkedList is used in an application and is no longer needed?
• janos: @HassanAlthaf The OS cleaning up at program exit is as good an excuse as the computer cleaning up when you switch the power off. A useless excuse, it's best to erase from your vocabulary. A utility component should be reusable at multiple places in a program if needed. It should not leave garbage behind it, preventing no longer used memory areas from being used by other parts of the program. Whenever you allocate memory, it's your responsibility to provide the means to free that memory. Now that is something to commit to memory
• codez: @janos Alright. Makes sense.
• Deduplicator: Well, one should not dismiss the fact that the OS reclaims all memory on program-termination anyway, because sweeping the floors before calling the wrecking-crew is counter-productive. But yes, one should, for anything reusable, unless there are weighty valid arguments otherwise, at least have the option of cleaning it up before and keep going with the next task.

Answer 3

As you always add elements to the end of the list you should consider adding a lastElement pointer to your LinkedList, it makes you able to add elements in O(1) instad than O(n).

Consider also having another function to add an element at the start of the list.

• Deduplicator: Yes, good idea. Though one could also simply add at the front and then (if neccessary) reverse the list in-place in linear time.
• codez: But that would break the concept?
• Deduplicator: @HassanAlthaf: Adding additional members to speed up some operations would not quite break the concept, though it's no longer as pure, and optimized for other uses than before.
• N74: @HassanAlthaf I'd say that using your LinkedList as a Heap breaks the concept: you should always use the data structure that better fits your needs, and in your implementation the best use for your class is a Stack, where yoiu push and pop from the head.

Answer 4

Let's talk code.

Your code with commentary.

Tip #1. Do not add comments to code if you can avoid it. Change the way code is written to avoid comments.

#include <stdio.h>
#include <stdlib.h>
// Do not need typedef. It creates unnecessary indirection. 
// You need to check what it is defined as. 
struct Element {
 int value;
 struct Element *nextElement;
};
// LinkedList should maintain a few more things if you are going this path.
// Keep track of last node.
// Keep track of element count.
// etcetra
struct LinkedList {
 struct Element *firstElement; 
};
// add is too long. Divide it into multiple functions.
void add(struct LinkedList *list, int value) {
 if(list->firstElement == NULL) {
 struct Element *newElement;
 newElement = malloc(sizeof(struct Element));
 newElement->value = value;
 newElement->nextElement = NULL;
 list->firstElement = newElement;
 } else {
 struct Element *lastElement;
 lastElement = list->firstElement;
 while(lastElement->nextElement != NULL) {
 lastElement = lastElement->nextElement; 
 }
 struct Element *newElement;
 newElement = malloc(sizeof(struct Element));
 newElement->value = value;
 newElement->nextElement = NULL;
 lastElement->nextElement = newElement;
 }
}
int getElement(struct LinkedList *list, int index) {
 int iteratedIndex = 0;
 int returnValue = 0;
 struct Element *temporaryElement = list->firstElement;
 while(temporaryElement != NULL) {
 if(iteratedIndex == index) {
 returnValue = temporaryElement->value;
 return returnValue;
 }
 iteratedIndex = iteratedIndex + 1;
 temporaryElement = temporaryElement->nextElement;
 }
 return 0;
}
void showAllElements(struct LinkedList *list) {
 struct Element *lastElement = list->firstElement;
 while(lastElement != NULL) {
 printf("%d\n", lastElement->value);
 lastElement = lastElement->nextElement;
 }
}
int main()
{
// add this code to a different function.
 struct LinkedList list = {NULL};
 add(&list, 5);
 add(&list, 10);
 add(&list, 15);
 showAllElements(&list);
 int value = getElement(&list, 0);
 printf("%d\n", value);
 return 0; 
}

Change #1 - Naming

struct item {
 int value;
 struct item *next;
};
struct list {
 struct item *first;
 struct item *last;
 int count;
 int id;
 /// .... more stuff ....
};

Naming is a choice. Keep it simple and to the point. But it still is a choice.

Change #2 - Breaking add function

struct list * create_empty_list(){
 return (struct list *) malloc(sizeof(struct list));
}
struct list * create_list(int id){
 struct list * tmp = create_empty_list();
 tmp -> id = id;
 /// .... more things ....
 return tmp;
}
struct item * create_empty_item(){
 // probably check for null 
 // probably fetch new item/node from cache.
 return (struct item *) malloc(sizeof(struct item));
}
struct item * create_item(int value){
 struct item * tmp = create_empty_item();
 tmp -> value = value;
 /// .... more ....
 return tmp;
}
struct list * append_item_to_list(struct list * l, int val){
 struct item * i = create_item(val);
 l -> last -> next = i;
 l -> count ++;
 /// ... more ...
 return l; // or go with void to begin with.
}

Change #3 - runner function

struct list * generate_example_list(){
 struct list * newList = create_list(generate_id());
 append_item_to_list(newList, 5);
 append_item_to_list(newList, 25);
 append_item_to_list(newList, 55);
 return newList;
}
void run(){
 struct list * newList = generate_example_list();
 print_list(newList);
}
int main(){
 run();
 return 0;
}

Naming conventions

• Keep names of variables and functions simple.
• Pick one style and stick to it.

Function Responsibility

• Usually one function should take responsibility of doing just one thing. A function can do multiple things by calling other functions, that's valid case. But refrain from doing a lot in single function.

• Break complex functionality into small functions that you can use as building blocks.

• It helps in debugging too.

Code structure

• Structures and included header files should move to list.h file that you can refer in list.c as #include "list.h".

Style

• typedef is matter of taste and collective team mindset. Try to see both the sides by writing code with and without typedef.

• use function_like_this or functionLikeThis or FunctionLikeThis as per taste and team requirements.

---

• Deduplicator: "add is too long": Yes, because it's too damn over-complicated. See for complete rewrite which is far shorter and clearer. Far better than splitting that monstrosity. Extracting the contents of main into another function just makes that the main-function, so no advantage. Also, as the code is at least C99, return 0; in main is superfluous. Includes in a header-file should be the bare minimum to compile that header; no more, no less.