Skip to main content

Linked List

Introduction​

This document describes an implementation of the malloc function using a linked list of memory blocks.
The core idea is to represent memory as a sequence of blocks, each one holding metadata and user data.

Main characteristics:

  • Fast allocation with first-fit strategy.
  • Suffers from fragmentation and poor memory efficiency.

Linked-list Structure​

Linked-list

Management of Memory​

Allocation​

  1. User requests malloc(s).
  2. Traverse the linked list and find the first block with size ≥ s + metadata_size (first-fit).
  3. If the block is larger than needed:
    • Split it into two:
      • One block with exactly s bytes for the user.
      • Another block containing the remaining free space.
  4. Return the address of the block and mark it as used.

Alternative: best-fit strategy, which searches for the block that best matches the requested size (less wasted space, but slower).

Free​

  1. Mark the block as free.
  2. To reduce fragmentation, attempt to merge neighboring free blocks (fusion operation).
  3. If the whole page is free, it can be unmapped.

Metadata​

Each block contains metadata before the user’s data. Typical fields include:

  • Block status (allocated/free).
  • Block size.
  • Pointer to the next block.
  • Pointer to the previous block if needed.

Video example of a linked list implementation​

warning

For this representation, you need to be good at handling raw pointers. Undefined behaviors can quickly occur.