I was trying to implement the Linked List code in C. It compiles fine but doesn't give any output. What seems to be the error? I think I messed up at passing pointer references as function parameters.
My Code (Insert At Beginning):
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
void insertBegin(Node *head, int data) {
Node *newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Out of Memory\n");
}
if (head == NULL) {
newNode->next = NULL;
} else {
newNode->next = head;
}
newNode->data = data;
head = newNode;
}
void printList(Node *head) {
Node *temp = head;
while (temp != NULL) {
printf("%d\n", temp->data);
temp = temp->next;
}
}
int main(int argc, char const *argv[]) {
Node *head = NULL;
int i;
for (i = 1; i <= 10; i++) {
insertBegin(head, i);
}
printList(head);
return 0;
}
EDIT1:
I tested the above code with valgrind and it seems the memory is being allocated properly for the 10 elements. But there is some sort of memory leak.
lulz@no-one:~/Projects/C-Cpp$ valgrind --leak-check=full ./LinkedList
==22882== Memcheck, a memory error detector
==22882== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==22882== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==22882== Command: ./LinkedList
==22882==
==22882==
==22882== HEAP SUMMARY:
==22882== in use at exit: 160 bytes in 10 blocks
==22882== total heap usage: 10 allocs, 0 frees, 160 bytes allocated
==22882==
==22882== 160 bytes in 10 blocks are definitely lost in loss record 1 of 1
==22882== at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==22882== by 0x4005CE: insertBegin (in /home/lulz/Projects/C-Cpp/LinkedList)
==22882== by 0x40068C: main (in /home/lulz/Projects/C-Cpp/LinkedList)
==22882==
==22882== LEAK SUMMARY:
==22882== definitely lost: 160 bytes in 10 blocks
==22882== indirectly lost: 0 bytes in 0 blocks
==22882== possibly lost: 0 bytes in 0 blocks
==22882== still reachable: 0 bytes in 0 blocks
==22882== suppressed: 0 bytes in 0 blocks
==22882==
==22882== For counts of detected and suppressed errors, rerun with: -v
==22882== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
EDIT2:
So I solved the problem. The final working code is given below.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node *head = NULL;
void insertBegin(Node **head_ref, int val) {
Node *newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Out of Memory\n");
}
newNode->data = val;
if (*head_ref == NULL) {
newNode->next = NULL;
} else {
newNode->next = *head_ref;
}
*head_ref = newNode;
}
void printList(Node **head_ref) {
Node *temp = NULL;
temp = *head_ref;
while (temp != NULL) {
printf("%d\n", temp->data);
temp = temp->next;
}
}
int main(int argc, char const *argv[]) {
int i;
for (i = 1; i <= 10; i++) {
insertBegin(&head, i);
}
printList(&head);
return 0;
}
Important Takeaway
C parameters are always passed by value rather than by reference. However, if you think of the address of an object as being a reference to that object then you can pass that reference by value. If you did not have pointers, then you could not "fake" pass by reference.
In the earlier version of my code, a copy of head pointer value was being sent and the nodes were created and references to head but they are all individuals. The nodes didn't form a list at all.
Another error is that I just modified a local copy of the head node. To fix this we have 3 options:
- Make the head node global
- Pass a pointer to the head node(pointer to pointer) to the function.
- Return the modified head node by the function.
Please read about Reference Semantics.