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;
}
Advertisements

One thought on “Pointers and Dynamic Linked Lists in C

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s