3
\$\begingroup\$

I'm looking for some feedback on this code I wrote tackling a general solution to the age old "Add 2 numbers represented by Linked Lists". This specific one aims to be able to sum any given number of linked lists.

Ofcourse, the input linked lists must contain the number in reverse order.

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

typedef struct ListNode {
    // Basic Node data structure of a Linked List
    int val;
    struct ListNode* next;
}node_t;

void appendNode(node_t** headref, int data)
{
    // Inserts node with given data
    node_t* temp, * node;
    node = (node_t*)malloc(sizeof(node_t));
    if (node == NULL)
    {
        printf("An error occured while allocating memory for node in appendNode\n");
        exit(1);
    }
    temp = (node_t*)malloc(sizeof(node_t));
    if (temp == NULL)
    {
        printf("An error occured while allocating memory for temp in appendNode\n");
        exit(1);
    }
    node->val = data;
    node->next = NULL;
    if (*headref == NULL)
    {
        *headref = node;
        return;
    }
    temp = *headref;
    while (temp->next != NULL)
    {
        temp = temp->next;
    }
    temp->next = node;
}

void createList(node_t** headref, int data[], int length)
{
    // Calls appendNode iteratively to assign whole array of data to list
    for (int i = 0; i < length; i++)
    {
        appendNode(headref, data[i]);
    }
}

void printList(node_t* headref)
{
    // Basic Linked List printing
    if (headref == NULL)
    {
        printf("\nLinked List is empty!\n");
        return;
    }
    printf("HEAD->");
    while (headref != NULL)
    {
        printf("%d->", headref->val);
        headref = headref->next;
    }
    printf("NULL\n");
}

void printListArray(node_t* linkedListArray[], int length)
{
    // Calls printList iteratively to print whole array of lists
    for (int i = 0; i < length; i++)
    {
        printList(linkedListArray[i]);
    }
}

void destroyList(node_t** headref)
{
    node_t* nextNode, * currentNode;
    nextNode = (node_t*)malloc(sizeof(node_t));
    if (nextNode == NULL)
    {
        printf("An error occured while allocating memory for nextNode in appendNode\n");
        exit(1);
    }
    currentNode = (node_t*)malloc(sizeof(node_t));
    if (currentNode == NULL)
    {
        printf("An error occured while allocating memory for currentNode in appendNode\n");
        exit(1);
    }
    if (*headref == NULL)
    {
        printf("\nLinked List is empty!\n");
        return;
    }
    currentNode = *headref;
    while (currentNode != NULL)
    {
        nextNode = currentNode->next;
        free(currentNode);
        currentNode = nextNode;
    }
}

void destroyListArray(node_t** linkedListArray[], int length)
{
    // Calls destroyList iteratively to print whole array of lists
    for (int i = 0; i < length; i++)
    {
        destroyList(linkedListArray[i]);
    }
}

bool isEnd(node_t* linkedListArray[], int length)
{
    // Checks if all lists have been exhausted
    int nullCount = 0;
    for (int i = 0; i < length; i++)
    {
        if (linkedListArray[i] == NULL)
        {
            nullCount++;
        }
    }
    return nullCount == length ? true : false;
}

void resvalAppend(node_t** resultList, int resultingValue, int* overflow)
{
    /**
    * A recursive function to keep stripping resval until it is single digit
    *
    * If resultingValue is a multi digit number, the other digits are stripped and put in
    * overflow, which is a global variable
    *
    * If resultingValue is a single digit number, it gets added to the result Linked List
    */
    if (resultingValue > 9)
    {
        *overflow = resultingValue / 10;
        resvalAppend(resultList, resultingValue % 10, overflow);
    }
    else
    {
        appendNode(resultList, resultingValue);
    }
}

node_t* addNumbers(node_t* linkedListArray[], int length)
{
    /** 
    * Accepts an array of pointers to HEAD of Linked Lists
    * along with the number of Linked Lists
    *
    * Returns a pointer to result Linked List
    */
    int resultingValue = 0, overflow = 0;
    node_t* resultList = NULL;
    while (!isEnd(linkedListArray, length) || overflow != 0)
    {
        // Loop only breaks once all lists are exhausted AND overflow is 0
        for (int i = 0; i < length; i++)
        {
            if (linkedListArray[i] != NULL)
            {
                // Adding in values to resval, ignoring NULL(s)
                resultingValue += linkedListArray[i]->val;
                linkedListArray[i] = linkedListArray[i]->next;
            }
        }
        // Adding in overflow, if any
        resultingValue += overflow;
        overflow = 0;
        // Putting resultingValue through the recursive function to strip overflow
        resvalAppend(&resultList, resultingValue, &overflow);
        resultingValue = 0;
    }
    return resultList;
}


void testcase()
{
    // Mess with inputs here, the below code is just an example
    /**
    * First Declare all the Pointers to Linked Lists that you'd like to use and assign them to NULL
    * Then use createList to create an entire Linked List at once instead of doing multiple appendNode
    *
    * createList requires the address of the pointer to HEAD, so it can modify the list
    * It also needs the dataset itself, which should be an int array
    * The final param is the length of this array
    *
    * Lastly use addNumbers and pass all the Pointers to Linked Lists in an array
    * Pass in the length of the array as well
    *
    * You can then use printList to print the result
    *
    * If you'd like, you can also use printListArray and pass in the array of pointer to lists
    * to print them all at once
    * This may be useful to make sure the input lists were created correctly
    */
    node_t* l1 = NULL, * l2 = NULL, * l3 = NULL, * l4 = NULL, * l5 = NULL, * l6 = NULL, * l7 = NULL, * l8 = NULL, * l9 = NULL, * l10 = NULL, * l11 = NULL, * l12 = NULL;
    node_t* resultList;
    createList(&l1, (int[]) { 9 }, 1);
    createList(&l2, (int[]) { 9 }, 1);
    createList(&l3, (int[]) { 9 }, 1);
    createList(&l4, (int[]) { 9 }, 1);
    createList(&l5, (int[]) { 9 }, 1);
    createList(&l6, (int[]) { 9, 9 }, 2);
    createList(&l7, (int[]) { 9, 9 }, 2);
    createList(&l8, (int[]) { 9, 9 }, 2);
    createList(&l9, (int[]) { 9, 9 }, 2);
    createList(&l10, (int[]) { 9, 9 }, 2);
    createList(&l11, (int[]) { 9, 9 }, 2);
    createList(&l12, (int[]) { 9, 9 }, 2);
    node_t* listArray[] = {
        l1, l2, l3, l4, l5, l6, l7, l8, l9, l10, l11, l12
    };
    printListArray(listArray, 12);
    resultList = addNumbers(listArray, 12);
    printList(resultList);
    destroyList(&resultList);
    destroyListArray((node_t** []) { &l1, &l2, &l3, &l4, &l5, &l6, &l7, &l8, &l9, &l10, &l11, &l12 }, 12);
}

int main()
{
    clock_t t0 = clock();
    testcase();
    clock_t t1 = clock();
    double time = (double) (t1 - t0) / CLOCKS_PER_SEC;
    printf("Time: %f\n", time);
    return 0;
}

The testcase() is where new linked lists are created and added, if you'd like to mess around with inputs, do it there!

Alongside the quality of the code, I'd also like feedback on speed and optimization, that's really the primary thing I'm usually concerned with. Also I've not used free() all that much as I was never very good with it for some reason. I'd love advice on where to use free() and how.

\$\endgroup\$
  • \$\begingroup\$ This question is being discussed on meta \$\endgroup\$ – Mast Feb 10 at 12:19
  • \$\begingroup\$ While it is true that you don't currently need the entire list of functions, you might want to create a library of functions that you could use for the future. The second thing to consider is that real code needs to be maintained because there will be feature requests. \$\endgroup\$ – pacmaninbw Feb 10 at 18:53
5
\$\begingroup\$

The answer uses this structure declared in the program:

typedef struct ListNode {
    // Basic Node data structure of a Linked List
    int val;
    struct ListNode* next;
} node_t;

Symbolic Constants for Return From main() and exit()

The program is already including <stdlib.h>. There are two system defined macros or Symbolic Constants supplied by <stdlib.h>, these are EXIT_SUCCESS and EXIT_FAILURE. These macros can also be using in C++ by including <cstdlib>.

Complexity

Several of the functions are too complex (do too much). One of the problems in these functions is that code is repeated, specifically the calls to malloc() are repeated. One basic principle in programming is Don't Repeat Yourself sometimes known as DRY code. In this case it would be better to create a function that creates a node_t struct.

node_t *createNode(int data, char *errorLocation)  // It is ok to define this function without the string errorLocation but that limits the error message below.
{
    node_t *newNode = malloc(sizeof(*newNode));
    if (newNode == NULL)
    {
        fprintf(stderr, "An error occurred while allocating memory for node_t in %s\n", errorLocation);
        exit(EXIT_FAILURE);
    }

    newNode->val = data;
    newNode->next = NULL;

    return newNode;
}

Please note that the cast to node_t* is not necessary because malloc() returns void*. It is also better to use the size of what the variable is pointing to, so that if the type of the variable is changed only one item needs to be changed on the line. It is better to print error messages to stderr, the operating system may highlight errors and error messages will be outside the flow of normal output.

When one works with linked list there are a basic set of functions that should be created:

  • node_t *createNode(int data); - shown above.
  • node_t *appendNode(node_t *newNode, node_t *listHead);
  • node_t *insertNode(node_t *newNode, node_t *listHead);
  • node_t *deleteNode(node_t *node, node_t *listHead);
  • node_t *findNode(int data, node_t *listHead);
  • void deleteList(node_t *listHead);

Using the above list of functions makes it much easier to create and manipulate linked lists.

There is also a programming principle called the Single Responsibility Principle that applies here. The Single Responsibility Principle states:

that every module, class, or function should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by that module, class or function.

Here are a few examples of the functions to be created:

node_t *appendNode(node_t* newNode, node_t* listHead)
{
    if (listHead != NULL)
    {
        node_t *head = listHead;
        while (head->next != NULL)
        {
            head = head->next;
        }
        head->next = newNode;
        return  listHead;
    }

    return newNode;
}

node_t *insertNode(node_t *newNode, node_t *listHead)
{
    newNode->next = listHead;
    return newNode;
}

node_t *createList(int data[], int length)
{
    node_t *head = NULL;
    for (int i = 0; i < length; i++)
    {
        node_t *newNode = createNode(data[i], "createList()");
        head = appendNode(newNode, head);
    }

    return head;
}

Rather than passing in a pointer to the list of items to modified, it is better for functions to return lists.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for the write up! I had 2 questions : 1) Some of the general linked lists functions (i.e insertNode, deleteNode, findNode) are out of the scope for this specific program and will never be used. Should they still be included? 2) I noticed you mentioned there are several problems regarding complexity in the code but only listed one, could you expand on that please? \$\endgroup\$ – Chase Feb 10 at 16:47
  • \$\begingroup\$ appendNode, and destroyList are both too complex. Specifically in destroyList there is no reason to malloc() new nodes. The test case would be much simpler if createList returned a list rather than passing in a list to be modified. \$\endgroup\$ – pacmaninbw Feb 10 at 18:44
  • \$\begingroup\$ Perhaps createNode(int data, const char *errorLocation)? (add const) \$\endgroup\$ – chux - Reinstate Monica Feb 11 at 11:55
3
\$\begingroup\$

The description of resvalAppend() is beside the point to the point of being misleading:

  • there is no source code entity resval
  • there is one recursive call, at most
    (serving no purpose I can discern)
  • overflow no longer is a global variable
  • added to the result Linked List better be appended to avoid confusion with the arithmetic operation at hand

(almost) keeping the interface:

#include <stdlib.h>

int resvalAppend(node_t** digits, int value, int base)
{
    /** 
    * Append one digit of value expressed in base to *digits.
    *
    * Returns value / base
    */
    div_t split = div(value, base);
    appendNode(digits, split.rem);
    return split.quot;
}
…
static const int BASE = 10;
…
    // Putting resultingValue through resvalAppend() to strip overflow
    overflow = resvalAppend(&resultList, resultingValue, BASE);
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

There's enough to review in just the appendNode() function; much of this applies to the rest of the code, too.


Don't cast the result of malloc() like this:

node = (node_t*)malloc(sizeof(node_t));

If declared properly, malloc() returns a void*; that's assignable to any pointer type. (If not declared properly, fix that first).

Also, instead of making readers check the type of node, use it as argument to sizeof. Like this:

node = malloc(sizeof *node);

In fact, node is declared but not assigned in the line above. Remove that gap, so we can't accidentally add code that uses the uninitialized value:

node_t *const node = malloc(sizeof *node);

Don't write error messages to stdout - that's for program output. Write such messages to stderr, where users expect them:

    fputs("An error occurred while allocating memory for node in appendNode\n", stderr);

(I fixed the typo in "occurred" - that sort of thing gives a bad impression.)

For larger programs, you want to return an indicator of failure, so the calling code can decide whether it can recover or alert the user. This is a good opportunity to return a pointer to the new node (or NULL on failure), so that the caller can pass that back in, and we don't have to walk the whole list every time we add a digit (that's Shlemiel the painter’s algorithm).


We point temp to some newly allocated memory, but then ignore that and point it somewhere else instead. That memory is now leaked, with no way to access or release it. Just remove that block.


Modified code

node_t *appendNode(node_t** headref, int data)
{
    node_t *const node = malloc(sizeof *node);
    if (!node) {
        return node;
    }
    node->val = data;
    node->next = NULL;

    if (!*headref) {
        *headref = node;
        return node;
    }
    node_t *temp = *headref;
    while (temp->next) {
        temp = temp->next;
    }
    temp->next = node;
    return node;
}
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

feedback on speed and optimization

O(n) to O(1).

Consider changing appendNode() from O(n) to O(1).

Rather than have a link-list point to the head, let the LL point to the tail and the tail point to the head.

To append to the end of the list or to the front is a similar O(1) operation.

// add to the end or front of the LL
void addNode(node_t** ref, int data, bool end) {
  node_t* ptr = malloc(sizeof *ptr);
  if (ptr == NULL) ...
  ptr->val = data;
  if (*ref == NULL) {
    *ref = ptr;
    ptr->next = ptr;
  } else {
    ptr->next = (*ref)->next;
    (*ref)->next = ptr;
    if (end) {
      *ref = ptr;
    }
  }
}

Functions that walk the list need to look for a repeat of the (*ref)->next rather than NULL to know when to stop.

Code can pop off the front of the list in O(1). Popping off the end of the list remains O(n).


This avoids a huge O(n) on one of the addition functions without the cost of a head and tail pointer. It provides for better distribution of activity.

I find this approach useful when code may add to the front, add to the end and remove from just one end.


Apply rather than just print

Consider a function the passes in the LL, a function pointer and state and returns error status.

int LL_apply(node_t *ref, int (*f)(void *state, node_t *node), void *state) {
  // pseudo code
  for each `node *` in LL
    int retval = f(state, node);
    if (retval) return retval;
  }
  return 0;
}

Now the print can be had with a supporting helper function f.

All sorts of functions can be applied: search, find max, average, ..., even a simple count.

| improve this answer | |
\$\endgroup\$

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.