current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 6 down vote favorite

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");
}
share|improve this question

3 Answers 3

up vote 3 down vote accepted

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().

share|improve this answer
    
Thanks for your answer! The way that I thought linked list operations worked in C was to assign the result of a function to the pointer to the linked list. For example, SLLNode* p = new_SLLNode(1); p = SLLdelete(p, 1);, which is why I was returning the head even if we reach the end of the linked list without finding the value to be deleted. Is there a better way of implementing operations, ideally with void functions? –  Impossibility Oct 30 '14 at 21:07
    
I must admit that it has been a long time since I've coded in C and perhaps it is true that I am out of touch with what a classic linked list implementation in C looks like. Because of this perhaps I am not the best person to review C code. My sensibilities have certainly been influenced by higher level languages where language support for exception handling and memory management are taken for granted. It is still possible, of course, to write C code that has a self-documenting public interface, is fault tolerant, and follows the principle of least astonishment. –  Eric Zoerner Oct 30 '14 at 22:16
    
I am curious why you think implementing the operations as void functions would be better. It seems more useful to me to return some value back to the caller to provide some feedback, e.g. about success or failure, if only a boolean value. –  Eric Zoerner Oct 30 '14 at 22:35
    
Returning the head of the list might be okay as well, perhaps to support chaining of function calls(?). To me, however, it seems like that doesn't provide very useful information since the caller already has the head of the list, and I don't see chaining of calls to be very useful or desirable in C. As for "the way linked list operations work in C": it is your code, you can design it any way you like, and there certainly isn't just one way that linked lists can be implemented in C. –  Eric Zoerner Oct 30 '14 at 22:47
up vote 2 down vote

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.

share|improve this answer
up vote 3 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.