Pointers and Dynamic Linked Lists in C

One of the more awe-inspiring features of C is its use of pointers.

Pointers enable us to create complex and dynamic data structures like linked lists and binary trees. A dynamic data structure is one that can grow or shrink as needed.

Structures can contain pointers, even a pointer to another instance of the same structure.

The malloc() function allocates storage for a variable and then returns a pointer to that storage. Data objects created by malloc() can only be referenced, never named; this means we have to deal with malloc-ed memory via pointers.

#include "stdafx.h"
#include <stdlib.h>

struct dataStruct {
 int iData;
 double dData;
 struct dataStruct *structPtrNext;
};

//use the typedef to create an alias for
//a pointer to the dataStruct structure
typedef struct dataStruct* node;

int main()
{
 node currentNode;
 node startNode = (node)malloc(sizeof(dataStruct));

 startNode->iData = 73;
 startNode->dData = 3.14;
 
 startNode->structPtrNext = (node)malloc(sizeof(dataStruct));
 currentNode = startNode->structPtrNext;

 currentNode->iData = 42;
 currentNode->dData = 19.99;

 currentNode->structPtrNext = (node)malloc(sizeof(dataStruct));

 currentNode = currentNode->structPtrNext;
 currentNode->iData = 404;
 currentNode->dData = .5772;
 currentNode->structPtrNext = NULL;


 currentNode = startNode;
 while (currentNode != NULL) {
  printf("%d \t %f\n", currentNode->iData, currentNode->dData);
  currentNode = currentNode->structPtrNext;
 }


 return 0;
}

The malloc() function takes a single argument, the number of bytes to allocate. If malloc() cannot allocate the requested memory, it returns a null pointer. We can use malloc() to allocate space on an as-needed business. We use the sizeof() operator to determine the size of the structure in bytes; this is easier and less error-prone than using a hard number to allocate the bytes.

The malloc() function gets memory from the heap. To free that memory after we are finished utilizing it, we should call the clearly named free() function. The free() function takes a single argument, the pointer to the block of memory to be freed.

struct structTypeA{
 char chA;
 int iB;
};

struct structTypeB {
 double dA;
 double dB;
};

int main()
{
 printf("Sizeof structTypeA %d\n", sizeof(structTypeA));
 printf("Sizeof structTypeB %d\n", sizeof(structTypeB));

 struct structTypeA *aPtr = NULL;
 struct structTypeB *bPtr = NULL;

 //lets malloc the memory
 aPtr = (structTypeA *)malloc(sizeof(structTypeA));
 if (aPtr != NULL) {
  printf("Memory for the type A structure allocated!\n");
 }

 bPtr = (structTypeB *)malloc(sizeof(structTypeB));

 if (bPtr != NULL) {
  printf("Memory for the type B structure allocated!\n");
 }

 //lets free the memory, return it to the heap
 free(aPtr);
 aPtr = NULL;
 free(bPtr);
 bPtr = NULL;

 return 0;
}

While we do not have to set the pointer to NULL after calling free(), it is generally considered a best practice, as doing so prevents us from trying to use free memory.

Note that the structure pointer operator, ->, provides a shorthand way to access the data field of a structure being pointed to by a pointer.

A linked list is a chain of nodes in which each node points to the next one in the chain. A linked-list data structure is like an array we can grow as needed.

#include <stdlib.h>
#include <string.h>

const int string_length = 256;

struct linkedList {
 char string[string_length];
 struct linkedList *nextPtr;
};

typedef struct linkedList *list;


int main()
{
 list firstNode = (list)malloc(sizeof(linkedList));
 list nextNode = NULL;

 //set firstNode to point to NULL
 firstNode->nextPtr = NULL;
 strcpy_s(firstNode->string, string_length, "Do you have stairs in your house?");
 

 //create new node for the list
 nextNode = (list)malloc(sizeof(linkedList));

 strcpy_s(nextNode->string, string_length, "Nice boat!");
 //have the new node point to the first node
 nextNode->nextPtr = firstNode;
 //set the first or "top" node to be the new node
 firstNode = nextNode;
 //assign the new node new memory
 nextNode = (list)malloc(sizeof(linkedList));

 strcpy_s(nextNode->string, string_length, "Shaka, when the walls fell.");
 //set the new node to point to the top node
 nextNode->nextPtr = firstNode;
 //set the first node to the node
 firstNode = nextNode;

 //let's do it one more time 

 nextNode = (list)malloc(sizeof(linkedList));

 strcpy_s(nextNode->string, string_length, "For relaxing times, make it Suntory time.");
 nextNode->nextPtr = firstNode;

 firstNode = nextNode;

 while (firstNode != NULL) {
  printf("%s\n", firstNode->string);
  firstNode = firstNode->nextPtr;
 }

 return 0;
}

Of course, it’s easier if we offload some of this into some functions. One of the blessings (some say it is a curse) of dynamically allocated memory is that we are free from worrying about scope.

#include <stdlib.h>
#include <string.h>
#include <stddef.h>


const int string_length = 256;

struct linkNode {
 //unicode strings? why not!
 wchar_t string[string_length];
 struct linkNode *nxtPtr;
};

struct linkNode * initializeList(void) {
 struct linkNode *firstNode = (struct linkNode *)malloc(sizeof(linkNode));
 firstNode->nxtPtr = NULL;
 return firstNode;
}

//need to have a pointer to the pointer
//now we see the point of typedefs!
//we have to have a pointer to a pointer
//in order for the changes to persist
void addNode(struct linkNode **lPtrFirst) {
 struct linkNode *newNode = (struct linkNode *)malloc(sizeof(linkNode));
 if (newNode == NULL) {
 printf("Error allocating memory.\n");
 exit(EXIT_FAILURE);
 }
 newNode->nxtPtr = *lPtrFirst;
 *lPtrFirst = newNode;
}

int main()
{
 wchar_t answer[2];

 struct linkNode *lPtrFirst = initializeList();

 while (true) {
 printf("Please enter the text to store:\t");
 fgetws(lPtrFirst->string, string_length, stdin);

 printf("Would you like to enter another string? (y/n) \t");
 wscanf_s(L"%s", answer, 2);
 //clear buffer
 while (getwchar() != L'\n') {}
   if (answer[0] == L'n' || answer[0] == L'N') {
   break;
 }
  addNode(&lPtrFirst);
 }

 while (lPtrFirst != NULL) {
   wprintf(L"%s", lPtrFirst->string);
   lPtrFirst = lPtrFirst->nxtPtr;
 }

 return 0;
}

Binary Trees in C

A binary tree is a data structure that visually looks cool, but more importantly allows for rapid searching by the way it is structured. The hierarchical structure is analogous to the family tree model, with parents and children the branch off from parents, and one single common ancestor, the root. Ideally, if we organize the tree well, the search time for any one element or “node” in the tree should take a time of log2n.

However, in order to get this to work, the tree must be balanced with the height of the left subtrees equaling the height of the right subtrees.

A binary tree can be set up as a multiply linked list in which each node consists of a link pointing to its left child, another link pointing to its right child, and its node data.

In our free-and-easy implementation, a node with NULL pointer values for the left child and right child is a leaf node.

To dynamically create and use a node, we will first allocate memory space via the malloc() system call. Therefore, the entire binary tree can dynamically grow or shrink during the execution of the program.

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

typedef struct structNode {
 struct structNode *lChildPtr;
 struct structNode *rChildPtr;
 int iNodeData;
} sNode;

//create a new node with an int i
//data value
sNode * createNode(int i) {

 sNode *nPtr = (sNode*)malloc(sizeof(sNode));
 if (nPtr != NULL) {
 nPtr->lChildPtr = NULL;
 nPtr->rChildPtr = NULL;
 nPtr->iNodeData = i;
 return nPtr;
 }
 else {
 printf("Failed to allocated another node.\n");
 exit(EXIT_FAILURE);
 }
}

//release the memory space after it is used
void disposeNode(sNode * nPtr) {
 free(nPtr);
 nPtr = NULL;
}

int populateSubTree(int num, sNode *theNode) {
 theNode->lChildPtr = createNode(++num);
 theNode->rChildPtr = createNode(++num);
 return num;
}

//visit each node of the tree in order
//starts printing from the leftmost leaf node
//ends at the rightmost leaf node
void traverseInOrder(sNode *root) {
 if (root != NULL) {
 traverseInOrder(root->lChildPtr);
 //print root
 printf("%d\n", root->iNodeData);
 traverseInOrder(root->rChildPtr);
 }
}

//visit each node in tree
//starting from leftmost leaf node
//ending at the root of the trea
void traversePostOrder(sNode *root) {
 if (root != NULL) {
 traversePostOrder(root->lChildPtr);
 traversePostOrder(root->rChildPtr);
 //finally print root
 printf("%d\n", root->iNodeData);
 }
}



int main()
{
 int i = 1;
 sNode * rootNode = createNode(i);
 sNode * currentNode;

 i = populateSubTree(i, rootNode);
 i = populateSubTree(i, rootNode->lChildPtr);
 i = populateSubTree(i, rootNode->rChildPtr);

 
 currentNode = rootNode->lChildPtr;
 i = populateSubTree(i, currentNode->lChildPtr);
 i = populateSubTree(i, currentNode->rChildPtr);

 currentNode = rootNode->rChildPtr;
 i = populateSubTree(i, currentNode->lChildPtr);
 i = populateSubTree(i, currentNode->rChildPtr);

 printf("Traversing the tree, in order\n");
 traverseInOrder(rootNode);

 printf("\nTraversing the tree, post order\n");
 traversePostOrder(rootNode);

 return 0;
}

That’s enough for today. If you want, take a look at my book on Amazon.com http://www.amazon.com/Big-Als-C-Standard-ebook/dp/B00A4JGE0M

Dynamic Storage Allocation

The malloc() function provides dynamically-allocated storage.

The malloc() function sets aside a contiguous chunk of bytes of memory and returns the address of this chunk to be stored in a pointer.

The calloc() function sets aside a block of memory in the same fashion as malloc(), but it also zero-initializes the memory, meaning that the allocated memory is filled with 0-bits. The calloc() function also takes two arguments, whereas malloc() takes only one. The calloc() function allocates the number of bytes produced by the product of the two arguments it receives.

#include "stdafx.h"
#include <stdlib.h>

int main()
{
 //allocate 1 int's worth of memory
 int *i = (int *)malloc(sizeof(int));
 //allocate 5 double variable's worth of memory
 double *dArray = (double *)malloc(sizeof(double) * 5);

 //let's use calloc()
 char *szText = (char *)calloc(64, sizeof(char));
 int *i2 = (int *)calloc(1, sizeof(int));

 //will display 'garbage' value
 printf("Allocated with malloc(), *i = %d\n", *i);
 //will display 0
 printf("Allocated with calloc(), *i2 = %d\n", *i2);

 return 0;
}

Allocated memory storage is on the heap. Traditionally, the heap started at the low address of the process and grew upwards, whereas the stack started at a high address and grew downwards. Occasionally, a stack-heap collision would occur, where the stack or the heap grew overwrote one or the other.  As memory on modern OSes is pageable virtual memory, this is no longer a concern. At this point, even the idea of the stack growing downward and the head growing upward is conceptual rather than literal.

If the allocated memory function asks for more bytes than are available on the heap, the malloc() or calloc() function returns a NULL pointer. So, by checking the pointer with NULL, we can ensure that the memory was allocated.

#include "stdafx.h"
#include <stdlib.h>

int main()
{
 int *iPtrArray = (int*)malloc(10 * sizeof(int));

 if (iPtrArray != NULL) {
 printf("Memory allocated.\n");
 }

 return 0;
}

When allocated memory has been used and is no longer needed, we can return it to the heap with the free() function. Memory that has been allocated dynamically should be free, otherwise we will end up with memory leaks.

Now, when a process ends, all of the memory is reclaimed by the system . Therefore, it is not necessarily a big deal if we do not call free() in the small programs we have been writing. However, it’s best to maintain the ironclad habit of free-ing all memory that has been dynamically allocated.

 #include "stdafx.h"
#include <stdlib.h>

int main()
{
 double *dPtrArray = (double *)malloc(sizeof(double) * 5);

 if (dPtrArray != NULL) {
 printf("Memory allocated!\n");
 }

 //free the memory
 free(dPtrArray);
 dPtrArray = NULL;

 return 0;
}

After calling free on a pointer, we should consider the pointer to have an undefined value. Setting the value of the pointer to NULL explicitly is a good practice. A dangling pointer can result if we try to access deallocated memory via a pointer.