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

Repeated DNA Sequences In Java

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: “ACGAATTCCG”. When studying DNA, it is sometimes useful to identify repeated sequences within the DNA. Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example, given String s = “AAAAAACCCCCAAAAAACCCCCCAAAAAAGGGGTTTT”, return: [“AAAAACCCCC”, “CCCCCAAAAA”,”CCCCAAAAAA”].

Solution:
The key to solving the problem is that each of the 4 nucleotides can be stored in 2 bits. So the 10 letter long sequence can be converted to 20 bits long integer. The following is a Java solution. You may use an example to manually execute the program and see how it works.

package com.algorithm.dna;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class RepeatedDNA {

    public static void main(String[] args) {
        String s = "AAAAAACCCCCAAAAAACCCCCCAAAAAAGGGGTTTT";
        for (String output : findRepeatedDnaSequences(s)) {
            System.out.println(output);
        }
    }

    public static List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new ArrayList<String>();
        int len = s.length();
        if (len < 10) {
            return result;
        }

        Map<Character, Integer> map = new HashMap<Character, Integer>();
        map.put('A', 0);
        map.put('C', 1);
        map.put('G', 2);
        map.put('T', 3);

        Set<Integer> temp = new HashSet<Integer>();
        Set<Integer> added = new HashSet<Integer>();

        int hash = 0;
        for (int i = 0; i < len; i++) {
            if (i < 9) {
                hash = (hash << 2) + map.get(s.charAt(i));
            } else {
                hash = (hash << 2) + map.get(s.charAt(i));
                hash = hash & (1 << 20) - 1;
                if (temp.contains(hash) && !added.contains(hash)) {
                    result.add(s.substring(i - 9, i + 1));
                    added.add(hash);
                } else {
                    temp.add(hash);
                }
            }
        }
        return result;
    }
}

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;
    }
}