Skip to main content
Commonmark migration
Source Link

A Better Abstraction

#A Better Abstraction TheThe way you have it now, a user of this linked list type has to do a bunch of work to create and maintain the list. You could make it a lot easier on a user to define a list type separate from the node type. Something like this:

Memory Management

#Memory Management YouYou are correct that not calling free() on something that you've created with malloc() is a problem. In the code you currently have, you should be freeing result and every node in the list after you're done using them. Note that that's one more thing a user of this code has to keep track of: some lists are created on the stack and some are created on the heap, and it's even possible that some nodes in the same list could be created in different places and need to be handled differently for freeing them.

#A Better Abstraction The way you have it now, a user of this linked list type has to do a bunch of work to create and maintain the list. You could make it a lot easier on a user to define a list type separate from the node type. Something like this:

#Memory Management You are correct that not calling free() on something that you've created with malloc() is a problem. In the code you currently have, you should be freeing result and every node in the list after you're done using them. Note that that's one more thing a user of this code has to keep track of: some lists are created on the stack and some are created on the heap, and it's even possible that some nodes in the same list could be created in different places and need to be handled differently for freeing them.

A Better Abstraction

The way you have it now, a user of this linked list type has to do a bunch of work to create and maintain the list. You could make it a lot easier on a user to define a list type separate from the node type. Something like this:

Memory Management

You are correct that not calling free() on something that you've created with malloc() is a problem. In the code you currently have, you should be freeing result and every node in the list after you're done using them. Note that that's one more thing a user of this code has to keep track of: some lists are created on the stack and some are created on the heap, and it's even possible that some nodes in the same list could be created in different places and need to be handled differently for freeing them.

Fixed some stuff I forgot thanks to chux comment.
Source Link
user1118321
  • 11.8k
  • 1
  • 19
  • 46

Here you'd write the create_new_list() function and the append() function that would add the new value to the end of the list. Now you don't have allocation code in a math function, and you don't need to keep track of the current node and keep incrementing it. (As pointed out by @chux, you will need some way to tell whether append() successfully allocated memory or not. I would probably have it return a boolean indicating success or failure and make sure to check it after calling.)

void free_list(IntList *list)
{
    if (list == NULL)
    {
        return;
    }
    
    IntNode* current_node = list->head;
    IntNode* next_node = NULL;
    while (current_node != NULL)
    {
        next_node = current_node->next;
        free(current_node);
        current_node = next_node;
    }
    list->head = NULL;
    list->tail = NULL;
    free(list);
}

Here you'd write the create_new_list() function and the append() function that would add the new value to the end of the list. Now you don't have allocation code in a math function, and you don't need to keep track of the current node and keep incrementing it.

void free_list(IntList *list)
{
    if (list == NULL)
    {
        return;
    }
    
    IntNode* current_node = list->head;
    IntNode* next_node = NULL;
    while (current_node != NULL)
    {
        next_node = current_node->next;
        free(current_node);
        current_node = next_node;
    }
}

Here you'd write the create_new_list() function and the append() function that would add the new value to the end of the list. Now you don't have allocation code in a math function, and you don't need to keep track of the current node and keep incrementing it. (As pointed out by @chux, you will need some way to tell whether append() successfully allocated memory or not. I would probably have it return a boolean indicating success or failure and make sure to check it after calling.)

void free_list(IntList *list)
{
    if (list == NULL)
    {
        return;
    }
    
    IntNode* current_node = list->head;
    IntNode* next_node = NULL;
    while (current_node != NULL)
    {
        next_node = current_node->next;
        free(current_node);
        current_node = next_node;
    }
    list->head = NULL;
    list->tail = NULL;
    free(list);
}
Source Link
user1118321
  • 11.8k
  • 1
  • 19
  • 46

I think you're on the right track with this, but that there are some improvements you could make.

#A Better Abstraction The way you have it now, a user of this linked list type has to do a bunch of work to create and maintain the list. You could make it a lot easier on a user to define a list type separate from the node type. Something like this:

typedef struct IntNode {
    int value;
    struct IntNode *next;
} IntNode;

and

typedef struct IntList {
    IntNode *head;
    IntNode *tail;
} IntList;

What this allows you to do is quickly insert at the head and tail, which are 2 common operations. It also means that a user of this type doesn't have to make all the links between the nodes manually.

You could add a function to create a new empty list, a function to insert an int into the list at the tail, and another to remove an int from the list. Once you have the creation and insertion functions, you don't need to put memory allocation code into the add() function. You would simply create the list at the start of the add() function, then as you go through the 2 input lists, generate the new int containing the sum, and insert it into the list. It might look something like this:

SinglyLinkedListInt *add_two_numbers(SinglyLinkedListInt *l1, SinglyLinkedListInt *l2) {
  SinglyLinkedListInt *result = create_new_list();
  if (result == NULL)
  {
    return NULL;
  }

  int carry = 0;
  while (l1 || l2 || carry) {
    int a = l1 ? l1->value : 0;
    int b = l2 ? l2->value : 0;
    int value = carry + a + b;

    append(result, value % 10);

    carry = value / 10;
    l1 = l1 ? l1->next : NULL;
    l2 = l2 ? l2->next : NULL;
  }

  return result;
}

Here you'd write the create_new_list() function and the append() function that would add the new value to the end of the list. Now you don't have allocation code in a math function, and you don't need to keep track of the current node and keep incrementing it.

#Memory Management You are correct that not calling free() on something that you've created with malloc() is a problem. In the code you currently have, you should be freeing result and every node in the list after you're done using them. Note that that's one more thing a user of this code has to keep track of: some lists are created on the stack and some are created on the heap, and it's even possible that some nodes in the same list could be created in different places and need to be handled differently for freeing them.

If they were always created on the heap, it would simplify using the type by having a free_list() function that did it for you. If you used my above suggestion about creating a separate IntList type, it might look something like this:

void free_list(IntList *list)
{
    if (list == NULL)
    {
        return;
    }
    
    IntNode* current_node = list->head;
    IntNode* next_node = NULL;
    while (current_node != NULL)
    {
        next_node = current_node->next;
        free(current_node);
        current_node = next_node;
    }
}

Then your call sequence becomes:

IntList* list = create_new_list();
// ... Add some nodes
list->append(...);
list->append(...);
//... do whatever else with the list
free_list(list);