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

Recall & Review

beginner

What is the purpose of the 'Get Length of Linked List' operation?

It counts how many nodes are in a linked list, telling us the total number of elements stored.

beginner

In a singly linked list, how do you find the length?

Start at the head node and move through each node one by one, counting until you reach the end (nullptr).

intermediate

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, 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, so we must count nodes by visiting each one.

beginner

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

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

What does the 'Get Length of Linked List' function return?

A Number of nodes in the list

B Value of the last node

C Pointer to the last node

D Sum of all node values

The function counts and returns how many nodes are 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 node pointer

D Null pointer

Counting starts from the head pointer, which points to the first node.

What condition ends the traversal when counting linked list length?

A When current node value is zero

B When count reaches 10

C When current node is null

D When current node points to head

Traversal ends when the current node pointer becomes null, meaning the list ended.

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

A O(n^2)

B O(1)

C O(log n)

D O(n)

Counting nodes requires visiting each node once, so it is O(n).

Can you get the length of a linked list instantly without traversal?

A Yes, always

B No, unless length is stored separately

C Only if list is empty

D Only for doubly linked lists

Linked lists do not store length by default, so traversal is needed unless length is tracked separately.

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

Think about walking through the list one node at a time.

Write a simple C++ function to get the length of a linked list and explain how it works.

Focus on the loop and counting logic.

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