Data Structures for Beginners: Arrays, Lists, Stacks, Queues, Trees and Graphs Compared

What is Data Structure?

Data Structure is a method for efficiently storing and managing data. How you organize data in a program significantly affects performance.

Why Are Data Structures Important?

// ❌ Inefficient: deleting middle element from array (O(n))
vector<int> arr = {1, 2, 3, 4, 5};
arr.erase(arr.begin() + 2);  // To delete 3, must shift all following elements
// ✅ Efficient: deleting middle element from list (O(1))
list<int> lst = {1, 2, 3, 4, 5};
auto it = next(lst.begin(), 2);
lst.erase(it);  // Just adjust pointers

The same task can be O(n) or O(1) per operation depending only on the structure behind it, and the choice also affects memory use and how simple the code is. There is a catch in this very example, though: the list’s O(1) erase assumes you already hold an iterator to the element. Getting there with next(lst.begin(), 2) walks the nodes one by one, which is O(n) again. Big-O labels describe one operation in isolation; what matters is the cost of the whole sequence of operations your program actually performs. The sections below go through the common linear and non-linear structures, compare their time complexities, and end with a selection guide and a small browser-history example.

---

Table of Contents

1. Linear Data Structures
   • Array
   • Linked List
   • Stack
   • Queue
2. Non-Linear Data Structures
   • Tree
   • Graph
   • Hash Table
3. Time Complexity Comparison
4. Practical Selection Guide

---

Linear Data Structures

Array

Stores same-type data in contiguous memory space.

#include <iostream>
#include <vector>
using namespace std;
int main() {
    // Static array
    int arr[5] = {1, 2, 3, 4, 5};
    
    // Dynamic array (vector)
    vector<int> vec = {1, 2, 3, 4, 5};
    
    // Fast access by index O(1)
    cout << vec[2] << endl;  // 3
    
    // Append at end O(1)
    vec.push_back(6);
    
    // Insert in middle O(n)
    vec.insert(vec.begin() + 2, 99);
}

Advantages:

• Fast access by index (O(1))
• Memory efficient (contiguous placement)
• Cache-friendly Disadvantages:
• Slow middle insertion/deletion (O(n))
• Size change cost (reallocation) When to Use?
• When data size is fixed
• When index access is frequent
• When sequential traversal is main operation

push_back is O(1) amortized, not in every call. When a vector runs out of capacity it allocates a larger block (typically 1.5x or 2x the old size), copies or moves every element, and frees the old block. That occasional O(n) step is spread across many cheap appends. The practical side effect is that any pointer, reference or iterator into the vector becomes invalid after a reallocation, a frequent source of crashes when code keeps &vec[0] or an iterator across a push_back. Calling reserve() up front avoids both the copies and the invalidation if you know the final size.

Contiguity is the real reason arrays win so often. The CPU loads memory in cache lines (64 bytes on common hardware) and its prefetcher detects sequential access, so scanning a vector<int> touches memory in the most favorable pattern possible.

---

Linked List

Structure where nodes are connected by pointers.

#include <list>
#include <iostream>
using namespace std;
int main() {
    list<int> lst = {1, 2, 3, 4, 5};
    
    // Insert at front O(1)
    lst.push_front(0);
    
    // Insert in middle O(1) - when iterator is available
    auto it = next(lst.begin(), 2);
    lst.insert(it, 99);
    
    // Traverse
    for (int val : lst) {
        cout << val << " ";
    }
}

Advantages:

• Fast middle insertion/deletion (O(1))
• No size limit Disadvantages:
• Slow index access (O(n))
• Extra memory needed (pointers)
• Not cache-friendly When to Use?
• When insertion/deletion is frequent
• When size is unpredictable
• When only sequential access is needed

In practice those conditions rarely justify a linked list on their own. Each node of a std::list<int> is a separate heap allocation holding the value plus two pointers, so on a 64-bit system a 4-byte integer costs 24 bytes or more before allocator overhead, and consecutive nodes can be anywhere in memory. Walking the list is a chain of dependent loads, each of which may miss the cache. For small and medium sizes, a vector that shifts elements on insert is often faster than a list that does not, because shifting contiguous memory is exactly what CPUs are good at. When I have profiled code that used std::list “because we insert in the middle”, replacing it with a vector was usually a speedup rather than a slowdown.

Linked lists earn their place when element addresses must stay stable (other structures hold pointers into them), when you splice whole ranges between lists in O(1), or when you already hold the position, as in an LRU cache where a hash map stores iterators into the list.

---

Stack

LIFO (Last In, First Out) - last in comes out first.

#include <stack>
#include <iostream>
using namespace std;
int main() {
    stack<int> st;
    
    // Insert
    st.push(1);
    st.push(2);
    st.push(3);
    
    // Remove (reverse order)
    while (!st.empty()) {
        cout << st.top() << " ";  // 3 2 1
        st.pop();
    }
}

Practical Applications:

• Function call stack
• Parenthesis checking
• Undo functionality
• DFS (Depth-First Search) Example: Parenthesis Checking

bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char top = st.top();
            st.pop();
            if ((c == ')' && top != '(') ||
                (c == '}' && top != '{') ||
                (c == ']' && top != '[')) {
                return false;
            }
        }
    }
    return st.empty();
}

The stack fits this problem because the most recently opened bracket is always the one that must close next. The two early exits matter: a closing bracket with an empty stack means there is nothing to match, and a non-empty stack at the end means some bracket was never closed. Forgetting the st.empty() check before st.top() is undefined behavior with std::stack, not an exception, so input like ")(" can crash rather than return false. Note that this version treats every non-opening character as a closer; real input with letters or spaces needs an explicit check for ), } and ].

std::stack and std::queue are container adapters: they wrap a deque by default and expose only the operations that preserve LIFO or FIFO order. That restriction is the feature. It keeps code from reaching into the middle of the structure and breaking the invariant.

---

Queue

FIFO (First In, First Out) - first in comes out first.

#include <queue>
#include <iostream>
using namespace std;
int main() {
    queue<int> q;
    
    // Insert
    q.push(1);
    q.push(2);
    q.push(3);
    
    // Remove (in order)
    while (!q.empty()) {
        cout << q.front() << " ";  // 1 2 3
        q.pop();
    }
}

Practical Applications:

• Task queue
• BFS (Breadth-First Search)
• Printer spooler
• Message queue

A queue is the natural fit for BFS because it processes vertices in the order they were discovered, which guarantees that each vertex is first reached through a shortest path in an unweighted graph. Replacing the queue with a stack turns the same loop into a depth-first traversal and loses that guarantee.

---

Non-Linear Data Structures

Tree

Represents hierarchical structure.

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// Binary search tree insertion
TreeNode* insert(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    
    if (val < root->val) {
        root->left = insert(root->left, val);
    } else {
        root->right = insert(root->right, val);
    }
    return root;
}
// Inorder traversal (sorted order)
void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

Tree Types:

• Binary Tree: Maximum 2 children
• Binary Search Tree (BST): left < parent < right
• AVL Tree: Balanced BST
• Heap: Priority queue implementation When to Use?
• Representing hierarchical structure (file system, organization chart)
• Fast search/insertion/deletion (O(log n) when balanced)
• Maintaining sorted data

The insert function above is a plain, unbalanced BST, and the O(log n) promise only holds if the tree stays roughly balanced. Insert already-sorted data (1, 2, 3, 4, …) and every new node becomes the right child of the previous one; the “tree” is a linked list with O(n) search, and the recursive functions can overflow the call stack on large inputs. This is the most common surprise when people test their first BST with sequential IDs. Self-balancing trees such as AVL and red-black trees fix it by rotating nodes during insertion; std::set and std::map are typically red-black trees, which is why they guarantee O(log n) in the worst case. Also note that nodes allocated with new here are never freed; a real implementation needs a destructor or unique_ptr children.

A heap is a tree in concept but is almost always stored in an array, with the children of index i at 2i+1 and 2i+2. It only guarantees that the top element is the largest (or smallest), not full sorted order, which is why priority_queue gives you O(1) access to the maximum and O(log n) push/pop but no way to iterate in sorted order.

---

Graph

Represents relationships with nodes (vertices) and edges.

#include <vector>
#include <queue>
using namespace std;
// Adjacency list representation
class Graph {
    int V;  // Number of vertices
    vector<vector<int>> adj;
    
public:
    Graph(int V) : V(V), adj(V) {}
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);  // Undirected graph
    }
    
    // BFS
    void BFS(int start) {
        vector<bool> visited(V, false);
        queue<int> q;
        
        visited[start] = true;
        q.push(start);
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            cout << u << " ";
            
            for (int v : adj[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    q.push(v);
                }
            }
        }
    }
};

Practical Applications:

• Social networks (friend relationships)
• Maps/navigation (shortest path)
• Web crawling (link structure)
• Dependency management

An adjacency list uses O(V + E) memory and lets you iterate over a vertex’s neighbors in time proportional to its degree, which suits sparse graphs such as road networks or social graphs. An adjacency matrix uses O(V²) memory but answers “is there an edge between u and v?” in O(1); it only makes sense for small or dense graphs. Marking a vertex as visited when it is pushed, as the code does, rather than when it is popped, prevents the same vertex from entering the queue several times.

---

Hash Table

Quickly stores/searches key-value pairs.

#include <unordered_map>
#include <iostream>
using namespace std;
int main() {
    unordered_map<string, int> ages;
    
    // Insert O(1)
    ages["Alice"] = 25;
    ages["Bob"] = 30;
    
    // Search O(1)
    cout << ages["Alice"] << endl;  // 25
    
    // Check existence
    if (ages.find("Charlie") == ages.end()) {
        cout << "Not found" << endl;
    }
}

Practical Applications:

• Caching
• Duplicate removal
• Frequency counting
• Hash indexes and hash joins in databases (most general-purpose database indexes are B-trees, because they also support range queries and sorted scans)

The O(1) figures are averages. A hash table computes a bucket from the key’s hash; when many keys land in the same bucket, lookups degrade toward O(n). That happens with a poor hash function, and it can be forced deliberately by an attacker who controls the keys, which is why some languages randomize string hashing. Growing the table also triggers a rehash of every element, a one-off O(n) pause. There is a C++-specific pitfall in the example too: ages["Alice"] inserts a default value (0) when the key is missing. Using operator[] just to check a value silently adds entries, so use find(), count() or C++20 contains() for lookups that must not modify the map.

---

Time Complexity Comparison

Data Structure	Access	Search	Insert	Delete
Array	O(1)	O(n)	O(n)	O(n)
Linked List	O(n)	O(n)	O(1)*	O(1)*
Stack	O(n)	O(n)	O(1)	O(1)
Queue	O(n)	O(n)	O(1)	O(1)
Binary Search Tree (balanced)	O(log n)	O(log n)	O(log n)	O(log n)
Hash Table	-	O(1) avg	O(1) avg	O(1) avg

*When an iterator to the position is already available. Array insert is O(1) amortized at the end, O(n) elsewhere. An unbalanced BST degrades to O(n) in the worst case, and a hash table to O(n) when many keys collide.

---

Practical Selection Guide

Recommendations by Scenario

1. Only sequential access needed

vector<int> data;  // Array is best

2. Frequent insertion/deletion

list<int> data;  // Linked list

3. Recent items first

stack<int> history;  // Stack (Undo functionality)

4. First-come-first-served

queue<Task> tasks;  // Queue (task queue)

5. Priority processing

priority_queue<int> pq;  // Heap

6. Fast search

unordered_set<int> seen;  // Hash table

7. Maintain sorted + fast search

set<int> sorted_data;  // Binary search tree

---

Practical Example: Recent Visited Pages

#include <iostream>
#include <deque>
#include <string>
using namespace std;
class BrowserHistory {
    deque<string> history;
    int current = -1;
    
public:
    void visit(string url) {
        // Remove after current position
        while (history.size() > current + 1) {
            history.pop_back();
        }
        history.push_back(url);
        current++;
    }
    
    string back() {
        if (current > 0) current--;
        return history[current];
    }
    
    string forward() {
        if (current < history.size() - 1) current++;
        return history[current];
    }
};
int main() {
    BrowserHistory browser;
    browser.visit("google.com");
    browser.visit("youtube.com");
    browser.visit("facebook.com");
    
    cout << browser.back() << endl;     // youtube.com
    cout << browser.back() << endl;     // google.com
    cout << browser.forward() << endl;  // youtube.com
}

The example is deliberately minimal. back() and forward() assume at least one visit; on an empty history history[current] with current == -1 is undefined behavior. The comparison history.size() > current + 1 mixes an unsigned size_t with a signed int, which works here only because current + 1 is never negative; compilers warn about it with -Wsign-compare, and in general it is safer to keep indices as size_t or to cast explicitly.

---

Four questions that decide the structure

1. Which operation is most frequent?
   • Access by position or full scans: array (vector)
   • Lookup by key: hash table, or a balanced tree if you also need ordering
   • Insert/remove at a position you already hold: linked list
2. How large is the data? For small collections (tens to a few hundred elements) a vector with a linear search is often fastest regardless of the Big-O labels, because constant factors and cache behavior dominate. Asymptotic differences start to matter as the size grows.
3. Is order important?
   • Insertion order: queue
   • Reverse order: stack
   • Sorted order: balanced tree (set/map); only the extreme element: heap
4. Memory constraints? Arrays have the least per-element overhead; node-based structures (lists, trees, unordered_map) pay for pointers and separate allocations per element.

When two options look equally good on paper, start with vector or unordered_map and measure with realistic data before switching.

---

Frequently Asked Questions

Q: What’s the difference between data structures and algorithms? A: Data structures are “how to store data”, algorithms are “how to process data”. They are closely related.

Q: Which data structures are most used in practice? A: Array (vector), hash table (unordered_map), and queue are most frequent.

Q: Should I implement data structures myself? A: In practice, use STL/standard libraries. But implementing yourself is important for interviews and understanding.

Q: Which data structure should I study first? A: Recommended order: Array → List → Stack/Queue → Tree → Graph.

Q. Why does the browser history example use a deque instead of two stacks?

A. Back and forward navigation can be modeled with two stacks, but the example keeps one deque plus a current index so moving back or forward is just an index change. When you visit a new page after going back, everything after current is popped from the back, which is exactly how a real browser discards the forward history. A deque fits because it supports indexed access and cheap removal at the end.

Related Articles

• Arrays vs Linked Lists for Coding Interviews
• Stacks and Queues in Interviews
• Binary Trees and BSTs
• Graph Representation: Adjacency List vs Matrix
• std::vector in Practice
• Fixing TLE: Reading Constraints and Cutting Time Complexity

---