Get Length of Linked List in DSA C++ - Execution Trace

Concept Flow - Get Length of Linked List

Start at head node

↓

Is current node NULL?

Yes→Stop

No↓

Increment count by 1

↓

Move to next node

↩Back to check current node

Start from the head node, check if current node exists. If yes, count it and move to next node. Repeat until no nodes left.

Execution Sample

DSA C++

int getLength(Node* head) {
    int count = 0;
    Node* current = head;
    while (current != nullptr) {
        count++;
        current = current->next;
    }
    return count;
}

Counts nodes in a linked list by moving from head to end, incrementing count for each node.

Execution Table

Step	Operation	Current Node	Count	Visual State
1	Start at head	Node(1)	0	1 -> 2 -> 3 -> null
2	Check current != null	Node(1)	0	1 -> 2 -> 3 -> null
3	Increment count	Node(1)	1	1 -> 2 -> 3 -> null
4	Move to next node	Node(2)	1	1 -> 2 -> 3 -> null
5	Check current != null	Node(2)	1	1 -> 2 -> 3 -> null
6	Increment count	Node(2)	2	1 -> 2 -> 3 -> null
7	Move to next node	Node(3)	2	1 -> 2 -> 3 -> null
8	Check current != null	Node(3)	2	1 -> 2 -> 3 -> null
9	Increment count	Node(3)	3	1 -> 2 -> 3 -> null
10	Move to next node	null	3	1 -> 2 -> 3 -> null
11	Check current != null	null	3	1 -> 2 -> 3 -> null

💡 Current node is null, end of list reached, total count is 3

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	Final
count	0	1	2	3	3
current	Node(1)	Node(2)	Node(3)	null	null

Key Moments - 3 Insights

Why do we check if current node is null before counting?

Because if current is null, it means we reached the end of the list and there are no more nodes to count. This is shown in execution_table rows 2, 5, 8, and 11.

Why do we move to next node after incrementing count?

We count the current node first, then move to the next node to continue counting. This order ensures no node is skipped, as seen in steps 3 and 4, 6 and 7, 9 and 10.

What happens if the list is empty (head is null)?

The loop never runs because current is null at start, so count stays 0. This is implied by the exit condition in step 11.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of count at step 6?

A 1

B 2

C 3

D 0

💡 Hint

Check the 'Count' column at step 6 in execution_table

At which step does current node become null?

A Step 10

B Step 9

C Step 11

D Step 8

💡 Hint

Look at 'Current Node' column where it changes to null

If the linked list had 5 nodes instead of 3, how many times would count increment?

A 3

B 4

C 5

D 6

💡 Hint

Count increments once per node, see variable_tracker for count changes

Concept Snapshot

Get Length of Linked List:
- Start at head node
- While current node is not null:
  - Increment count
  - Move to next node
- Return count
Counts nodes by traversing list from head to end.

Full Transcript

To get the length of a linked list, start at the head node. Check if the current node exists. If yes, add one to the count and move to the next node. Repeat this until the current node is null, which means the end of the list. The count then holds the total number of nodes. If the list is empty, the count remains zero. This method ensures every node is counted exactly once.

Practice

1. What does the function getLength do when given the head of a linked list?

easy

A. Deletes the linked list

B. Returns the value of the first node

C. Returns the number of nodes in the linked list

D. Returns the last node of the linked list

Solution

1. Step 1: Understand the function purpose

   The function getLength counts nodes starting from the head until the end.

2. Step 2: Identify the output

   It returns the total count of nodes, which is the length of the linked list.

3. Final Answer:

   Returns the number of nodes in the linked list -> Option C

4. Quick Check:

   Counting nodes = length [OK]

Hint: Count nodes one by one until null [OK]

Common Mistakes:

• Confusing length with node value
• Trying to delete nodes instead of counting
• Returning the last node instead of count

2. Which of the following is the correct syntax to initialize a pointer to the head of a linked list in C++?

easy

A. Node* head = NULL;

B. Node head = NULL;

C. Node* head = 0;

D. Node head = 0;

Solution

1. Step 1: Understand pointer initialization

   In C++, a pointer to a node is declared as Node* and can be initialized to NULL or nullptr.

2. Step 2: Check each option

   Node* head = NULL; uses Node* head = NULL; which is correct pointer initialization syntax.

3. Final Answer:

   Node* head = NULL; -> Option A

4. Quick Check:

   Pointer declaration uses * and NULL [OK]

Hint: Use * for pointers and NULL for empty [OK]

Common Mistakes:

• Declaring pointer without *
• Assigning NULL to non-pointer variable
• Using 0 instead of NULL (less clear)

3. What will be the output of the following code snippet?

struct Node {
  int data;
  Node* next;
};

int getLength(Node* head) {
  int count = 0;
  while (head != NULL) {
    count++;
    head = head->next;
  }
  return count;
}

int main() {
  Node n3 = {30, NULL};
  Node n2 = {20, &n3};
  Node n1 = {10, &n2};
  int length = getLength(&n1);
  std::cout << length;
  return 0;
}

medium

A. 3

B. 2

C. 1

D. 0

Solution

1. Step 1: Trace the linked list nodes

   The list has nodes n1 -> n2 -> n3 -> NULL, so total 3 nodes.

2. Step 2: Count nodes in getLength

   The function counts each node until NULL, so count becomes 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   3 nodes counted = 3 [OK]

Hint: Count nodes by following next pointers until NULL [OK]

Common Mistakes:

• Counting only first node
• Off-by-one error in loop
• Confusing data values with count

4. Identify the error in the following code that tries to get the length of a linked list:

int getLength(Node* head) {
  int count = 0;
  while (head->next != NULL) {
    count++;
    head = head->next;
  }
  return count;
}

medium

A. It causes a segmentation fault

B. It misses counting the last node

C. It counts nodes twice

D. It returns the data of the last node

Solution

1. Step 1: Analyze the loop condition

   The loop runs while head->next != NULL, so it stops before the last node.

2. Step 2: Check counting logic

   Since last node is not counted, the returned count is one less than actual length.

3. Final Answer:

   It misses counting the last node -> Option B

4. Quick Check:

   Loop condition excludes last node [OK]

Hint: Use while(head != NULL) to count all nodes [OK]

Common Mistakes:

• Using head->next in loop condition
• Not counting last node
• Confusing node data with count

5. Given a linked list where each node contains an integer, how would you modify the getLength function to return the length only if all node values are positive? If any node has zero or negative value, return -1.

hard

A. Count nodes normally and ignore values

B. Return -1 if list is empty, else return length

C. Return length only if first node is positive

D. Traverse nodes, if value <= 0 return -1, else count nodes and return count

Solution

1. Step 1: Traverse each node checking value

   While moving through the list, check if node's data is <= 0; if yes, return -1 immediately.

2. Step 2: Count nodes if all values positive

   If all nodes have positive values, count them and return the count as length.

3. Final Answer:

   Traverse nodes, if value <= 0 return -1, else count nodes and return count -> Option D

4. Quick Check:

   Check values during count, return -1 if any non-positive [OK]

Hint: Check values while counting, stop early if non-positive [OK]

Common Mistakes:

• Ignoring node values during count
• Checking only first node value
• Returning length even if negative values exist