AF
HomeTagSubmit NotesAsk AnythingLoginSubscribe Us
AF
1. Feel Free to ask and submit anything on Anyforum.in and get satisfactory answer
2. Registration is not compulsory, you can directly login via google or facebook
3. Our Experts are looking for yours ?.



programming-basics: Could you explain the data Structures concepts in Java?

Data Structure Concepts Like " Single Liked List, Double Liked List, BST".

Explain Above mention concepts with Insertion, Deletion of Nodes.

programming x 150
basics x 169
Posted On : 2017-11-18 14:55:49.0
profile MOHAMMAD SALEEM BASHA - anyforum.in MOHAMMAD SALEEM BASHA
266150
up-rate
5
down-rate

Answers


Singly Linked List Implementation in Java:
---------------------------------------------------------------------------------
public class SinglyLinkedListImpl<T> {

private Node<T> head;
private Node<T> tail;

public void add(T element){

Node<T> nd = new Node<T>();
nd.setValue(element);
System.out.println("Adding: "+element);
/**
* check if the list is empty
*/
if(head == null){
//since there is only one element, both head and
//tail points to the same object.
head = nd;
tail = nd;
} else {
//set current tail next link to new node
tail.setNextRef(nd);
//set tail as newly created node
tail = nd;
}
}

public void addAfter(T element, T after){

Node<T> tmp = head;
Node<T> refNode = null;
System.out.println("Traversing to all nodes..");
/**
* Traverse till given element
*/
while(true){
if(tmp == null){
break;
}
if(tmp.compareTo(after) == 0){
//found the target node, add after this node
refNode = tmp;
break;
}
tmp = tmp.getNextRef();
}
if(refNode != null){
//add element after the target node
Node<T> nd = new Node<T>();
nd.setValue(element);
nd.setNextRef(tmp.getNextRef());
if(tmp == tail){
tail = nd;
}
tmp.setNextRef(nd);

} else {
System.out.println("Unable to find the given element...");
}
}

public void deleteFront(){

if(head == null){
System.out.println("Underflow...");
}
Node<T> tmp = head;
head = tmp.getNextRef();
if(head == null){
tail = null;
}
System.out.println("Deleted: "+tmp.getValue());
}

public void deleteAfter(T after){

Node<T> tmp = head;
Node<T> refNode = null;
System.out.println("Traversing to all nodes..");
/**
* Traverse till given element
*/
while(true){
if(tmp == null){
break;
}
if(tmp.compareTo(after) == 0){
//found the target node, add after this node
refNode = tmp;
break;
}
tmp = tmp.getNextRef();
}
if(refNode != null){
tmp = refNode.getNextRef();
refNode.setNextRef(tmp.getNextRef());
if(refNode.getNextRef() == null){
tail = refNode;
}
System.out.println("Deleted: "+tmp.getValue());
} else {
System.out.println("Unable to find the given element...");
}
}

public void traverse(){

Node<T> tmp = head;
while(true){
if(tmp == null){
break;
}
System.out.println(tmp.getValue());
tmp = tmp.getNextRef();
}
}

public static void main(String a[]){
SinglyLinkedListImpl<Integer> sl = new SinglyLinkedListImpl<Integer>();
sl.add(3);
sl.add(32);
sl.add(54);
sl.add(89);
sl.addAfter(76, 54);
sl.deleteFront();
sl.deleteAfter(76);
sl.traverse();

}
}

class Node<T> implements Comparable<T> {

private T value;
private Node<T> nextRef;

public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}
public Node<T> getNextRef() {
return nextRef;
}
public void setNextRef(Node<T> ref) {
this.nextRef = ref;
}
@Override
public int compareTo(T arg) {
if(arg == this.value){
return 0;
} else {
return 1;
}
}
}


Doubly Linked List Implementation in Java:
-------------------------------------------------------------------------------
public class DoublyLinkedList {

int size =0;
Node head = null;
Node tail = null;

public Node addAtStart(int data){
System.out.println("Adding Node " + data + " at the start");
Node n = new Node(data);
if(size==0){
head = n;
tail = n;
}else{
n.next = head;
head.previous = n;
head = n;
}
size++;
return n;
}

public Node addAtEnd(int data){
System.out.println("Adding Node " + data + " at the End");
Node n = new Node(data);
if(size==0){
head = n;
tail = n;
}else{
tail.next = n;
n.previous = tail;
tail =n;
}
size++;
return n;
}

public Node addAfter(int data, Node prevNode){
if(prevNode==null){
System.out.println("Node after which new node to be added cannot be null");
return null;
}else if(prevNode==tail){//check if it a last node
return addAtEnd(data);
}else{
System.out.println("Adding node after "+ prevNode.data);
//create a new node
Node n = new Node(data);

//store the next node of prevNode
Node nextNode = prevNode.next;

//make new node next points to prevNode
n.next = nextNode;

//make prevNode next points to new Node
prevNode.next = n;

//make nextNode previous points to new node
nextNode.previous = n;

//make new Node previous points to prevNode
n.previous = prevNode;
size++;
return n;
}
}

public void deleteFromStart(){
if(size==0){
System.out.println("\nList is Empty");
}else{
System.out.println("\ndeleting node " + head.data + " from start");
head = head.next;
size--;
}
}

public void deleteFromEnd(){
if(size==0){
System.out.println("\nList is Empty");
}else if(size==1){
deleteFromStart();
}else{
//store the 2nd last node
int x = tail.data;
Node prevTail = tail.previous;

//detach the last node
tail = prevTail;
tail.next=null;
System.out.println("\ndeleting node " + x + " from end");
size--;
}
}

public int elementAt(int index){
if(index>size){
return -1;
}
Node n = head;
while(index-1!=0){
n=n.next;
index--;
}
return n.data;
}

//get Size
public int getSize(){
return size;
}

public void print(){
Node temp = head;
System.out.print("Doubly Linked List: ");
while(temp!=null){
System.out.print(" " + temp.data);
temp = temp.next;
}
System.out.println();
}

public static void main(String[] args) {
DoublyLinkedList d = new DoublyLinkedList();
Node x = d.addAtStart(2);
d.addAtStart(1);
d.print();
d.addAtEnd(3);
d.print();
d.addAfter(4,x);
d.print();
d.deleteFromStart();
d.print();
System.out.println("Element at index 2: "+d.elementAt(2));
d.addAtStart(1);
d.print();
d.deleteFromEnd();
d.print();
System.out.println("Size of the Linked List: " + d.getSize());
}
}
class Node{
int data;
Node next;
Node previous;
public Node(int data){
this.data = data;
next = null;
previous = null;
}
}

BST Implementation in Java:
------------------------------------------------------------
public class BinarySearchTree {
public static Node root;
public BinarySearchTree(){
this.root = null;
}

public boolean find(int id){
Node current = root;
while(current!=null){
if(current.data==id){
return true;
}else if(current.data>id){
current = current.left;
}else{
current = current.right;
}
}
return false;
}
public boolean delete(int id){
Node parent = root;
Node current = root;
boolean isLeftChild = false;
while(current.data!=id){
parent = current;
if(current.data>id){
isLeftChild = true;
current = current.left;
}else{
isLeftChild = false;
current = current.right;
}
if(current ==null){
return false;
}
}
//if i am here that means we have found the node
//Case 1: if node to be deleted has no children
if(current.left==null && current.right==null){
if(current==root){
root = null;
}
if(isLeftChild ==true){
parent.left = null;
}else{
parent.right = null;
}
}
//Case 2 : if node to be deleted has only one child
else if(current.right==null){
if(current==root){
root = current.left;
}else if(isLeftChild){
parent.left = current.left;
}else{
parent.right = current.left;
}
}
else if(current.left==null){
if(current==root){
root = current.right;
}else if(isLeftChild){
parent.left = current.right;
}else{
parent.right = current.right;
}
}else if(current.left!=null && current.right!=null){

//now we have found the minimum element in the right sub tree
Node successor = getSuccessor(current);
if(current==root){
root = successor;
}else if(isLeftChild){
parent.left = successor;
}else{
parent.right = successor;
}
successor.left = current.left;
}
return true;
}

public Node getSuccessor(Node deleleNode){
Node successsor =null;
Node successsorParent =null;
Node current = deleleNode.right;
while(current!=null){
successsorParent = successsor;
successsor = current;
current = current.left;
}
//check if successor has the right child, it cannot have left child for sure
// if it does have the right child, add it to the left of successorParent.
// successsorParent
if(successsor!=deleleNode.right){
successsorParent.left = successsor.right;
successsor.right = deleleNode.right;
}
return successsor;
}
public void insert(int id){
Node newNode = new Node(id);
if(root==null){
root = newNode;
return;
}
Node current = root;
Node parent = null;
while(true){
parent = current;
if(id<current.data){
current = current.left;
if(current==null){
parent.left = newNode;
return;
}
}else{
current = current.right;
if(current==null){
parent.right = newNode;
return;
}
}
}
}
public void display(Node root){
if(root!=null){
display(root.left);
System.out.print(" " + root.data);
display(root.right);
}
}
public static void main(String arg[]){
BinarySearchTree b = new BinarySearchTree();
b.insert(3);b.insert(8);
b.insert(1);b.insert(4);b.insert(6);b.insert(2);b.insert(10);b.insert(9);
b.insert(20);b.insert(25);b.insert(15);b.insert(16);
System.out.println("Original Tree : ");
b.display(b.root);
System.out.println("");
System.out.println("Check whether Node with value 4 exists : " + b.find(4));
System.out.println("Delete Node with no children (2) : " + b.delete(2));
b.display(root);
System.out.println("\n Delete Node with one child (4) : " + b.delete(4));
b.display(root);
System.out.println("\n Delete Node with Two children (10) : " + b.delete(10));
b.display(root);
}
}

class Node{
int data;
Node left;
Node right;
public Node(int data){
this.data = data;
left = null;
right = null;
}
}

Posted On : 2017-11-25 23:41:02
Satisfied : 0 Yes  0 No
profile Garima Gupta - anyforum.in Garima Gupta
596128122204
Reply This Thread
up-rate
0
down-rate



Post Answer
Please Login First to Post Answer: Login login with facebook - anyforum.in