Your scheme may call it Data Structures & File Processing.
This is the most important paper in the whole degree, and it is not close. Everything a product company asks in an interview comes from here. Everything a service company asks in its written round comes from here. And it is the paper with the highest backlog rate in every batch we have taught, for one reason: it is taught as definitions to memorise when it is really a paper about drawing.
The subject is short to describe. You will meet about eight structures — array, stack, queue, linked list, tree, heap, graph, hash table — and for each one you answer three questions: how is it laid out in memory, what does it cost to insert, delete and search, and when would you choose it over the others. That is the whole paper.
If you are behind, do not start at the beginning. Start with linked lists, because they are the bridge from C to everything else, and because half the exam questions are a linked list wearing a different name. A stack is a linked list where you only touch one end. A queue is one where you touch both. A tree is one where each node points at two.
We teach this
This is not only a page about Data Structures. It is a subject we teach in a classroom on Majitha Road, and a good share of every batch is college students taking it alongside their own semester. Bring your scheme and we cover what is on it.
What that means in practice: the whole syllabus gets covered rather than the parts that make a good demo, you write code on a machine instead of copying it into a file, and the lab work gets done here rather than the night before submission.
What we will not say is that this guarantees you marks or a job. We do not run placements and we do not promise results. Come and sit in a class, decide for yourself.
What each unit actually contains, and whether it is there because it matters or because it is on the paper. Unit order and numbering vary between GNDU, PTU and your batch’s scheme — check your own before you plan a revision week.
Primitive and non-primitive structures, linear versus non-linear, arrays in one and two dimensions, row-major and column-major address calculation, sparse matrices, and asymptotic notation — big O, omega and theta.
The address calculation formula is asked almost every year and takes ten minutes to learn. Big O you will use forever.
Push, pop and peek, stack overflow and underflow, infix to postfix and prefix conversion, evaluating a postfix expression, checking balanced parentheses, and recursion as a stack.
Infix to postfix is guaranteed to appear. Learn the algorithm as a table you fill in, not as a paragraph.
Simple queue, the wasted-space problem, circular queue and the modulo trick, double-ended queue, priority queue, and queue implementation with arrays and with linked lists.
Why a circular queue exists is a favourite question. Draw the array with front and rear moving round it.
Singly, doubly and circular lists; insert at beginning, end and a given position; delete by value and by position; reverse a list; search; and the comparison against arrays.
The centre of the paper and of every interview. If you can reverse a singly linked list on paper without hesitating, you are ahead of most of your batch.
Terminology, binary tree, binary search tree, the three traversals with recursion and without, insertion and deletion in a BST, height and balance, AVL trees with the four rotations, and B-trees as an idea.
Traversals are free marks — practise until you can write all three from memory. AVL rotations look terrifying and are four fixed patterns.
Representation as an adjacency matrix and adjacency list, breadth-first and depth-first search, spanning trees, Prim's and Kruskal's algorithms, and Dijkstra's shortest path.
Usually the last unit and the least revised, so the questions are often the easiest marks on the paper.
Linear and binary search; bubble, selection, insertion, merge and quick sort with their best, average and worst cases; hash functions; and collision handling by chaining and by open addressing.
Know the complexity table cold. Quick sort's worst case being O(n squared) on already-sorted data is asked constantly.
Sequential, indexed sequential, direct and relative file organisation, the idea of an index, and external sorting on files too large for memory.
Dry, and in the syllabus because databases need it. Two or three definitions carry the whole unit.
Revise all of it — the marks are the marks. But it is worth knowing which half of this paper you will still be using in two years, and which half exists because it is on the paper.
Not a guess paper, and not a promise about what will be set. These are the questions this subject keeps asking because they are the ones that test whether you understood it.
From teaching this paper, not from a list somewhere. Each of these costs marks every year.
Wrong — Learning the definitions of all eight structures and none of the operations.
Right — Papers ask you to do things, not to define them. For every structure, be able to draw an insert and a delete. Definitions carry two marks; the operations carry ten.
Wrong — Writing linked list code without drawing the pointers first.
Right — Draw the boxes and arrows, decide the order of the reassignments, then write the code. Almost every wrong linked-list answer is two statements in the wrong order — and a diagram makes that order obvious.
Wrong — Saying quick sort is faster than merge sort, full stop.
Right — Quick sort is usually faster in practice and O(n squared) in the worst case; merge sort is always O(n log n) but needs extra space. The examiner is looking for the trade-off, not for a winner.
Wrong — Losing the head of a linked list while reversing it, then not noticing.
Right — Keep three pointers — previous, current and next — and set next before you touch current's link. If you only keep two, the rest of the list is gone the moment you reverse the first pointer.
These compile and run as written — type them in, break them, and fix them. Copying a program into a file you never ran is how a practical viva goes badly.
The most asked question in this paper and in interviews. Three pointers, one pass.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
struct Node *reverse(struct Node *head) {
struct Node *prev = NULL;
struct Node *curr = head;
struct Node *next = NULL;
while (curr != NULL) {
next = curr->next; /* save it before we overwrite the link */
curr->next = prev; /* turn the arrow round */
prev = curr; /* shuffle both pointers forward */
curr = next;
}
return prev; /* prev is the old tail, now the head */
}
struct Node *push(struct Node *head, int value) {
struct Node *n = malloc(sizeof(struct Node));
n->data = value;
n->next = head;
return n;
}
void print(struct Node *head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
int main(void) {
struct Node *head = NULL;
int i;
for (i = 5; i >= 1; i--) {
head = push(head, i);
}
printf("Before: ");
print(head);
head = reverse(head);
printf("After: ");
print(head);
return 0;
}Shows why the modulo is there. Handles full and empty correctly, which is where marks go.
#include <stdio.h>
#define SIZE 5
int queue[SIZE];
int front = -1, rear = -1;
int isFull(void) {
return (rear + 1) % SIZE == front;
}
int isEmpty(void) {
return front == -1;
}
void enqueue(int value) {
if (isFull()) {
printf("Queue is full\n");
return;
}
if (isEmpty()) {
front = 0;
}
rear = (rear + 1) % SIZE;
queue[rear] = value;
printf("Inserted %d\n", value);
}
void dequeue(void) {
if (isEmpty()) {
printf("Queue is empty\n");
return;
}
printf("Removed %d\n", queue[front]);
if (front == rear) {
front = rear = -1; /* the queue just became empty */
} else {
front = (front + 1) % SIZE;
}
}
int main(void) {
enqueue(10); enqueue(20); enqueue(30);
dequeue();
enqueue(40); enqueue(50); enqueue(60);
return 0;
}Inorder on a BST prints the values in sorted order, which is the point of the structure.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *left, *right;
};
struct Node *insert(struct Node *root, int value) {
if (root == NULL) {
struct Node *n = malloc(sizeof(struct Node));
n->data = value;
n->left = n->right = NULL;
return n;
}
if (value < root->data) {
root->left = insert(root->left, value);
} else if (value > root->data) {
root->right = insert(root->right, value);
}
return root; /* duplicates ignored */
}
void inorder(struct Node *root) {
if (root == NULL) return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
int main(void) {
struct Node *root = NULL;
int values[] = {50, 30, 70, 20, 40, 60, 80};
int i;
for (i = 0; i < 7; i++) {
root = insert(root, values[i]);
}
printf("Inorder: ");
inorder(root);
printf("\n");
return 0;
}Not model answers to reproduce. What the examiner is checking for, and where the marks actually sit in each one.
Answer: A B C * + D E / -. Show the table — three columns, symbol read, stack contents, output so far — and fill a row for every character. Examiners give most of the marks for the working, so a correct answer with no table scores worse than a slightly wrong one with a complete table. The rules to state first: operands go straight to output; an operator pops everything of higher or equal precedence before it is pushed; a closing bracket pops until the opening one.
Memory: an array is one contiguous block, a list is scattered nodes joined by pointers. Size: fixed at declaration versus grown at run time. Access: an array reaches element n in constant time, a list has to walk there. Insert and delete in the middle: an array shifts everything after it, a list rewires two pointers. Extra cost: a list pays a pointer per node. Finish with the judgement — arrays when you mostly read by index, lists when you mostly insert and delete.
Hashing maps a key to an array index through a hash function, so a lookup is constant time instead of a search. A collision is two keys landing on the same index, which is unavoidable once there are more possible keys than slots. Two families of answer: chaining, where each slot holds a linked list of everything that landed there; and open addressing, where you probe for another free slot — linear probing, quadratic probing, or double hashing. Mention the load factor and that performance degrades as the table fills; that sentence is usually worth a mark on its own.
Bubble, selection and insertion: O(n squared) average and worst; insertion is O(n) on nearly sorted data. Merge sort: O(n log n) in all three cases, O(n) extra space, stable. Quick sort: O(n log n) average, O(n squared) worst when the pivot is always the smallest or largest element — which is what happens on already-sorted input with a naive pivot. Heap sort: O(n log n) always, in place, not stable. Draw it as a table with best, average, worst and space columns; that is what the examiner is looking for.
Your paper stops somewhere, and a job interview does not. If you want the version of this subject that goes further than the scheme asks for, there is a full course for it.