linked list


C/C++: Full example using a linked list with custom struct

The following code is an example that presents some basic functionality on simply linked lists. Specifically, it presents how to add an element to an empty list and then how to add more elements either to the start (prepend) or to the end (append) of the list.

[download id=”2444″]

We assume that our structure holds an integer and a dynamically created string, which we free after pop.

[download id=”2444″]

 

Source file (list_helpers.c)

#include <malloc.h>
#include "list_helpers.h"

void append(node_t **head, element_t *element) {

  struct node_t *new = malloc(sizeof(node_t));
  new->element = element;
  new->next = NULL;

  if (*head == NULL) {
    *head = new;
    return;
  }

  struct node_t *current = *head;

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

  current->next = new;
  return;
}

void prepend(node_t **head, element_t *element) {
  struct node_t *new = malloc(sizeof(node_t));

  new->element = element;
  new->next = *head;
  *head = new;
}

element_t *pop(node_t **head) {

  node_t *next = NULL;

  if (*head == NULL) {
    return NULL;
  }

  next = (*head)->next;
  element_t *element = (*head)->element;
  free(*head);
  *head = next;

  return element;
}

void clear(node_t **head) {
  element_t *current = pop(head);
  while (current != NULL) {
    free(current->username);
    free(current);
    current = pop(head);
  }
}

Header file (list_helpers.h)

#ifndef GM_S_LITTLE_HELPERS_LIST_HELPERS_H
#define GM_S_LITTLE_HELPERS_LIST_HELPERS_H

#ifdef __cplusplus
extern "C" {
#endif

typedef struct element_t element_t;
struct element_t {
  //We add random members to the element struct for the sake of the example
  char *username;
  unsigned int server;
};

typedef struct node_t node_t;
struct node_t {
  element_t *element;
  node_t *next;
};

void append(node_t **head, element_t *element);

void prepend(node_t **head, element_t *element);

element_t *pop(node_t **head);

void clear(node_t **head);

#ifdef __cplusplus
}
#endif

#endif //GM_S_LITTLE_HELPERS_LIST_HELPERS_H

Usage example (main.cpp)

#include <iostream>
#include "list_helpers.h"

element_t *create_user(const unsigned int server, const char *username) {

  element_t *user = (element_t *) malloc(sizeof(element_t));
  user->server = server;

  //For the sake of the example we used snprintf.
  //Upon successful return, snprintf returns the number of characters printed (excluding the null byte used to end output to strings).
  //For that reason we add one at the end of the length.
  const int length = snprintf(NULL, 0, "%s", username) + 1;
  user->username = (char *) malloc((sizeof(char) * length));
  snprintf(user->username, (size_t) length, "%s", username);
  return user;
}

int main(int argc, char *argv[]) {

  node_t *head = NULL;

  //Add the first element to the linked list
  append(&head, create_user(10, "xeirwn"));

  //Add the second element to the end of the linked list
  append(&head, create_user(12, "test"));

  //Add the third element to the end of the linked list
  append(&head, create_user(14, "banana"));

  //Add the fourth element to the beginning of the linked list
  prepend(&head, create_user(8, "apple"));

  //Popping each one to process it and then free it
  //Clearing the list
  element_t *current = pop(&head);
  while (current != NULL) {

    printf("%s\t%u\n", current->username, current->server);
    free(current->username);
    free(current);
    current = pop(&head);
  }

  //Safely clear the list. In this specific scenario it will have 0 side effects as the list was cleared above
  clear(&head);
  return 0;
}

[download id=”2444″]