Data Structures Explained: Arrays, Linked Lists, Trees & Graphs

Introduction: Why Data Structures Matter

Imagine trying to find a book in a library where every book is scattered randomly on the floor. Finding your book would take forever. But if the library organises books by genre, author, and title — your search becomes instant.

That is precisely what data structures do for your programs. They organise data so it can be accessed, processed, and stored as efficiently as possible. Whether you are building a calculator or a large-scale platform like Facebook, your choice of data structure directly affects speed, memory usage, and overall performance.

In this tutorial, you will learn the four most important data structures every programmer must know — with real code, complexity analysis, and the real-world contexts where each shines.

1. Arrays: The Foundation of All Data Structures

What is an Array?

An array is the simplest and most widely used data structure. It stores a collection of elements in contiguous (adjacent) memory locations, where each element is identified by a zero-based index.

Think of an array as a row of numbered mailboxes. Each mailbox has a unique number (its index), and you can go directly to any mailbox if you know its number. This is why arrays support random access — retrieving any element takes the same time regardless of array size.

How Arrays Work in Memory

When you declare an array, the program reserves a fixed block of contiguous memory. Because every element occupies the same space, the exact address of any element can be calculated instantly:

// Address formula
Address of arr[i] = Base Address + (i × element size)

int arr[5] = {10, 20, 30, 40, 50};
// arr[0] → 10  (O(1) access)
// arr[2] → 30  (O(1) access)
// arr[4] → 50  (O(1) access)

Time & Space Complexity

Real-World Applications

• Image processing — a digital image is a 2D array of pixel values
• Spreadsheets — Excel cells are stored as a 2D array of rows and columns
• Machine learning — tensors (multi-dimensional arrays) power neural networks
• Hash tables — arrays are the underlying structure of most hash maps

2. Linked Lists: Dynamic and Flexible Storage

What is a Linked List?

Unlike arrays, a linked list does not store elements in contiguous memory. Instead, it is made up of nodes, where each node contains the actual data and a pointer to the next node in the sequence.

A good analogy is a treasure hunt. Each clue (node) contains a piece of treasure (data) and a hint about where to find the next clue (pointer). You cannot skip directly to clue 5 — you must follow the chain from the beginning. This is why linked lists do not support direct random access.

struct Node {
    int   data;   // The actual value
    Node* next;   // Pointer to next node
};

// Building: 10 → 20 → 30 → NULL
Node* head = new Node{10, nullptr};
head->next          = new Node{20, nullptr};
head->next->next    = new Node{30, nullptr};

Types of Linked Lists

• Singly Linked List — each node points only to the next; traversal in one direction only
• Doubly Linked List — each node has both a next and a previous pointer, enabling bidirectional traversal
• Circular Linked List — the last node points back to the first, forming a loop; used in round-robin scheduling

Arrays vs Linked Lists at a Glance

Real-World Applications

• Browser history — forward/back navigation uses a doubly linked list
• Music players — previous/next track is a classic doubly linked list operation
• Undo/redo — text editors store states as a linked list of history snapshots
• Memory allocation — operating systems track free memory blocks using linked lists

3. Trees: Hierarchical Structures for Organised Data

What is a Tree?

Up to this point, we have examined linear structures. Now it is time to move into non-linear territory. A tree is a hierarchical data structure that resembles an upside-down real tree — with a root at the top and branches extending downward to leaves.

More formally, a tree is a collection of nodes connected by directed edges where: there is exactly one root, every non-root node has exactly one parent, and there are no cycles.

Binary Search Tree (BST)

The Binary Search Tree is the most important tree type. Each node has at most two children. Its golden rule: all values in the left subtree are smaller; all values in the right subtree are larger. This ordering allows you to eliminate half the possibilities at every step.

struct TreeNode {
    int       data;
    TreeNode* left;   // smaller values
    TreeNode* right;  // larger values
};

// Visual BST:
//      10         ← Root
//     /  \
//    5    15      ← Level 1
//   / \    \
//  3   7   20     ← Leaves

Tree Traversal Methods

BST Time Complexity

Other Important Tree Types

• AVL Tree — self-balancing BST; guarantees O(log n) always
• Red-Black Tree — used inside Java's TreeMap and C++'s std::map
• Heap — complete binary tree; implements priority queues
• Trie — tree for fast string search; powers autocomplete
• B-Tree / B+ Tree — used in database indexing and file systems

Real-World Applications

• File systems — directories are trees (Windows Explorer, Linux)
• HTML/DOM — browsers represent web pages as a tree of elements
• Databases — MySQL, PostgreSQL use B-Trees for indexing
• Compilers — Abstract Syntax Trees (ASTs) represent source code structure
• AI/ML — Decision trees are core classification algorithms

4. Graphs: The Most Powerful Data Structure

What is a Graph?

A graph is the most versatile data structure in computer science. In fact, a tree is a special type of graph. A graph is a collection of vertices (nodes) and edges (connections), where edges can represent any kind of relationship — friendship, road, dependency, hyperlink.

Unlike trees, graphs have no strict hierarchy. A node can connect to any number of others, connections can be bidirectional, and cycles are allowed. This flexibility makes graphs the perfect model for real-world networks.

Graph Representations

Adjacency Matrix

A 2D array where matrix[i][j] = 1 means an edge exists from vertex i to j. Simple, but uses O(V²) space — wasteful for sparse graphs.

Adjacency List (preferred)

Each vertex stores a list of its neighbours. Space-efficient at O(V + E) and preferred in most real-world applications.

#include <vector>
vector<int> adj[4];

adj[0] = {1, 3};  // 0 connects to 1 and 3
adj[1] = {0, 2};  // 1 connects to 0 and 2
adj[2] = {1, 3};  // 2 connects to 1 and 3
adj[3] = {0, 2};  // 3 connects to 0 and 2

Graph Traversal Algorithms

Real-World Applications

• Google Maps — cities are vertices, roads are weighted edges; Dijkstra finds the shortest route
• Social networks — Facebook's friends graph, LinkedIn's professional connections
• The web — the World Wide Web is a directed graph of pages linked by hyperlinks
• Recommendation engines — Netflix and Amazon use graph-based collaborative filtering
• Fraud detection — banks analyse transaction graphs for suspicious patterns

5. Complete Comparison: Choosing the Right Structure

Now that you understand all four structures, the key skill is knowing which to choose for a given problem. Use this table as your decision guide:

6. Interview Questions You Must Know

Data structure questions are a staple of technical interviews at Google, Amazon, Microsoft, and Meta. Here are the most important ones, grouped by topic:

Conclusion: Your Learning Roadmap

Congratulations on completing this guide! You now have a solid foundation in all four core data structures. As a next step, practise implementing each from scratch and solve problems on LeetCode, HackerRank, or GeeksforGeeks.