/* 08dec04 John Pfeiffer example of using dynamic memory allocation for a linked list
This example uses root/parent node and child nodes in a double linked list
updated 15jun08 with freemem
*/
#include <stdio.h>
#include <stdlib.h>
#define MAX_NUMBER_OF_NODES 4 /* the max # of nodes, including the root */
typedef struct node tnode;
typedef struct node* nodeptr;
struct node /*note this is a doubly linked list (forward & back!) */
{ int node_id;
nodeptr next;
nodeptr prev;
};
nodeptr talloc(void) /* allocate space in memory for the size of the structure */
{ return( (nodeptr)malloc( sizeof( struct node)) ); }
nodeptr create_node(nodeptr parent)
{
nodeptr newnode = talloc();
newnode->node_id = (parent->node_id) + 1; /* number our node as parent# + 1*/
newnode->prev = parent;
newnode->next = NULL;
return newnode;
}/* end create_node function */
void forward_traversal( nodeptr current )
{
do{ printf("Node #%d -> ",current->node_id);
current = current->next;
}while( current != NULL );
printf("NULL");
}/* end forward_traversal function */
void reverse_traversal( nodeptr current )
{
while( current->next != NULL) /* find the last node */
{ current = current->next; }
do{
printf("Node #%d -> ",current->node_id);
current = current->prev; /* travel the list backwards */
}while( current != NULL );
printf("NULL");
}/* end reverse_traversal function */
void free_list( nodeptr current )
{
nodeptr temp;
do{
temp = current;
current = current->next;
free( temp );
printf(".");
}while( current != NULL );
}/* end reverse_traversal function */
/* MAIN ***************************************************************************/
int main(int argc, char* argv[])
{
nodeptr current; /* to traverse the list */
nodeptr root = talloc();
root->node_id = 1; /* To count the nodes */
root->prev = NULL; /* so backwards traversal doesn't crash the program */
root->next = NULL;
current = root;
printf("\nListing elements from root down (only root exists)\n");
forward_traversal( root );
/* for( current = root, k=0; current->i <MAX; k++, current=current->next)
for(current = root; current != NULL; current = p)*/
while( (current->node_id) < MAX_NUMBER_OF_NODES )
{
current->next = create_node(current); /* create a new child node from parent node */
current = current->next;
}
printf("\n\nListing elements from root to the last element (MAX=%d)\n",MAX_NUMBER_OF_NODES);
forward_traversal( root );
printf("\n\nListing elements from the last node back to the root\n");
reverse_traversal( root );
printf("\n\nFreeing memory from all elements in the list: ");
free_list( root );
return 0;
}/* end of main */