Singly Linked List Implementation in C

Question

I'm preparing for an interview soon, and I've written the following linked list implementation from scratch.

This is all self-taught, and I'm still working on my C. I feel that the implementation is correct (if someone catches a corner case though, that would be great!), and I'm looking for feedback on best C practices.

For example: Is the spacing excessive? Are 1-line control flow statements okay? Is the constructor implementation idiomatic?

Header file:

#ifndef Interview_Prep_SLL_h
#define Interview_Prep_SLL_h

typedef struct SLLNode
{
    int val;
    struct SLLNode* next;
} SLLNode;

SLLNode* new_SLLNode(int val);
SLLNode* SLLappend(SLLNode* head, int val);
SLLNode* SLLinsert(SLLNode* head, int val, int ind);
SLLNode* SLLdelete(SLLNode* head, int val);
SLLNode* SLLreverse(SLLNode* head);
void SLLprint(SLLNode* head);

#endif

Source file:

// constructor
SLLNode* new_SLLNode(int val)
{
    SLLNode* head = malloc(sizeof(SLLNode));
    head->val = val;
    head->next = NULL;
    return head;
}

// add node to end
SLLNode* SLLappend(SLLNode* head, int val)
{
    if (head == NULL) return new_SLLNode(val);

    SLLNode* curr = head;

    while (curr->next != NULL) curr = curr->next;

    curr->next = new_SLLNode(val);

    return head;
}

// insert node at index (position) ind
SLLNode* SLLinsert(SLLNode* head, int val, int ind)
{
    if (head == NULL && ind > 0) return head;
    if (head == NULL && ind == 0) return new_SLLNode(val);

    SLLNode* curr = head;
    int count = 0;

    while (curr != NULL && count < ind - 1)
    {
        curr = curr->next;
        count++;
    }

    if (curr == NULL) return head;

    SLLNode* temp = curr->next;
    SLLNode* new = new_SLLNode(val);

    curr->next = new;
    new->next = temp;

    return head;
}

SLLNode* SLLdelete(SLLNode* head, int val)
{
    if (head == NULL) return head;

    if (head->val == val) return head->next;

    SLLNode* curr = head;

    while (curr->next != NULL && curr->next->val != val) curr = curr->next;

    if (curr->next == NULL) return head;

    SLLNode* temp = curr->next;
    curr->next = curr->next->next;
    free(temp);

    return head;
}

SLLNode* SLLreverse(SLLNode* head)
{
    if (head == NULL) return head;
    if (head->next == NULL) return head;

    SLLNode* curr = head;
    SLLNode* next = curr->next;
    SLLNode* nextnext = next->next;

    while (true)
    {
        if (curr == head) curr->next = NULL;

        next->next = curr;
        curr = next;
        next = nextnext;

        if (nextnext == NULL) return curr;

        nextnext = nextnext->next;
    }
}

// print values of nodes separated by spaces
void SLLprint(SLLNode* head)
{
    while (head != NULL)
    {
        printf("%d ", head->val);
        head = head->next;
    }
    printf("\n");
}

Answer 1

An area I would suggest improving is in how you are handling exceptional cases.

For example, it may be better to handle a NULL head parameter as an error condition rather than as a normal use case, and instead represent an empty list by using a node that has a next pointer that points to itself. Then add a separate function that tests for an empty list.

Also, inserting a node at an index beyond the end of the list should either be an error condition or else just append to the list instead. Your code just returns the head in this case, which is rather astonishing behavior. The behavior on exceptional cases like this should be clearly documented in the code.

Another one might be an attempt to delete a value from the list that is not present. This could be an error condition or not, but this should be clearly documented. You could also have two versions of delete, one that fails when the value is not present and another one that does not. Make the behavior clear in the name of the function.

In general, it is better to "fail fast" rather than to propagate the error down the line. By failing immediately, it will make the program easier to debug.

However, handling exceptional cases in C is tricky. One way to do that would be to use return codes, but that will clutter your API. Perhaps a better way in C is to use setjmp() and longjmp().

Answer 2

Overall this seems fine: a classing linked list implementation in C. A couple of things can be simplified or improved here and there.

---

Instead of testing head == NULL twice:

if (head == NULL && ind > 0) return head;
if (head == NULL && ind == 0) return new_SLLNode(val);

It would be better to eliminate this duplication and do it only once:

if (head == NULL) {
    if (ind > 0) return NULL;
    if (ind == 0) return new_SLLNode(val);
}

Notice that I also changed return head to return NULL. I know that head is NULL there, but it's more explicit this way.

I have a feeling that after the while loop that iterates until ind to insert an element, when you do this:

if (curr == NULL) return head;

Possibly you really meant this instead:

if (curr == NULL) return curr;
// or
if (curr == NULL) return NULL;

I could be wrong, but perhaps not using explicit NULLs somehow led to mistakes like this. (I assume it was a mistake to return head when trying to insert beyond end + 1 of the linked list, which indicates a likely bug in the caller.)

---

Is the spacing excessive?

No, I think it's just right.

Are 1-line control flow statements okay?

They are ok. But keep in mind that if/for/while statements without a { ... } block can lead to nasty bugs, like in this famous example. Some static analysis tools flag a warning for such statements.

Answer 3

IMHO your code is quite good. The only general change I would recommend is avoiding the single semicolon at the end of conditional and loop statements. They can easily be overlooked, both when writing and when maintaining the code. That's why I prefer to place them in separate line:

NO:

    while(*dst++ = *src++);

YES:

    while(*dst++ = *src++)
        ;

Even without curly braces this makes a prominent statement, so you won't confuse the following code as being controlled by this loop.

Some specific notes to your implementation.

In the 'insert' routine you don't need to test for head being NULL if ind==0; inserting a node as the new head of a non-empty list does not essentially differ from inserting a head into an empty list.

You also needn't check for head == NULL when ind > 0, because it's a special case of a more general condition 'ind exceeds the list length'.

Finally, you don't need a temp variable – once you found a node, after which a new node is inserted, link the list's tail to the new node, then append them to the head part:

SLLNode* SLLinsert(SLLNode* head, int val, int ind)
{
    if (ind == 0)               // make a new head
    {
        SLLNode* newhead = new_SLLNode(val);
        newhead->next = head;   // possibly NULL, if the list was empty
        return newhead;
    }

    SLLNode* curr = head;

    while (curr != NULL && --ind != 0)   // hope ind was positive...!
    {
        curr = curr->next;
    }

    if (curr != NULL)
    {
        SLLNode* new = new_SLLNode(val);

        new->next = curr->next;
        curr->next = new;
    }
    return head;
}

There is an error in the 'delete' routine: if val == head->val it just skips the head node instead of deleting it. The initial part should look like:

SLLNode* SLLdelete(SLLNode* head, int val)
{
    if (head == NULL)
       return NULL;

    if (head->val == val)
    {
        SLLNode* next = head->next;
        free(head);
        return next;
    }

    ....
}

Note that you can append or insert multiple nodes with the same val. In such case you might want to delete all nodes with the same value. One quite easy way to do that is unlinking those nodes first, then deleting them:

SLLNode* SLLdeleteall(SLLNode* head, int val)
{
    if (head == NULL)
       return NULL;

    SLLNode *rmv = NULL, *curr = head, *next;

    while ((next = curr->next) != NULL)
    {
        if (next->val == val)         // test all except *head
        {
            curr->next = next->next;  // unlink *next
            next->next = rmv;         // and push it to rmv
            rmv = next;
        }
        else
            curr = next;
    }

    if (head->val == val)             // test *head
    {
        next = head->next;            // store the tail of the list
        head->next = rmv;             // push *head to rmv
        rmv = head;
        head = next;                  // define a new head
    }

    while (rmv != NULL)               // delete all unlinked nodes
    {
        next = rmv->next;
        free(rmv);
        rmv = next;
    }

    return head;
}

Testing the *head node as the last one saves us additional loop to remove consecutive heads in case of multiple equal values at the beginning of the list.

A shorter version of 'reverse':

SLLNode* SLLreverse(SLLNode* curr)
{
    SLLNode* prev = NULL;

    while (curr != NULL)
    {
        SLLNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }

    return prev;
}

Invariant, satisfied on start and end of each iteration: curr is the head of (shrinking) list to reverse, prev is the head of a (growing) reversed list.

A fixed 'print':

void SLLprint(SLLNode* head)
{
    if (head != NULL)
    {
        printf("%d", head->val);

        while (head = head->next, head != NULL)
        {
            printf(" %d", head->val);
        }
    }
    printf("\n");
}

This one calls printf in two places, but it won't print a space after the last value.

Answer 4

I think some of your questions come down to personal preference. Certain companies and interviewers will have certain code styles that they look for, but I think that some things can be a definite turn-off to some people. For me, that includes single line control statements (if, while, etc.). I think this is especially true when doing loops because if you accidentally type:

while (logical_check == true && second_logical_check == false && long_logical_check == true);

it is harder to realize that there is a missing statement after the while when scanning the code. If you always use the curly braces {} with your control statements it is easy to see when one is empty or missing a body.

Answer 5

A few problems were reported by my compiler: You're missing declarations for malloc(), free(), printf(), true and NULL; these can be fixed by including <stdlib.h>, <stdio.h> and <stdbool.h> in your implementation file.

---

Looking at the constructor:

SLLNode* new_SLLNode(int val)
{
    SLLNode* head = malloc(sizeof(SLLNode));
    head->val = val;
    head->next = NULL;
    return head;
}

I prefer to allocate sizeof *head rather than duplicating the type information, but that's a personal preference. More serious is that undefined behaviour follows if malloc() returns a null pointer.

---

Throughout, there's quite a few equality tests against NULL. It's more idiomatic to allow the standard pointer conversion to bool. So

if (head == NULL) return new_SLLNode(val);

becomes simply

if (!head) return new_SLLNode(val);

---

In SLLinsert, you can remove the local variable count by decrementing the passed-in parameter ind instead:

while (curr && --ind > 0)
{
    curr = curr->next;
}

You can also avoid the local temp by assigning new->next before modifying curr.

This function also inserts in the wrong place when head is non-null and ind is 0.

---

SLLdelete only frees the removed element if it wasn't first in the list. If the head matches, then it is unlinked but not freed.

Also, it's not clear without reading the implementation whether it's intended to remove every matching value, or just the first.

---

SLLreverse seems overcomplicated. I didn't need a nextnext variable when I implemented this by copying each element from head to before curr.

---

The print function doesn't modify the list, so the argument should be declared as pointer to const:

void SLLprint(SLLNode const *head)

---

Although you provided a new_SLLNode() allocator, you didn't provide a matching deallocator. It's pretty simple to do so, and it allows a test program to demonstrate (in Valgrind) that it cleans up correctly.

---

You might want to experiment with having an unused empty node at the beginning of the list, to see which special-case checks of head can be eliminated this way. I've done this with the temporary n in the insert function to show how this can help.

---

Here's my version of your code, with the above issues addressed:

typedef struct SLLNode
{
    int val;
    struct SLLNode* next;
} SLLNode;

SLLNode* new_SLLNode(int val);
SLLNode* SLLappend(SLLNode* head, int val);
SLLNode* SLLinsert(SLLNode* head, int val, int ind);
SLLNode* SLLdelete(SLLNode* head, int val);
SLLNode* SLLreverse(SLLNode* head);
void delete_SLL(SLLNode *head);
void SLLprint(SLLNode const* head);


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

// constructor
SLLNode* new_SLLNode(int val)
{
    SLLNode* head = malloc(sizeof *head);
    if (head) {
        head->val = val;
        head->next = NULL;
    }
    return head;
}

// add node to end
SLLNode* SLLappend(SLLNode* head, int val)
{
    if (!head) return new_SLLNode(val);

    SLLNode* curr = head;

    while (curr->next)
        curr = curr->next;

    curr->next = new_SLLNode(val);

    return head;
}

// insert node at index (position) ind
/* Does nothing if the list has fewer than ind elements */
SLLNode* SLLinsert(SLLNode* head, int val, int ind)
{
    SLLNode n;                  /* dummy node so we can always use 'next' */
    n.next = head;

    SLLNode *curr = &n;

    while (curr && ind-- > 0)
        curr = curr->next;

    if (!curr) return head;

    SLLNode* new = new_SLLNode(val);
    if (new)
        new->next = curr->next;
    /* else SILENTLY_FAIL! - TODO */
    curr->next = new;

    return n.next;
}

/* Remove and destroy the first node with value equal to val */
SLLNode* SLLdelete(SLLNode* head, int val)
{
    if (!head) return head;

    if (head->val == val) {
        SLLNode *rest = head->next;
        free(head);
        return rest;
    }

    SLLNode* curr = head;

    while (curr->next && curr->next->val != val)
        curr = curr->next;

    if (!curr->next) return head;

    SLLNode* temp = curr->next;
    curr->next = temp->next;
    free(temp);

    return head;
}

SLLNode* SLLreverse(SLLNode* head)
{
    SLLNode *curr = NULL;
    while (head) {
        SLLNode *next = head->next;
        head->next = curr;
        curr = head;
        head = next;
    }
    return curr;
}

void delete_SLL(SLLNode *head)
{
    while (head) {
        SLLNode *next = head->next;
        free(head);
        head = next;
    }
}

// print values of nodes separated by spaces
void SLLprint(SLLNode const *head)
{
    for (;  head;  head = head->next)
        printf("%d ", head->val);
    printf("\n");
}


int main()
{
    SLLNode *n = new_SLLNode(3);
    n = SLLappend(n, 4);
    n = SLLappend(n, 6);

    n = SLLinsert(n, 5, 2);
    n = SLLinsert(n, 5, 15);
    n = SLLdelete(n, 3);
    n = SLLreverse(n);
    n = SLLinsert(n, 8, 0);

    SLLprint(n);                /* expect: 8 6 5 4 */

    delete_SLL(n);
}

I haven't addressed the behaviour of SLLinsert when allocation fails - you'll want to consider how to report this back to the caller. There's not a single 'right' answer to that one!