Get Length of Linked List in DSA C# - Time & Space Complexity

Time Complexity: Get Length of Linked List

O(n)

Understanding Time Complexity

We want to know how long it takes to find the length of a linked list as the list grows.

How does the time needed change when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public int GetLength(Node head) {
    int count = 0;
    Node current = head;
    while (current != null) {
        count++;
        current = current.next;
    }
    return count;
}
    

This code counts how many nodes are in a linked list by moving through each node once.

Identify Repeating Operations

• Primary operation: Looping through each node in the linked list.
• How many times: Once for every node in the list (n times).

How Execution Grows With Input

As the list gets longer, the time to count nodes grows directly with the number of nodes.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The steps increase evenly as the list size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to get the length grows in a straight line with the number of nodes.

Common Mistake

[X] Wrong: "Getting the length is instant because we just need one number."

[OK] Correct: We must visit each node to count them, so time grows with list size.

Interview Connect

Knowing how to find the length of a linked list efficiently is a basic skill that shows you understand list traversal and loops.

Self-Check

"What if the linked list stored its length as a variable updated on insertions? How would the time complexity change?"

Practice

1. What does the length of a linked list represent?

easy

A. The sum of all node values

B. The value of the first node

C. The memory size of the linked list

D. The number of nodes in the linked list

Solution

1. Step 1: Understand linked list structure

   A linked list is made of nodes connected one after another.

2. Step 2: Define length meaning

   The length is how many nodes are present in the list.

3. Final Answer:

   The number of nodes in the linked list -> Option D

4. Quick Check:

   Length = count of nodes [OK]

Hint: Count nodes to get length quickly [OK]

Common Mistakes:

• Confusing length with node values
• Thinking length is memory size
• Assuming length is sum of values

2. Which of the following C# code snippets correctly initializes a variable to count the length of a linked list?

easy

A. int length = 0;

B. int length = null;

C. string length = "0";

D. bool length = false;

Solution

1. Step 1: Identify correct data type for counting

   Length is a number, so it should be an integer type.

2. Step 2: Check initialization value

   Start counting from zero before traversing nodes.

3. Final Answer:

   int length = 0; -> Option A

4. Quick Check:

   Use int and start at 0 [OK]

Hint: Use int zero to start counting length [OK]

Common Mistakes:

• Using null for int variable
• Using string instead of int
• Using bool for counting

3. What will be the output of the following C# code?

public class Node {
  public int data;
  public Node next;
  public Node(int d) { data = d; next = null; }
}

public class LinkedList {
  public Node head;
  public int GetLength() {
    int count = 0;
    Node current = head;
    while (current != null) {
      count++;
      current = current.next;
    }
    return count;
  }
}

LinkedList list = new LinkedList();
list.head = new Node(5);
list.head.next = new Node(10);
list.head.next.next = new Node(15);
Console.WriteLine(list.GetLength());

medium

A. 0

B. 2

C. 3

D. Error

Solution

1. Step 1: Count nodes in the linked list

   Nodes are 5 -> 10 -> 15, total 3 nodes.

2. Step 2: Trace GetLength method

   Loop increments count for each node until null is reached.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   3 nodes counted = 3 [OK]

Hint: Count each node until null to get length [OK]

Common Mistakes:

• Counting only head node
• Returning zero without counting
• Confusing next pointer with data

4. Identify the error in this C# method to get linked list length:

public int GetLength() {
  int count = 0;
  Node current = head;
  while (current.next != null) {
    count++;
    current = current.next;
  }
  return count;
}

medium

A. It misses counting the last node

B. It causes infinite loop

C. It returns count plus one extra

D. It throws null reference exception

Solution

1. Step 1: Analyze loop condition

   Loop runs while current.next is not null, so last node is skipped.

2. Step 2: Understand counting effect

   Count increments only for nodes before last, missing last node.

3. Final Answer:

   It misses counting the last node -> Option A

4. Quick Check:

   Loop condition excludes last node [OK]

Hint: Use current != null to include last node [OK]

Common Mistakes:

• Using current.next != null instead of current != null
• Not incrementing count for last node
• Assuming loop covers all nodes

5. Given a linked list where each node contains an integer, how would you modify the length calculation to count only nodes with even values?

public int GetEvenLength() {
  int count = 0;
  Node current = head;
  while (current != null) {
    // Your code here
    current = current.next;
  }
  return count;
}

hard

A. Add count++ unconditionally inside the loop

B. Add if (current.data % 2 == 0) count++; inside the loop

C. Add if (current.data % 2 != 0) count++; inside the loop

D. Return head.data instead of count

Solution

1. Step 1: Check node value for evenness

   Use modulo operator to test if data is even (data % 2 == 0).

2. Step 2: Increment count only if node is even

   Inside loop, increment count only when condition is true.

3. Final Answer:

   Add if (current.data % 2 == 0) count++; inside the loop -> Option B

4. Quick Check:

   Count only even nodes [OK]

Hint: Use modulo to filter even nodes before counting [OK]

Common Mistakes:

• Counting all nodes without condition
• Counting odd nodes instead of even
• Returning node data instead of count