Implementation aspects: Memory representation

Definition

Memory representation is the method of organizing, storing, and accessing data elements in computer memory so that a data structure can be efficiently implemented and manipulated.

It describes:

• where data is stored,
• how elements are related in memory,
• how addresses and pointers are used,
• and how operations such as insertion, deletion, traversal, and searching are performed efficiently.

Main Content

1. Linear Memory Representation

Linear memory representation refers to storing data elements in a sequential manner, where elements are arranged one after another in memory or are logically connected in a linear order.

Contiguous and sequential storage

In arrays, elements are stored in adjacent memory locations. If the base address of the array is known, the address of any element can be calculated directly using its index. This makes access very fast.
Example:
If A[0] is stored at address 1000 and each element occupies 4 bytes, then A[3] will be at address 1000 + (3 × 4) = 1012.

Logical order in linked structures

In linked lists, elements are not stored contiguously. Instead, each node contains data and a link to the next node. The logical sequence is maintained through pointers rather than physical adjacency.
Example representation:

  HEAD -> [10 | *] -> [20 | *] -> [30 | NULL]

Here, each node may be stored in different memory locations, but the pointers create a linear arrangement.

Linear representation is used in data structures where ordering matters and operations like traversal, insertion, and deletion are common.

2. Sequential and Linked Representation

Sequential and linked representation are two major ways of implementing data structures in memory. Both are used to store collections of elements, but they differ significantly in how memory is allocated and accessed.

Sequential representation

Data items are placed in contiguous memory locations. Arrays are the best example of sequential representation. Since memory addresses are continuous, accessing an element by index is very efficient and usually takes constant time, O(1).
Advantages include simple implementation, fast indexing, and low overhead.
Limitation: size is often fixed in advance, and insertion/deletion in the middle can be costly because elements must be shifted.

Linked representation

Each element is stored in a node, and nodes are connected using links or pointers. This allows dynamic memory usage because memory can be allocated as needed.
Example:

  [5 | next] -> [15 | next] -> [25 | NULL]

Advantages include flexible size, efficient insertion/deletion when the position is known, and better memory utilization when the number of elements changes frequently.
Limitation: extra memory is needed for pointers, and direct access is not possible; traversal is required to reach a specific element.

These two representations are foundational for understanding how most data structures are built and optimized.

3. Static and Dynamic Memory Allocation

Memory representation also depends on whether memory is allocated before program execution or during program execution.

Static memory allocation

In static allocation, memory size is fixed at compile time. The data structure gets a predetermined amount of memory, and that memory cannot grow or shrink during execution. Arrays often use static allocation.
Example:
int arr[10]; allocates space for exactly 10 integers.
This is simple and fast, but it may waste memory if fewer elements are used or cause overflow if more elements are needed.

Dynamic memory allocation

In dynamic allocation, memory is requested during runtime using functions such as malloc(), calloc(), new, or similar mechanisms depending on the programming language. Linked lists, trees, and graphs often rely on dynamic allocation.
Example:
A node can be created when needed and freed when no longer used.
This is memory-efficient and flexible, but it requires careful management to avoid memory leaks, dangling pointers, and fragmentation.

Dynamic allocation is especially useful for data structures whose size changes frequently. Static allocation is suitable when the size is known in advance.

Working / Process

1. Decide the logical structure of the data

• First, identify whether the data structure is linear or non-linear, fixed-size or variable-size, and whether random access or sequential access is needed.
• This decision influences the type of memory representation to use.

2. Choose the memory allocation strategy

• If the data size is fixed and access must be fast, sequential/static representation may be chosen.
• If the data size changes often, dynamic/linked representation is better.
• The choice depends on performance requirements and available memory.

3. Store elements and maintain relationships

• In sequential representation, elements are stored in adjacent memory cells and accessed using index calculation.
• In linked representation, each node stores data plus a pointer to another node.
• Example process for a linked list insertion:
  • create a new node,
  • store data in it,
  • adjust pointers so the node becomes part of the chain.

Advantages / Applications

Improves efficiency of data access and manipulation

Proper memory representation helps achieve faster searching, easier traversal, and reduced time complexity for common operations.

Supports different types of data structures

Arrays, stacks, queues, linked lists, trees, and graphs all rely on specific memory representations that suit their behavior.

Widely used in real-world programming and system design

Memory representation is essential in operating systems, databases, compilers, embedded systems, and application development where memory usage must be carefully controlled.

Summary

• Memory representation explains how data is stored and connected in computer memory.
• Sequential and linked storage are the main implementation styles.
• Static and dynamic allocation affect flexibility and efficiency.
• Important terms to remember

Memory representation, sequential storage, linked storage, static allocation, dynamic allocation, pointer, node, address, contiguous memory, fragmentation