What Are Data Structures?
A data structure is a way of organizing and storing data so that it can be accessed and modified efficiently. Choosing the right data structure can improve the performance of an algorithm and optimize memory usage.
Types of Data Structures:
- Primitive Data Structures – Basic building blocks such as integers, floats, characters, and booleans.
- Non-Primitive Data Structures – More complex structures like arrays, linked lists, stacks, queues, trees, and graphs.
For technical interviews, non-primitive data structures are crucial because they help in solving problems related to searching, sorting, and optimizing time complexity.
Primitive vs. Non-Primitive Data Structures
Type | Examples | Description |
Primitive | int, float, char, boolean | Basic data types that store single values. |
Non-Primitive | Arrays, Linked Lists, Stacks, Queues, Trees, Graphs | Complex structures that organize multiple values efficiently. |
Since most interview questions focus on non-primitive data structures, let's dive deeper into these.
Non-Primitive Data Structures: A Deep Dive
1. Arrays
An array is a collection of elements stored in contiguous memory locations.
Key Features:
- Fixed size (static array) or resizable (dynamic array).
- Fast access via indexing (O(1) time complexity).
- Costly insertions/deletions (O(n) in worst case).
Example:
arr = [1, 2, 3, 4, 5]
print(arr[2]) # Output: 3
2. Linked Lists
A linked list is a collection of nodes where each node contains data and a reference to the next node.
Types:
- Singly Linked List
- Doubly Linked List
- Circular Linked List
Example:
class Node:
def __init__(self, data):
self.data = data
self.next = None
head = Node(1)
head.next = Node(2)
print(head.next.data) # Output: 2
3. Stacks
A stack follows the LIFO (Last In, First Out) principle.
Operations:
- Push (Add element to top)
- Pop (Remove element from top)
- Peek (View top element)
Example:
stack = []
stack.append(10) # Push
stack.append(20)
print(stack.pop()) # Output: 20
4. Queues
A queue follows the FIFO (First In, First Out) principle.
Types:
- Simple Queue
- Circular Queue
- Priority Queue
Example:
from collections import deque
queue = deque()
queue.append(1)
queue.append(2)
print(queue.popleft()) # Output: 1
5. Trees
A tree is a hierarchical data structure with nodes connected by edges.
Common Trees in Interviews:
- Binary Trees
- Binary Search Trees (BST)
- AVL Trees
- Trie
Example (Binary Tree Node):
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
6. Graphs
A graph consists of vertices (nodes) and edges (connections).
Types of Graphs:
- Directed vs. Undirected Graphs
- Weighted vs. Unweighted Graphs
Graph Representation Using Adjacency List:
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print(graph['A']) # Output: ['B', 'C']
Common Data Structures Interview Questions
Here are some frequently asked data structures interview questions:
- Arrays: Find the second largest element in an array.
- Linked Lists: Detect a cycle in a linked list.
- Stacks: Implement a stack with O(1) time complexity for min/max retrieval.
- Queues: Implement a queue using two stacks.
- Trees: Find the lowest common ancestor in a binary search tree.
- Graphs: Implement Dijkstra’s algorithm for shortest path.
Best Practices for Mastering Data Structures
- Understand the Time Complexity: Know the Big-O complexities of common operations.
- Practice Coding Daily: Use platforms like LeetCode, HackerRank, and CodeChef.
- Master Recursion: Many tree and graph problems require recursion.
- Work on Real-World Projects: Apply data structures to real-world problems.
- Study Previous Interview Questions: Review top companies’ coding interview problems.
Conclusion
This data structures tutorial covered essential concepts, focusing on non-primitive data structures that frequently appear in coding interviews. By mastering arrays, linked lists, stacks, queues, trees, and graphs, you’ll be well-prepared for technical interviews. Keep practicing and stay confident—your dream job is within reach!
If you're serious about acing technical interviews, start implementing these data structures in real-world projects today. Good luck!
