MODULE 02

Linked List and Memory Management

Singly Linked List - Operations on Linked List, Stacks and Queues using Linked List, Polynomial
representation using Linked List; Doubly Linked List; Circular Linked List; Memory allocation -
First-fit, Best-fit, and Worst-fit allocation schemes; Garbage collection and compaction.

Watch Class: (tap here)

PREREQUISITES
Pointers
A pointer is a variable that stores the memory address of another variable.

Basic Pointer Assignment

int a = 22;

• a is an integer variable storing the value 22.

Now let’s assign the address of a to a pointer:

int *p; // declaring a pointer to int

p = &a; // storing address of 'a' in pointer 'p'

At this point:
• p contains the address of a
• *p (called dereferencing) gives the value stored at that address
Memory Representation
Assume:
• a has value 10 and is stored at address 2000
• p is storing adress of a at address 4000

Then:

a = 10 → stored at 2000
p = 2000 → pointer stores address of a
*p = 10 → value at address 2000
&p = 4000 → address of pointer itself

Pointer with Array

int arr[10];

• Here, arr is the name of the array.

• The name arr represents the base address of the array (i.e., the address of the first
element arr[0]).
• So:
arr == &arr[0];

This is why we can use a pointer to access array elements using pointer arithmetic.
Self-Referential Structure
A structure in C is a user-defined data type used to group different data types together.
Example:

struct Name {
int rollno;
int marks;
char* fullname;
};

• Here, struct Name groups different types: int, int, and char*.

What is a Self-Referential Structure?

A self-referential structure is a structure that contains a pointer to a structure of the same
type. This is especially useful in creating linked data structures like linked lists, trees, etc.
Example:

struct Node {
int info;
struct Node *link;
};

• The member link is a pointer to the same structure type (struct Node). Ie link‘s data type
is type of struct node
• This allows one node to link to another node — a concept known as self-reference.
• This structure is called self-referential because it refers to itself.

Used to create dynamic data structures like: Singly Linked List, Doubly Linked List, Binary
Trees, Graphs
Static Memory Allocation
Example:
int a[100]; // or static int a[100];
int sum;

• Here, a is an integer array of fixed size 100.

• If int takes 4 bytes, then the array takes 100 × 4 = 400 bytes.

In Static Allocation:
• Size is fixed at compile time.
• Memory is allocated automatically at runtime (on stack or data segment).

🔹 Problem:
If we only need 10 elements during execution, then the remaining 90 elements' memory is
unused and wasted.
Dynamic Memory Allocation
Dynamic memory is allocated at runtime using special functions. These memory blocks are
accessed using pointers.

In Dynamic Allocation:
• Size is chosen at runtime (using user input, logic, etc.).
• Memory is allocated manually using functions like malloc(), calloc(), etc.

Using malloc() Function

Syntax:
ptr = (data_type *) malloc(n * sizeof(data_type));

Example:
int *a; // Pointer to int
int n; // Variable to read size from user

a = (int *) malloc(n * sizeof(int));

• malloc() dynamically allocates n × sizeof(int) bytes of memory.

• Returns the base address of the allocated memory block.
• Since it returns a void * (generic pointer), it must be typecasted to the correct data type
(int * in this case).

Example:
If n = 4, and sizeof(int) = 4, then memory allocated = 4 × 4 = 16 bytes.
Applying to Structure:

struct node {
int info;
struct node *link;
};

• info stores the data.

• link is a pointer to the next node (used in linked lists).

Declaring and Allocating a Node Dynamically:

struct node *s;

s = (struct node *) malloc(sizeof(struct node));

• s is a pointer of type struct node.

• malloc() allocates memory of size equal to one struct node.
• The returned base address is stored in s.

Let’s say the memory allocated by malloc() starts at address 1000. Then:

• s contains 1000
• At address 1000, the structure block contains two parts:
info
link

This memory block layout can be visualized as:

S Info Link
2000 → 2000

🔹
Accessing Structure Members:
If using a structure variable (not pointer):
[Link];
[Link];

🔹 But since here s is a pointer, we access members using:

s->info;
s->link;
• -> is used to access members through a structure pointer.
• Equivalent to: (*s).info and (*s).link
Linked List
A linked list is a type of linear data structure.
Unlike arrays, which require a fixed size and continuous memory, a linked list:

• Uses dynamic memory allocation

• Does not require continuous memory blocks
• Grows or shrinks as needed during runtime (memory efficient)

Each element in a linked list is called a node.

Every node contains two parts:

1. info – stores the actual data
2. link – stores the address of the next node

So a general node looks like:

info link
Base Address

Example:

X
2 1000
2000

X -> info = 2 // value part

X -> link = 1000 // address of next node
X = 2000 // base address of this node

2000
HEAD

HEAD -> info = 2

HEAD -> link = 1000

Why Use Pointers?

• All nodes are created using malloc(), which returns an address.
• These addresses are stored in pointer variables.
• So linked list traversal, insertion, deletion, etc., all happen through pointers.
Array as Linked list

Assume:
• Base address of arr is 2000
• Each integer occupies 4 bytes

Then memory layout looks like:

Address Value Index

2000 2 arr[0]
2004 4 arr[1]
2008 6 arr[2]

2000 2004 2008

Arr = 2 4 6
0 1 2

• Array elements are stored in continuous memory

• You can directly access any element using index (arr[1], arr[2], etc.)
• Access is fast and based on position

In linked list:
Each node stores:
• Data
• Address of the next node (link)

HEAD

2000

2 3000 4 4000 6 X
2000 3000 4000

Drawbacks of Linked List:

• Cannot access intermediate elements directly
(must always start from the head)
• Requires extra memory to store the link (pointer part)
Linked List vs Array
Feature Array Linked List
Memory allocation Static (fixed size) Dynamic (size can grow/shrink at runtime)
Memory layout Continuous memory Non-continuous memory
Accessing elements Direct (using index) Sequential (traverse from head)
Insertion/Deletion Expensive (may need shifting) Easier (by adjusting pointers)
Extra memory No extra memory (only data
Extra memory for pointer in each node
needed stored)
Can be resized anytime using dynamic
Resize flexibility Not possible once size is fixed
allocation
Better (due to locality of
Cache performance Poor (nodes may be scattered in memory)
reference)
Implementation Simple and easy More complex due to pointers
Possible (unused allocated
Wastage of memory Minimal (allocates memory as needed)
space)

Implementing Linked List in C

Step 1: Define the Structure
struct node {
int info;
struct node *link;
} *x;

• info holds the data

• link is a pointer to the next node
• s is a pointer

Step 2: Create First Node Dynamically

struct node *x;

x = (struct node *) malloc(sizeof(struct node)); // allocate memory for first node

x->info = 2255; // store value 2255 at the node's info part
x->link = NULL; // since it's the only node now, link part is NULL

Assume: Memory address of x (the node) = 2000

So:
• x->info = 2255 → stored at address 2000
• x->link = NULL
Step 3: Create a Head Pointer
struct node *head = NULL; // head initially points to nothing
head = x; // head now points to the first node (address 2000)

• head = 2000
• Now, head and x both point to the same node

Step 4: Create a Second Node y

struct node *y;

y = (struct node *) malloc(sizeof(struct node)); // allocate memory for second node

y->info = 369; // assign value 369
y->link = NULL; // currently the second node is the last node

Assume: Memory address of y = 3000

Step 5: Link x to y (Connect Nodes)

x->link = y; // now first node points to second node
Now the chain looks like this: head → x → y

Final Code Together:

#include <stdio.h>
#include <stdlib.h>

struct node {
int info;
struct node *link;
};

int main() {
struct node *x, *y, *head = NULL;

x = (struct node *) malloc(sizeof(struct node));

x->info = 2255;
x->link = NULL;

head = x; // head points to first node

y = (struct node *) malloc(sizeof(struct node));

y->info = 369;
y->link = NULL;

x->link = y; // first node now points to second node

return 0;
}
Types of Linked List
1. Singly Linked List: Each node points to the next node only. Traversal is one-way, from
head to NULL.
2. Doubly Linked List: Each node has two pointers: one to the next node and one to the
previous. Enables two-way traversal.
3. Circular Linked List: The last node points back to the first node. Can be singly or
doubly circular. No NULL at the end.

OPERATIONS ON SINGLY LINKED LIST

Main operations are:
• Traversal
• Insertion
• Deletion

1. Traversal of Singly Linked List (SLL)

HEAD ptr

2000

2 3000 4 4000 6 X
2000 3000 4000

1. Set a pointer to the head node.

struct node *ptr = head;

2. Accessing the first node:

ptr->info; // gives 2 (value at 2000)

3. Move to next node:

ptr = ptr->link;

4. Now,
ptr->info; // gives 4 (value at 3000)
 5. Repeat this until ptr becomes NULL (end of the list):

while (ptr != NULL) {

printf("%d\n", ptr->info); // print current node data
ptr = ptr->link; // move to next node
}

Linked List Traversal – Condition Analysis

Case 1: while(ptr != NULL)

HEAD

2000

2 3000 4 4000 6 X
2000 3000 4000

struct node *ptr = head;

while(ptr != NULL) {
printf("%d\n", ptr->info); // process current node
ptr = ptr->link; // move to next node
}

• This condition is correct for traversing all nodes, including the last node.
• The loop continues as long as the pointer ptr is not NULL.
• Last node is processed because the loop ends only after processing the node with link =
NULL.

Case 2: while(ptr->link != NULL)

struct node *ptr = head;

while(ptr->link != NULL) {
printf("%d\n", ptr->info); // process current node
ptr = ptr->link; // move to next node
}

• This skips the last node.

• The condition checks ptr->link != NULL, so it exits before reaching the last node where link
== NULL.
• Only nodes before the last node are processed.

Condition Output Values

ptr != NULL 2, 4, 6
ptr->link != NULL 2, 4
Algorithm: Traversal of Singly Linked List
Step 1: If head == NULL
→ The list is empty
→ Exit the algorithm

Step 2: Create a temporary pointer

→ ptr = head
→ Now ptr points to the first node

Step 3: Repeat while (ptr ≠ NULL)

→ Display ptr->info (or perform any operation on data)
→ Move to next node: ptr = ptr->link

Step 4: End While

Step 5: Return
Insertion in Singly Linked List (SLL)
There are 3 possible insertion cases:

1. At the beginning
2. At the end
3. In between

Creating a Node – getnode() Function

To create a new node dynamically, we use:

struct node* getnode() {

return (struct node*) malloc(sizeof(struct node));
}

You can call this function to get memory for any new node.

Example:
new = getnode(); // dynamically allocates memory for new node

1. Insertion at Beginning

HEAD

2000

2 3000 4 4000 6 X
2000 3000 4000

Assume we want to insert a new node with info = 8 at the beginning.

Step 1:
new->info = 8; //Store the value to be inserted.

8
5000
NEW

Step 2:
new->link = head;

8 2000
5000
NEW

Point the new node’s link to the current first node (which head points to).
Step 3:
head = new; //Now, update the head to point to the new node.

HEAD

5000 8 2000
5000
NEW

Special Case – When List is Initially Empty

HEAD

5000

8 X
5000
NEW

Even if head == NULL, this method still works:

new->link = head; // head is NULL

head = new; // head now points to the new node

This makes the new node both the first and last node.

Algorithm: Insertion at Beginning of Singly Linked List

1. Allocate memory for a new node
→ new = getnode()
2. Assign the value to the info part of the new node
→ new->info = item
3. Link the new node to the current first node
→ new->link = head
4. Update the head pointer to point to the new node
→ head = new
5. Exit
2. Insertion at End – Singly Linked List
To insert a node at the end:
• Traverse the list until the last node
• Update the last node’s link to point to the new node

HEAD

2000

2 3000 4 4000 6 X
2000 3000 4000

Idea:
• After traversal, the pointer will be at the last node
• Then, do: ptr->link = new;

Special Case:
• If the list is empty (head == NULL), simply make head = new.

Algorithm: Insertion at End

1. Allocate memory for a new node
→ new = getnode()
2. Assign value to the info part
→ new->info = item
3. Set link of new node to NULL
→ new->link = NULL
4. Check if list is empty:
If head == NULL → head = new & Return
5. Else, set a temporary pointer to head, ptr = head
6. Traverse to the last node
while (ptr->link != NULL)
ptr = ptr->link;
7. Once loop ends, ptr is at the last node
→ ptr->link = new
8. End
3. Insertion After a Node
To insert a new node after a specific value (key), we first search for the node containing that
value, and then insert the new node after it.

Suppose we want to insert after the node with info = 4, and that node is located at base
address 2000.

HEAD

1000

2 2000 4 3000 6 X
1000 2000 3000

Search the Node

We need to find the node that contains the required key (in this case, 4).
Once found, the pointer PTR will point to that node, and we can use it to insert a new node.

Algorithm: PART A – Search

Input: head – pointer to the first node, key – value to search
Output: Pointer to the node with info == key, Or NULL if not found

Steps:
1. Initialize a pointer
PTR = head → Start traversal from the beginning of the list.
2. Repeat the following until end of list or match found:
while (PTR != NULL && PTR->info != key) do
PTR = PTR->link
3. Return the result
→ If found, PTR points to the node with the key
→ If not found, PTR becomes NULL

HEAD ptr
1000

2 2000 4 3000 6 X
1000 2000 3000

8
5000
NEW
Algorithm: PART B
Input:
head: pointer to the first node
key: value after which new node should be inserted
item: value to insert
Output:
Inserts the new node with value item after the node containing `key`.

Steps:
1. PTR = Search(head, key) // Search for the node containing the key
2. If PTR == NULL
→ Display "Insertion not possible"
→ Return
3. new = getNode() // Dynamically allocate memory for the new node
4. new->info = item // Store value in the info field
5. new->link = PTR->link // Connect new node to the node after PTR
6. PTR->link = new // Link the current node to the new node
7. Return

8 3000
5000
NEW

HEAD ptr
1000

2 2000 4 3000 6 X
1000 2000 3000

finally,

HEAD

1000

2 2000 4 5000 8 3000

1000 2000 5000
NEW

6 X
3000
Deletion in Singly Linked List (SLL)
Deletion – 3 Possibilities:
1. At the beginning
2. At the end
3. A particular node (by value)

1. Deletion at Beginning
To delete the first node in a singly linked list:
• Make the head point to the second node
• Free the memory of the old first node

HEAD ptr
1000

2 2000 4 3000 6 X
1000 2000 3000

Special Cases:
1. Underflow – List is empty (head == NULL)
2. Only one node – After deletion, list becomes empty (head = NULL)

Algorithm
Input: head → pointer to the first node
Output: The value (info) of the deleted node

1. If head == NULL
→ Print "Underflow"
→ Return

2. PTR = head // Save the current head node

3. head = PTR->link // Move head to the next node
4. item = PTR->info // Store the deleted value
5. free(PTR) // Deallocate memory
6. Return item // Return the value

After deleting,

HEAD

1000

4 3000 6 X
2000 3000
2. Deletion at End
In a singly linked list, we can’t move backwards, so to delete the last node, we must:
• Traverse the list to reach the last node
• Also keep track of the second last node (previous), since we need to update its link to
NULL
prev ptr
HEAD

1000

2 2000 4 3000 6 X
1000 2000 3000

Why Two Pointers?

We can’t go back once we reach the last node, so we maintain:
• ptr → to reach the last node
• prev → to hold the address of the second last node

Special Case: Only One Node

If there’s only one node, then:
• head->link == NULL
• Just delete that node and set head = NULL

Algorithm
Input: head → pointer to the first node
Output: Value (info) of the deleted node

1. If head == NULL
→ Print "Underflow"
→ Return

2. If head->link == NULL
→ item = head->info
→ free(head)
→ head = NULL
→ Return item

3. PTR = head
PREV = NULL

4. while (PTR->link != NULL)

→ PREV = PTR
→ PTR = PTR->link

5. PREV->link = NULL // Detach last node

6. item = PTR->info // Store deleted value
7. free(PTR) // Free last node
8. Return item
3. Deletion of a Particular Element
To delete a node that contains a specific value (key, here value 6) from the list,

HEAD prev ptr

1000

2 2000 4 3000 6 4000

1000 2000 3000

8 X
4000

• We traverse the list to find the node whose info matches the given key.
• We keep track of the previous node (PREV) because we need to change its link to skip
over the node to be deleted.

Special Case: If the Deleting Node is First Node

If the node is the first one (here, MA: 1000), we handle it specially, since there's no previous
node.

HEAD ptr
1000

2 2000 4 X
1000 2000

• If head->info == key, then the first node itself contains the key.
• In this case:
PTR = head;
head = head->link;
free(PTR);
We simply update the head to point to the second node and free the original node.

Special Case: If the Element (key) not found!

If PTR == NULL while iterating, then there is no such element (key).
Algorithm
Input:
head: pointer to the first node
key: value to be deleted
Output: Updated list with the specified node removed (if found)

1. Check if list is empty

if (head == NULL)
→ Display: "List is empty" //underflow
→ Return
2. Check if node to delete is the first node
if (head->info == key)
→ PTR = head
→ head = PTR->link
→ free(PTR)
→ Return
3. Initialize pointers
PTR = head
PREV = NULL
4. Traverse to find key
while (PTR != NULL && PTR->info != key) //come out of the loop if any one condition false
→ PREV = PTR
→ PTR = PTR->link
5. Check if key was not found
if (PTR == NULL)
→ Display: "Element not present"
→ Return
6. Delete the node
Else
PREV->link = PTR->link
free(PTR)
7. Return
SOME PREVIOUS YEAR QUESTIONS – UPTO SLL
1. Write an algorithm to count number of nodes in a singly linked list. (REPEATED)

Input: head → Pointer to the first node in the list

Output: Number of nodes in the linked list (an integer)

1. Initialize a counter → count = 0

2. Set a pointer to the head → PTR = head
3. Repeat until end of list
→ While PTR ≠ NULL
→ Increment count: count = count + 1
→ Move to next node: PTR = PTR->link
4. Return the count

2. Write an algorithm to delete a given node in a singly linked list.

NOTES

3. Explain self-referential structure with an example. Give any one use.

NOTES

4. Advantages of Linked List over Arrays

NOTES
DOUBLY LINKED LIST (DLL)
A Doubly Linked List is a linear data structure where Each node contains two pointers:

LLINK: Points to the previous node

RLINK: Points to the next node

You can traverse in both directions — forward and backward.

Structure of a Node:
struct node {
int info;
struct node* LLINK;
struct node* RLINK;
};

A node contains:
INFO → the data (e.g., 10)
LLINK → address of the previous node
RLINK → address of the next node

Example:

HEAD

1000
X 2 2000 1000 4 3000 2000 6 4000
1000 2000 3000
NODE

3000 8 X
4000
Node->INFO = 4;
Node->LLINK = 1000;
Node->RLINK = 3000;

This means:
NodeX stores 4 as data.
Its previous node is stored at address 1000.
Its next node is stored at address 3000.
The base address (B.A) of Node is 2000 (assumed here).

Significance of Two Pointers:

Using RLINK, we can move forward (→)
Using LLINK, we can move backward (←)
This gives more flexibility than a singly linked list
Advantages of Doubly Linked List:
• Can be traversed in both directions
• Easy to delete a node without complete traversal
• Efficient insertions/deletions at both ends

Disadvantages:
• Requires extra memory for LLINK
• Slightly more complex pointer management
• More prone to bugs if LLINK and RLINK aren't correctly maintained

OPERATIONS ON DOUBLY LINKED LIST

Main operations are:
• Traversal
• Insertion
• Deletion

1. Traversal of Doubly Linked List (DLL)

We move from the first node to the last using RLINK.

HEAD
ptr
1000

X 2 2000 1000 4 3000 2000 6 4000

1000 2000 3000
NODE

3000 8 X
4000

Algorithm
Input: HEAD: pointer to the first node
Output: Visits and prints all node values in forward order

1. Set PTR = HEAD

2. While PTR ≠ NULL
→ Print PTR->INFO // Any operation
→ Move to next node: PTR = PTR->RLINK
3. End
Insertion in DLL
There are 3 possible insertion cases:

1. At the beginning
2. At the end
3. In between

1. Insertion at Beginning

HEAD

1000

X 2 2000 1000 4 3000 2000 6 4000

1000 2000 3000

3000 8 X
4000

Step 1: new → INFO = ITEM

Assign the data to the new node.

9
5000
NEW

Step 2: new → LLINK = NULL

Since the new node will be the first, it has no previous node.

X 9
5000
NEW

Step 3 (Special Case – If List is Empty):

if HEAD == NULL
This means the list is currently empty.

Then:
new → RLINK = NULL → No next node either.
HEAD = new → Make new node the head.

HEAD

5000

X 2 X
5000
NEW
Step 4 (Else – List is NOT empty):
If the list already has elements:

HEAD

1000

X 2 2000 1000 4 3000 2000 6 4000

1000 2000 3000

3000 8 X
X 9 4000
5000
NEW

head → LLINK = new → Old first node now links back to new node.
new → RLINK = head → New node points to the old head.
head = new → Update head pointer to new node.

Algorithm
1. new = getnode() //Allocate memory for the new node.

2. new->info = ITEM //Store the item in the info field.

3. new->llink = NULL //Since it's going to be the first node, its left link is set to NULL.

4. If head == NULL //The list is empty

→ new->rlink = NULL
→ head = new
5. Else
→ The list is not empty
→ head->llink = new
→ new->rlink = head
→ head = new
6. Return
2. Insertion at End
To Insert a new node containing ITEM at the end of a doubly linked list.

HEAD

1000

X 2 2000 1000 4 3000 2000 6 4000 ptr

1000 2000 3000

3000 8 X
4000

Steps:

1. PTR->RLINK = new // link old last node to new

2. new->LLINK = PTR // link new node back to old last

After these steps, the new node will become,

4000 9 X
5000
NEW

Special Case:
If the list is empty (head == NULL):

new->RLINK = NULL
new->LLINK = NULL
head = new

HEAD

5000

X 2 X
5000
NEW
Algorithm
1. new = getnode() //Allocate memory for new node
2. new->info = ITEM //Store value
3. new->RLINK = NULL //Set right link of new node to NULL
4. If list is empty (head == NULL)
new->LLINK = NULL
head = new
Return
5. Else (list is not empty)
PTR = head
while (PTR->RLINK != NULL) //Traverse to the last node:
PTR = PTR->RLINK
(while end)
6. PTR->RLINK = new // link old last node to new
new->LLINK = PTR // link new node back to old last
7. Return
3. Insertion After a Given Element in DLL
To insert a node after a particular value (say 4): First, search for the node with info == key (e.g.,
4).
Then, insert the new node after it.

ptr
HEAD

1000

X 2 2000 1000 4 3000 2000 6 X

1000 2000 3000

Part 1: Search for the node

Traverse the list and find the node with info == key.
Let's call that node PTR.

1. PTR = head
2. while (PTR != NULL && PTR->info != key)
PTR = PTR->RLINK

If PTR == NULL, key not found → stop.

If PTR != NULL, proceed to insertion.

Part 2: Insertion
There are 3 possibilities:
- Inserting in between two nodes.
- Inserting at the end (i.e., PTR->RLINK == NULL).
- Key not present – Then exit with message: Insertion not possible.

Case 1: Inserting between PTR and NXT

We use two pointers:

PTR: points to the node where key is found.
NXT: points to the node currently after PTR, (i.e., PTR->RLINK).

ptr nxt
HEAD

1000

X 2 2000 1000 4 5000 5000 6 X

1000 2000 3000

1. NXT = PTR->RLINK
4000
2000 9 3000
2. NEW->LLINK = PTR 5000
3. NEW->RLINK = NXT NEW

4. PTR->RLINK = NEW

5. if (NXT != NULL) then NXT->LLINK = NEW

Case 2: If KEY is present at last node (when NXT == NULL)

HEAD ptr
1000
4000
1000 9 X
X 2 X 5000
NEW
1000

1. NEW->LLINK = PTR
2. NEW->RLINK = NXT (Already NXT = NULL)
3. PTR->RLINK = NEW

No need to update NXT->LLINK because NXT == NULL.

Algorithm: Search
1. PTR = HEAD
2. While PTR ≠ NULL && PTR->info ≠ key do
PTR = PTR->RLINK
3. Return PTR

Algorithm: Insertion
1. PTR = Search(key)
2. If PTR == NULL then
Display "Key not present"
Return

3. new = getnode()
4. new->INFO = ITEM
5. nxt = PTR->RLINK (3 steps are common)

6. new->LLINK = PTR
7. new->RLINK = nxt
8. PTR->RLINK = new

9. If nxt ≠ NULL then (If nxt ≠ NULL then only need to do this)
nxt->LLINK = new

10. Return
Deletion in DLL
There are 3 possible cases:

• At the beginning
• At the end
• In between

1. Deletion From Beginning

ptr
HEAD

1000

X 2 2000 1000 4 3000 2000 6 X

1000 2000 3000

Main Steps:
1. Check for Underflow – if list is empty (head is NULL), deletion not possible.
2. Check for Single Node – if only one node exists, make head NULL after storing info.
3. General Case (2 or more nodes) – update head, adjust LLINK, and free the deleted node.

Algorithm
1. If head == NULL then
Display "Underflow"
Return

2. PTR = head

3. If PTR->RLINK == NULL then (ONLY 1 NODE)

Temp = PTR->INFO
head = NULL
Free(PTR)
Return Temp

4. Temp = PTR->INFO
5. head = PTR->RLINK
6. head->LLINK = NULL
7. Free(PTR)
8. Return Temp
2. Deletion of Last Node
List with 2 or More Nodes

prev
ptr
HEAD

1000

X 2 2000 1000 4 3000 2000 6 X

1000 2000 3000

Start from head, traverse until last node using:

while (PTR → RLINK != NULL)

PTR = PTR → RLINK

Once at last node:

TEMP = PTR → INFO //Store its data

PREV = PTR → LLINK //Get previous node

PREV → RLINK = NULL //Disconnect last node
free(PTR) //Free last node
return TEMP //Return deleted data

Special Case: If List Has Only One Node (head → RLINK == NULL)
- Save the INFO to a temporary variable
- Set head = NULL
- Free the only node using free(PTR)
- Return the deleted value

Algorithm
1. If HEAD == NULL then
1.1 Display "Underflow"
1.2 Return

2. PTR = HEAD

3. If PTR → RLINK == NULL then

3.1 TEMP = PTR → INFO
3.2 HEAD = NULL
3.3 Free(PTR)
3.4 Return TEMP

4. While PTR → RLINK != NULL

4.1 PTR = PTR → RLINK

5. TEMP = PTR → INFO

6. PREV = PTR → LLINK
7. PREV → RLINK = NULL
8. Free(PTR)
9. Return TEMP
3. Deleting a Particular Node (with a given key)
Delete the node that contains a given key (4).

HEAD ptr
1000

X 2 2000 1000 4 3000 2000 6 X

1000 2000 3000

Step 1: Check if the list is empty:

If (HEAD == NULL)
Print "Underflow" & Exit

Step 2; Search for the node with the given key

PTR = HEAD
While (PTR ≠ NULL && PTR → INFO ≠ KEY)
PTR = PTR → RLINK
We loop to find the node. If not found, PTR becomes NULL.

Step 3: If key not found:

If (PTR == NULL)
Print "Key not present" & Exit

Step 4: If key found:

ptr
HEAD

1000

X 2 2000 1000 4 3000 2000 6 X

1000 2000 3000

Case 1: Only one node in the list

HEAD ptr
2000
X 4 X
2000

If (PTR → LLINK == NULL && PTR → RLINK == NULL)

HEAD = NULL
Case 2: Node to delete is the first node

ptr
HEAD

1000

X 2 2000 1000 4 3000 2000 6 X

1000 2000 3000

Else If (PTR → LLINK == NULL)

Call Del_Beg() // existing function

Case 3: Node to delete is the last node

ptr
HEAD

1000

X 2 2000 1000 4 3000 2000 6 X

1000 2000 3000

Else If (PTR → RLINK == NULL)

Call Del_End() // existing function

Case 4: Node is somewhere in the middle

prev ptr next

HEAD

1000

X 2 2000 1000 4 3000 2000 6 X

1000 2000 3000

Else

PREV = PTR → LLINK

NEXT = PTR → RLINK
PREV → RLINK = NEXT
NEXT → LLINK = PREV
Algorithm

1. If (HEAD == NULL)
Print "Underflow" & Exit

2. PTR = HEAD

3. While (PTR ≠ NULL AND PTR → INFO ≠ KEY)

PTR = PTR → RLINK

4. If (PTR == NULL)
Print "Key not present" & Exit

5. If (PTR → LLINK == NULL AND PTR → RLINK == NULL) // only one node
HEAD = NULL
Free(PTR)
Exit

6. Else If (PTR → LLINK == NULL)

Call Del_Beg() //Already explained
Exit

7. Else If (PTR → RLINK == NULL)

Call Del_End() //Already explained
Exit

8. Else
PREV = PTR → LLINK
NEXT = PTR → RLINK
PREV → RLINK = NEXT
NEXT → LLINK = PREV
Free(PTR)

9. Exit
CIRCULAR LINKED LIST
In a circular linked list, the last node doesn’t point to NULL — instead, it points back to the
head node, forming a circle.

HEAD

2000

2 3000 4 4000 6 X
2000 3000 4000

In a regular singly linked list, traversal stops at NULL. But here, we must stop when we loop
back to the head, i.e., PTR → LINK == head.

OPERATIONS ON CIRCULAR LINKED LIST

Main operations are:

• Traversal
• Insertion
• Deletion
Traversal Of CLL

HEAD

2000

2 3000 4 4000 6 2000

2000 3000 4000

1. If (head == NULL)
Display "Empty" and Return

2. PTR = head

3. While (PTR -> LINK != head)

Process(PTR -> info) //Eg: Print, Count
PTR = PTR -> LINK

4. Process(PTR -> info) // Last node sepratly

5. Return

Insertion in CLL
There are 3 possible insertion cases:

1. At the beginning
2. At the end
3. In between
1. Insertion at Beginning

HEAD

2000

2 3000 4 4000 6 2000

2000 3000 4000

Algorithm
1. Create a node new.
2. Set new → data = item .
3. If head = NULL (empty list):
1. head = new
2. new → link = new (self-loop since only one node)
4. Else (non-empty list):
1. Set ptr = head.
2. While ptr → link != head do
1. ptr = ptr → link (move to last node).
3. Set new → link = head.
4. Update head = new.
5. Set ptr → link = head (last node points to new head).
1. Insertion at End

HEAD

2000

2 3000 4 4000 6 2000

2000 3000 4000

Algorithm
1. Create a node new.
2. Set new→data = x.
3. If head = NULL (empty list):
1. new→link = new (self-loop).
2. head = new.
4. Else (non-empty list):
1. Set ptr = head.
2. While ptr→link != head do
1. ptr = ptr→link (move to last node).
3. ptr→link = new.
4. new→link = head.
1. Insertion After Specific Node

HEAD

2000

2 3000 4 4000 6 2000

2000 3000 4000

Algorithm
1. If head = NULL (empty list):
Print "List is empty. Insertion not possible."
Return.
2. Else:
Set ptr = head.
While ptr→data != key do //Traverse list to find key
ptr = ptr→link

3. If ptr == head (back to start), break.

4. If ptr→data == key:
Create a node new.
new→data = x.
new→link = ptr→link.
ptr→link = new.
5. Else:
Print "Search data not found. Insertion not possible."

Deletion in DLL
There are 3 possible cases:

• At the beginning
• At the end
• In between
1. Deletion From Beginning

HEAD

2000

2 3000 4 4000 6 2000

2000 3000 4000

Algorithm
1. If head = NULL then
Print "List is Empty. Deletion is not possible"

2. Else if head→link = head then

ptr = head
head = NULL
free(ptr)

3. Else
ptr = head
While ptr→link != head do
ptr = ptr→link
temp = head
head = head→link
ptr→link = head
free(temp)
1. Deletion From End

HEAD

2000

2 3000 4 4000 6 2000

2000 3000 4000

Algorithm
1. If head = NULL then
Print "List is Empty. Deletion is not possible"

2. Else if head→link = head then

ptr = head
head = NULL
free(ptr)

3. Else
prev = head
curr = head→link
While curr→link != head do
prev = curr
curr = curr→link

prev→link = head
free(curr)
1. Deletion After Specific Node

HEAD

2000

2 3000 4 4000 6 2000

2000 3000 4000

Algorithm
1. If head = NULL then
Print "List is Empty. Deletion is not possible"

2. Else if head→link == head then

1. If head→data == key then
ptr = head
head = NULL
free(ptr)
2. Else
Print "Search data not found."

3. Else if head→data == key then

1. ptr = head
2. While ptr→link != head do
ptr = ptr→link
3. temp = head
4. head = head→link
5. ptr→link = head
6. free(temp)

4. Else
1. prev = head
2. curr = head→link
3. While curr→link != head and curr→data != key do
prev = curr
curr = curr→link
4. If curr→data == key then
prev→link = curr→link
free(curr)
5. Else
Print "Search data not found."
STACK USING LINKED LIST
HEAD / TOP

2000

2 3000 4 4000 6 X
2000 3000 4000

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle.

• Insertion (PUSH) and Deletion (POP) are performed at the same end, called TOP.
• Using a linked list for implementing a stack allows dynamic memory allocation, unlike
arrays which require fixed memory size.

Representation
Each node contains:
Data (info) – the element stored.
Link (next pointer) – points to the next node.

• The TOP pointer always points to the most recently inserted node.
• When the stack is empty, TOP = NULL.

PUSH Operation (Insertion at Beginning)

1. new = getnode() // Create a new node
2. new->info = item // Assign value
3. new->link = top // Link new node to stack
4. top = new // Update top
5. Return

Time Complexity: O(1)

POP Operation (Deletion from Beginning)

1. If top == NULL
1. Display "Stack Underflow / No elements".
2. Else:
1. item = top->info
2. ptr = top
3. top = top->link
4. free(ptr) //Free memory
3. Return item.

Time Complexity: O(1)

QUEUE USING LINKED LIST
A queue is a linear data structure that follows the FIFO (First In, First Out) principle.

Insertion (ENQUEUE) → takes place at the rear.

Deletion (DEQUEUE) → takes place at the front.

Unlike arrays, queues implemented with linked lists use dynamic memory allocation, so they
can grow/shrink as needed.

Representation
Each node contains:
Data (info) – the element stored.
Link (next pointer) – points to the next node.

• The front pointer points to the first element (for deletion).

• The rear pointer points to the last element (for insertion).
• When the queue is empty, both front = rear = NULL.

HED / FRONT

2000

2 3000 4 4000 6 X
2000 3000 4000

REAR

4000

ENQUEUE Operation (Insertion at Rear)

1. new = getnode() // Create a new node

2. new->info = item // Assign value
3. new->link = NULL // Set link
4. If front == NULL:
1. front = rear = new
5. Else:
1. rear->link = new.
6. rear = new // Update rear
7. Return.

Time Complexity: O(1)

DEQUEUE Operation (Deletion at Front)
1. If front == NULL:
1. Display "Queue Underflow", return.
2. Else:
1. item = front->info.
2. ptr = front.
3. If front == rear:
1. front = rear = NULL.
4. Else:
1. front = front->link.
2. free(ptr).
5. Return item.

Time Complexity: O(1)

POLYNOMIAL REPRESENTATION USING SLL

• This is one of the most effective methods to represent polynomials.

• We use a singly linked list (SLL) for storing polynomial terms.
• We assume only one variable (x) in the polynomial, and terms are arranged in
decreasing order of exponents.

Structure of Node
Each node in the polynomial linked list contains three fields:
• Coefficient (Coeff) → stores the coefficient of the term.
• Exponent (Expo) → stores the exponent of the variable.
• Link → pointer to the next node.

COEFF. EXPO. LINK

1000
NEW NODE

So 4X3 + 3X2 + 2 is representated as:

HEAD

1000
4 3 2000 3 2 3000 2 0 X
1000 2000 3000
POLYNOMIAL ADDITION

Consider Example:

P : 6X3 + 3X + 6
Q : 4X4 + 2X

RESULT: 4X4 + 6X3 + 5X + 6

Basic Working:

Polynomial P:
P
P HEAD

1000
6 3 2000 3 1 3000 6 0 X
1000 2000 3000

Polynomial Q:

Q
Q HEAD

1000
4 4 2000 2 1 X
1000 2000
Algorithm

1. Initialize pointers:
P = Phead (first polynomial)
Q = Qhead (second polynomial)
Rhead = NULL (head of result polynomial)

2. While P ≠ NULL and Q ≠ NULL do

1. Create a new node new.

2. If P→Expo == Q→Expo (same powers):

new→Coeff = P→Coeff + Q→Coeff
new→Expo = P→Expo
new→Link = NULL
Move both lists: P = P→Link, Q = Q→Link

3. Else if P→Expo > Q→Expo (P’s term has higher power):

new→Coeff = P→Coeff
new→Expo = P→Expo
new→Link = NULL
Move P forward: P = P→Link

4. Else (Q→Expo > P→Expo) (Q’s term has higher power):

new→Coeff = Q→Coeff
new→Expo = Q→Expo
new→Link = NULL
Move Q forward: Q = Q→Link

5. Insert new into result polynomial:

If Rhead == NULL → set Rhead = R = new
Else → R→Link = new, R = new

3. While P ≠ NULL (remaining terms in P):

Create a node new.
Copy term: new→Coeff = P→Coeff, new→Expo = P→Expo.
new→Link = NULL.
Insert into result list:
If Rhead == NULL → Rhead = R = new
Else → R→Link = new, R = new
Move P = P→Link.

4. While Q ≠ NULL (remaining terms in Q):

Create a node new.
Copy term: new→Coeff = Q→Coeff, new→Expo = Q→Expo.
new→Link = NULL.
Insert into result list:
If Rhead == NULL → Rhead = R = new
Else → R→Link = new, R = new
Move Q = Q→Link.

5. Return Rhead (resultant polynomial).

POLYNOMIAL MULTIPLICATION
Consider Example:
P = 2X3 + 1X2
Q = 4X4 + 3X3 + 3X2

We take each term of P1 and multiply with all terms of P2.

(2x³) × Q
(2x³)(4x⁴) = 8x⁷
(2x³)(3x³) = 6x⁶
(2x³)(3x²) = 6x⁵

(1x²) × Q
(1x²)(4x⁴) = 4x⁶
(1x²)(3x³) = 3x⁵
(1x²)(3x²) = 3x⁴

Polynomial BEFORE combining like terms: 8 x 7 +6 x 6 +6 x 5 +4 x 6 +3 x 5 +3 x 4

Combine Like Terms (Adjustment Phase)

For x 7: 8x⁷
For x 6: 6 x 6 +4 x 6 =10 x 6
For x 5: 6 x 5 +3 x 5 =9 x 5
For x 4: 3x⁴

Polynomial AFTER combining like terms: 8 x 7 +10 x 6 +9 x 5 +3 x 4

Basic Working
Polynomial P: 2X3 + 1X2
P
Q HEAD

1000
2 3 2000 1 2 X
1000 2000

Polynomial Q: 4X4 + 3X3 + 3X2

Q
P HEAD

1000
4 4 2000 3 3 3000 3 2 X
1000 2000 3000

Polynomial BEFORE combining like terms: 8 x 7 +6 x 6 +6 x 5 +4 x 6 +3 x 5 +3 x 4

Algorithm
1. Initialization

P = Phead (first polynomial)

Q = Qhead (second polynomial)
Rhead = NULL (head of result polynomial)

Phase 1: Multiply Terms and Form Initial Result

2. While P ≠ NULL do

1. Set Q = Qhead (restart Q for each P term)

2. While Q ≠ NULL do
Create a new node new.
new→Coeff = P→Coeff × Q→Coeff // Multiply coefficients
new→Expo = P→Expo + Q→Expo // Add exponents
new→Link = NULL.
Insert into result list:
If Rhead == NULL → Rhead = R = new
Else → R→Link = new, R = new
Q = Q→Link // Move to next term in Q
3. P = P→Link // Move to next term in P

Phase 2: Combine Like Terms (Same Exponents)

1. Set P = Rhead.

2. While P ≠ NULL do
prev = P
Q = P→Link
While Q ≠ NULL do
If P→Expo == Q→Expo then
P→Coeff = P→Coeff + Q→Coeff (combine terms)
prev→Link = Q→Link (unlink duplicate)
Free(Q)
Q = prev→Link
Else (if exponent are not same)
prev = Q
Q = Q→Link
Move P to next: P = P→Link.

3. Return Rhead // final polynomial product

MEMORY ALLOCATION SCHEMES
Memory allocation is the process of assigning portions of main memory to processes when
they are executed.

• Since multiple processes compete for memory, the Operating System decides which part
of memory each process should occupy.
• Linked Lists are often used to represent free blocks and allocated blocks of memory.
Memory Allocation is an Application of Linked List.

Role of Linked List (Avail List)

• Memory is usually divided into blocks (or partitions).
• An Avail List (or Free List) is a linked list that maintains information about free memory
blocks.

Each node in the list contains:

- Starting address of the block
- Size of the block
- Link to the next free block

When a process requests memory, the OS searches the Avail List and allocates a suitable block
based on an allocation scheme.

Example
Suppose three processes arrive:

- P1 needs 75 KB
- P2 needs 180 KB
- P3 needs 440 KB

The OS must decide where in memory to place these processes from the available free blocks.
This decision is made using allocation schemes.

There are three main strategies:

1. First Fit
2. Best Fit
3. Worst Fit
First Fit
The process is allocated to the first free block that is large enough.

Example:

100 KB 200 KB 350 KB 400 KB

Free Memory:

Free blocks = 100 KB, 200 KB, 350 KB, 400 KB, then allocating of P1 (180 KB):

100 KB 200 KB 350 KB 400 KB

20
Free Memory: P1 = 180 KB
KB

Process P1 = 180 KB → allocated in 200 KB block (first block large enough).

Advantages:
• Simple to implement.
• Faster than Best Fit and Worst Fit (search stops at first match).
• Reduces allocation time.
Disadvantages:
• Leads to external fragmentation (many small unusable holes near the beginning).

Example:
After P1 allocation → leftover = 20 KB. Next process P2 = 90 KB → goes in 100 KB block,
leaving 10 KB.

100 KB 200 KB 350 KB 400 KB

10
Free Memory: P2 = 90 KB
KB
P1 = 180 KB 20 KB

Now memory looks like: 10 KB, 20 KB, 350 KB, 400 KB.

If a process P3 with 450 KB arrives, it cannot be allocated because no single memory

block of 450 KB is available, even though the total free memory is more than 450 KB. This
happens due to fragmentation.
Best Fit
The process is allocated to the smallest available block that can hold enough.
Example:

100 KB 200 KB 350 KB 400 KB

Free Memory:

Free blocks = 100 KB, 200 KB, 350 KB, 400 KB

100 KB 200 KB 350 KB 400 KB

P1 = 180 20
Free Memory: KB
KB

Process P1 = 180 KB → allocated in 200 KB block (best fit).

Advantages:
• Leaves larger free blocks available for bigger processes.
• Reduces large wastage of memory.

Disadvantages:
• Searching for the best fit takes more time (slow).
• Creates many small unusable fragments (external fragmentation).

Example:
P1 (180 KB) goes into 200 KB block → leftover = 20 KB. Over time → memory has lots of tiny
useless gaps.
Worst Fit
The process is allocated to the largest free block available.
Example:

100 KB 200 KB 350 KB 400 KB

Free Memory:

Process P1 = 180 KB → allocated in 400 KB block. Remaining free = 220 KB.

100 KB 200 KB 350 KB 400 KB

P1 = 180
Free Memory: KB
220 KB

Advantages:
• Leaves medium and small blocks free for other processes.
• Reduces small fragmentation.
• May be useful if mostly small processes arrive.

Disadvantages:
• Wastes large memory blocks.
• A future large process may not fit.

Example:
After P1 allocation, If P2 = 370 KB arrives → cannot be allocated, even though total free memory
= 870 KB.
Comparison
Feature First Fit Best Fit Worst Fit
Allocates the first free Allocates the smallest
Allocates the largest
Definition block that is large free block that is large
free block available.
enough. enough.
Reduce wasted space Leave big blocks free for
Aim Fast allocation
(minimize leftover space) future processes
Sequential from Searches entire memory Searches entire memory
Search Method
beginning of memory list list
Fast (simple scan, stop Slow (must check all Slow (must check all
Speed
early) blocks) blocks)
Space Efficient, but may cause Poor, since it may leave
Moderate
Utilization many small fragments unusable small blocks
High external
External fragmentation External fragmentation,
Fragmentation fragmentation (many small
occurs large holes split
holes)
Free blocks: 100KB,
Same free blocks Same free blocks
300KB, 200KB
Request: 120KB → Request: 120KB →
Example Request: 120KB →
Allocated to 200KB Allocated to 300KB
Allocated to 300KB (first
(smallest suitable) (largest block)
fit found)
Fast and simple to Keeps large blocks
Advantages Efficient use of space
implement available
Time-consuming search, Poor space utilization,
May waste large blocks
Disadvantages leads to many small wastes large memory
early
unusable blocks blocks

When Two Schemes Accommodate the Same Number of Processes?

→ If First Fit and Best Fit both succeed equally:

• Best Fit is preferred in theory (better memory utilization, reduces waste).

• First Fit is often preferred in real systems (faster allocation, less overhead).

→ If Worst Fit ties with another scheme: it is rarely preferred, since it usually causes poor
utilization.

Exam Tip:
Write First Fit = faster, Best Fit = efficient, Worst Fit = least preferred.
• If asked which to choose when both First Fit and Best Fit allocate the same → say: “Best
Fit is better in terms of memory utilization, but First Fit is faster in practice.”
MEMORY ALLOCATION ALGORITHMS
1. First Fit Algorithm
1. Mark all memory blocks as free.
2. For each process:
1. Start from the first free block.
2. If Process Size ≤ Block Size:
- Allocate the block to the process.
- Move to the next process.
3. Else:
- Continue checking the next free blocks.

2. Best Fit Algorithm

1. Mark all memory blocks as free.
2. For each process:
1. Search the entire list of free blocks.
2. Choose the smallest block that is large enough to hold the process.
3. Allocate the process to that block.

3. Worst Fit Algorithm

1. Mark all memory blocks as free.
2. For each process:
1. Search the entire list of free blocks.
2. Choose the largest block available that can hold the process.
3. Allocate the process to that block.
QUESTIONS
Memory blocks of size 202,302 and 101 are allocated for programs of size 150,100, 125,
100 and 100. Which allocation method is better in this case and why?

Solution:

• Free blocks: 202, 302, 101 (in this order)

• Processes: P1 = 150, P2 = 100, P3 = 125, P4 = 100, P5 = 100

202 KB 302 KB 101 KB

Free
Memory:

First Fit (scan from the beginning each time)

202 KB 302 KB 101 KB

Free
P1 P2 P3 P4
Memory:
52 77

P1: 150 → 202 → leftover 52

P2: 100 → 302 → leftover 202
P3: 125 → 202 → leftover 77
P4: 100 → 101 → leftover 1
P5: 100 → fail (only 52, 77, 1 left)

Allocated: 4/5
Free after: 52, 77, 1 (total 130)

Best Fit (choose the smallest adequate block)

150 → 202 → leftover 52

100 → 101 → leftover 1
125 → 302 → leftover 177
100 → 177 → leftover 77
100 → fail (only 52, 77, 1 left)

Allocated: 4/5
Free after: 52, 77, 1 (total 130)
Worst Fit (choose the largest adequate block)

150 → 302 → leftover 152

100 → 202 → leftover 102
125 → 152 → leftover 27
100 → 102 → leftover 2
100 → 101 → leftover 1

Allocated: 5/5
Free after: 2, 27, 1 (total 30)

Worst Fit is best for this case because it successfully allocates all 5 processes, while First
Fit and Best Fit both fail on the last 100 KB request.

SOME TO WORKOUT
1. Given five memory partitions of 300Kb, 700Kb, 400Kb, 500Kb, 800Kb (in order), how
would the first-fit, best-fit, and worst-fit algorithms place processes of 412Kb, 617 Kb, 112
Kb, and 626Kb (in order)? (6 MARKS, Ans: Best-Fit)

2. Given five memory partitions of 400Kb, 600Kb, 350Kb, 200Kb, 800Kb (in order), how
would the first-fit, best-fit, and worst-fit algorithms place processes of 520 Kb, 617 Kb, 200
Kb, and 750 Kb (in order)? (6 MARKS, Ans: Best-Fit – based on memory utilization)
MEMORY DEALLOCATION – COMPACTION
Compaction is a memory management technique used to collect scattered free memory
fragments into one large contiguous block, thereby removing external fragmentation.

Example
Suppose we have Main Memory = 1000 KB. Allocated processes and free spaces look like this:
Before Compaction:
Block Size (KB) Status
P1 200 Occupied
Hole 100 Free
P2 300 Occupied
Hole 50 Free
P3 250 Occupied
Hole 100 Free

Total free space = 100 + 50 + 100 = 250 KB

But it is scattered → no process requiring >100 KB can be loaded. So, a process P4 of 200 KB
cannot be allocated.

After Compaction:
We shift all occupied processes upwards and collect free space at the end:

Block Size (KB) Status

P1 200 Occupied
P2 300 Occupied
P3 250 Occupied
Hole 250 Free

Now total free space = 250 KB (contiguous)

→ Process P4 of 200 KB can now be allocated successfully.

Advantages
• Removes external fragmentation.
• Efficient memory usage.
• Supports loading of large processes.

Disadvantages
• Time-consuming.
• CPU remains idle during compaction.
• Not always possible in real systems.
Garbage Collection
Garbage Collection (GC) is the process of automatically or manually reclaiming memory that is
no longer in use by the program so it can be reused.

Why Needed
• Prevent memory leaks (unused memory still occupied).
• Avoid dangling pointers and undefined behavior.
• Improve memory utilization and program reliability.

Techniques
Technique Description
Mark & Sweep Marks reachable objects and frees unmarked memory.
Reference Counting Keeps a count of references; frees memory when count is zero.
Copying Copies live objects to another space, leaving garbage behind.

Difference from Compaction

• Garbage Collection: Frees memory that is no longer used.
• Compaction: Rearranges memory to eliminate fragmentation, making free memory
contiguous.
• GC may identify garbage, compaction reorganizes memory.

PYQ CORNER (AFTER SLL)

Very Important
1. Doubly Linked List – Algorithms
2. Memory allocation schemes – Theory & Problems
3. Polynomial Representation – Addition, Multiplication

All other Algorithms are equally important, Please try to study all. It is worth to study DSA !