6
\$\begingroup\$

I'm a python dev by day trying to learn C.

This is a simple implementation of a singly linked list. As a noob I would like comments on style and C conventions as well as functional remarks on memory management etc.

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

/*
        --------linkedList---------
        |                          |
        |                          |
        |                          |
        |                          | 
        *head  -->  nodes  -->   *end   
*/

struct linkedList {
    struct node * head;
    struct node * end;
    int len;
};
struct node {
    int id;
    int val;
    struct node * next;
};
struct linkedList * createList() {
    struct linkedList * l_list = (struct linkedList * ) malloc(sizeof(struct linkedList));

    l_list->head = NULL;
    l_list->end = NULL;
    l_list->len = 0;
    printf("created list\n");
    return l_list;
}

struct node * createNode(int id, int val) {
    struct node * n_node = (struct node * ) malloc(sizeof(struct node));

    n_node->id = id;
    n_node->val = val;
    n_node->next = NULL;
    printf("created node\n");
    return n_node;
}

void addNode(struct linkedList * ptr, int id, int val) {
    struct node * new_node = createNode(id, val);
    if (ptr->len == 0) {
        ptr->head = new_node;
        ptr->end = new_node;
        ptr->len += 1;
        printf("created a list and added a new value\n");
    } else {
        // update next of previous end
        // make new end this node 
        struct node * temp;
        temp = ptr->end;
        temp->next = new_node;
        ptr->end = new_node;
        ptr->len += 1;
        // printf("updated a preexisting list\n");
    }
}

void printListWithFor(struct linkedList * someList) {
    struct node currentNode = * someList->head;
    printf("current length of list is %d\n", someList->len);
    printf("first item is %d, last item is %d\n", someList->head->val, someList->end->val);
    if (currentNode.next == NULL) {
        printf("current node id is %d, with a value of %d\n", currentNode.id, currentNode.val);
    }
    for (int i = 0; i < ( * someList).len; i++) {
        printf("current node id is %d, with a value of %d\n", currentNode.id, currentNode.val);
        currentNode = * currentNode.next;
    }
}

void printListWithWhile(struct linkedList * someList) {
    struct node currentNode = * someList->head;
    struct node endNode = * someList->end;
    printf("current length of list is %d\n", someList->len);
    printf("first item is %d, last item is %d\n", someList->head->val, someList->end->val);
    if (currentNode.next == NULL) {
        printf("current node id is %d, with a value of %d\n", currentNode.id, currentNode.val);
    }
    while (currentNode.id != endNode.id) {
        printf("current node id is %d, with a value of %d\n", currentNode.id, currentNode.val);
        currentNode = * currentNode.next;
    }
    printf("current node id is %d, with a value of %d\n", currentNode.id, currentNode.val);
}
struct node * findNode(struct linkedList * someList, int id) {
    struct node headNode = * someList->head;
    struct node endNode = * someList->end;
    struct node * nullNode = createNode(-1, -1);

    if (headNode.id == id) {
        free(nullNode);
        return someList->head;
    }
    if (endNode.id == id) {
        free(nullNode);
        return someList->end;
    }
    struct node * currentNode = headNode.next;
    while (currentNode-> id != endNode.id) {
        if (currentNode->id == id) {
            free(nullNode);
            return currentNode;
        }
        currentNode = currentNode->next;
    }
    return nullNode;
}

int delNode(struct linkedList * someList, int id) {
    struct node * headNode = someList->head;
    struct node * endNode = someList->end;

    if (headNode->id == id) {
        // remove node, replace it with next node, free memory
        struct node * temp = headNode->next;
        someList->head = temp;
        printf("removed a node with id of %d and value of %d\n", headNode->id, headNode->val);
        free(headNode);
        someList->len -= 1;
        return 0;
    }
    if (endNode->id == id) {
        printf("removed a node with id of %d and value of %d\n", endNode->id, endNode->val);
        free(endNode);
        someList->len -= 1;
        return 0;
    }
    struct node * currentNode = headNode->next;
    struct node * prevNode = headNode;
    while (prevNode->id != endNode->id) {
        if (currentNode->id == id) {
            struct node * temp = currentNode->next;
            prevNode->next = temp;
            printf("removed a node with id %d and value of %d\n", currentNode->id, currentNode->val);
            free(currentNode);
            someList->len -= 1;
            return 0;
        }
        prevNode = currentNode;
        currentNode = currentNode->next;
    }
    return -1;

}
int main() {

    struct linkedList * list = createList();
    addNode(list, 1, 7);
    addNode(list, 2, 6);
    addNode(list, 3, 11);
    addNode(list, 5, 92);
    addNode(list, 18, 6);
    addNode(list, 10, 3);
    addNode(list, 50, 9);

    // printListWithWhile(list);
    // printListWithFor(list);
    printf("\n");
    struct node * foundNode = findNode(list, 1);
    printf("Node id : %d\n", foundNode->id);
    printf("Node val : %d\n", foundNode->val);

    printf("\n");
    // printListWithWhile(list);
    delNode(list, 2);
    printListWithWhile(list);
    delNode(list, 18);
    printf("\n");
    printListWithWhile(list);
    return 0;
}
\$\endgroup\$
0
4
\$\begingroup\$

In C, it's not necessary or desirable to cast the return value from malloc(). It is however essential to check the result isn't null before dereferencing it:

struct linkedList *createList() {
    struct linkedList *list = malloc(sizeof *list);
    if (list) {
        list->head = NULL;
        list->end = NULL;
        list->len = 0;
    }
    return list;
}

Note that the caller of createList also needs to check whether the returned list pointer is null before attempting to use it.

There doesn't seem to be a corresponding function to release a list; this is likely what makes the test program leak memory. See this Valgrind output:

==868== HEAP SUMMARY:
==868==     in use at exit: 104 bytes in 6 blocks
==868==   total heap usage: 10 allocs, 4 frees, 1,176 bytes allocated
==868== 
==868== 104 (24 direct, 80 indirect) bytes in 1 blocks are definitely lost in loss record 6 of 6
==868==    at 0x483577F: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==868==    by 0x109186: createList (217145.c:24)
==868==    by 0x1096D7: main (217145.c:151)

We can't rely on the node id values being unique:

if (currentNode.next == NULL) {
    printf("current node id is %d, with a value of %d\n", currentNode.id, currentNode.val);
}
while (currentNode.id != endNode.id) {
    printf("current node id is %d, with a value of %d\n", currentNode.id, currentNode.val);
    currentNode = * currentNode.next;
}

This looks very weird, because it is copying the entire value of each node into currentNode. A more efficient and more idiomatic approach is to define currentNode as a pointer; since we don't want to modify the list through it, make it a pointer to const.

void printListWithWhile(const struct linkedList * someList)
{
    const struct node *currentNode = someList->head;
    printf("current length of list is %d\n", someList->len);
    if (someList->head) {
        printf("first item is %d, last item is %d\n",
               someList->head->val, someList->end->val);
    }

    while (currentNode) {
        printf("current node id is %d, with a value of %d\n",
               currentNode->id, currentNode->val);
        currentNode = currentNode->next;
    }
}

Or more idiomatically (though now belying the name) as a for loop:

void printListWithWhile(const struct linkedList * someList)
{
    printf("current length of list is %d\n", someList->len);
    if (someList->head) {
        printf("first item is %d, last item is %d\n",
               someList->head->val, someList->end->val);
    }

    for (const struct node *currentNode = someList->head;  currentNode;  currentNode = currentNode->next) {
        printf("current node id is %d, with a value of %d\n", currentNode->id, currentNode->val);
    }
}

These observations apply to most of the functions.

Other odd things:

  • Why does findNode() create a dummy object to return on failure, rather than just returning NULL?
  • And why waste resources creating it in the cases where it's simply deleted again?
  • What does the return value of delNode() signify? A common convention is true (i.e. non-zero) for success and false (zero) if not found; is there a reason for a different convention here?
  • printListWithFor() never seems to be called.
  • Lots of commented-out code and unnecessary printf()s seem to have been left in when debugging. These should be removed before the code is ready to use.
\$\endgroup\$
8
  • \$\begingroup\$ You wouldn't recommend using typedef for the node and list type? \$\endgroup\$ – pacmaninbw Apr 10 '19 at 19:07
  • \$\begingroup\$ I don't have a strong opinion, though it can make code easier to read. You're welcome to post an answer of your own, of course... \$\endgroup\$ – Toby Speight Apr 10 '19 at 20:17
  • \$\begingroup\$ I think typedef is overused by beginners; I would not use it if you have a choice. See kernel.org/doc/html/v4.10/process/coding-style.html#typedefs. \$\endgroup\$ – Neil Apr 10 '19 at 21:04
  • \$\begingroup\$ You may also want to mention that the argument to printListWithWhile should be const and that generally, one would just name that printList. \$\endgroup\$ – Edward Apr 11 '19 at 20:12
  • \$\begingroup\$ Thanks @Edward; I've updated the argument to that function. The naming is unconventional, but OTOH, I can see that it's done for (auto?)didactic purposes, to compare two ways of terminating the loop, so I think that wasn't a mistake. \$\endgroup\$ – Toby Speight Apr 12 '19 at 7:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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