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 visualise 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++ there 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 visualise 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 insure 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 lists. Here we look at what
features we could use to represent a simple linked list. The example code has been taken from:
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.
data_node *NextNode; int MyValue; };
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
CurrentNode->NextNode = malloc(sizeof(struct data_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
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.