C implementation of singly linked list

Question

I realize my code is rather long so I'd like opinions mainly on a couple of things if your time is short:

1) Returning INT_MIN to indicate that it was empty.

2) The removeHead and removeTail functions.

Feel free to add more criticism.

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

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

typedef struct
{
    Node* head;
    Node* tail;
}LinkedList;

void printListRec(Node* node);
void printHeadAndTail(LinkedList* list);
int printList(LinkedList* list);
int linkedListSize( LinkedList* list );
int searchForElement( LinkedList* list , int value );
int isEmpty( LinkedList* list );
int removeElement( LinkedList* list , int value);
int removeTail( LinkedList* list );
int removeHead( LinkedList* list );
void addTail( LinkedList* list , int value);
void addHead( LinkedList* list , int value);
LinkedList* initialize() ;

//implement a clear list function

int main()
{
    LinkedList* linkedlist = initialize();

    addHead(linkedlist , 1);
    printHeadAndTail(linkedlist);
    printList(linkedlist);

    addHead(linkedlist , 2);
    printHeadAndTail(linkedlist);
    printList(linkedlist);

    removeTail(linkedlist);
    printHeadAndTail(linkedlist);
    printList(linkedlist);

    removeTail(linkedlist);
    printHeadAndTail(linkedlist);
    printList(linkedlist);

    addTail(linkedlist , 3);
    printHeadAndTail(linkedlist);
    printList(linkedlist);



    return 0;
}

LinkedList* initialize() //creates linked list with no nodes, initializes head & tail to 0
{
    LinkedList* list = malloc(sizeof(LinkedList));
    list->head = NULL;
    list->tail = NULL;
    return list;
}

void addHead( LinkedList* list , int value)
{
    Node* newNode = malloc( sizeof(Node) );
    newNode->value = value;

    if( isEmpty(list) )
    {
        newNode->next = NULL;
        list->head = list->tail = newNode;
    }

    else
    {
        newNode->next = list->head;
        list->head = newNode;
    }
    puts("Add head");
}

void addTail( LinkedList* list , int value)
{
    Node* newNode = malloc( sizeof(Node) );
    newNode->value = value;
    newNode->next = NULL;

    if( isEmpty(list) )
    {
        newNode->next = NULL;
        list->head = list->tail = newNode;
    }

    else
    {
        list->tail->next = newNode;
        list->tail = newNode;
    }
    puts("Add tail");
}

int removeHead( LinkedList* list )
{
    if(isEmpty(list))
        return INT_MIN;

    Node* nodeToDelete = list->head;
    int value = nodeToDelete->value;


    if(list->head == list->tail) //if node is the only node present
        list->head = list->tail = NULL;
    else
        list->head = list->head->next;

    free(nodeToDelete);
    puts("Remove head");
    return value;
}

int removeTail( LinkedList* list )
{
    if( isEmpty(list) )
        return INT_MIN;

    int value ;
    if(list->head == list->tail)
    {
        value = list->tail->value;
        free(list->tail);
        list->head = list->tail = NULL;
        return value;
    }

    Node* nodeToDelete = list->tail;
    value = nodeToDelete->value;

    Node* nodeBeforeTail = list->head;
    while( nodeBeforeTail->next != nodeToDelete )
        nodeBeforeTail = nodeBeforeTail->next;

    nodeBeforeTail->next = NULL;
    list->tail = nodeBeforeTail;

    free(nodeToDelete);
    puts("Remove tail");
    return value;
}

int removeElement( LinkedList* list , int value)
{
    if( list->head->value == value )
    {
        removeHead(list);
        return 0; //element found
    }

    if(list->tail->value == value)
    {
        removeTail(list);
        return 0;
    }

    Node* node = list->head;
    while( (node->next) != list->tail )
    {
        if( node->next->value == value)
        {
            Node* nodeToDelete = node->next;
            node->next = node->next->next;
            free(nodeToDelete);
            return 0;
        }
        node = node->next;
    }
    return 1;
}

int isEmpty( LinkedList* list )
{
    return !list->head && !list->tail;
}

int searchForElement( LinkedList* list , int value )
{
    if(isEmpty(list))
        return -1;

    Node* node = list->head;

    do
    {
        if(node->value == value) return 0;
    }while( (node = node->next) );

    return 1;
}

int linkedListSize( LinkedList* list )
{
    int counter = 0;
    Node* node = list->head;
    while( node )
    {
        counter++;
        node = node->next;
    }
    return counter;
}

void printHeadAndTail(LinkedList* list)
{
    if(isEmpty(list))
    {
        printf("\nHead pointer : %d , tail pointer : %d\n" , list->head , list->tail);
        return;
    }
    printf("Head pointer: %d , Head's pointer to next : %d\n" , list->head, list->head->next );
    printf("Tail pointer: %d , tail's pointer to next : %d\n" , list->tail, list->tail->next );
}

void printListRec(Node* node)
{
    if( !node )
        return;
    printf("%d " , node->value);
    printListRec(node->next);
}

int printList(LinkedList* list)
{
    if( isEmpty(list) )
    {
        puts("List is empty");
        return 1;
    }

    puts("\nPrint Linked List: ");
    Node* node = list->head;
    while( node )
    {
        printf("%d " , node->value);
        node = node->next;
    }

    puts("\n*******************\n");

    return 0;
}

I don't see the printList implementation in the question. DId you forget it ? — Isac
– Isac, Commented Mar 20, 2018 at 23:22
I removed it from the submitted code cause my code is kinda long, just to make your job easier :D — BareWithImANoob
– BareWithImANoob, Commented Mar 21, 2018 at 9:25
@BareWithImANoob Your edit adding the implementation of printList does so using a different naming / naming convention. Can you fix that so the code can be compiled? — 301_Moved_Permanently
– 301_Moved_Permanently, Commented Mar 21, 2018 at 13:34
Sorry, I had to do some homework using it and decided everything linkedlist related should start with "list_". Gonna re-edit again :) — BareWithImANoob
– BareWithImANoob, Commented Mar 22, 2018 at 14:41

Snowhawk · Accepted Answer · 2018-03-21 00:35:51Z

    LinkedList* list = malloc(sizeof(LinkedList));

Always ensure that the allocation functions malloc and friends succeed. These functions return a null pointer when they are unable to allocate memory. If the environment isn't configured to guard/crash when malloc fails, then you have a bunch of null pointer dereferences causing undefined behavior.

    puts("Add head");

These messages do nothing but produce noise. You should either use a precompiler directive to switch function call tracing in debug builds or move the the tracing to your test driver. Even better, use a debugger.

int removeHead( LinkedList* list )
{
    if(isEmpty(list))
        return INT_MIN;
    // ...
}

Don't try to return both error codes and actual representable data through the same return variable. A library user may be using INT_MIN in their data set and a call to removeXXXX() may result in some user-code believing some data was actually removed. Decide whether you want to inform the callee of success or failure and don't bother returning data from the list. If the callee really wants the data, they can copy it themselves before deleting.

Keep functions short and simple. When functions gets to be longer than a few lines, look for opportunities to refactor into higher levels of abstraction. For example, your removeTail function has one large block that is essentially removeHead and another block that essentially finds the previous node.

int isEmpty( LinkedList* list )
{
    return !list->head && !list->tail;
}

Is there ever a situation where either list->head or list->tail exists while the other doesn't? What happens if the callee passes a list that is null?

        if(node->value == value) return 0;
    }while( (node = node->next) );

    if(isEmpty(list))
    if( !node )

Be consistent with your formatting.

    if( isEmpty(list) )
    if( !node )

Be safe and always brace your single-line body scopes. They can't be misinterpreted by maintainers (both human and machine).

    if( node->value == value) 
    {
        return 0;
    }
}
while( (node = node->next) );

Something to consider: Differentiate control structures from function calls to assist with readability and code understanding. More time will be spent reading code than writing code. e.g.

    if (node->value == value) 
    {
        return 0;
    }
}
while (node = node->next);

int linkedListSize( LinkedList* list )
{
    int counter = 0;
    Node* node = list->head;
    while( node )
    {
        counter++;
        node = node->next;
    }
    return counter;
}

Calculating the size is a linear operation. Have you considered just storing the current size in the LinkedList structure and updating the value as you operate on the list? That would make calling size a constant time operation at the cost of the size of an int.

Where is the function to free the list? printList() is forward declared. No implementation?

I changed quite a bit based on your comments. Will implement a size field as well. Question related to me returning INT_MIN: should my functions check for errors or should it be the callee. Or more specifically should I be checking if my list is empty before deque() or should I implement error checking inside the function as well like I did with INT_MIN. What I'm getting from you is that my functions should do pretty much a thing or two. — BareWithImANoob
– BareWithImANoob, Commented Mar 21, 2018 at 13:11
Figured I should google that question instead of asking haha. Anyway, thanks a lot for the help!!! — BareWithImANoob
– BareWithImANoob, Commented Mar 21, 2018 at 13:22
That Where is the function to free the list? printList() is forward declared. No implementation? is more of a comment than a review, therefore I did not rollback the edit that was made to the question. — Simon Forsberg
– Simon Forsberg, Commented Mar 21, 2018 at 20:40
@BareWithImANoob Just don't use the same variable for multiple purposes. Want to return a status? return the status and nothing else. Want to return both a status and a value, return the status and have the function be defined with an in-out parameter (bool load(char *file_name, char *buffer) { ... }). — Snowhawk
– Snowhawk, Commented Mar 22, 2018 at 1:21
Minor: Use NULL, null pointer or null pointer constant rather than lowercase null in "callee passes a list that is null". — chux
– chux, Commented Mar 22, 2018 at 14:08

Toby Speight · Accepted Answer · 2018-03-23 11:43:01Z

Match `printf` conversions with types

GCC warns me:

190060.c:220:35: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘Node *’ {aka ‘struct node *’} [-Wformat=]
         printf("\nHead pointer : %d , tail pointer : %d\n" , list->head , list->tail);
                                  ~^                          ~~~~~~~~~~
190060.c:220:55: warning: format ‘%d’ expects argument of type ‘int’, but argument 3 has type ‘Node *’ {aka ‘struct node *’} [-Wformat=]
         printf("\nHead pointer : %d , tail pointer : %d\n" , list->head , list->tail);
                                                      ~^                   ~~~~~~~~~~

(and more). We want *p for pointers:

void printHeadAndTail(LinkedList* list)
{
    if(isEmpty(list))
    {
        printf("\nHead pointer : %p , tail pointer : %p\n" , (void*)list->head , (void*)list->tail);
        return;
    }
    printf("Head pointer: %p , Head's pointer to next : %p\n" , (void*)list->head, (void*)list->head->next );
    printf("Tail pointer: %p , tail's pointer to next : %p\n" , (void*)list->tail, (void*)list->tail->next );
}

Use `const` for non-modifying operations

This is easy enough:

void printListRec(const Node *node);
void printHeadAndTail(const LinkedList *list);
int printList(const LinkedList *list);
int linkedListSize(const LinkedList *list);
int searchForElement(const LinkedList *list, int value);
int isEmpty(const LinkedList *list);

Implement the `clearList` function

There's a common that mentions it's missing; without this, it's harder to check for memory leaks.

void clearList(LinkedList *list)
{
    Node *n = list->head;
    while (n) {
        Node *n2 = n->next;
        free(n);
        n = n2;
    }
    list->head = list->tail = NULL;
}

Consider a "dummy head" implementation

If we make a head element that is never used for value, but only for its next member, we reduce the complexity of many of the functions. This is an example of the Null Object design pattern.

For example:

// allocation error-checking omitted - please add some!

void addHead(LinkedList* list, int value)
{
    Node* newNode = malloc(sizeof *newNode);
    newNode->value = value;
    newNode->next = NULL;

    if (!list->head.next) {
        list->tail = newNode;
    }
    newNode->next = list->head.next;
    list->head.next = newNode;
    puts("Add head");
}

void addTail(LinkedList* list , int value)
{
    Node* newNode = malloc(sizeof *newNode);
    newNode->value = value;
    newNode->next = NULL;

    list->tail->next = newNode;
    list->tail = newNode;
    puts("Add tail");
}

int removeHead(LinkedList* list)
{
    Node* nodeToDelete = list->head.next;
    int value = INT_MIN;
    if (nodeToDelete) {
        value = nodeToDelete->value;
        list->head.next = nodeToDelete->next;
        free(nodeToDelete);
        if (!list->head.next) {
            list->tail = &list->head;
        }
    }
    puts("Remove head");
    return value;
}

int removeTail(LinkedList* list)
{
    if (!list->head.next)
        return INT_MIN;

    Node *n = &list->head;
    while (n->next->next) n = n->next;

    Node* nodeToDelete = n->next;
    int value = nodeToDelete->value;

    n->next = NULL;
    list->tail = n;

    free(nodeToDelete);
    puts("Remove tail");
    return value;
}

int removeElement(LinkedList* list , int value)
{
    Node *n = &list->head;
    while (n->next && n->next->value != value)
        n = n->next;

    if (!n->next)
        /* not found */
        return 0;

    if (list->tail == n->next)
        return removeTail(list), 1;

    Node *newNext = n->next->next;
    free(n->next);
    n->next = newNext;
    return 1;
}

int searchForElement(const  LinkedList* list , int value)
{
    const Node *n = &list->head;
    while ((n=n->next)) {
        if (n->value == value) return 0;
    }
    return 1;
}

I'm not sure whether this is actually much simpler or clearer, but it's a technique to be aware of and have available when you need it. It tends to be more useful in doubly-linked lists.

Consider also whether having a tail pointer is worth the cost of keeping it updated. It might be for long lists that are appended to, but if you can prepend instead, then it may be better to omit it.

Some prefer using double-pointers instead of a dummy node for double-indirection because that avoids the unused payload-members in languages allowing that... — Deduplicator
– Deduplicator, Commented Mar 23, 2018 at 22:03

Stack Exchange Network

C implementation of singly linked list

2 Answers 2

Match `printf` conversions with types

Use `const` for non-modifying operations

Implement the `clearList` function

Consider a "dummy head" implementation

You must log in to answer this question.

Hot Network Questions

C implementation of singly linked list

2 Answers 2

Match printf conversions with types

Use const for non-modifying operations

Implement the clearList function

Consider a "dummy head" implementation

You must log in to answer this question.

Related

Hot Network Questions

Match `printf` conversions with types

Use `const` for non-modifying operations

Implement the `clearList` function