Why dynamic memory allocation is used in linked list

Dynamic memory allocation

Linked lists are inherently dynamic data structures; they rely on new and delete (or malloc and free) for their operation. Normally, dynamic memory management is provided by the C/C++ standard library, with help from the operating system. However, nothing stops us from writing our own allocator, providing the same services as malloc and free.

Differences between C++ and C

In C++, to dynamically allocate memory, we write newtype or newtype[size] for an array, and we get back a pointer, a type*. Internally, both of these boil down to a request for a contiguous chunk of memory of a certain size (sizeof(type) * size). In C, this is provided directly: malloc(bytes) takes a number of bytes as a parameter and returns a void* (a generic pointer) to a contiguous region of memory. Similarly, when we do delete p we are passing the pointer p to the allocator to inform it that the memory is not needed. In C, this is done via free(p). I’ll use the C versions, as they are more low level.

In C++, most standard library classes which need dynamic memory (string, vector, etc.) take a compile-time allocator parameter, which allows a different allocator to be “plugged in” to the class. In C, the standard allocator can only be replaced globally, by linking with a different allocator library.

Restrictions

When we’re writing an allocator, we must bear in mind that we are responsible for handling dynamic memory requests. This means that the allocator code should itself try to be as efficient in terms of memory as possible, and of course, the allocator cannot use any dynamic memory! Thus, although they would be useful, normal implementations of things like linked lists, trees, etc. are not possible in an allocator. We will see that something like linked lists can be used, with some care as to where the “nodes” are placed.

Fragmentation

Fragmentation refers to the tendency of the heap to go from one large available block at the beginning to many small available blocks. It may be possible that, while the total amount of memory is larger than the amount requested, no single block is big enough to satisfy it. For example, suppose we have a heap of size 20, and the following memory requests:

void* a = malloc(5); void* b = malloc(5); void* c = malloc(5); void* d = malloc(5); free(b); free(d);

There are theoretically 10 bytes of memory available, but the largest malloc we can handle is of size 5! This particular example is called external fragmentation, fragmentation where the available memory is broken into many small blocks rather than a few large ones.. There’s relatively little an allocator can do about external fragmentation, partly because we are not allowed to move existing blocks (this would require finding every pointer into that block and updating it to the block’s new location, something that is not possible in either C or C++).

(Internal fragmentation occurs when an allocator reserves more space per-block than is actually requested.)

Basic allocator functionality

The allocator maintains some internal state to keep track of free/in-use memory and responds to two kinds of requests:

• malloc(n) – A request for n bytes of contiguous memory. The allocator should return a pointer to such a block, if it has one available, or a null pointer if it does not. The block of memory should be marked as “in-use” in the allocators internal state. (Secure allocators might zero memory before giving it over, to ensure that existing data is not “leaked”.)

• free(p) – An offer to release the memory pointed to by p. The allocator should mark the memory used by p as not in-use. (Error-checking allocators might fill the memory with a recognizable byte pattern so that use-after-free errors are easy to detect.)

We assume that once a given region has been given to us (as a pointer returned from malloc) the allocator will not later give us a pointer to the same region; that is, blocks of memory returned by malloc are required to not overlap each other. Similarly, when we release a block with free, we expect that only that block will be affected. The allocator has access to a large region of memory (the heap section), which it may be able to expand via operating system request, but which is otherwise reserved entirely for the allocator’s use.

No-free allocation

The simplest possible allocator is one where we simply add each allocated block of memory immediately after the end of the previous allocation. That is, if we have the following three requests:

void* p1 = malloc(12); void* p2 = malloc(3); void* p3 = malloc(7);

then we have the following memory layout:

When memory is free-d, we do nothing. Allocated memory is never released, until the program ends. The reason why we make this choice is that keeping track of which blocks of memory are in-use and which are not requires a fair bit of complexity, so we avoid it by not doing it at all.

This allocator’s internal state is simply a pointer fp to the next free address (e.g., in the above, this would point to address 22). The implementation of malloc is thus:

void* fp = 0; // Starting address void* malloc(size_t n) { fp += n; // Reserve n bytes return fp - n; // Start of block }

while free is just

void free(void* p) { // Does nothing }

The only advantages to this allocator are that both allocation and deallocation run in \(O(1)\) time. Despite its simplicity, this “never-free” allocator can be quite useful for structures which are partially dynamic, but which are created once, at program startup, and then not freed until program end.

Note that while we can’t free individual blocks, we can free the entire heap, all at once, and revert to a state where nothing has been allocated.

Stack-based allocation

Looking at the previous allocator, we can see that there always one block of memory which we could free easily: the last one. If a free is received for the most-recently allocated block, we can deallocate it by simply decrementing fp by the size of the block. Note that we do not above store the size of the blocks anywhere, so we will need to add some extra information. At the end of each block, just after the last byte, we will write a pointer to the beginning of the block, and similarly, before the beginning of the block, we will write a pointer to the end. This allows us to navigate through the blocks as if they were a doubly-linked list.

Each block now looks like this:

Given a pointer to a block, we can find its starting record (containing its size) by simply going back 8 bytes (1 qword), and then we can find its ending record by adding the size to the pointer.

Malloc must be implemented to maintain these structures:

void* fp = 0; void* malloc(size_t n) { void* block = fp + 8; // Address of block *fp = n; // Write size record *(block + n) = fp; // Write start record fp += 8 + n; return block; }

free looks at the block being released and checks to see if it is the last block allocated; this will be the case if fp points to the address immediately after the start record of the block.

void free(void* p) { size_t n = *(p - 8); if(p + n == fp) { // Last block fp = p - 8; } else { // Not last block // Do nothing. } }

This allocator can free all the memory allocated, provided that calls to free arrive in the opposite of the order of their corresponding mallocs. If this order is not maintained, then some memory will be lost.

With a simple modification, we can allow out-of-order frees to at least partially free their memory. We will add a one-bit flag to the size record at the beginning of every block set to 0 if the block is unused, or 1 if it is used. (Although pointers are 64-bit on x86-64, the system actually only supports addresses up to 40 bits in length; thus, the high 24 bits of every pointer are available for us to use for other purposes.) When we free a block, we perform the following steps:

• If it is not the last block then we simply mark it as unused (set its in-use flag to 0).

• If it is the last block, then we free it as above, and then we repeatedly check for not-in-use blocks before it, and free those as well.

Thus, a chain of not-in-use blocks at the end of the heap will all be freed at once. Note that we still do not reuse the memory of not-in-use blocks, unless they are “really” freed. A block’s memory is only really freed if every block after it has also been freed.

A general-purpose allocator

Using the idea of blocks arranged into a linked-list-like structure, with a flag on each block for “in-use” or not, we can generalize the above to a general-purpose allocator which correctly frees memory on every free, not just those that are in the right order. This is called a free list.

Initially, we set things up so that the entire heap is treated as a single entry in the free-list, marked as not in use. Because we’re not treating the list in a stack-like manner, there’s no need for the “backwards” pointers, so each block has a small record before the beginning which consists of a pointer to the next free block. Because the list only contains free blocks, there’s no need to record whether an entry is free or in-use.

To malloc a block, we search through the list for a block whose size is at least as big as requested. Of all these blocks, we have a choice as to which one to use, determined by the allocation strategy:

• First Fit: use the first block in the list which fits

• Best Fit: use the block in the list whose size is closest to the requested size.

• Use the most/least recently free-d block (LIFO, FIFO).

If the size of the block chosen is larger than the requested size, then we split the block; part of it becomes used, and the remainder is still free. If the size of the block exactly matches the requested size, then the block is removed from the free list entirely.

When a block is freed, we add it to the list. This can be done in several ways:

• Add to the front of the list. (When used with first-fit, this results in LIFO-like behavior).

• Add to the back of the list. (FIFO)

• Insert it into the list so that the list is always ordered by address. This is most common, as the structure of the list mirrors the structure of the memory layout.

Insert-in-memory order has the advantage that it makes it relatively easy to coalesce free blocks which are physically adjacent to each other. E.g., if the free list contains an entry for a block 10-19, and an entry for a block 20-49, these should be removed and replaced with a single entry 10-49. This is easiest to detect if the blocks in the list are address-ordered.

Eager coalescing refers to coalescing done during free. Deferred coalescing is done later, either during a malloc (if no block of sufficient size is found), or perhaps during a later free.

The main disadvantage to this allocator is speed: requests for memory must traverse the list, making them run in \(O(m)\) time, where r is the number of malloc calls so far. Calls to free run in \(O(1)\), as in the worst case, only three blocks will need to be examined and coalesced.

Fixed-size allocator

If we know that every allocation request will be for a block of the same size (or we know that they will all be ≤ some maximum size, and we don’t mind wasting space), we can build a specialized version of any of the above allocators where the block size is hard-coded. We can avoid storing the block size in the records around each block, so these records become either much smaller or, in some cases, non-existent. (E.g., finding the next/previous block is easy if they all have the same size.) A fixed-size allocator is sometimes called an object pool (or memory pool), because a typical use of it is storing objects all of the same type (and hence, having the same size).

An object pool also has the advantage that an allocation for k objects takes the same amount of time as for 1 object, again, because the size of the objects is fixed.

Some allocators reserve a section of the heap for “small” object allocations, and use a fixed-size allocator only in this region, while using a more general method for the rest of the heap.

It’s also possible to reserve several regions, each dedicated to a particular size; if a free space cannot be found in a smaller-sized region, we proceed to search the next larger region.

Dynamic memory allocation

Before we dive in, check out this animated explanation of pointers. Fun!

C does not have language support for dynamically allocating new ‘things’. Instead, the programmer has to call a library function called malloc() to allocate a new chunk of memory from the heap segment, and later call free() to return that chunk of memory to the heap. The programmer has to remember to initialize the chunk of bytes received from malloc() – which otherwise should be assumed to contain random data. The programmer has to be careful allocate a large enough chunk to hold the data she intends to store there, and not to use pointers to write “outside” that chunk of memory. Lots of flexibility and power - but as with any great power, you must take great care in using it.

In Java, you can use new to dynamically create a new object, and delete to discard an object created with new, but for the most part the Java compiler and runtime handles object deletion and memory recovery automatically - it’s called ‘garbage collection.’

There are four related functions you should understand:

• malloc p = malloc(n) - allocates n bytes of heap memory; the memory contents remain uninitialized.
• calloc p = calloc(count, size) allocates count*size bytes of heap memory and initializes it all to zero; this call is appropriate when you want to allocate an array of count items, each of size bytes.
• realloc p = realloc(p, n) - where p is a pointer to heap memory - expands (or shrinks) its allocation to n bytes.
• free free(p) - where p is a pointer to heap memory - releases that portion of heap memory for future use.

Our examples today show how to use malloc to allocate space to store a string, and later, a struct holding aggregate types. For an example using calloc and realloc, read about how readlinep() works.

Memory allocation of Linked List nodes

The nodes that will make up the list’s body are allocated in the heap memory. We can allocate dynamic memory in C using the malloc() or calloc() function. malloc() takes a single argument (the amount of memory to allocate in bytes). In contrast, calloc() needs two arguments (the total number of variables to allocate in memory and the size in bytes of a single variable). malloc() does not initialize the memory allocated, while calloc() guarantees that all bytes of the allocated memory block have been initialized to 0. To deallocate the allocated memory, we can use free().

Linked lists

Introduction

Linked lists are the best and simplest example of a dynamic data structure that uses pointers for its implementation. However, understanding pointers is crucial to understanding how linked lists work, so if you've skipped the pointers tutorial, you should go back and redo it. You must also be familiar with dynamic memory allocation and structures.

Essentially, linked lists function as an array that can grow and shrink as needed, from any point in the array.

Linked lists have a few advantages over arrays:

1. Items can be added or removed from the middle of the list
2. There is no need to define an initial size

However, linked lists also have a few disadvantages:

1. There is no "random" access - it is impossible to reach the nth item in the array without first iterating over all items up until that item. This means we have to start from the beginning of the list and count how many times we advance in the list until we get to the desired item.
2. Dynamic memory allocation and pointers are required, which complicates the code and increases the risk of memory leaks and segment faults.
3. Linked lists have a much larger overhead over arrays, since linked list items are dynamically allocated (which is less efficient in memory usage) and each item in the list also must store an additional pointer.

What is a linked list?

A linked list is a set of dynamically allocated nodes, arranged in such a way that each node contains one value and one pointer. The pointer always points to the next member of the list. If the pointer is NULL, then it is the last node in the list.

A linked list is held using a local pointer variable which points to the first item of the list. If that pointer is also NULL, then the list is considered to be empty.

Let's define a linked list node:

Notice that we are defining the struct in a recursive manner, which is possible in C. Let's name our node type node_t.

Now we can use the nodes. Let's create a local variable which points to the first item of the list (called head).

We've just created the first variable in the list. We must set the value, and the next item to be empty, if we want to finish populating the list. Notice that we should always check if malloc returned a NULL value or not.

To add a variable to the end of the list, we can just continue advancing to the next pointer:

This can go on and on, but what we should actually do is advance to the last item of the list, until the next variable will be NULL.

Iterating over a list

Let's build a function that prints out all the items of a list. To do this, we need to use a current pointer that will keep track of the node we are currently printing. After printing the value of the node, we set the current pointer to the next node, and print again, until we've reached the end of the list (the next node is NULL).

Adding an item to the end of the list

To iterate over all the members of the linked list, we use a pointer called current. We set it to start from the head and then in each step, we advance the pointer to the next item in the list, until we reach the last item.

The best use cases for linked lists are stacks and queues, which we will now implement:

Adding an item to the beginning of the list (pushing to the list)

To add to the beginning of the list, we will need to do the following:

1. Create a new item and set its value
2. Link the new item to point to the head of the list
3. Set the head of the list to be our new item

This will effectively create a new head to the list with a new value, and keep the rest of the list linked to it.

Since we use a function to do this operation, we want to be able to modify the head variable. To do this, we must pass a pointer to the pointer variable (a double pointer) so we will be able to modify the pointer itself.

Removing the first item (popping from the list)

To pop a variable, we will need to reverse this action:

1. Take the next item that the head points to and save it
2. Free the head item
3. Set the head to be the next item that we've stored on the side

Here is the code:

Removing the last item of the list

Removing the last item from a list is very similar to adding it to the end of the list, but with one big exception - since we have to change one item before the last item, we actually have to look two items ahead and see if the next item is the last one in the list:

Removing a specific item

To remove a specific item from the list, either by its index from the beginning of the list or by its value, we will need to go over all the items, continuously looking ahead to find out if we've reached the node before the item we wish to remove. This is because we need to change the location to where the previous node points to as well.

Here is the algorithm:

1. Iterate to the node before the node we wish to delete
2. Save the node we wish to delete in a temporary pointer
3. Set the previous node's next pointer to point to the node after the node we wish to delete
4. Delete the node using the temporary pointer

There are a few edge cases we need to take care of, so make sure you understand the code.