Last Updated: Mar 27, 2024

# Decimal Equivalent of Binary Linked List

## Introduction

In this problem we have been given a linked list and value at each node is either 0 or 1, ie. binary numbers. Now what we want to do is we want to find out is what will be the decimal number if we try to look at the linked list as the representation of a binary number.

We can understand this more properly below.

Input  : 0->0->0->1->0->0->1->0

Output : 18 ie. 2^1 + 2^4

Input  : 1->0->0

Output : 4 ie. 2^2

## Observations

1. We can observe that the head is the most significant bit and then the tail is the least significant bit.
2. Letâ€™s suppose the length of the linked list is n, then the answer is sum of values of the linked list multiplied by 2^(k-1) where k = n-i, where i is the number of steps away from head.

We can achieve the same calculation if we always multiply the current ans with 2 at each step of traversal of linked list and add the current value. If the current value if 1 it will add 1 to the answer else it will just be ignored.

Recommended Topic, Floyds Algorithm

## Algorithm

• Initialise ans=0,
• Traverse the whole linked list, and each step makes the result double and then add the current value to it.
• Traverse till the list is empty.

## Code

``````int LinkedListToDecimal(Node* head)
{
// we are given the head of the linked list, we have to return the decimal value.
int ans=0; // initialising the ans to be zero.
{
ans=ans*2 + head->val; // multiplying the current value to 2
}
return ans;
}

# we are given the head of the linked list, we have to return the decimal value.
ans=0 # initialising the ans to be zero.
ans=ans*2 + head.value # multiplying the current value to 2
# and then adding the value of the node to the answer.
return ans``````

## Time Complexity

We are iterating the linked list once so the complexity will be Linear ie. O(n).

Must read decimal to binary c++

#### What is a binary linked list?

A Binary Linked List is a linked list with all its nodes data either 0 or 1. Find the decimal number that is equivalent to a given binary linked list. Let's solve this by taking an example. A binary linked list with binary number 101001. Let's take the above example with binary number 101001

#### What is a linked list in data structure?

In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.

#### What is the binary system?

Binary number system, in mathematics, positional numeral system employing 2 as the base and so requiring only two different symbols for its digits, 0 and 1, instead of the usual 10 different symbols needed in the decimal system.

#### How is the linked list represented in memory?

Linked lists can be represented in memory by using two arrays respectively known as INFO and LINK, such that INFO[K] and LINK[K] contain information of element and next node address respectively.

## Conclusion

So in this article we learnt how we can convert a binary linked list into a decimal number and also wrote the code for it in python and c++.

Check out our Coding Ninjas Studio Guided Path to learn about Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and more, Take a look at the mock test series and participate in the contests hosted by Coding Ninjas Studio if you want to improve your coding skills. If you are new to preparation and want to work for firms such as Amazon, Microsoft, Uber, and others, you should review the problemsinterview experiences, and interview bundle for placement preparations.

Consider taking one of our paid courses to give yourself and your profession an edge!

Please vote for our blogs if you find them valuable and exciting.

Happy Learning!!

Topics covered
1.
Introduction
2.
Observations
3.
Algorithm
4.
Code
5.
Time Complexity
6.
6.1.
What is a binary linked list?
6.2.
What is a linked list in data structure?
6.3.
What is the binary system?
6.4.
How is the linked list represented in memory?
7.
Conclusion