When to Use These 4 Data Structures in C

Introduction

No, unfortunately we can't use arrays or lists for storing data all the time (technically we can, but it may not be just as efficient as other data structures, like linked lists, hash tables, and tries.)

This guide will count down four of the most common data structures in C, and when it's most to use them.

Arrays

• stores a number of elements consecutively in memory with either an index or a key

• bad for insertion

  • lots of shifting

  • likely requires memory allocation

• bad for deletion

  • lots of shifting

  • likely requires memory allocation

• good for lookup

  • indexing allows for random access

  • ex: can directly access the 8th element via arr[8]

• good for sorting

Linked Lists

• stores a number of nodes non-consecutively in memory, with each node containing data and a pointer to the address of the next node

• good for insertion

  • since there is no indexing, order usually doesn't matter

  • simply create a new node, set the data field to a value, set the next field to the address of the header (which is currently pointing to the previous first node), and set the header to the address of the new node

// assume node is a struct we've predefined
node* new_node = (node*)malloc(sizeof(node));
new_node->data = new_data;
new_node->next = headptr;
headptr = new_node;

• good for deletion once element is found

• bad for lookup

  • no indexing

  • requires linear search

• bad for sorting

Hash Tables

• maps keys to values (ex: dictionary / array of linked lists)

• okay for insertion

  • first, hash the element

  • second, add the element to its respective location

• good for deletion once element is found

• bad for lookup

  • better than linked lists

• bad for sorting

Tries

• stores nodes in a tree-like formation, with each node usually containing a character / string, arranged to form strings along different paths (eliminates repetition)
  

• complex for insertion

  • requires lots of dynamic memory allocation at first

  • later, as more elements appear, less allocation is needed

• good for lookup

• comes pre-sorted

Final Thoughts

Hopefully you have a better idea of the various data structures available to you in C, beyond arrays and you can find a time and place to apply them. Thanks for reading!