Quick Index
Overview


In this section we'll look at memory usage for a linked list.

Note that we are not talking about Big-O algorithm space complexity analysis, but rather memory usage by the structure.

Wasted Space


When we say "wasted space" will mean space in computer memory that is part of the structure and not the data.

We will assume each linked list node has three pointers (prevNode, nextNode, data).

Let us assume each pointer is 8 bytes (64 bits). Then we have:

3 * 8 = 24 bytes of wasted space per data element in a linked list.

When to Analyze Wasted Space


The problem and the target hardware will dictate if wasted space need be considered. Here are a couple reasons that would drive us to analyze wasted space:


Data (Element) Size


Let us assume for both of the cases below that we know that memory usage is something that needs to be considered.

Large Data Elements


It is common that data size is much larger than "wasted space".

If our structure contains "customers", and for example purposes, we estimate "Customer" objects average 2500 bytes each, then the wasted space (24/2500) is less than 1% of the data memory use, and thus becomes a minor factor.

In this case, we would generally not perform a "wasted space" analysis. (naturally there are always exceptions if later in the project we are desperate to find ways to save even small amounts of memory usage -- then we may undertake the analysis)

Small Data Elements


However, if we have a specific case where each data elements are relatively small, then may want to consider wasted space.

If our structure contains "lines", and for example purposes, we estimate "Line" objects average 48 bytes each, then the wasted space (24/48) is almost 50% of the data memory use.

In this case, we would want to do a memory space analysis.