my destroy_list(pHead1_reversed) and destroy_list(pHead2_reversed) function in my list_sum function doesn't seem to be freeing up the nodes. I'm getting a memory leak. What am I doing wrong?
int main(int argc, char* argv[])
{
//add up 189 + 11
Node* head1 = NULL;
Node* head2 = NULL;
Node* head_sum = NULL;
//create a list for the number 189
head_insert(&head1, 9);
head_insert(&head1, 8);
head_insert(&head1, 1);
//create a list for the number 11
head_insert(&head2, 1);
head_insert(&head2, 1);
head_sum = list_sum(head1, head2);
printf("The sum of ");
print_list(head1);
printf(" + ");
print_list(head2);
printf("\n");
printf(" = ");
print_list(head_sum);
printf("\n");
//clean up three lists
destroy_list(head1); head1 = NULL;
destroy_list(head2); head2 = NULL;
destroy_list(head_sum); head_sum = NULL;
return 0;
}
**********************************************************************
void head_insert(Node** hHead, int newItem)
{
Node* pNode = NULL;
pNode = (Node*)malloc(sizeof(Node));
if (pNode == NULL)
{
printf("malloc failed for node \n");
exit(1);
}
pNode->data = newItem;
pNode->next = *hHead;
*hHead = pNode;
}
void destroy_list(Node* hHead)
{
Node* current = hHead;
Node* next;
while (current != NULL) {
next = current->next;
free(current);
current = next;
}
}
Node* list_sum(Node* hHead1, Node* hHead2)
{
Node* pHead1_reversed=reverse(hHead1);
Node* pHead2_reversed=reverse(hHead2);
Node* result_reversed;
Node* resultHead = NULL;
int carry = 0;
while (pHead1_reversed != NULL || pHead2_reversed != NULL || carry != 0) {
int digit1 = (pHead1_reversed != NULL) ? pHead1_reversed->data : 0;
int digit2 = (pHead2_reversed != NULL) ? pHead2_reversed->data : 0;
int sum = digit1 + digit2 + carry;
carry = sum / 10;
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("malloc failed for result node \n");
exit(1);
}
newNode->data = sum % 10;
newNode->next = NULL;
if (resultHead == NULL) {
resultHead = newNode;
}
else {
Node* temp = resultHead;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
if (pHead1_reversed != NULL) pHead1_reversed = pHead1_reversed->next;
if (pHead2_reversed != NULL) pHead2_reversed = pHead2_reversed->next;
}
destroy_list(pHead1_reversed);
destroy_list(pHead2_reversed);
result_reversed = reverse(resultHead);
destroy_list(resultHead);
return result_reversed;
}
void print_list(Node* hHead)
{
Node* pHead = (Node*)hHead;
printf("*******\n");
while (pHead != NULL)
{
printf("%d\n", pHead->data);
pHead = pHead->next;
}
printf("*******\n");
}
Node* reverse(Node* hHead)
{
Node* resultHead = NULL;
Node* next;
while (hHead != NULL) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("malloc failed for result node \n");
exit(1);
}
newNode->data = hHead->data;
newNode->next = resultHead;
resultHead = newNode;
hHead = hHead->next;
}
return resultHead;
}
Tried setting pHead2_reversed to NULL and it did not work. Also tried freeding the nodes directly in the reverse function instead of using the function call. The top is my main driver file and the bottom is the function implementation file.
You're leaking memory in list_sum:
Although you have:
destroy_list(pHead1_reversed);
destroy_list(pHead2_reversed);
...these pointers are not pointing to the heads of these reversed lists, since you moved them forward in the preceding loop:
if (pHead1_reversed != NULL) pHead1_reversed = pHead1_reversed->next;
if (pHead2_reversed != NULL) pHead2_reversed = pHead2_reversed->next;
You'll have to keep a reference to these heads before looping, and then free the lists starting from those head nodes.
You can better avoid this from happening by defining a separate type (struct) for a linked list, which would have as member the head of the list. This would make it easier to guarantee that this head really is the head of the linked list. The function to free a linked list would be distinct from the function that frees a single node.
Secondly, it is not efficient if in reverse you have to find the end of the list each time to append to the result list, only to reverse that list at the end. More efficiently is to create the result in the right order immediately, by inserting the sum-digits at the front of the result list.
You could also destroy the reversed lists at the same time you build the sum: during that same loop. This can lead to quite elegant code.
It is also good practice to have only one function that allocates a node. Currently this code is spread in three locations.
Here is some code showing how it could be done taking the above remarks into consideration:
#include <stdio.h>
#include <stdlib.h>
//////////////////////// Node /////////////////////////////////
typedef struct node {
int data;
struct node *next;
} Node;
Node* create_node(int data, Node *next_node) {
Node* node = malloc(sizeof(*node));
if (node== NULL) {
printf("malloc failed for creating node with data %d\n", data);
exit(1);
}
node->data = data;
node->next = next_node;
return node;
}
Node* destroy_node(Node* node) // Returns the successor
{
Node* next = node->next;
free(node);
return next;
}
//////////////////////// Linked List /////////////////////////////////
typedef struct linkedlist {
Node *head;
} LinkedList;
LinkedList* create_list() {
LinkedList* list = malloc(sizeof(*list));
if (list == NULL) {
printf("malloc failed for creating list\n");
exit(1);
}
list->head = NULL;
return list;
}
int list_is_empty(LinkedList *list) {
return list->head ? 0 : 1;
}
int list_pop_head(LinkedList *list, int defaultValue)
{
if (list_is_empty(list)) {
return defaultValue;
}
int data = list->head->data;
list->head = destroy_node(list->head);
return data;
}
void destroy_list(LinkedList *list)
{
while (!list_is_empty(list)) {
list_pop_head(list, 0);
}
}
void list_insert_head(LinkedList *list, int data)
{
list->head = create_node(data, list->head);
}
LinkedList* list_reverse(LinkedList* list)
{
LinkedList *result = create_list();
for (Node* node = list->head; node; node = node->next) {
list_insert_head(result, node->data);
}
return result;
}
LinkedList* list_sum(LinkedList* list1, LinkedList* list2)
{
LinkedList* reversed1 = list_reverse(list1);
LinkedList* reversed2 = list_reverse(list2);
LinkedList* result = create_list();
int carry = 0;
while (!list_is_empty(reversed1) || !list_is_empty(reversed2) || carry) {
int sum = list_pop_head(reversed1, 0) + list_pop_head(reversed2, 0) + carry;
carry = sum / 10;
list_insert_head(result, sum % 10);
}
return result;
}
void list_print(LinkedList* list)
{
for (Node* node = list->head; node; node = node->next) {
printf("%d -> ", node->data);
}
printf("NULL\n");
}
int main(int argc, char* argv[])
{
//add up 189 + 11
LinkedList* list1 = create_list();
LinkedList* list2 = create_list();
//populate a list for the number 189
list_insert_head(list1, 9);
list_insert_head(list1, 8);
list_insert_head(list1, 1);
//populate a list for the number 11
list_insert_head(list2, 1);
list_insert_head(list2, 1);
LinkedList *head_sum = list_sum(list1, list2);
printf("The sum of\n");
list_print(list1);
printf("+\n");
list_print(list2);
printf("=\n");
list_print(head_sum);
//clean up three lists
destroy_list(list1);
destroy_list(list2);
destroy_list(head_sum);
return 0;
}