Java: Linear Data Structures

What are the Data Structures -

Data structure is a an organization system of data (same data type) collection. It is a system to store the data (like arrays) in the memory on the computer and the method to access and manipulate the data efficiently. There are two types of data structures -

Linear Data Structures -

In Linear data structures, data is stored sequentially and linked to previous and next elements (data). They are linked on the single level and connected in such a way that they are traversed sequentially. The data elements can be traverse in the single run using the iterations (loops). The examples of Linear Data Structures are - Arrays, Queue, Stack and LinkedList. Classes and interfaces - Arrays, Stack, Queue and LinkedList, can be accessed through java.util package. We already discussed briefly about data structures Arrays and Stack in our earlier posts - Arrays and How to create a class stack.

Stack -

• Stack is a collection of same data type elements / class objects.
• New data element is pushed (added) on top of the stack, and only the data element on the top is popped out (retrieved).
• Always the data element last pushed in the stack, will be popped out - LIFO (Last In First Out).
• Stack data elements are stored in contiguous memory locations.
• Push - pushes (appends) the new data element on top of the stack and points to the last element of the stack.
• Pop - pops (gets) the top element from the stack, uses it and the second last data element comes on top (points to the second last data element). The last retrieved element has no connection with the stack.
• Empty stack - When the last data element in the stack is popped up, stack is empty - there are no data elements left in the stack.
• Full stack - When the stack has the data elements equals to the stack size, no other element can be pushed in, the stack is full.
• Java has its own generic (For all data types) class as Stack and it has methods - push(), pop(), peek(), empty(), search()
• Example of how stack works - I have created a custom class Stack of integers in the post - How to create a class Stack.

Queue -

• Queue is a collection of same data type elements / class objects.
• New data element is put (added) in start of the queue, but only the data element in the end is got out (retrieved).
• Always the data element first put in the queue, will be retrieved - FIFO (First In First Out).
• Queue data elements are stored in contiguous memory locations.
• Put - puts (appends) the new data element on start of the queue and points to the first element of the queue.
• Get - gets (retrieves) the first element from the queue, uses it and the second data element becomes the first data element (points to the second data element). The last retrieved element has no connection with the queue.
• Empty queue - When the last data element in the queue is got out, queue is empty - there are no data elements left in the queue.
• Full queue - When the queue has the data elements equals to the queue size, no other element can be put in, the queue is full.
• Java has its own generic (For all data types) interface as Queue and to implement this interface, the programmer has to override the methods - add(), offer(), remove(), poll(), element() and peek().

Linked List -

• Linked List is a collection of same data type elements / class objects.
• New data element can be added at start, end or middle of the Linked List.
• LinkedList data elements are not stored in contiguous memory locations. Each data element is like a container which has two parts - data and address to the next data element. The last data element has address as null. 
• Any data element can be accessed randomly by using index no, and can be referred any time till it is not removed explicitly.
• Java has its own generic (For all data types) class as LinkedList and it has several methods to add, remove or manipulate data elements in the list - getFirst(), getLast(), removeFirst(), removeLast(), addFirst(), addLast(), contains(), size(), add(), remove(), addAll(), clear(), get(), set(), indexOf(), listIterator() and toArray() etc.

Non-Linear Data Structures -

In Non-Linear Data Structures, data is stored in multi-level hierarchy, and are complex to implement. The data elements can not be accessed sequentially and can't be traversed in the single run by using the iterations (loops). The examples of Non-Linear Data Structures are - Trees and Graphs.

Note: I will cover Non-Linear Data Structures in a separate post.

Java: Multiply Binary Numbers

We already know what are the binary numbers through earlier posts - What are the binary numbers, conversion between the binary numbers and decimal numbers and addition of the binary numbers. Let's discuss how to multiply binary numbers.

How to multiply bits (0 and 1)

Bits are multiplied in the similar way as we multiply the decimal numbers -

	0			0			1
x	0		x	1		x	1
	0			0			1

And -

		1	1			1	1
		x	0			x	1
		0	0			1	1

When we do binary multiplication with 2 or more bits, the approach will be the same like as normal decimal multiplication, just we do binary addition after multiplying by each of the bits - 

		1	1	1	1	=	15
			x	1	1	=	3
		1	1	1	1
+	1	1	1	1	0	x	10
1	0	1	1	0	1	=	45	Binary Addition

Here is another example -

				1	0	1	1	=	11
				x	1	0	1	=	5
				1	0	1	1
			0	0	0	0	0	x	10
	+	1	0	1	1	0	0	x	100
		1	1	0	1	1	1	=	55	Binary Addition

We already have programs to convert binary numbers to decimal and decimal to binary numbers, and to add two binary numbers. Using same methods, we will write our new class MultipleBinaryNumbers. This class uses the same methods from our previous classes - binaryToDecimal(), calcPower() and addBinaryNumbers(). A new method is added - multiplyBinaryNumbers()

// Multiplies Two Binary Numbers
public static Long multiplyBinaryNumbers(Long binary1, Long binary2) {
    Long binaryVal = 0L;

    int rem;

    int pos = 1;
    Long tempBinaryVal = 0L;

    // Multiplication is done bit by bit by binary2
    while(binary2 != 0) {
        rem = (int)(binary2 % 10);
        tempBinaryVal = binary1 * rem;
        for(int i = 1; i < pos; i++)
            tempBinaryVal = tempBinaryVal * 10;

        binaryVal = addBinaryNumbers(binaryVal, tempBinaryVal);

        pos++;
        binary2 = binary2 / 10;
    }

    int totVal = binaryToDecimal(binaryVal);
    System.out.println();
    System.out.println("Multiplication of two binary numbers => " + binaryVal +  " : " + totVal);
    return binaryVal;
}

The method takes two binary numbers as the parameters - binary1 and binary2, 

• Set the result binary number as 0
• Set the position as 1 for the rightmost bit of the second binary number
• Set the temporary binary value as 0
• While loop is run till the leftmost bit of the second binary number -

1. Gets rightmost bit using mod (%) operator
2. Multiply first binary number by bit got using step 1 and put result in the temporary variable
3. If position of the bit is greater than 1 
• Multiply temporary number by 10 to the power of position of the bit
4. Assign result binary value to the temporary binary value + last result
5. Position is increased
6. Second binary number is changed by removing the rightmost bit

Here is the whole program:

import java.util.Scanner;

public class MultiplyBinaryNumbers {
    public static void main(String args[]) {
        System.out.println("Enter two binary values");
        Scanner sc = new Scanner(System.in);
        Long binary1 = sc.nextLong();
        Long binary2 = sc.nextLong();

        int decVal1 = binaryToDecimal(binary1);
        int decVal2 = binaryToDecimal(binary2);

        System.out.println("Binary number 1 => " + binary1 + " : " + decVal1);
        System.out.println("Binary number 2 => " + binary2 + " : " + decVal2);

        multiplyBinaryNumbers(binary1, binary2);
    }

    // Converts Binary Number To Decimal Number
    public static int binaryToDecimal(Long binaryVal) {
        int decVal = 0;
        int rem, pow = 0;

        while(binaryVal != 0) {
            rem = (int)(binaryVal % 10);
            decVal = decVal + rem * calcPower(2, pow);
            binaryVal = binaryVal / 10;
            pow++;
        }
        return decVal;
    }

    // Calculate to the power
    public static int calcPower(int no1, int no2) {
        int powVal = 1;
        for(int i = 0; i < no2; i++) {
            powVal = powVal * no1;
        }
        return powVal;
    }

    // Adds Two Binary Numbers
    public static Long addBinaryNumbers(Long binary1, Long binary2) {
        Long binaryVal = 0L;

        int sum = 0;
        int rem1, rem2, remainder = 0, i = 0, pow = 0;

        // Addition is done bit by bit
        while(binary1 != 0 || binary2 != 0) {
            // rem1 is next bit of binary1 and rem2 is next bit of binary2
            rem1 = (int)(binary1 % 10);
            rem2 = (int)(binary2 % 10);

            // remaining bits of binary numbers
            binary1 = binary1 / 10;
            binary2 = binary2 / 10;

            // sum of the bits + carryover if any
            sum = (rem1 + rem2 + remainder) % 2;  // remainder is carry over
            remainder = (rem1 + rem2 + remainder) / 2;
            binaryVal = binaryVal + sum * calcPower(10, pow);
            pow++;
        }
        if(remainder != 0) {
            // If last bit addition has carryover, add it too
            binaryVal = binaryVal + calcPower(10, pow);
        }

        int totVal = binaryToDecimal(binaryVal);

        return binaryVal;
    }

    // Multiplies Two Binary Numbers
    public static Long multiplyBinaryNumbers(Long binary1, Long binary2) {
        Long binaryVal = 0L;

        int rem;

        int pos = 1;
        Long tempBinaryVal = 0L;

        // Multiplication is done bit by bit by binary2
        while(binary2 != 0) {
            rem = (int)(binary2 % 10);
            tempBinaryVal = binary1 * rem;
            for(int i = 1; i < pos; i++)
                tempBinaryVal = tempBinaryVal * 10;

            binaryVal = addBinaryNumbers(binaryVal, tempBinaryVal);

            pos++;
            binary2 = binary2 / 10;
        }

        int totVal = binaryToDecimal(binaryVal);
        System.out.println();
        System.out.println("Multiplication of two binary numbers => " + binaryVal +  " : " + totVal);
        return binaryVal;
    }
}

And Here is the output:

Enter two binary values

1011

101

Binary number 1 => 1011 : 11

Binary number 2 => 101 : 5

Multiplication of two binary numbers => 110111 : 55

The code can be accessed here: Github Link