Courses / HEC NSCT – National Skill Competency Test: Complete Preparation for Computing Graduates
3.2 Linear Data Structures – Arrays, Linked Lists, Stacks, Queues
Area 3 – Data Structures & Algorithms (10%) · 45 min read · 22 MCQs to check yourself
| Structure | Idea | Access | Insert/delete | Real use |
|---|---|---|---|---|
| Array | Contiguous memory, fixed size | O(1) by index | O(n) in middle (shifting) | Lookup tables, matrices |
| Singly linked list | Nodes with data + next pointer | O(n) | O(1) at head (given position) | Dynamic lists, implementing stacks/queues |
| Doubly linked list | Next and previous pointers | O(n) | O(1) at known node | Browser back/forward, LRU cache |
| Stack | LIFO – last in, first out | top only | push/pop O(1) | Undo, function calls, bracket matching, DFS |
| Queue | FIFO – first in, first out | front only | enqueue/dequeue O(1) | Printer jobs, BFS, CPU scheduling |
| Circular queue | Rear wraps to the start | Buffers | ||
| Deque | Insert/delete at both ends | Sliding window | ||
| Priority queue | Highest priority leaves first (usually a heap) | O(log n) | Dijkstra, task scheduling |
Stack applications
- Checking balanced brackets
{[()]}. - Converting infix → postfix and evaluating postfix:
2 3 4 * += 2 + 12 = 14. - Recursion uses the call stack. Errors: popping an empty stack = underflow; pushing to a full stack = overflow.
Arrays, linked lists, stacks and queues (Alex Merced)
This lesson ends with a quiz of 22 MCQs. Open the lesson on PrepOasis to take it and save your progress.
Previous: 3.1 Asymptotic Analysis – Big-O Without Fear · Next: 3.3 Trees and Heaps