Custom LinkedList implementation using Java

LinkedList is one of the most used data structure. We know how to use java.util.LinkedList class in Java. But, most of them are not aware, how it has been implemented it’s methods internally. Please have a look at below program to know how LinkedList will work internally.

Note: This is not exactly equal to the java.util.LinkedList implementation. This is a custom implementation of LinkedList class.

package com.ds.practice.linked;

public class LinkedList<T> {
 Node head;

 static class Node<T> {
  Node next;
  T data;

  public Node(T data) {
   this.data = data;
   next = null;
  }
 }

 public void add(T new_data) {
  addLast(new_data);
 }

 public void addFirst(T new_data) {
  Node new_node = new Node<Object>(new_data);
  new_node.next = head;
  head = new_node;
 }

 public void add(Node prevNode, T new_data) {
  if (prevNode == null) {
   System.out.println("The give previous Node can't be null");
   return;
  }

  Node new_Node = new Node<Object>(new_data);
  new_Node.next = prevNode.next;
  prevNode.next = new_Node;

 }

 public void addLast(T new_data) {
  if (head == null) {
   head = new Node<Object>(new_data);
   return;
  }

  Node new_node = new Node<Object>(new_data);
  new_node.next = null;

  Node last = head;
  while (last.next != null)
   last = last.next;

  last.next = new_node;
  return;
 }

 public void print() {
  if (head == null) {
   System.out.println("LinkedList is empty");
   return;
  }

  Node tempNode = head;
  while (tempNode != null) {
   System.out.println(tempNode.data + "");
   tempNode = tempNode.next;
  }
 }

 @SuppressWarnings("unchecked")
 public T removeFirst() {
  if (head == null)
   return null;

  Node temp = head;
  if (temp.next == null) {
   head = null;
  } else {
   head = temp.next;
  }
  return (T) temp.data;
 }

 @SuppressWarnings("unchecked")
 public T remove(T data) {
  Node temp = head, prev = null;
  if (temp != null && temp.data == data) {
   head = temp.next;
   return (T) temp.data;
  }

  while (temp != null && temp.data != data) {
   prev = temp;
   temp = temp.next;
  }

  if (temp == null)
   return null;

  prev.next = temp.next;
  return (T) temp.data;
 }

 @SuppressWarnings("unchecked")
 public T removeLast() {
  Node temp = head;
  while (temp.next.next != null)
   temp = temp.next;
  T result = (T) temp.next.data;
  temp.next = null;
  return result;
 }

 public int size() {
  Node temp = head;
  int count = 0;
  while (temp != null) {
   count++;
   temp = temp.next;
  }
  return count;

 }

 public boolean search(T data) {
  Node temp = head;

  while (temp != null) {
   if (temp.data == data)
    return true;

   temp = temp.next;
  }

  return false;

 }

 public static void main(String[] args) {
  LinkedList<Integer> inList = new LinkedList<Integer>();
  inList.add(2);
  inList.addFirst(1);
  inList.addLast(4);
  inList.add(inList.head.next, 4);
  inList.print();
  System.out.println();
  System.out.println("Removed from LinkedList: " + inList.remove(25));
  inList.print();
  System.out.println(inList.search(10));
  System.out.println("Size of the LinkedList is: " + inList.size());
  System.out.println("\n");
  LinkedList<String> stList = new LinkedList<String>();
  stList.add("Subba");
  stList.addLast("Reddy");
  stList.addFirst("Nallamachu");
  System.out.println("Removed First element: " + stList.removeFirst());
  System.out.println("Removed Last element: " + stList.removeLast());
  stList.print();
 }

}

Advertisement

Bitwise AND of Numbers range

Problem:
Given a range [m,n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive. For example, given the range [5,7], you should return 4.

Solution:
The key to solving this problem is bitwise AND consecutive number. You can use the following the example to walk through the code.

———————————————————————————
  8    4    3    2
———————————————————————————
 5 | 0 1 0 1
 6 | 0 1 1 0
 7 | 0 1 1 1
———————————————————————————

package com.algorithm.bitwise;

public class BitwiseAND {

    public static void main(String[] args) {
        System.out.println(rangeBitwiseAnd(5, 7));
    }

    public static int rangeBitwiseAnd(int m, int n) {
        while (n > m) {
            n = n & n - 1;
        }
        return m & n;
    }
}

Sum of two integers without plus operator

Problem:

Calculate the sum of two integers a and b, but you are not supposed to use + operator. For example, given a=1 and b=2, return 3.

Solution:
Given two numbers a and b, a&b returns the number formed by 1 bits on a and b. When it is left shifted by 1 bit, it is the carry.
For example, give a = 101 and b = 111(binary), a&b = 101. a&b << 1 =1010. a^b is the number formed by different bits of a and b. a&b=10.

package com.algorithm.twosum;

public class TwoSumWithoutPlusOperator {

    public static void main(String[] args) {
        System.out.println("Sum of a and b is: " + getSum(1, 2));
    }

    private static int getSum(int a, int b) {
        while (b != 0) {
            int c = a & b;
            a = a ^ b;
            b = c << 1;
        }
        return a;
    }
}

As per the above, the output is like Sum of a and b is: 3