Introduction

Counting nodes in a Linked List means finding the total number of nodes present in the list.

The task is to:

  • traverse the linked list
  • visit every node
  • increment count variable

Example:

Input:
1 -> 2 -> 3 -> 4

Output:
4

Explanation:

There are:1
2
3
4

Total nodes:
4

This problem is one of the most important basics of:

Linked List Data Structure

Constraints

 1 <= Number of Nodes <= 10^5-10^9 <= Node Value <= 10^9

Approach 1 : Brute Force (Using Extra Array)

Explanations:

Explanation:

The idea is:

  • traverse linked list
  • store nodes into array
  • return array size

Steps:

  1. Traverse linked list.
  2. Store node values.
  3. Return array length.

This approach works but:

  • uses unnecessary extra space

So direct traversal counting is preferred.

Dry Run

Input:
1 -> 2 -> 3 -> 4

Step 1:
Visit 1

Array:
[1]

Step 2:
Visit 2

Array:
[1,2]

Step 3:
Visit 3

Array:
[1,2,3]

Step 4:
Visit 4

Array:
[1,2,3,4]

Count:
4

Practice :

Complexity Analysis :

Time Complexity:- O(n)Explanation :
Each node is visited once.

Space Complexity:- O(n)
Explanation :
Extra array is used.

Approach 2 : Optimal Solution(Direct Traversal Counting)

Explanations:

Explanation:

This is the most optimized and interview-preferred solution.

The idea is:

  • traverse linked list directly
  • increment count variable
  • return total count

This avoids extra space usage.

Dry Run

Input:1 -> 2 -> 3 -> 4

Count:
0

Visit 1
Count = 1

Visit 2
Count = 2

Visit 3
Count = 3

Visit 4
Count = 4

Traversal Ends

Final Output:
4

Practice :

Complexity Analysis :

Time Complexity:- O(n)
Explanation :
Each node is visited only once.

Space Complexity:- O(1)
Explanation :
No extra space is used.


Why This Problem is Important

This problem builds the foundation for:

  • Linked List traversal
  • Pointer movement
  • Node processing
  • Sequential access
  • Dynamic data structures

Real-World Applications

Node counting in linked lists is used in:

  • Memory allocation
  • Dynamic scheduling
  • Browser history systems
  • Playlist management
  • Data stream processing

Common Beginner Mistakes

  • Forgetting NULL condition
  • Infinite traversal loops
  • Incorrect count updates
  • Losing current pointer
  • Wrong traversal logic

Interview Tip

Interviewers often expect:

  • proper linked list traversal
  • clean counting logic
  • O(n) traversal explanation
  • correct NULL handling

Always explain:

  • how traversal moves node by node
  • why linked lists require sequential traversal

Related Questions

  • Traverse Linked List
  • Search in Linked List
  • Reverse Linked List
  • Middle of Linked List
  • Detect Cycle in Linked List

Final Takeaway

The Count Nodes problem is one of the most important beginner linked list problems.

It teaches:

  • linked list traversal
  • node counting
  • pointer movement
  • sequential processing

Understanding this problem builds a strong foundation for:

  • advanced linked list algorithms
  • pointer manipulation
  • interview-level data structure questions.