Get Length of Linked List in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the purpose of getting the length of a linked list?

To find out how many nodes are present in the linked list, which helps in understanding its size and for operations like traversal or insertion at specific positions.

beginner

How do you traverse a linked list to count its nodes?

Start from the head node and move to the next node repeatedly until you reach the end (null), counting each node you visit.

beginner

What is the time complexity of getting the length of a singly linked list by traversal?

O(n), where n is the number of nodes in the linked list, because you visit each node once.

intermediate

Why can't we get the length of a linked list in O(1) time without extra storage?

Because linked lists do not store their size inherently, so you must count nodes by traversing. To get O(1), you need to maintain a separate size variable updated on insertions/deletions.

beginner

Show the basic Java code snippet to get the length of a singly linked list.

int length = 0; Node current = head; while (current != null) { length++; current = current.next; } // length now holds the number of nodes

What does the length of a linked list represent?

A Memory size of the list

B Value of the last node

C Number of nodes in the list

D Number of null pointers

The length is the count of nodes present in the linked list.

Which pointer do you start with to count nodes in a singly linked list?

A Head pointer

B Tail pointer

C Random pointer

D Middle pointer

Counting starts from the head node and moves forward.

What is the time complexity of counting nodes in a linked list by traversal?

A O(1)

B O(log n)

C O(n^2)

D O(n)

You must visit each node once, so time is proportional to n.

If a linked list has 5 nodes, what will be the length after traversal?

A 5

B 4

C 6

D 0

Length equals the total number of nodes, which is 5.

Which of these is needed to get length in O(1) time?

A Sorting the list

B Extra size variable updated on changes

C Recursion

D Double linked list

Maintaining a size variable updated on insert/delete allows O(1) length retrieval.

Explain how to find the length of a singly linked list step-by-step.

Think about walking through the list like counting people in a line.

Describe why linked lists do not store their length by default and how you can optimize length retrieval.

Consider the trade-off between storage and speed.

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: Length counts nodes, not values or memory [OK]

Common Mistakes:

• Confusing length with sum of values
• Thinking length is memory size
• Using first node value as length

2. Which of the following Java code snippets correctly initializes a variable to count the length of a linked list named head?

easy

A. int length = head; Node current = 0;

B. int length = 0; Node current = head;

C. Node length = 0; int current = head;

D. int length = null; Node current = head;

Solution

1. Step 1: Identify correct variable types

   Length should be an integer starting at 0; current should be a Node starting at head.

2. Step 2: Check each option

   int length = 0; Node current = head; correctly declares int length = 0; and Node current = head;. Others mix types or assign invalid values.

3. Final Answer:

   int length = 0; Node current = head; -> Option B

4. Quick Check:

   Initialize count as int 0 and pointer as Node head [OK]

Hint: Count is int zero; pointer is Node starting at head [OK]

Common Mistakes:

• Mixing variable types
• Assigning head to int
• Using null for int variable

3. What is the output of the following Java code snippet?

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

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

  public static void main(String[] args) {
    Node n1 = new Node(5);
    Node n2 = new Node(10);
    Node n3 = new Node(15);
    n1.next = n2;
    n2.next = n3;
    System.out.println(getLength(n1));
  }
}

medium

A. 0

B. 2

C. 3

D. NullPointerException

Solution

1. Step 1: Trace linked list nodes

   Nodes are n1 -> n2 -> n3, so total 3 nodes linked.

2. Step 2: Count nodes in getLength

   Loop increments count for each node until current is null, so count = 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   3 nodes counted in list [OK]

Hint: Count increments once per node until null [OK]

Common Mistakes:

• Counting nodes incorrectly
• Expecting 0 for non-empty list
• Confusing null pointer errors

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

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

medium

A. It does not count the last node

B. It causes infinite loop

C. It throws NullPointerException immediately

D. It counts nodes twice

Solution

1. Step 1: Analyze loop condition

   The loop runs while head.next != null, so it stops before last node.

2. Step 2: Check counting logic

   Since last node's next is null, it is never counted, so count misses last node.

3. Final Answer:

   It does not count the last node -> Option A

4. Quick Check:

   Loop condition excludes last node [OK]

Hint: Loop on current != null to count all nodes [OK]

Common Mistakes:

• Using head.next != null instead of head != null
• Missing last node count
• Confusing loop conditions

5. Given a linked list where each node contains an integer, write a method to find the length of the list but only count nodes with even values. Which approach is correct?

hard

A. Traverse all nodes, increment count only if node's data % 2 == 0

B. Count nodes until first odd value is found

C. Count all nodes and then subtract odd nodes count

D. Only count nodes if next node is even

Solution

1. Step 1: Understand problem requirement

   We must count nodes with even values only, ignoring odd nodes.

2. Step 2: Choose correct counting method

   Traverse entire list, check each node's data; increment count if even (data % 2 == 0).

3. Final Answer:

   Traverse all nodes, increment count only if node's data % 2 == 0 -> Option A

4. Quick Check:

   Count even nodes by checking each node [OK]

Hint: Check each node's value; count only if even [OK]

Common Mistakes:

• Stopping count at first odd node
• Subtracting odd count after full count
• Checking next node's value instead of current