Get Length of Linked List in DSA Python

Mental Model

Count each node one by one until you reach the end of the list.

Analogy: Like counting people standing in a line by moving from the first person to the last one.

head -> 1 -> 2 -> 3 -> null

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> null

Goal: Find how many nodes are in the linked list

Step 1: start at head node with value 1

head -> [curr->1] -> 2 -> 3 -> null

Why: We begin counting from the first node

Step 2: count node 1 and move curr to next node

head -> 1 -> [curr->2] -> 3 -> null

Why: Counted first node, move to second to continue counting

Step 3: count node 2 and move curr to next node

head -> 1 -> 2 -> [curr->3] -> null

Why: Counted second node, move to third node

Step 4: count node 3 and move curr to null (end)

head -> 1 -> 2 -> 3 -> [curr->null]

Why: Counted last node, reached end of list

Result:

head -> 1 -> 2 -> 3 -> null
Length = 3

Annotated Code

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, val):
        new_node = Node(val)
        if not self.head:
            self.head = new_node
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = new_node

    def get_length(self):
        count = 0
        curr = self.head
        while curr:
            count += 1  # count current node
            curr = curr.next  # move to next node
        return count

# Driver code
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
length = ll.get_length()
print(f"Length = {length}")

while curr:

loop through each node until end of list

count += 1 # count current node

increment count for each node visited

curr = curr.next # move to next node

advance pointer to next node to continue counting

Output

Length = 3

Complexity Analysis

Time: O(n) because we visit each node once to count

Space: O(1) because we only use a few variables for counting

vs Alternative: Alternative would be storing length in a variable updated on insert/delete, which uses extra space but gives O(1) length retrieval

Edge Cases

empty list

returns length 0 because head is None and loop never runs

DSA Python

while curr:

single node list

returns length 1 by counting the single node

DSA Python

while curr:

When to Use This Pattern

When you need to know how many elements are in a linked list, use a simple traversal counting each node until the end.

Common Mistakes

Mistake: Forgetting to move the current pointer to the next node inside the loop
Fix: Add 'curr = curr.next' inside the while loop to advance the pointer

Mistake: Initializing count to 1 instead of 0, causing off-by-one error
Fix: Initialize count to 0 before starting the loop

Summary

Counts the number of nodes in a linked list by visiting each node once.

Use when you need to find the size of a linked list without stored length.

The key is to start at the head and move through each node until you reach the end.

Practice

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

easy

A. The memory size of the linked list

B. The value of the first node

C. The number of nodes in the linked list

D. The value of the last node

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 C

4. Quick Check:

   Length counts nodes = number of nodes [OK]

Hint: Length = count of nodes from head to end [OK]

Common Mistakes:

• Confusing length with node values
• Thinking length is memory size
• Counting only first or last node

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

easy

A. length = None

B. length = 0

C. length = head

D. length = []

Solution

1. Step 1: Identify counting variable type

   Length should be a number starting at zero before counting nodes.

2. Step 2: Check each option

   length = 0 sets length to 0, ready to increment. Others assign wrong types.

3. Final Answer:

   length = 0 -> Option B

4. Quick Check:

   Initialize count as 0 before loop [OK]

Hint: Start counting length from zero [OK]

Common Mistakes:

• Initializing length as None or list
• Assigning length to head node
• Using wrong data types for count

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

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def get_length(head):
    count = 0
    current = head
    while current:
        count += 1
        current = current.next
    return count

# Creating linked list: 10 -> 20 -> 30 -> None
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)

print(get_length(head))

medium

A. 3

B. 2

C. 0

D. None

Solution

1. Step 1: Trace linked list nodes

   List has nodes with values 10, 20, and 30, total 3 nodes.

2. Step 2: Follow get_length function

   Function counts nodes by moving current pointer until None, increments count each step.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Count nodes 10,20,30 = 3 [OK]

Hint: Count nodes by traversing until None [OK]

Common Mistakes:

• Stopping count early
• Not incrementing count inside loop
• Returning None instead of count

4. Find the error in this code to get the length of a linked list:

def get_length(head):
    count = 0
    while head.next:
        count += 1
        head = head.next
    return count

medium

A. It misses counting the last node

B. It causes infinite loop

C. It returns None instead of count

D. It counts nodes twice

Solution

1. Step 1: Analyze loop condition

   Loop runs while head.next exists, so it stops before last node.

2. Step 2: Check counting logic

   Last node is not counted because loop ends early, count misses one node.

3. Final Answer:

   It misses counting the last node -> Option A

4. Quick Check:

   Loop condition excludes last node [OK]

Hint: Use 'while current' not 'while current.next' to count all nodes [OK]

Common Mistakes:

• Using head.next in loop condition
• Not counting last node
• Assuming loop covers all nodes

5. You have a linked list where each node contains a number. Write a function to find the length of the linked list only if all node values are positive. If any node has zero or negative value, return 0 immediately. What is the correct approach?

hard

A. Check only first node value, then count all nodes

B. Count nodes first, then check values in a second pass

C. Return length without checking values

D. Traverse nodes, if value <= 0 return 0, else count nodes till end

Solution

1. Step 1: Traverse and check values simultaneously

   Move through each node, check if value is positive.

2. Step 2: Return 0 immediately if value is zero or negative, else keep counting

   If any node fails condition, stop and return 0; otherwise, return total count.

3. Final Answer:

   Traverse nodes, if value <= 0 return 0, else count nodes till end -> Option D

4. Quick Check:

   Check values while counting, stop early if invalid [OK]

Hint: Check values during traversal, stop early if invalid [OK]

Common Mistakes:

• Counting first, then checking values
• Ignoring node values
• Checking only first node value