Chapter 7

Data Structures
Complete Study Notes

■ Subject: Computer Science / IT

■ Chapter: Chapter 7 — Data Structures

■ Includes: Notes + 30 MCQs + 15 Short Questions

■ Purpose: Exam Preparation (Full)

■ COMPLETE NOTES — CHAPTER 7

1. Data Structures (Introduction)

Data structures are abstractions of actual data organization in main memory. They allow users to
perceive data as logical units — for example, arranging data in rows and columns.

Key Points:
• Data in memory is stored as 0s and 1s — hard to understand directly.
• Data structures give us a simple, organized view of that complex data.
• Example: A table with rows and columns is a logical view — memory does not actually store it that way.

■ Real Life Misaal: Memory mein sab 0s aur 1s hain — data structure un ko samajhne laiq banata hai, jaise numbers
ko table ki shakal dena.

2. Pointers
Pointer = A memory location that stores the address of another memory location. It does not store data
itself — it points to where the data is stored.

Key Points:
• A pointer holds an address, not actual data.
• It is the basic tool for creating dynamic data structures.
• Example: Address 64B0 holds book 'A Farewell to Arms' and pointer F02A (pointing to next book).

■ Real Life Misaal: Kaagaz pe ghar ka address likha ho — woh kaagaz pointer hai, ghar actual data hai.

3. Static vs Dynamic Data Structures

Feature Static Dynamic
Size Fixed — cannot change Flexible — can grow/shrink

Memory Allocated at start Allocated as needed

Speed Faster Slightly slower

Example Array: int Table[2][9] Stack, Linked List

■ Real Life Misaal: Static = school ki fixed 30 kursiyan. Dynamic = rubber band jaise — zaroorat ke mutabiq barhao
ya ghatao.

4. Arrays
An array is a 1-D homogeneous data structure that stores elements of the same type in contiguous
(side-by-side) memory locations.

Key Points:
• Homogeneous = all elements same data type.
• Contiguous = all stored next to each other in memory.
• Example: float Readings[24] — stores 24 temperature values.

■ Address Formula: Address of Readings[i] = x + (i - 1)

Element Formula Address

Readings[1] x + (1-1) x+0=x

Readings[2] x + (2-1) x+1

Readings[5] x + (5-1) x+4

■ Real Life Misaal: Building ke flats: Flat 1 = x, Flat 2 = x+1, Flat 3 = x+2 — har flat ek number aage.

5. Lists (2-D Arrays)

A 2-D array can store an ordered list. Example: char Names[10][8] — stores 10 names, each up to 8
characters long.

■■ Problem — Expensive Data Movements:

• Adding or removing an element from the middle requires shifting all other elements.
• The larger the list, the more time and processing required.
• This is why arrays are NOT ideal for frequently changing lists.

■ Real Life Misaal: Queue mein beech se koi nikle t■ sab ko aage khisna pade — yahi expensive movement hai!

6. Linked Lists
A linked list avoids expensive data movements by using pointers. Each node has two parts: Data
(Name) and a Pointer to the next node. The last node contains NIL.

Part Meaning
Head Pointer Points to the FIRST node of the list

Name (Data) The actual value stored in the node

Pointer Address of the NEXT node

NIL End of the list — no more nodes

Deleting a Node:
• Change only ONE pointer — the previous node points to the node after the deleted one.
• No data movement or shifting needed. ■

Inserting a Node (2 Steps):

• Step 1: New node's pointer → points to the FOLLOWING node.
• Step 2: Previous node's pointer → points to the NEW node.
• ■■ Order matters! Always do Step 1 first, then Step 2.

■ Real Life Misaal: Har bande ke haath mein agli wali ki address ka kaagaz — koi aaye ya jaye, sirf kaagaz badlo!

7. Stacks
A stack is a data structure where insertion and removal happen at ONE END ONLY — the top. It follows
the LIFO principle: Last In, First Out.

Operation Meaning Direction

PUSH Add a new item to the stack Always from the TOP

POP Remove an item from the stack Always from the TOP

Stack in Memory:
• Stack has a base (starting point), stack entries, and space for growth.
• A Stack Pointer always tracks the current TOP of the stack.
• If size is known → use array. If size is unknown → use pointers (dynamic).

Typical Use — Procedure Calls (LIFO):

Main → calls A → calls B → calls C
Return order: C returns first → then B → then A → back to Main

Using Stack to Print Linked List in Reverse:

• Phase 1 (PUSH): Push each node onto the stack in order (Alfred, Bob, Carol).
• Phase 2 (POP): Pop and print — Carol prints first, then Bob, then Alfred.

■ Real Life Misaal: Plates ka stack: upar se rakho (PUSH), upar se uthao (POP). Jo aakhir mein rakhi, pehle uthegi
— LIFO!
 ■ 30 MULTIPLE CHOICE QUESTIONS (MCQs)

Q1. Data structures are best described as:

A) Physical circuits in CPU B) Abstractions of data organization in main memory C) Programming languages D)
Operating system files
■ Answer: B

Q2. Which of the following allows users to perceive data as logical units?
A) CPU registers B) Data structures C) Compilers D) Hard disks
■ Answer: B

Q3. A pointer is defined as:

A) A variable that stores actual data B) A memory location storing the address of another location C) A type of
array D) A fixed-size data structure
■ Answer: B

Q4. In a linked list, what does a pointer in each node contain?

A) The data value B) The size of the list C) The address of the next node D) NIL always
■ Answer: C

Q5. What does NIL indicate in a linked list?

A) The first node B) An empty node C) The end of the list D) A deleted entry
■ Answer: C

Q6. Which data structure has a FIXED size that cannot change?
A) Stack B) Linked List C) Static Array D) Dynamic List
■ Answer: C

Q7. int Table[2][9] is an example of a:

A) Dynamic data structure B) Linked list C) Stack D) Static data structure
■ Answer: D

Q8. The formula for finding the address of Readings[i] in an array is:
A) x + i B) x * i C) x + (i-1) D) x - (i+1)
■ Answer: C

Q9. If the base address of an array is x, what is the address of the 4th element?
A) x + 4 B) x + 3 C) x + 2 D) x + 5
■ Answer: B

Q10. What is the main disadvantage of using arrays for lists?

A) They use too much memory B) They cannot store numbers C) Insertion and deletion require expensive data
movements D) They are too slow to read
■ Answer: C

Q11. char Names[10][8] means:

A) 10 characters, 8 names B) 8 names of 10 characters each C) 10 names each up to 8 characters long D) 80
individual characters
■ Answer: C
Q12. How many pointer changes are needed to DELETE a node from a linked list?
A) 3 B) 2 C) 0 D) 1
■ Answer: D

Q13. What is the FIRST step when inserting a node into a linked list?
A) Update the preceding node's pointer B) Set new node's pointer to the following node C) Delete the old node D)
Change the head pointer
■ Answer: B

Q14. How many pointer changes are needed to INSERT a node in a linked list?
A) 1 B) 4 C) 2 D) 3
■ Answer: C

Q15. Which principle does a Stack follow?

A) FIFO — First In First Out B) FILO — First In Last Out C) LIFO — Last In First Out D) Random Access
■ Answer: C

Q16. PUSH operation in a stack means:

A) Removing an item from the top B) Adding an item to the bottom C) Adding an item to the top D) Deleting all
items
■ Answer: C

Q17. POP operation in a stack means:

A) Adding an item to the top B) Removing an item from the top C) Accessing the bottom element D) Reversing the
stack
■ Answer: B

Q18. Which part of a stack always tracks the current top element?
A) Base pointer B) Head pointer C) NIL pointer D) Stack pointer
■ Answer: D

Q19. If maximum stack size is UNKNOWN, which approach should be used?

A) Use a 2-D array B) Use pointers for dynamic growth C) Use a fixed array D) Use NIL values
■ Answer: B

Q20. What is a 'contiguous block of memory'?

A) Memory cells scattered randomly B) Memory cells stored side-by-side C) Memory with gaps between elements
D) External storage memory
■ Answer: B

Q21. To print a linked list in reverse, which data structure is used?

A) Array B) Queue C) Stack D) 2-D List
■ Answer: C

Q22. In reversing a linked list using a stack, the PUSH phase:

A) Prints elements in reverse B) Removes elements from the stack C) Adds all list elements onto the stack in order
D) Deletes the linked list
■ Answer: C

Q23. In the diagram Alfred->Bob->Carol, after all PUSH operations, which is at the TOP of the stack?
A) Alfred B) Bob C) NIL D) Carol
■ Answer: D

Q24. The 'Head Pointer' in a linked list points to:

A) The last node B) NIL C) The first node D) The middle node
■ Answer: C

Q25. Which data structure uses PUSH and POP operations?

A) Array B) Linked List C) Stack D) 2-D Array
■ Answer: C

Q26. What makes a linked list more efficient than an array for insertions?
A) It uses less memory overall B) Only pointer changes are needed — no shifting C) It is faster to search D) It uses
a fixed size
■ Answer: B

Q27. In procedure calls, the stack follows which return order?

A) First called, first returned B) Random order C) Last called, first returned D) Alphabetical order
■ Answer: C

Q28. Which of the following is a Dynamic data structure?

A) int Table[5][5] B) char Name[20] C) float Grades[10] D) Linked List
■ Answer: D

Q29. The address of Readings[7] when base address x = 100 is:

A) 107 B) 105 C) 106 D) 108
■ Answer: C

Q30. Why are pointers called the 'basic aid' in dynamic data structures?
A) They store large amounts of data B) They allow structures to grow/shrink by linking nodes via addresses C)
They speed up array operations D) They eliminate the need for memory
■ Answer: B
■ 15 SHORT QUESTIONS & ANSWERS

Q1. What is a data structure?

A data structure is an abstraction of actual data organization in main memory. It allows users to
perceive data as logical units, such as arrangement in rows and columns, making complex memory
data easy to understand and use.

Q2. What is a pointer? Give an example.

A pointer is a memory location that stores the address of another memory location — it does not store
data itself, but points to where data is stored. Example: In a linked list, each node's pointer holds the
address of the next node.

Q3. What is the difference between static and dynamic data structures?

A static data structure has a fixed size that cannot change during execution (e.g., arrays). A dynamic
data structure can grow or shrink as needed during execution (e.g., linked lists, stacks using pointers).

Q4. Write the address formula for a 1-D array and explain it.

Address of element Readings[i] = x + (i - 1), where x is the base address (address of first element). For
example, Readings[4] is at address x+3. This works because array elements are stored contiguously in
memory.

Q5. Why is using an array for a list considered 'expensive' for insertions and deletions?

Because inserting or deleting an element in the middle of an array requires shifting all other elements
either forward or backward. The larger the array, the more shifts are needed, making it time-consuming
and computationally expensive.

Q6. What is a linked list and how does it solve the array problem?

A linked list is a dynamic data structure where each node contains data and a pointer to the next node.
It solves the array shifting problem because adding or removing nodes only requires changing one or
two pointers — no data movement or shifting is needed.

Q7. How is a node deleted from a linked list?

To delete a node, only ONE pointer needs to be changed. The previous node's pointer is updated to
point directly to the node after the deleted one, effectively bypassing it. No data movement is required.

Q8. Explain the two steps for inserting a node into a linked list.
Step 1: Set the new node's pointer to point to the node that will follow it. Step 2: Update the preceding
node's pointer to point to the new node. The order is important — Step 1 must always come first to
avoid losing the address of the following node.

Q9. What is a stack? What principle does it follow?

A stack is a data structure where insertion (PUSH) and removal (POP) are restricted to one end only —
the top. It follows the LIFO principle: Last In, First Out — the last item added is the first one removed.

Q10. What are PUSH and POP operations?

PUSH is the operation of adding a new item to the top of a stack. POP is the operation of removing an
item from the top of the stack. Both operations always occur at the top only.

Q11. How is a stack stored in memory?

A stack in memory consists of a reserved block of contiguous memory cells. It has a base (starting
point), stack entries (current data), and space for growth. A stack pointer tracks the current top of the
stack at all times.

Q12. When should pointers be used for a stack instead of arrays?

When the maximum stack size is unknown, pointers should be used. This allows the stack to grow
dynamically as needed, whereas an array requires a fixed size to be declared in advance.

Q13. How is a linked list printed in reverse using a stack?

Phase 1 (PUSH): Traverse the linked list and push each node onto the stack in order. Phase 2 (POP):
Pop elements from the stack one by one and print them. Since the stack follows LIFO, the last element
pushed (last node) is printed first, achieving reverse order.

Q14. What is the role of the Head Pointer and NIL in a linked list?

The Head Pointer stores the address of the first node in the linked list, providing the entry point to the
list. NIL is stored in the pointer field of the last node, indicating that there are no more nodes and the list
has ended.

Q15. List and compare the common data structures covered in Chapter 7.

Arrays: static, homogeneous, contiguous memory, fast access but expensive for insertion/deletion.
Linked Lists: dynamic, pointer-based, efficient insertion/deletion with only pointer changes. Stacks:
dynamic, LIFO principle, uses push/pop operations, used in procedure calls and reverse printing.
■ Chapter 7 — Data Structures | Complete Notes + 30 MCQs + 15 Short Questions | All the Best for Your Exam! ■