Data Structures — Class 12 ISC Computer Science revision notes
A 3-page visual revision sheet for Data Structures, written for Class 12 ISC Computer Science. Formulas, diagrams and the traps that cost marks, laid out to be read the night before rather than the term before. Free, and it opens inside CapCompass.
Page 1 as PDF
Data Structures in one look
arrays, the stack, the queue, and the linked list, as ways to hold data
The array, the data structure you already have
- an array is already a data structure: a fixed number of slots, all the same type, reached directly by index
- reaching any slot by its index takes the same effort no matter how big the array is, which is what makes an array fast for lookup
- the two structures this chapter adds, the stack and the queue, are really just RULES for how items go in and come out of a collection, not new storage in themselves
- the syntax for declaring and creating an array is covered in the Programming in Java review, this chapter only needs the idea of indexed slots
The stack: last in, first out
- a stack only allows adding and removing at one end, called the top, so the last item pushed is always the first item popped
- Java's java.util.Stack class provides this directly: push adds an item on top, pop removes and returns the top item, peek returns the top item without removing it
- calling pop or peek on an empty stack throws an exception, so a real program checks the stack is not empty first
- a stack of function calls is exactly what backs recursion: each call pushes a frame, each return pops one
Three pushes, a pop, and a peek
Q. Starting from an empty stack, run push(5), push(3), push(8), pop(), then peek(). What does each call return, and what is left on the stack?
- push(5): the stack holds 5, with 5 on top
- push(3): the stack holds 5, 3, with 3 on top
- push(8): the stack holds 5, 3, 8, with 8 on top
- pop(): removes and returns 8, the stack is left holding 5, 3, with 3 now on top
- peek(): returns 3, the top item, without removing it, the stack still holds 5, 3
Answer: pop() returns 8, peek() returns 3, and the stack ends up holding 5 then 3
Page 1 of 3. The full sheet, all 3 pages, opens free in the app.
What this Data Structures sheet covers
- The array, the data structure you already have
- The stack: last in, first out
- Three pushes, a pop, and a peek
- The queue: first in, first out
- Stack (last in, first out) against queue (first in, first out)
- Stack
- Queue
- The linked list, the concept
- Three nodes, a chain built from references
- Node A
- Node B
- Node C
- What a linked list buys, and what it costs
- Traps that cost marks
- Tricks that save time
How CapCompass uses this sheet
These notes are not a standalone PDF. CapCompass plans Computer Science chapter by chapter against your real exam dates and free hours, and when the plan reaches Data Structures the sheet opens inside the study block itself — at the page covering the sub-topic that block is on, with the timer still running. Revision arrives at the moment the plan says revise, instead of having to be gone looking for.