Linked Lists Complete Study Guide — Data Structures Chapter 4
What Is a Linked List? — The Big Picture
Imagine you are standing in a long queue. You know who is in front of you, but you cannot see the person at the end of the line directly. To reach the last person, you must walk through every single person one by one. That is exactly how a linked list works.
In earlier chapters, you learned about arrays. An array stores data in continuous memory locations. For example, if you declare an array A[100], the computer sets aside 100 memory slots right next to each other. The problem? That memory is fixed. You cannot make it bigger or smaller while the program is running.
A linked list solves this problem. It is a linear collection of data elements called nodes, and these nodes are connected to each other using pointers. There is no need for continuous memory. Each node can live anywhere in memory, and the pointer tells you where to find the next node.
Inside a Node — The Building Block
Every linked list is made of nodes. Think of a node as a small box. This box has two parts:
- Data part (Information field): This stores the actual value — it could be an integer, a name, a float number, or any data you want.
- Link part (Next pointer / Address field): This stores the memory address of the next node in the list.
The NEXT field is also called the link field or pointer field. It is the part that connects one node to the next.
The START Pointer and the NULL Pointer
There are two more very important concepts you must understand:
- START pointer: This is a special external pointer that holds the address of the first node in the list. If START = NULL, it means the list is empty (no nodes at all).
- NULL pointer: The last node in the list has its NEXT field set to NULL. This does not point to any address. It simply means “this is the end of the list — stop here.”
Look at the diagram above. START points to Node 1. Node 1’s pointer points to Node 2. Node 2’s pointer points to Node 3. Node 3’s pointer is NULL — it is the end of the list.
If a linked list has only one node, what will the NEXT field of that node contain?
The NEXT field will contain NULL. Since there is no second node, the only node is also the last node. The last node always has NULL in its NEXT field to indicate the end of the list.
Why Do We Need Linked Lists? — Advantages
Now, you might ask: “Why not just use arrays?” That is a very good question. Let me explain the advantages of linked lists clearly.
1. Dynamic Size — Grow and Shrink Freely
In an array, the size is fixed at compile time. If you declare int A[100], you get exactly 100 slots — no more, no less. But a linked list is dynamic. You can add a new node whenever you need it, and you can remove a node when you do not need it. The size changes during program execution.
2. Efficient Memory Utilization
In arrays, memory is pre-allocated even if you do not use all of it. If you declare 100 slots but only use 10, the remaining 90 slots are wasted. In a linked list, memory is allocated only when needed (using the new operator). When a node is deleted, its memory is released (using the delete operator). No waste!
3. Easy Insertion and Deletion
In an array, inserting or deleting an element requires shifting many elements. If you insert at position 2 in an array of 1000 elements, you must shift 998 elements to the right. That is slow! In a linked list, you only need to change a few pointers. No shifting needed!
4. Supports Complex Applications
Many advanced data structures like stacks, queues, graphs, and trees are built using linked lists. They form the foundation of many complex applications.
Q1 (MCQ): Which of the following is TRUE about linked lists?
A) Memory is pre-allocated at compile time
B) Nodes are stored in continuous memory locations
C) The size can grow or shrink during program execution
D) Random access to any element is direct and fast
C) The size can grow or shrink during program execution
Explanation: This is the key feature of a linked list. Options A and B describe arrays, not linked lists. Option D is false because linked lists do NOT support random access — you must traverse from the beginning to reach any element.
Q2 (True/False): In a linked list, memory is allocated only when a new node is needed.
TRUE. This is called dynamic memory allocation. Memory is not pre-allocated. It is given only when you create a new node using the new operator.
Q3 (Fill in the Blank): The _________ pointer holds the address of the first node, and the _________ pointer in the last node indicates the end of the list.
START pointer holds the address of the first node, and the NULL pointer in the last node indicates the end of the list.
Disadvantages of Linked Lists
Everything has two sides. Let me be honest with you — linked lists also have some disadvantages that you must know for the exam.
1. More Memory Per Element
To store a single integer (say, the number 10), an array uses just the space for that integer. But in a linked list, each node needs space for both the data AND the pointer. So storing the same integer 10 requires extra memory for the NEXT field. This overhead adds up when you have thousands of nodes.
2. No Random Access — Slow to Reach Any Element
In an array, you can directly access A[50] in one step. But in a linked list, to reach the 50th node, you must start from the first node and walk through all 49 nodes before it. This is called sequential access, and it is time consuming.
Q1 (MCQ): Why does a linked list use more memory than an array for the same data?
A) Because nodes are larger in physical size
B) Because each node stores both data and a pointer
C) Because linked lists use double memory
D) Because pointers are larger than data
B) Because each node stores both data and a pointer
Explanation: The extra pointer field in every node adds memory overhead. If you store 100 integers, the array needs space for 100 integers only. The linked list needs space for 100 integers PLUS 100 pointers.
Q2 (Short Answer): Can you access the 100th element of a linked list directly? Why or why not?
No. A linked list does not support random access. You must start from the START pointer and traverse through nodes 1, 2, 3, …, 99 to finally reach the 100th node. There is no formula or index to jump directly to any node.
Quick Review: Pointers, new, and delete
Before we dive into operations, let me quickly remind you about pointers and dynamic memory. This is essential because linked lists completely depend on these concepts.
A pointer is a variable that stores the memory address of another variable. In C++, we use the new operator to allocate memory dynamically, and the delete operator to free that memory.
Pointer_Variable = new data_type;
Examples:
$int\ *Var1 = new\ int;$
$float\ *Var2 = new\ float;$
General form of delete:
$delete\ Pointer\_Variable;$
$delete\ Var1;$
When you write new int, the computer finds an empty memory slot big enough for an integer and returns its address. The pointer variable stores that address. When you write delete Var1, that memory slot is released and can be reused.
new stays alive until you explicitly destroy it with delete. If you forget to delete, you cause a “memory leak” — the examiners love to ask about this!Q1 (MCQ): What happens to memory allocated with new if you never use delete?
A) It is automatically freed when the function ends
B) It stays occupied and cannot be reused (memory leak)
C) It is moved to a different location
D) The program crashes immediately
B) It stays occupied and cannot be reused (memory leak)
Explanation: Unlike local variables, dynamically allocated memory is NOT automatically freed. It remains allocated until you explicitly call delete. This is called a memory leak and is a common programming error.
Operations on Linked Lists — Full Detail
Now we come to the heart of this chapter. There are six main operations performed on linked lists:
- Creation — Creating a new linked list
- Insertion — Adding a new node
- Deletion — Removing a node
- Traversing — Visiting all nodes from start to end
- Searching — Finding a specific node
- Concatenation — Joining two linked lists
How We Represent a Node in Code
Before we learn the algorithms, look at how a node is defined using a struct:
struct node {
char name[20]; // Data field — name up to 20 letters
int age; // Data field — age as integer
node *nxt; // Pointer to next node
};
struct node *start_ptr = NULL; // START pointer, initially empty list
Here, each node has two data fields (name and age) and one pointer field (nxt). The start_ptr is initialized to NULL, which means the list is empty at the beginning.
Insertion in Singly Linked List — Three Cases
Insertion means adding a new node into the list. There are three positions where you can insert:
- At the beginning of the list
- At the end of the list
- At any specified position in between
Case 1: Insert at the Beginning
This is the simplest case. Let me walk you through it step by step with an example.
Example: We have a list: 20 → 30 → NULL. We want to insert 10 at the beginning.
2 Create a NewNode
3 NewNode → DATA = 10
4 If START is NULL (empty list), then NewNode → Link = NULL
5 Else, NewNode → Link = START (new node points to old first node)
6 START = NewNode (START now points to the new node)
7 Done!
The key insight here is: the new node must point to the OLD first node, and then START must be updated to point to the NEW node. If you do it in the wrong order, you lose the rest of the list!
Q1 (MCQ): When inserting a node at the beginning of a linked list, which step must be done FIRST?
A) START = NewNode
B) NewNode → Link = START
C) NewNode → Link = NULL
D) Create the NewNode
B) NewNode → Link = START
Explanation: You must connect the new node to the existing list BEFORE moving START. If you set START = NewNode first, the old list is lost because nothing points to it anymore. Creating the node (D) happens even before B, but among the pointer operations, B comes first.
Q2 (True/False): If the linked list is empty (START = NULL), inserting at the beginning sets the new node’s link to NULL.
TRUE. When the list is empty, there is no next node. So the new node’s link must be set to NULL, and START points to this single node. It is both the first and last node.
Case 2: Insert at the End
Now let us insert at the end of the list. This requires us to traverse to the last node first.
Example: List: 10 → 20 → NULL. Insert 30 at the end.
2 Create a NewNode
3 NewNode → DATA = 30
4 NewNode → Next = NULL (it will be the last node)
5 If START is NULL (empty list), then START = NewNode
6 Else:
a) TEMP = START
b) While (TEMP → Next is not NULL):
TEMP = TEMP → Next (keep moving forward)
7 TEMP → Next = NewNode (connect last node to new node)
8 Done!
The while loop is the critical part. It moves TEMP from node to node until TEMP reaches the last node (where TEMP → Next is NULL). Then we connect that last node to our new node.
Q1 (MCQ): In the “insert at end” algorithm, what condition does the while loop check?
A) TEMP → DATA is not NULL
B) TEMP → Next is not NULL
C) START is not NULL
D) NewNode is not NULL
B) TEMP → Next is not NULL
Explanation: The loop keeps moving TEMP forward as long as the current node has a next node. When TEMP → Next becomes NULL, it means TEMP is at the last node, and the loop stops.
Q2 (Fill in the Blank): When inserting at the end of an empty list, the new node’s Next is set to _________ and START is set to _________.
The new node’s Next is set to NULL and START is set to NewNode. Since the list was empty, the new node becomes the only node — it is both first and last.
Case 3: Insert at Any Specified Position
This is the most flexible case. You specify a position number, and the new node is inserted after that position.
Example: List: 10 → 20 → 30 → NULL. Insert 25 at position 1 (after the node at index 1, which is 20).
2 TEMP = START; k = 0
3 While (k < POS):
a) TEMP = TEMP → Next
b) If TEMP is NULL: display “List has fewer nodes than position” and exit
c) k = k + 1
4 Create NewNode; NewNode → DATA = 25
5 NewNode → Next = TEMP → Next
6 TEMP → Next = NewNode
7 Done!
Steps 5 and 6 are the most critical. Look at the order carefully:
- Step 5: NewNode → Next = TEMP → Next (the new node points to whatever the current node was pointing to)
- Step 6: TEMP → Next = NewNode (the current node now points to the new node)
If you reverse these two steps, you lose the rest of the list!
Q1 (MCQ): In the “insert at position” algorithm, what happens if POS is greater than the number of nodes in the list?
A) The node is inserted at the end automatically
B) The algorithm displays an error message and exits
C) The program crashes
D) The node replaces the last node
B) The algorithm displays an error message and exits
Explanation: Inside the while loop, there is a check: if TEMP becomes NULL (meaning we ran out of nodes before reaching the position), it displays “Node in the list less than the position” and exits. This prevents invalid insertion.
Q2 (True/False): In “insert at position,” you must set TEMP → Next = NewNode BEFORE setting NewNode → Next = TEMP → Next for correct results.
FALSE. It must be the opposite order. You must set NewNode → Next = TEMP → Next FIRST, then set TEMP → Next = NewNode. If you do it the other way, you lose the address of the remaining nodes.
Q3 (Short Answer): In the insert-at-position algorithm, why do we initialize k = 0 and check k < POS?
We use k as a counter starting from 0 (which represents the first node, position 0). The loop runs while k < POS, moving TEMP forward each time. When k equals POS, TEMP is pointing to the node AT that position, and the new node will be inserted AFTER this node.
Deletion in Singly Linked List
Deletion means removing a node that contains a specific DATA value from the list. The algorithm searches for the data and removes the node when found. Let me explain it clearly.
Example: List: 10 → 20 → 30 → NULL. Delete the node with data 20.
2 If START → DATA equals DATA (deleting the first node):
a) TEMP = START
b) START = START → Next
c) Free TEMP (release memory)
d) Exit
3 HOLD = START
4 While (HOLD → Next → Next is not NULL):
a) If HOLD → Next → DATA equals DATA:
i) TEMP = HOLD → Next
ii) HOLD → Next = TEMP → Next
iii) Free TEMP
iv) Exit
b) HOLD = HOLD → Next
5 If HOLD → Next → DATA equals DATA (checking the last node):
a) TEMP = HOLD → Next
b) Free TEMP
c) HOLD → Next = NULL
d) Exit
6 Display “DATA not found”
7 Exit
Let me break down the logic so you never get confused:
- Step 2: Handles the special case where the first node itself contains the data to delete. We simply move START to the second node.
- Step 4: Uses HOLD as a “look-ahead” pointer. HOLD → Next → Next checks TWO nodes ahead. This ensures we never go past the last node in this loop. If HOLD → Next contains the data, we bypass it by setting HOLD → Next = TEMP → Next.
- Step 5: After the loop, we check if the LAST node contains the data. If yes, we free it and set HOLD → Next = NULL.
Q1 (MCQ): In the deletion algorithm, what is the purpose of the HOLD pointer?
A) To hold the data to be deleted
B) To keep track of the node BEFORE the one being checked for deletion
C) To point to the last node
D) To count the number of nodes
B) To keep track of the node BEFORE the one being checked for deletion
Explanation: HOLD always stays one node behind. When we find that HOLD → Next contains the data to delete, we can easily bypass it by setting HOLD → Next = TEMP → Next. Without HOLD, we cannot reconnect the list after deletion.
Q2 (True/False): After deleting a node, we must free its memory using the delete operator.
TRUE. If you only remove the node from the list by changing pointers but do not free the memory, that memory remains occupied but unreachable — this is a memory leak.
Q3 (Fill in the Blank): If the node to be deleted is the first node, we set START = _________.
We set START = START → Next. This moves the START pointer to the second node, effectively removing the first node from the list.
Traversing a Linked List
Traversing means visiting every node from the first to the last, one by one. In a singly linked list, you can only traverse in the forward direction (left to right). There is no way to go backward because each node only has a NEXT pointer, not a PREVIOUS pointer.
The basic idea is simple:
2 While (TEMP is not NULL):
a) Process TEMP → DATA (print it, count it, etc.)
b) TEMP = TEMP → Next (move to the next node)
3 End
The loop continues until TEMP becomes NULL (which happens after we process the last node and try to move to the next one).
Q1 (MCQ): In a singly linked list, traversing is possible in:
A) Both forward and backward directions
B) Only the forward direction
C) Only the backward direction
D) Random direction
B) Only the forward direction
Explanation: A singly linked list has only a NEXT pointer in each node. There is no PREVIOUS pointer, so you cannot go backward. To go backward, you need a doubly linked list.
Types of Linked Lists
The textbook covers three types of linked lists. Let me explain each one clearly.
1. Singly Linked List
This is what we have been studying so far. Each node has one pointer (NEXT). You can only move forward. The last node points to NULL.
2. Doubly Linked List
Each node has three fields: a left pointer (Lpoint), data, and a right pointer (Rpoint). You can move both forward and backward. This is the most flexible type.
3. Circular Linked List
Similar to a singly linked list, but the last node points back to the first node instead of NULL. There is no “end” — it forms a circle.
Q1 (MCQ): Which type of linked list allows both forward and backward traversal?
A) Singly linked list
B) Circular linked list
C) Doubly linked list
D) Both B and C
C) Doubly linked list
Explanation: Only the doubly linked list has both a previous (Lpoint) and next (Rpoint) pointer in each node, enabling bidirectional traversal. A circular linked list still uses only one direction of pointers.
Q2 (Fill in the Blank): In a circular linked list, the NEXT field of the last node contains the address of the _________ node.
The NEXT field of the last node contains the address of the first node. This creates a cycle — there is no NULL at the end.
Doubly Linked List — Detailed Explanation
Now let us study the doubly linked list in depth, as the textbook gives specific algorithms for it.
Structure of a Doubly Linked List Node
Each node has three fields:
- Lpoint (Left Pointer): Holds the address of the previous node
- Data: Stores the actual information
- Rpoint (Right Pointer): Holds the address of the next node
Notice that the first node’s Lpoint is NULL (no previous node) and the last node’s Rpoint is NULL (no next node). Every node in between has both pointers connected to their neighbors.
Insertion in Doubly Linked List
The algorithm inserts a new node at a specified position (POS). Let me walk through it.
2 TEMP = START; i = 0
3 While (i < POS) AND (TEMP is not NULL):
TEMP = TEMP → RPoint; i = i + 1
4 If (TEMP is not NULL) AND (i equals POS):
a) Create NewNode; NewNode → DATA = DATA
b) NewNode → RPoint = TEMP → RPoint
c) NewNode → LPoint = TEMP
d) (TEMP → RPoint) → LPoint = NewNode
e) TEMP → RPoint = NewNode
5 Else: Display “Position NOT found”
6 Exit
Steps 4b through 4e are the heart of the algorithm. Let me explain each one with a diagram.
Example: List: NULL ↔ 10 ↔ 20 ↔ NULL. Insert 15 at position 0 (after node at index 0, which is 10).
1. $NewNode \rightarrow RPoint = TEMP \rightarrow RPoint$
2. $NewNode \rightarrow LPoint = TEMP$
3. $(TEMP \rightarrow RPoint) \rightarrow LPoint = NewNode$
4. $TEMP \rightarrow RPoint = NewNode$
Q1 (MCQ): How many pointers need to be updated when inserting a node in a doubly linked list (not at the ends)?
A) 2
B) 3
C) 4
D) 1
C) 4
Explanation: You must update NewNode’s RPoint, NewNode’s LPoint, the next node’s LPoint, and the current node’s RPoint. That is four pointer changes total.
Q2 (True/False): In doubly linked list insertion, if you update TEMP → RPoint before NewNode → RPoint, the algorithm still works correctly.
FALSE. If you set TEMP → RPoint = NewNode first, you lose the original address that TEMP → RPoint was holding (the address of the next node). Then you cannot set NewNode → RPoint correctly. The order is critical.
Q3 (Fill in the Blank): In a doubly linked list, the Lpoint of the first node is _________ and the Rpoint of the last node is _________.
The Lpoint of the first node is NULL (there is no previous node) and the Rpoint of the last node is NULL (there is no next node).
Q4 (Short Answer): Why is step 4d — (TEMP → RPoint) → LPoint = NewNode — necessary in the doubly linked list insertion algorithm?
Step 4d updates the Lpoint of the node that comes AFTER the insertion point. Before insertion, that node’s Lpoint was pointing to TEMP. After insertion, a new node (NewNode) is placed between TEMP and that node. So that node’s Lpoint must be changed from TEMP to NewNode. Without this step, the backward link would be broken.
Singly vs. Doubly Linked List — Comparison
| Feature | Singly Linked List | Doubly Linked List |
|---|---|---|
| Pointers per node | One (NEXT) | Two (LPOINT and RPOINT) |
| Memory per node | Less | More (extra pointer) |
| Traversal | Forward only | Forward and backward |
| Insertion complexity | Simpler (fewer pointer updates) | More complex (4 pointer updates) |
| Deletion complexity | Needs one predecessor pointer | Easier (can go backward directly) |
| End markers | NULL at last node | NULL at both ends |
Q1 (MCQ): Which linked list type requires more memory per node but allows backward traversal?
A) Singly linked list
B) Circular singly linked list
C) Doubly linked list
D) Static array
C) Doubly linked list
Explanation: The doubly linked list stores an extra pointer (Lpoint) in each node, which increases memory usage. But this extra pointer enables backward traversal, which is not possible in singly linked lists.
Chapter Summary — Everything to Remember for the Exam
Linked List Basics: A linear data structure of nodes connected by pointers. Each node = Data + Next pointer. START holds first node address. NULL marks the end.
Advantages: Dynamic size, efficient memory (allocate on demand), easy insert/delete (no shifting), supports complex applications.
Disadvantages: Extra memory per node (pointer overhead), no random access (sequential only — slow to reach specific positions).
Operations: Creation, Insertion (beginning/end/position), Deletion, Traversing, Searching, Concatenation.
Insert at Beginning: NewNode → Link = START, then START = NewNode. Order matters!
Insert at End: Traverse with TEMP until TEMP → Next = NULL, then TEMP → Next = NewNode.
Insert at Position: Traverse to position, then NewNode → Next = TEMP → Next, then TEMP → Next = NewNode.
Doubly Linked List: Each node has Lpoint + Data + Rpoint. Insertion requires 4 pointer updates in specific order. Supports bidirectional traversal.
Memory Operators: new allocates memory, delete frees memory. Never forget to delete — prevent memory leaks!
Challenge Conceptual Exam Questions
Test your understanding with these difficult questions. Each one is designed to check deep conceptual knowledge.
Explanation: START points to 5 (0 traversals). To reach 15, you traverse once (5 → 15). To reach 25, twice. To reach 35, three times. You traverse the pointers between nodes: 5→15 (1), 15→25 (2), 25→35 (3). You always need (n-1) traversals to reach the nth node.
Explanation: This is a famous trick. If you cannot go backward, you copy the data from the NEXT node into the current node, then delete the next node (which you CAN do because you have the current node’s pointer to reach it). This is a workaround, not a standard deletion, but it works for non-last nodes.
Explanation: TEMP → LPoint takes you to the previous node. That previous node’s RPoint should point back to the next node, which is TEMP. This is the fundamental property of a correctly built doubly linked list — every forward link has a matching backward link.
Explanation: When the list is empty, there are no other nodes to point to. So the new node’s Link = NULL (it is the only node, hence also the last). START = NewNode because this node is now the first (and only) node in the list.
Explanation: Inserting at the beginning requires only a constant number of operations regardless of the list size: create node, set its link to START, update START. No traversal is needed. Hence, it is O(1) — constant time.
Explanation: To insert at the end, you must traverse the entire list to reach the last node. If there are n nodes, you need n-1 pointer traversals. This is proportional to n, so the complexity is O(n).
Using HOLD → Next → Next not equal to NULL ensures that HOLD → Next is NEVER the last node inside the loop. This is important because inside the loop body, the algorithm accesses HOLD → Next → DATA and HOLD → Next → Next. If HOLD → Next were the last node, then HOLD → Next → Next would be NULL, and the algorithm could not safely access TEMP → Next when setting HOLD → Next = TEMP → Next. The separate step 5 after the loop handles the case where the last node contains the data to be deleted.
Explanation: The new operator allocates memory but does NOT initialize it for basic types like int and float. The memory contains whatever garbage value was previously there. You must explicitly assign a value. (Note: new int() with parentheses would initialize to zero, but new int without parentheses does not.)
Explanation: In a standard (non-circular) doubly linked list, the first node’s Lpoint is NULL and the last node’s Rpoint is NULL. All other pointers (internal nodes’ Lpoint and Rpoint) point to actual nodes. So there are exactly 2 NULL pointers regardless of how many nodes there are.
Explanation: The third step updates the backward pointer of the node that comes after the insertion point: (TEMP → RPoint) → LPoint = NewNode. The fourth step updates the forward pointer of the current node: TEMP → RPoint = NewNode. This completes all four pointer updates needed for the insertion.
Explanation: When START = NULL, the list is empty. You CAN insert at the beginning (the new node becomes the only node) and you CAN insert at the end (same result for empty list). But you CANNOT delete because the deletion algorithm first checks START → DATA, and if START is NULL, accessing START → DATA causes a null pointer error — there is no node to check or delete.
Explanation: In a singly linked list, traversal stops when TEMP becomes NULL. But in a circular linked list, TEMP never becomes NULL because the last node points back to the first. The stopping condition must check if TEMP has returned to the START node (or use a do-while loop that checks after the first iteration).
The order is wrong. When the student sets START = NewNode first, START now points to the new node. Then when they set NewNode → Link = START, the new node points to ITSELF (because START is now the new node). The rest of the original list is lost forever. The correct order is: NewNode → Link = START FIRST, then START = NewNode.
Explanation: Inserting at the beginning of a linked list is O(1) — just change two pointers. In an array, inserting at the beginning requires shifting ALL elements one position to the right, which is O(n). Accessing the 50th element is O(1) in an array but O(n) in a linked list, so the linked list is WORSE for that. Searching and sorting have similar complexities in both structures.
Explanation: Concatenation takes two separate linked lists and connects them by making the last node of the first list point to the first node of the second list. After concatenation, you have one combined list accessible from a single START pointer.
Explanation: The pointer “nxt” needs to store the address of another node, which is of type “struct node”. So the pointer type must be “node *” to correctly interpret the memory it points to. Without the correct type, the compiler would not know what structure exists at that address.
Explanation: A single node in a doubly linked list has no previous node (so Lpoint = NULL) and no next node (so Rpoint = NULL). This node is both the first and last node of the list.
This check prevents attempting to insert at a position that does not exist. If the user requests position 10 but the list only has 3 nodes, TEMP will become NULL before the counter reaches 10. Without this check, the algorithm would try to access TEMP → Next on a NULL pointer, causing a runtime error. The check catches this problem early and displays an appropriate error message.
Explanation: The six primitive operations listed in the textbook are: Creation, Insertion, Deletion, Traversing, Searching, and Concatenation. Sorting is NOT listed as a primitive operation. While you can sort a linked list, it is considered an advanced operation built from the primitive ones, not a primitive itself.
Explanation: To delete the last node, you set the second-to-last node’s Next pointer to NULL (indicating it is now the last node), and then free the memory of the node that was previously last. The freed node is the one that HOLD → Next was pointing to before the update.
Explanation: 100 nodes were allocated, 90 were properly freed. The remaining 10 nodes were never deleted, so their memory is still occupied but unreachable — these are 10 memory leaks. Each undeleted node is one leak.
Explanation: To delete a node (say TEMP) from a doubly linked list, you set: (TEMP → LPoint) → RPoint = TEMP → RPoint (previous node’s Rpoint skips over TEMP) and (TEMP → RPoint) → LPoint = TEMP → LPoint (next node’s Lpoint skips over TEMP). That is 2 pointer updates. Then you free TEMP. This is actually simpler than insertion (which needs 4 updates).
If START is NULL, the list is empty. In a correctly written traversal algorithm, you set TEMP = START (so TEMP = NULL), then check “while TEMP is not NULL.” Since TEMP is NULL, the loop body never executes. The traversal simply does nothing — it visits zero nodes. This is correct behavior for an empty list. However, if the algorithm does NOT have the NULL check and directly tries to access TEMP → DATA, it would cause a null pointer error.
Explanation: The only structural difference is the extra Lpoint (left pointer) field in each node. A singly linked list node has Data + Next. A doubly linked list node has Lpoint + Data + Rpoint. The data field can be the same in both types.
Explanation: Searching means looking for a specific value. You start at the first node and check if its DATA field matches the target. If not, you move to the next node and repeat. You continue until you either find a match or reach NULL (end of list without finding it).