Here is my code for implementing an adjacency list from scratch. I would like to get feedback from the experts for optimization.

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

/*a single node of an adjacency list*/

int dest;

/*Image of a graph...*/

typedef struct Image{

int source;

} Image;

void initialize_graph(Image *graph, int vertices);

void print_graph(Image graph[], int vertices);

void free_graph(Image graph[], int vertices);

int main() {

int vertices;
scanf("%d", &vertices);

Image graph[vertices];

printf("size of graph: %d bytes\n", sizeof graph);

initialize_graph(graph, vertices);

printf("initialized image of graph\n");

print_graph(graph, vertices);

printf("                          \n");
//is the graph directed ? ans: false

print_graph(graph, vertices);

free_graph(graph, vertices);

/*if this print produces segmentation fault then the memory is fully freed*/

return 0;
}

void initialize_graph(Image graph[], int vertices) {

for(int i = 1; i<= vertices; i++){
graph[i].source = i;
}

return;
}

/*create a single node*/
cache->dest = dest;
cache->next = NULL;

}

else{

while( crawler->next != NULL){
crawler = crawler->next;
}

this will also link src -> dest*/

crawler->next = cache;
}

if (directed == false) {
directed = true;

/*notice we've changed the sequence. dest and src*/
}

return;
}

void print_graph(Image *graph, int vertices){

for(int i = 1; i<= vertices; i++){

printf("node: %d    ", graph[i].source);

while(crawl){

printf("%d ", crawl->dest);
crawl = crawl->next;
}

printf("\n");
}

return;
}

/*just a reverse version of crawling a graph*/

void free_graph(Image *graph, int vertices){

for(int i = 1; i<= vertices; i++){

printf("releasing elements of node: %d    ", graph[i].source);

/*put the next adjacency node in the cache*/
}

printf("\n");
}

return;
}


• Out-of-bounds access: an array

Image graph[vertices];


has vertices entries, starting with index 0, with the largest valid index being vertices - 1. The loop

for(int i = 1; i<= vertices; i++)


touches graph[vertices], which is illegal. A correct (and idiamatic) loop is

for(int i = 0; i < vertices; i++)

• Testing for memory correctly released via inducing a segfault is, to put it mildly, unconventional. You are not even guaranteed to get one.

• Crawling the list is a waste of time. It is much simpler to prepend the newly created node at the head of the list:

void add_adj_node(Image *graph, int src, int dest, bool directed)
{
}

• Recursive invocation of add_adj_node is confusing. I recommend to have a helper function do_add_adj_node and invoke it like this:

void add_adj_node(Image *graph, int src, int dest) {
}

• So, how can I confirm that the memory is cleared perfectly ? Nov 22, 2016 at 20:18
• @ph03n1x Nothing you can do from inside the program, at least portably. Use external tools like valgrind.
– vnp
Nov 22, 2016 at 21:30
• Hmm heard about the tool. I'll try it Nov 22, 2016 at 21:44

There are so many blank lines, look at how you have to scroll so much in order to read the code!

It is fine to have the occasional blank line in order to separate groups of statements within a function, or to separate functions by one or two blank lines. But gaps of more than two lines are just unnecessary in my opinion.

Here is how I would render the code. I've changed nothing except deleting 46 blank lines, which were about a quarter of all the original lines!

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

/*a single node of an adjacency list*/
int dest;

/*Image of a graph...*/
typedef struct Image{
int source;
} Image;

void initialize_graph(Image *graph, int vertices);
void print_graph(Image graph[], int vertices);
void free_graph(Image graph[], int vertices);

int main() {
int vertices;
scanf("%d", &vertices);

Image graph[vertices];
printf("size of graph: %d bytes\n", sizeof graph);

initialize_graph(graph, vertices);
printf("initialized image of graph\n");

print_graph(graph, vertices);
printf("                          \n");
//is the graph directed ? ans: false

print_graph(graph, vertices);

free_graph(graph, vertices);

/*if this print produces segmentation fault then the memory is fully freed*/

return 0;
}

void initialize_graph(Image graph[], int vertices) {
for(int i = 1; i<= vertices; i++){
graph[i].source = i;
}

return;
}

/*create a single node*/
cache->dest = dest;
cache->next = NULL;

}
else{

while( crawler->next != NULL){
crawler = crawler->next;
}
this will also link src -> dest*/
crawler->next = cache;
}

if (directed == false) {
directed = true;
/*notice we've changed the sequence. dest and src*/
}

return;
}

void print_graph(Image *graph, int vertices){
for(int i = 1; i<= vertices; i++){
printf("node: %d    ", graph[i].source);

while(crawl){
printf("%d ", crawl->dest);
crawl = crawl->next;
}
printf("\n");
}

return;
}

/*just a reverse version of crawling a graph*/
void free_graph(Image *graph, int vertices){
for(int i = 1; i<= vertices; i++){
printf("releasing elements of node: %d    ", graph[i].source);