Arrays are contiguous memory blocks with fixed size. They provide O(1) random access but O(n) insertion/deletion. Linked lists are dynamic, non-contiguous structures with nodes. They provide O(n) access but O(1) insertion/deletion at the beginning.

Key differences: Arrays are faster for access, linked lists are faster for insertion/deletion. Arrays use static memory, linked lists use dynamic memory.

A stack is a LIFO (Last In First Out) data structure. It follows the principle of "last in, first out".

Core operations:

• Push: Add an element to the top — O(1)
• Pop: Remove an element from the top — O(1)
• Peek/Top: View the top element — O(1)
• IsEmpty: Check if empty — O(1)

Real-world applications: Undo/redo operations, function call stack, expression evaluation, backtracking.

A queue is a FIFO (First In First Out) data structure. It follows the principle of "first in, first out".

Core operations:

• Enqueue: Add an element to the back — O(1)
• Dequeue: Remove an element from the front — O(1)
• Front/Peek: View the front element — O(1)
• IsEmpty: Check if empty — O(1)

Real-world applications: Print queue, CPU scheduling, breadth-first search, message queues.

Stack: LIFO (Last In First Out) — the last element added is the first removed. Think of a stack of plates.

Queue: FIFO (First In First Out) — the first element added is the first removed. Think of a line at a ticket counter.

Key operations: Stack uses push/pop, Queue uses enqueue/dequeue. Both have O(1) time complexity for core operations.

A tree is a hierarchical non-linear data structure with nodes connected by edges. It has a root node and child nodes.

Key properties:

• One root node
• No cycles (acyclic)
• Each node has a parent (except root)
• Nodes can have zero or more children

Common tree types: Binary trees, binary search trees, AVL trees, red-black trees, B-trees.

A binary search tree (BST) is a binary tree where each node has at most two children. The left subtree contains values less than the node, and the right subtree contains values greater than the node.

Key operations:

• Search: O(log n) average, O(n) worst-case
• Insert: O(log n) average, O(n) worst-case
• Delete: O(log n) average, O(n) worst-case
• Traversal: In-order, Pre-order, Post-order

Note: A balanced BST maintains O(log n) performance. Unbalanced BSTs can degrade to O(n).

A graph is a non-linear data structure consisting of vertices (nodes) and edges (connections). Unlike trees, graphs can have cycles.

Graph representations:

• Adjacency Matrix: 2D array of V×V size. O(1) edge lookup but O(V²) space.
• Adjacency List: Array of lists. O(V+E) space, efficient for sparse graphs.
• Edge List: List of all edges. Simple but slower for edge lookups.

Types of graphs: Directed vs Undirected, Weighted vs Unweighted, Cyclic vs Acyclic.

A hash table is a data structure that maps keys to values using a hash function. It provides O(1) average time complexity for insertion, deletion, and lookup.

How it works:

• The hash function converts a key to an index
• The value is stored at that index in an array
• Collisions are handled via chaining or open addressing

Key components: Hash function, array/table, collision resolution strategy.

Real-world applications: Database indexing, caching, symbol tables in compilers, associative arrays.

A heap is a specialized tree-based data structure that satisfies the heap property. It's a complete binary tree.

Types of heaps:

• Max Heap: Parent node is always greater than or equal to its children. Used for priority queues.
• Min Heap: Parent node is always less than or equal to its children. Used for Dijkstra's algorithm.

Key operations:

• Insert: O(log n)
• Extract Max/Min: O(log n)
• Peek: O(1)
• Heapify: O(n)

A trie (prefix tree) is a tree-like data structure used to store a dynamic set of strings. Each node represents a character, and paths from root to leaf form strings.

Key features:

• Fast prefix-based searching — O(L) where L is string length
• Efficient for auto-complete, spell checking
• Space-efficient for shared prefixes

Common applications:

• Auto-complete in search engines
• Spell checking and dictionary storage
• IP routing (longest prefix match)
• Word games and puzzles

Arrays and hash tables are the most important. They appear in almost every interview. Linked lists, trees, and graphs are also very common.

Practice coding problems daily, focus on understanding time/space complexity, and learn common patterns (two pointers, sliding window, DFS/BFS, dynamic programming).

Start with a working solution (even if it's brute force) and then optimize. Interviewers appreciate the ability to improve solutions iteratively.

Use the language you're most comfortable with. Python, Java, and C++ are the most common. Make sure you know the standard library well.