What is Data Structure? Complete Guide from Basics to

🎯 What You’ll Learn (Reading Time: 20 minutes)

TL;DR: Completely understand data structures from basics to practice. Learn the characteristics and selection criteria of arrays, lists, stacks, queues, trees, and graphs. What You’ll Learn:

• ✅ Perfectly understand 7 basic data structures
• ✅ Master time complexity concepts O(1), O(n), O(log n)
• ✅ Acquire ability to select optimal data structure by situation
• ✅ Improve coding test and practical application skills Real-World Applications:
• 🔥 Coding tests (LeetCode, Baekjoon)
• 🔥 Algorithm interview preparation
• 🔥 Performance optimization (choosing correct data structure)
• 🔥 System design fundamentals Difficulty: Beginner | Practical Examples: 10 | Essential CS Fundamentals

---

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

Choosing the right data structure:

• ⚡ Makes execution faster
• 💾 Saves memory
• 🧹 Makes code cleaner

---

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

---

1. 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

---

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

---

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();
}

---

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

---

2. 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))
• Maintaining sorted data

---

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

---

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
• Database indexing

---

3. 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	O(log n)	O(log n)	O(log n)	O(log n)
Hash Table	-	O(1)	O(1)	O(1)
*When iterator is available

---

4. 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
}

---

Conclusion

Data Structure Selection Checklist:

1. ✅ Which operation is most frequent?
   • Access: Array
   • Insertion/Deletion: List
   • Search: Hash table
2. ✅ Data size?
   • Small: Array (cache efficiency)
   • Large: Tree/Hash
3. ✅ Is order important?
   • Insertion order: Queue
   • Reverse order: Stack
   • Sorted: Tree/Heap
4. ✅ Memory constraints?
   • Limited: Array
   • Flexible: Tree/Graph Next Steps:

• Algorithm Series - Arrays and Lists
• C++ STL Container Complete Guide
• Time Complexity Optimization Checklist

---

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.

---

Frequently Asked Questions (FAQ)

Q. When would I use this in practice?

A. What are data structures? From arrays, lists, stacks, queues, trees, to graphs.

Q. What should I read before this?

A. Follow the previous article or related articles links at the bottom of each post to learn in sequence.

Q. Where can I study this more deeply?

A. Check cppreference and the relevant library’s official documentation. The reference links at the end of the article are also worth using.

---

Related Articles (Internal Links)

Other articles related to this topic.

• 배열과 리스트 | 코딩 테스트 필수 자료구조 완벽 정리
• 스택과 큐 | 코딩 테스트 필수 자료구조 완벽 정리
• 트리 자료구조 | 이진 트리, BST, 순회 완벽 정리
• 그래프 자료구조 | 인접 리스트, 인접 행렬, 탐색 완벽 정리
• C++ std::vector Complete Guide: Usage, Iterators, and

---

Keywords Covered in This Article (Related Search Terms)

This article covers data-structure, Data Structure, array, list, stack, queue, tree, graph, algorithm, CS fundamentals.