An Introduction to Linked Lists in C/C++

Introduction

The Problem with Arrays?

In low level languages like C/C++, if you want to store a list of related data, the instinctive choice is to use an array. When an array is created, the compiler reserves a block of memory to store the data. For instance, if we have 3000 elements of type float, the compiler computes the size of a float (4 bytes on a 32 bit system) and reserves memory to store 3000 elements of that size, each element is then laid out one after the other in memory. The compiler then only remembers the memory address of the beginning of the data block, the type of the elements and how many there are.

When it comes to retrieving data, the compiler takes that address to the beginning of the data and mathematically calculates the position of the element it needs relative to the starting address as it knows the elements are laid out one after another and knows the size of each element. A simple formula can be used:

Element Address = Array Start Address + (Element Index * Size Of Element)

For instance, to get element 100 in an array of floats, the compiler takes a pointer to the start of the array then moves the address by 100 * the size of a float element. We can visualize this in the following table that contains a representation of an array of five floats in memory. The compiler has reserved memory for the array starting at address 245:

This method of storing arrays fits in with the low level methodology of C\C++ which is to keep things efficient and minimalistic. However, there is one major drawback with this in that native C\C++ arrays cannot be resized. This means new elements cannot be added and removed on the fly.

There are often situations where you need a list data structure that, unlike C\C++ native arrays, can be dynamically resized. For instance, a booking system for a plane might need to adjust the list of seats available depending on the model of plane making the flight. Therefore, we look for other data structures that can do this, one such data structure is the linked list.

Why can't you resize arrays in C/C++? The simple logic the compiler uses to address elements in an array doesn't allow anything other than assuming that all the elements are laid out one after the other. Imagine how you would add a new element to the beginning of the array without breaking this logic. You would have to move every subsequent element down one, that is assuming there was free memory at the end of the block to accommodate this expansion. If there wasn't, you would have to then create a new array in a new memory location copying over all the existing data with the new element at the start. If array resizing operations like this were built into C\C++, their use could result in programs that involved unacceptably large amounts of time consuming memory operations.

The Linked List Data Structure

A linked list is a data structure that provides a simple but very elegant solution to this problem. There is no native 'Linked List' data type in C\C++ so you have to program your own (although there is one in the C++ standard library but more about that later).

A linked list is made up of nodes which hold the data in your list. Every linked list must have a root node which points to the first data node, each data node contains the data for that item in the list and a reference to the next node in the list. The end of the list is indicated when a node references a terminator.

The critical thing to remember about this is that each node does not have to be laid out after the previous one in memory because the design of the list incorporates a reference to the location of the next element inside its structure. This means we can add and remove elements to the list dynamically with a fraction of the memory operations that would be involved in trying to do the same thing on an array.

So now that we can visualize what a linked list data structure looks like, we can think about implementation. The most basic implementation of a linked list will involve the following operations as a minimum:

Traversing the list: You start with the root to get the first node. When you have finished on the first node, you read the reference to the next node and move onto that. This process can be repeated indefinitely until the terminator is found and is usually implemented as a loop.

Adding an Element: To add an element at a specific position requires a bit of consideration as you need to make sure you don't break the continuous nature of the list. If you insert a node, you need to record the 'next node' reference contained in the node that comes before it and use it as the 'next node' reference in the new node. You then need to overwrite the previous nodes 'next node' reference to point to your new node.

Remove an Element: When you remove a node, you need to record the 'next node' reference in the node that you are deleting and use it to overwrite the previous nodes 'next node' reference. This will again ensure the links between the nodes are not broken.

Implementation in C\C++ (Getting Started)

The C programming language has a number of features that lend themselves to implementing a linked list. Here, we look at what features we could use to represent a simple linked list. The example code has been taken from:

Data Node

A data node can be defined by a struct. Within that struct, we need to store the data for the node as well as pointer to another struct of the same type.

struct data_node
{
  data_node *NextNode; // Pointer to next node
  int MyValue; // node data.
};

Root Node

The root node can simply be implemented as a pointer to the data_node struct we previously defined.

struct data_node *RootNode;

Memory Allocation Considerations

When you add and remove nodes in C, you will need to ask the compiler for an area in memory the size of a node or deallocate the memory previously used by a node. We can do this using the sizeof(), malloc(), free() functions.

CurrentNode->NextNode = malloc(sizeof(struct data_node)); 
// allocate memory for a new node.

Armed with these basics, we can move onto implementing a fully functioning linked list in native C code including functions for traversing the list, adding nodes and removing nodes and any additional functionality required. A full implementation is beyond the scope of this introduction, but you can find plenty of examples online.

C++ Standard Library: The standard library for C++ provides access to a variety of classes and functions for use in your programs. Included are a number of data structures that you can use. A singular linked list is implemented as a container class template called forward_list and a doubly linked list as list. Developers will often use these templates as a base for their linked lists rather than writing an entire implementation from scratch to save time.