# Find Length Of A Linked List Iterative And Recursive ### Problem statement

Given a singly linked list, find its length.

Input: Output: 4.
As there are 4 nodes in the linked list.

Input: Output: 0.
As there is no node in the linked list.

How do we define the length of a linked list?
The length of a linked list is the total number of nodes in it.

### Approach (Iterative)

We know how to iterate through the linked list. In an iteration, we visit each node exactly once. We can keep track of the count of each node visited and that will be the length of the linked list.

### Algorithm

• Iterate through the linked list and for each iteration increment the answer by 1.
• After the iteration completes, return the answer.

### Implementation:

```#include<stdio.h>
#include<stdlib.h>

struct Node
{
int data;
struct Node* next;
};

/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));

/* put in the data  */
new_node->data  = new_data;

/* link the old list off the new node */

/* move the head to point to the new node */
}

/* Counts no. of nodes in linked list */
{
int count = 0;  // Initialize count
struct Node* current = head;  // Initialize current
while (current != NULL)
{
count++;
current = current->next;
}
return count;
}

/* Driver program to test count function*/
int main()
{

/* Use push() to construct below list
1->2->1->3->1  */

/* Check the count function */
printf("count of nodes is %d", getCount(head));
return 0;
}
```
```
#include<bits/stdc++.h>
using namespace std;

struct Node {
int val;
Node* next;

Node(int value){
val = value;
next = NULL;
}
};

Node* new_node = new Node(new_val);
}

// function to find length of a linked list
}
}

int main(){

}

```
```class Node
{
int data;
Node next;
Node(int d) { data = d; next = null; }
}
class Length
{
public void push(int new_data)
{
Node new_node = new Node(new_data);
}
public int getCount()
{
int count = 0;
while (temp != null)
{
count++;
temp = temp.next;
}
return count;
}
public static void main(String[] args)
{
Length llist = new Length();
llist.push(1);
llist.push(3);
llist.push(1);
llist.push(2);
llist.push(1);

System.out.println("Count of nodes is " +llist.getCount());
}
}

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

def __init__(self):

def push(self, new_data):

new_node = Node(new_data)

def getCount(self):

count = 0
while (temp):
count += 1
temp = temp.next
return count

if __name__=='__main__':
llist.push(10)
llist.push(3)
llist.push(7)
llist.push(2)
print (llist.getCount())

```

#### Output

4

Time complexity: O(n), since we are traversing the linked list once.
Space complexity: O(1), as we aren’t using any extra space.
Here, ‘n’ is the number of nodes in the linked list.

### Approach (Recursive)

To solve this problem recursively, we need to break this problem down into subproblems as we do in all recursive approaches.

For a given node of a linked list, we know it will contribute 1 to the total length. So, now we need to find the length of the linked list following the current node and add 1 to it. Finding the length of the remaining list can be seen as the same problem and hence can be solved by calling the same function for the next node.

So, the length of a linked list with ‘head’ as a pointer to 1st node can be written as: length(head) = 1 + length(head->next)

The length will be 0 for an empty linked list. This can be used as the base case in our recursive function. Since it is clear what we need to do, take some time and think about how we are going to do it.

### Algorithm

• If head points to NULL, return 0. (base case)
• Else recursively call the same function for head->next and add 1 to its result.

### Implementation

```#include<stdio.h>
#include<stdlib.h>

struct Node
{
int data;
struct Node* next;
};

/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));

/* put in the data  */
new_node->data  = new_data;

/* link the old list off the new node */

/* move the head to point to the new node */
}
{
// Base Case
return 0;
}
// Count this node plus the rest of the list
else {
}
}

/* Driver program to test count function*/
int main()
{

/* Use push() to construct below list
1->2->1->3->1 */

/* Check the count function */
printf("Count of nodes is %d",ans);
return 0;
}
```
```#include<bits/stdc++.h>
using namespace std;

struct Node {
int val;
Node* next;

Node(int value){
val = value;
next = NULL;
}
};

Node* new_node = new Node(new_val);
}

}

int main(){

}

```
```class Node
{
int data;
Node next;
Node(int d) { data = d; next = null; }
}
class LengthRecursive
{
public void push(int new_data)
{
Node new_node = new Node(new_data);
}
public int getCountRec(Node node)
{
if (node == null)
return 0;
return 1 + getCountRec(node.next);
}
public int getCount()
{
}
public static void main(String[] args)
{
LengthRecursive llist = new LengthRecursive();
llist.push(1);
llist.push(3);
llist.push(1);
llist.push(2);
llist.push(1);
System.out.println("Count of nodes is " +llist.getCount());
}
}

```
```
```

#### Output

4

Time complexity: O(n), as we are completely traversing the linked list once.
Space complexity: O(n), due to recursive function call stack.

Here ‘n’ is the number of nodes in the linked list.

Through this article, we learned how to find the length of a singly linked list using both iterative and recursive methods. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.