Linear Data Structures: Arrays, Stacks, Queues & Linked Lists: quick revision, 18 bites

Linear Data Structures: One After Another

Elements stand in a line, not a web.

A **linear data structure** stores elements sequentially, so each element has at most one predecessor and one successor.

Takeaway. Linear structures trade flexibility for simplicity — traversal is one-directional and predictable.

Array: Contiguous Memory Blocks

Same type, side by side, instant access.

Takeaway. Arrays give the fastest read access but the slowest insert/delete among linear structures.

Sparse Matrix: Mostly Zeros

When most entries are zero, store smart.

A **sparse matrix** has far more zero elements than non-zero ones. Storing it as a full 2D array wastes memory.

Takeaway. Sparse matrix representation stores only meaningful (non-zero) data, cutting memory waste.

Stack: Last In, First Out

The last plate placed is the first removed.

Takeaway. Stacks restrict access to one end, making them perfect for reversal and backtracking problems.

Stack Operations: Step by Step

Push, pop, peek — three moves only.

Takeaway. Every stack operation revolves around the top pointer — guard against overflow and underflow.

Polish & Reverse Polish Notation

No brackets needed — just order.

Takeaway. Stacks are the engine behind expression conversion and evaluation in compilers.

Recursion & Tower of Hanoi

Stacks hide inside every recursive call.

Takeaway. Recursion uses the call stack implicitly — Tower of Hanoi shows why stack-based thinking solves recursive problems.

Queue: First In, First Out

First in line gets served first.

Takeaway. Queues model fairness — whoever arrives first is served first.

Simple Queue vs Circular Queue

Wasted space? Go circular.

Takeaway. Circular queues solve the false-overflow problem of simple array-based queues.

Priority Queue & Deque

Not all elements are equal.

Takeaway. Priority queues add urgency ordering; deques add two-ended flexibility.

Where Queues Are Used

Printers, CPUs, and ticket counters.

Takeaway. Anywhere fairness or order-of-arrival matters, a queue is the go-to structure.

Linked List: Nodes & Pointers

No fixed size, just links.

Takeaway. Linked lists trade random access for dynamic size and efficient insertion/deletion.

Array vs Linked List

Fixed and fast vs flexible and linked.

Takeaway. Choose arrays for fast reads, linked lists for frequent insertions and deletions.

Linked Implementation of Stack & Queue

No overflow when you use nodes.

Takeaway. Linked implementations remove the size ceiling that array-based stacks and queues face.

Real-World Uses of Linked Lists

From music playlists to browser history.

Takeaway. Linked lists power any system that needs dynamic, order-preserving navigation.

Stack Overflow vs Underflow

Push on full? Pop on empty? Crash.

Takeaway. Guard every stack operation with a boundary check — overflow and underflow are the two classic stack bugs.

Exam Favourites in Linear DS

These questions repeat every year.

Takeaway. Master step-by-step traces and comparison tables — they carry the most marks.

LIFO vs FIFO in One Line

Stack stacks, queue queues.

**Stack = LIFO** (Last In, First Out) — like a stack of plates. **Queue = FIFO** (First In, First Out) — like a line at a ticket counter.

Takeaway. If you remember the physical object, you remember the order.