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.

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.

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.

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.

---