Program to find size of Doubly Linked List
Last Updated :
11 Jan, 2023
Given a doubly linked list, the task is to find the size of that doubly linked list. For example, the size of the below linked list is 4.
A doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.
Traversal of a doubly linked list can be in either direction. In fact, the direction of traversal can change many times, if desired.
For example, the function should return 3 for the above doubly linked list.
Algorithm :
- Initialize size to 0.
- Initialize a node pointer, temp = head.
- Do following while temp is not NULL
- temp = temp -> next
- size++;
- Return size.
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node *next;
struct Node *prev;
};
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
new_node->prev = NULL;
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node ;
(*head_ref) = new_node;
}
int findSize(struct Node *node)
{
int res = 0;
while (node != NULL)
{
res++;
node = node->next;
}
return res;
}
int main()
{
struct Node* head = NULL;
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
cout << findSize(head);
return 0;
}
|
C
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
void push(struct Node** head, int new_data)
{
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = *head;
new_node->prev = NULL;
if ((*head) != NULL) {
(*head)->prev = new_node;
}
(*head) = new_node;
}
int findSize(struct Node* node)
{
int res = 0;
while (node != NULL) {
res++;
node = node->next;
}
return res;
}
int main()
{
struct Node* head = NULL;
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
printf("%d", findSize(head));
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class Node
{
int data;
Node next, prev;
Node(int val)
{
data = val;
next = null;
prev = null;
}
}
class GFG
{
static Node push(Node head, int data)
{
Node new_node = new Node(data);
new_node.next = head;
new_node.prev = null;
if (head != null)
head.prev = new_node;
head = new_node;
return head;
}
static int findSize(Node node)
{
int res = 0;
while (node != null)
{
res++;
node = node.next;
}
return res;
}
public static void main(String args[])
{
Node head = null;
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
System.out.println(findSize(head));
}
}
|
Python3
class Node:
def __init__(self):
self.data = None
self.next = None
self.prev = None
def push( head_ref, new_data):
new_node = Node()
new_node.data = new_data
new_node.next = (head_ref)
new_node.prev = None
if ((head_ref) != None):
(head_ref).prev = new_node
(head_ref) = new_node
return head_ref
def findSize(node):
res = 0
while (node != None):
res = res + 1
node = node.next
return res
head = None
head = push(head, 4)
head = push(head, 3)
head = push(head, 2)
head = push(head, 1)
print(findSize(head))
|
C#
using System;
public class Node
{
public int data;
public Node next, prev;
public Node(int val)
{
data = val;
next = null;
prev = null;
}
}
class GFG
{
static Node push(Node head, int data)
{
Node new_node = new Node(data);
new_node.next = head;
new_node.prev = null;
if (head != null)
head.prev = new_node;
head = new_node;
return head;
}
static int findSize(Node node)
{
int res = 0;
while (node != null)
{
res++;
node = node.next;
}
return res;
}
public static void Main(String []args)
{
Node head = null;
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
Console.WriteLine(findSize(head));
}
}
|
Javascript
<script>
class Node {
constructor(val) {
this.data = val;
this.prev = null;
this.next = null;
}
}
function push(head , data) {
var new_node = new Node(data);
new_node.next = head;
new_node.prev = null;
if (head != null)
head.prev = new_node;
head = new_node;
return head;
}
function findSize(node) {
var res = 0;
while (node != null) {
res++;
node = node.next;
}
return res;
}
var head = null;
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
document.write(findSize(head));
</script>
|
Complexity Analysis:
- Time Complexity: O(n), as we are using a loop to traverse n times. Where n is the number of nodes in the linked list.
- Auxiliary Space: O(1), as we are not using any extra space.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...