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

First and Second Highest sum from unsorted Array in Java

Finding the highest and second highest sum from unsorted array in Java is one of the frequently asked question in most of the interviews. They can also ask to write only for finding the highest value sum from unsorted array with single iteration. I am not going to explain more of theory, let’s have a look at below programs.

 

Before going into the first and second highest sum, let’s find highest sum. The below source code will help you to find the same.

package com.ds.practice;

public class HighestSum1 {

public static void main(String[] args) {
// Given unsorted array
int[] ar = { 10, 20, 30, 4, 50, 10 };
// Hold highest two values from array
int first = 0, second = 0;
for (int i = 0; i < ar.length; i++) {
// check the value is greater than first
// if yes, assign first to second and hold new value in first
if (ar[i] > first) {
second = first;
first = ar[i];
}
}

System.out.println(first + second);
}
}

The below source code is the another way of finding the highest sum from an unsorted array in java. This way will help you to find second highest sum from given unsorted array in java.

package com.ds.practice;

public class HighestSum {

public static void main(String[] args) {
// Given unsorted array
int[] ar = { 10, 20, 30, 4, 50, 10 };
// Parameters to hold two highest values from array
int first, second;

//if array has only 1 element
if (ar.length < 2) {
System.out.println(ar[0]);
}
//if array has only 2 elements
else if (ar.length < 3) {
System.out.println(ar[0] + ar[1]);
}
//if array has more than 2 elements
else {

// take first 2 elements into first and second
if (ar[0] > ar[1]) {
first = ar[0];
second = ar[1];
} else {
first = ar[1];
second = ar[0];
}

//loop remaining elements in array and change first and second values based on value
for (int i = 2; i < ar.length; i++) {
if (ar[i] > first) {
second = first;
first = ar[i];
} else if (ar[i] > second && ar[i] != first) {
second = ar[i];
}
}

//Printing final highest sum
System.out.println(first + second);
}
}
}

Now, we will enter into the actual problem. The below source will help you how to find highest and second highest sum from given unsorted array in java.

package com.ds.practice;

public class MaxFirstSecondSum {

public static void main(String[] args) {
// Given unsorted array
int[] ar = { 10, 20, 30, 4, 50, 10 };
// Parameters to hold highest 3 values from array
int first = 0, second = 0, third = 0;
// if array has only 1 element
if (ar.length < 2) {
System.out.println(ar[0]);
}
// if array has only 2 elements
else if (ar.length < 3) {
third = ar[0] > ar[1] ? ar[0] : ar[1];
System.out.println(ar[0] + ar[1] + " " + third);
}
// if array has more than 2 elements
else {
// Holding first two elements from array
if (ar[0] > ar[1]) {
first = ar[0];
second = ar[1];
} else {
first = ar[1];
second = ar[0];
}
// Actual logic to find top 3 elements from array
for (int i = 2; i < ar.length; i++) {
if (ar[i] > first) {
third = second;
second = first;
first = ar[i];
} else if (ar[i] > second && ar[i] != first) {
third = second;
second = ar[i];
}
}
System.out.println((first + second) + " " + (second + third));
}
}
}

Stack ADT using Array in Java

The current post contains the custom implementation of Stack ADT using Array in Java. StackArray class is the reference of Stack implementation using Array with the fixed size elements.

• push(): is used to store elements in Stack. It will throw StackOverflowError, if stack is full.
• pop(): is used to remove top element from Stack. It will throw EmptyStackException, if Stack if empty.
• peek(): is used to get top most element from Stack. It will throw EmptyStackException, if Stack if empty.
• search(): is used to find the element is present or not in Stack. It will throw EmptyStackException, if Stack if empty.
• show(): is used to print total elements present in Stack. It will throw EmptyStackException, if Stack if empty.
• isEmpty(): is used to find the Stack is empty or not. It will return true/false based on Stack.
• isFull(): is used to find the Stack is full or not. It will return true/false based on Stack.
• size(): is used to fine the Stack size.

package com.dsalgorithms.stack;

import java.util.EmptyStackException;
/*
* Author : Subbareddy
*
* StackArray class is the reference of Stack implementation using Array in Java.
*
*/
public class StackArray {

private int size;
private int index = 0;
private int[] ar;

/*
* StackArray constructor is used to create an array with passing size
*
* Input: integer value
*/
public StackArray(int size){
this.size = size;
ar = new int[size];
}

/*
* push() used to insert element into the stack
*
* Input: integer value
*
* Throws StackOverflowError error if stack is full
*/
public void push(int element){
if(isFull())
throw new StackOverflowError();

ar[index] = element;
index++;
}

/*
* pop() method removes the top most element and return the deleted element
*
* Throws EmptyStackException if Stack is empty
*/
public int pop(){
if(isEmpty())
throw new EmptyStackException();

return ar[--index];
}

/*
* peek() method returns the top most element in the Stack
*
* Throws EmptyStackException exception if Stack is empty
*/
public int peek(){
if(isEmpty())
throw new EmptyStackException();

return ar[index];
}

/*
* search() method verifies the element is present or not in the Stack
*
* Input: integer value
*
* Throws EmptyStackException exception if Stack is empty
*/
public int search(int element){
if(isEmpty())
throw new EmptyStackException();

for(int i=0;i<index;i++){
if(ar[i] == element)
return ar[i-1];
}
return -1;
}

/*
* show() method will print Stack elements
*
* Throws EmptyStackException exception if Stack is empty
*/
public void show(){
if(isEmpty())
throw new EmptyStackException();

for(int i=0;i<index;i++){
System.out.println(ar[i]);
}
}

/*
* isEmpty() method validates whether the Stack is empty or not
*
* Throws EmptyStackException exception if Stack is empty
*/
public boolean isEmpty(){
if(index == 0)
return true;

return false;
}

/*
* isFull() method will return true or false based on Stack is full or not
*/
public boolean isFull(){
if(index == size)
return true;

return false;
}

/*
* size() method will return total stack size
*/
public int size(){
return index;
}



public static void main(String[] args) {
//Creating an Empty stack with the size of 10
StackArray stack = new StackArray(10);
System.out.println("Initial Size of Stack is: "+stack.size());

//Pushing 1 to 10 integer type elements into Stack
System.out.println("\nPUSH 1-10 VALUES INTO STACK");

for(int i=0;i<10;i++){
stack.push(i+1);
}

//Printing the Stack size after pushing elements into Stack
System.out.println("\nAfter PUSH stack size: "+stack.size());

//Printing total number of elements from Stack
stack.show();

//Remove/Pop top 5 elements from Stack
System.out.println("\nPOP 5 elements from Stack");
for(int i=0;i<5;i++){
System.out.println(stack.pop());
}

//Printing total elements after performing pop
stack.show();

//Searching for specific element from Stack
int position = stack.search(2);
if(position == -1)
System.out.println("\nElement not present in stack");
else
System.out.println("\nElement located in the position of "+position);

}

}