Decimal Equivalent of Binary Linked List

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

We will be given a Binary linked list, i.e, a list where each node will be having either 0 or 1 as its data, and we need to find its decimal equivalent.

Problem Statement Understanding

Let's try to understand the problem with the help of an example:

If the linked list given to us is 1→1→0→1→NULL

  • According to the problem statement, we need to find the decimal equivalent of the given binary list.
  • We can see that the binary equivalent of the given list is 1101.
  • Now, on converting this binary equivalent 1101 into decimal, we get 13.
  • So, the output will be 13.

Let’s take another example.
If the linked list given to us is 1→1→0→1→0→1→NULL.

  • In this case, the binary equivalent of the given list is 110101.
  • Now, on converting the binary equivalent 110101 into decimal, we get 53.
  • So, the output will be 53.

At this point, we have understood the problem statement. Now we will try to formulate an approach for this problem.

Before moving to the approach section, try to think about how you can approach this problem.

  • If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let’s move to the approach section.

Approach

Our approach will be straightforward:

  • We will iterate the list from starting and accumulate the result in a variable.
  • While we move through the list, the position of binary numbers that have been encountered till now in our result shifts by one to the left.
    • So that’s why we will multiply our result by 21 (as there is a shift by one position) and add the current position’s data.
  • Finally, we will be left with a decimal number, which will be our final decimal representation of our binary list.

Algorithm

  • Initialize an ans variable by 0 and a curr pointer by the head of the list.
  • Run a while loop till the curr pointer is not NULL.
  • Every time inside the loop, multiply the ans by 2 and add the curr->data in ans.
  • Move the curr pointer by one node.
  • Return the ans after the loop breaks.

Dry Run

Code Implementation

#include 
using namespace std;

class Node {
    public:
    int data;
    Node* next;
    Node(int d)
    {
        data = d;
        next = NULL;
    }
};

// This function will return decimal
// equivalent of a binary list
int binaryToDecimal(Node *head)
{
    // Initialize 'ans' by 0
    int ans = 0;
    // initialize 'curr' by 'head'
    Node* curr = head;
   
    // run a while loop till 'curr' is not NULL
    while (curr != NULL)
    {
        // multiply the 'ans' by 2 and add
       // 'curr' data to it
        ans = (ans * 2) + curr->data;
 
        // move 'curr' by one node 
        curr = curr->next;
    }
    return ans;
}

int main()
{
    Node *list = new Node(1);
    list->next = new Node(1);
    list->next->next = new Node(0);
    list->next->next->next = new Node(1);
    cout<<"Decimal Equivalent of the given binary list is: ";
    cout<

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

class LinkedList:

	def __init__(self):
		self.head = None

	# this function will return decimal
	# equivalent of a binary linked list
	def decimalValue(self, head):
		
		# Initialized result
		res = 0

		# Traverse linked list
		while head:

			# Multiply result by 2 and
			# add head's data
			res = (res << 1) + head.data

			# Move Next
			head = head.next
			
		return res

if __name__ == '__main__':

	llist = LinkedList()

	llist.head = Node(1)
	llist.head.next = Node(1)
	llist.head.next.next = Node(0)
	llist.head.next.next.next = Node(1)
	
	print("Decimal Equivalent of the given binary list is: {}".format(
		llist.decimalValue(llist.head)))

class BinaryLinkedList
{
	
// Link list Node /
static class Node
{
	boolean data;
	Node next;
};

// Returns decimal value of binary linked list /
static int decimalValue( Node head)
{
	// Initialized result
	int res = 0;

	// Traverse linked list
	while (head != null)
	{
		// Multiply result by 2 and add
		// head's data
		res = (res << 1) + (head.data?1:0);

		// Move next
		head = head.next;
	}
	return res;
}

// Utility function to create a new node.
static Node newNode(int data)
{
	Node temp = new Node();
	temp.data = (data==1? true:false);
	temp.next = null;
	return temp;
}

// Driver code/
public static void main(String args[])
{
	// Start with the empty list /
	Node head = newNode(1);
	head.next = newNode(0);
	head.next.next = newNode(1);
	head.next.next.next = newNode(1);

	System.out.print( "Decimal value is "+decimalValue(head));
}
}
#include
#include
#include

struct Node
{
    bool data;
    struct Node* next;
};
 
/* Returns decimal value of binary linked list */
int decimalValue(struct Node *head)
{
    // Initialized result
    int  res = 0;
 
    // Traverse linked list
    while (head != NULL)
    {
        // Multiply result by 2 and add
        // head's data
        res = (res  << 1) + head->data;
 
        // Move next
        head = head->next;
    }
    return res;
}
 
// Utility function to create a new node.
struct Node *newNode(bool data)
{
    struct Node *temp =(struct Node *)malloc(sizeof(struct Node));
    temp->data = data;
    temp->next = NULL;
    return temp;
}
 
/* Driver program to test above function*/
int main()
{
    /* Start with the empty list */
    struct Node* head = newNode(1);
    head->next = newNode(0);
    head->next->next = newNode(1);
    head->next->next->next = newNode(1);
	int ans = decimalValue(head);
	printf("Decimal value is %d ",ans);
 
    return 0;
}

Output

Decimal Equivalent of the given binary list is: 13

Time Complexity: O(n), where n is the number of nodes in the linked list.
[forminator_quiz id="5247"]

So, in this blog, we have tried to explain how you can get the decimal equivalent of a binary list in the most optimal way. 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.

Leave a Reply

Your email address will not be published. Required fields are marked *