Skip to main content

Introduction to Data Structures

A data structure is a systematic way of organizing, storing, and accessing data efficiently in computer memory. Selecting the right data structure allows you to build applications that are performant, scalable, and memory-efficient.

An algorithm is a step-by-step mathematical or logical procedure used to perform a specific task or solve a computational problem within a finite amount of time.

Together, Data Structures and Algorithms (DSA) form the building blocks of efficient software engineering.

1. Categorization by Access Pattern (Logical Layout)​

At a logical level, data structures can be classified by how their elements are traversed and accessed.

Linear Data Structures​

In a linear data structure, elements are logically arranged in a sequential sequence. Each element (except the first and the last) has a unique predecessor and successor.

  • Examples: Arrays, Linked Lists, Stacks, Queues.
  • Traversal: Elements are traversed sequentially in a single level.

Non-Linear Data Structures​

In a non-linear data structure, elements are not arranged sequentially. A single node or element can be connected to multiple other elements, forming hierarchical or network structures.

  • Examples: Trees, Graphs.
  • Traversal: Traversal is multi-level and non-sequential (e.g., depth-first or breadth-first search).

2. Categorization by Memory Storage (Physical Layout)​

At a physical level, data structures are categorized by how they occupy space in the computer's Random Access Memory (RAM).

Contiguous (Linear) Memory Storage​

Elements are stored in consecutive memory slots.

  • Primary Example: Array.
  • Key Characteristics:
    • O(1) Random Access: Accessing any element is extremely fast because its address can be calculated directly using: Address = Base Address + (Index * Element Size).
    • Fixed Size: Memory must be allocated as a single continuous block, which typically requires defining the size upfront.
    • Cache Friendliness: High cache locality because CPU caches load contiguous memory chunks.

Non-Contiguous (Dynamic) Memory Storage​

Elements are scattered in arbitrary, non-consecutive locations in memory.

  • Primary Example: Linked List.
  • Key Characteristics:
    • Dynamic Allocation: Memory is allocated on-demand (dynamically) for each individual node.
    • Pointer Overhead: Each element needs additional memory to store pointers (references) to the next element.
    • No Random Access: To access the N-th element, you must traverse all preceding N-1 elements.
    • Efficient Modifications: Inserting or deleting an element only requires updating pointers, without shifting other elements.

3. Abstract Data Types vs. Implementation​

Some data structures are Abstract Data Types (ADTs) that define behavior (what operations can be performed) rather than a concrete memory representation (how it is stored). Their physical storage depends entirely on how they are implemented.

  • Stack: Can be implemented using a contiguous array or a non-contiguous linked list.
  • Queue: Can also be implemented using an array or a linked list.
  • Trees & Graphs: While conceptually non-linear, they can be implemented using node pointers (non-contiguous) or flat arrays (contiguous, e.g., binary heaps stored in arrays).

4. Summary Matrix​

DimensionLinear Access PatternNon-Linear Access Pattern
Traversal FlowSequential (one element after another)Hierarchical or networked (multi-directional)
Memory AllocationCan be contiguous (Array) or non-contiguous (Linked List)Generally non-contiguous, connected by node references
Time ComplexityAccess: $O(1)$ for Arrays, $O(N)$ for Linked ListsAccess/Search: Typically $O(\log N)$ (Trees) to $O(N)$ (Graphs)
Common ExamplesArray, Linked List, Stack, QueueBinary Tree, BST, AVL Tree, Graph
info

KEY TAKEAWAYS

  • Logical vs. Physical: An access pattern is a logical view (how we navigate data), whereas memory storage is a physical view (how RAM stores bits).
  • Arrays are both logically linear and physically contiguous.
  • Linked Lists are logically linear but physically non-contiguous.
  • Trees and Graphs are both logically non-linear and physically non-contiguous.