Data Structure Using Java | Lectures | Appcoachers

Call Now+91-9971532163

Send Messageinfo@appcoachers.com

Our LocationExecube, A-3, Sector 4, Noida (U.P.) - 201301

Data Structure Using Java

Data Structure Using Java

Overview

In computer science, a data structure is a data organization, management, and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data. A data structure is a particular way of organizing data in a computer so that it can be used effectively. For example, we can store a list of items having the same data-type using the array data structure.

Introduction to complexity: O()-notation

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann,Edmund Landau, and others, collectively called Bachmann–Landau notation or asymptotic notation.

In computer science, big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows. In analytic number theory, big O notation is often used to express a bound on the difference between an arithmetical function and a better understood approximation; a famous example of such a difference is the remainder term in the prime number theorem.

Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.

Analysis Tools and Techniques

Linked lists & Iterators

Stacks & Queues

In the pushdown stacks only two operations are allowed: push the item into the stack, and pop the item out of the stack. A stack is a limited access data structure - elements can be added and removed from the stack only at the top. push adds an item to the top of the stack, pop removes the item from the top. A helpful analogy is to think of a stack of books; you can remove only the top book, also you can add a new book on the top.

import java.io.*;
import  java.util.*;
 
 class Test  
{    
    // Pushing element on the top of the stack
    static void stack_push(Stack<Integer> stack )
   {
        for(int i = 0; i < 5 ; i++)
       {
            stack .push(i);
       }
   }
     
    // Popping element from the top of the stack
    static void stack_pop(Stack<Integer> stack )
   {
       System.out.println( "Pop :" );
 
        for(int i = 0; i < 5 ; i++)
       {
           Integer y = (Integer) stack .pop();
           System.out.println(y);
       }
   }
 
    // Displaying element on the top of the stack
    static void stack_peek(Stack<Integer> stack )
   {
       Integer element = (Integer) stack .peek();
       System.out.println( "Element on stack top : "  + element);
   }
     
    // Searching element in the stack
    static void stack_search(Stack<Integer> stack, int  element)
   {
       Integer pos = (Integer) stack .search(element);
 
        if(pos == -1 )
           System.out.println( "Element not found" );
        else
           System.out.println( "Element is found at position "  + pos);
   }
 
 
    public static void main  (String[] args)
   {
       Stack<Integer> stack = new  Stack<Integer>();
 
       stack_push( stack );
       stack_pop( stack );
       stack_push( stack );
       stack_peek( stack );
       stack_search( stack, 2 );
       stack_search( stack, 6 );
   }
}

In the queue only two operations are allowed enqueue and dequeue. Enqueue means to insert an item into the back of the queue, dequeue means removing the front item. The picture demonstrates the FIFO access. The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.

import java.util.*;
public class  QueueUsingStackTest {
  private Stack stack1 = new  Stack<>();
  private Stack stack2 = new  Stack<>();
  public void enqueue(int  element) {
     stack1. push (element);
     System.out. println(element + " inserted" );
  }
  public void  dequeue() {
      if (stack2.isEmpty()) {
        while  (!stack1.isEmpty()) {
           stack2. push(stack1.pop ());
        }
     }
     System.out. println(stack2.pop() + " removed" );
  }
  public static void  main(String args[]) {
     QueueUsingStackTest test = new  QueueUsingStackTest();
     test.enqueue( 10 );
     test.enqueue( 50 );
     test.enqueue( 100 );
     test.dequeue();
  }
}

Trees

A Tree is a non-linear data structure where data objects are organized in terms of hierarchical relationship. The structure is non-linear in the sense that, unlike simple array and linked list implementation, data in a tree is not organized linearly. Each data element is stored in a structure called a node. The topmost or starting node of the (inverted) tree is called the root node. All nodes are linked with an edge and form hierarchical sub trees beginning with the root node.

public class Tree <T> {
    private  Node<T> root;

    public Tree (T rootData) {
       root = new  Node<T>();
       root.data = rootData;
       root.children = new  ArrayList<Node<T>>();
   }

    public static class Node <T> {
        private  T data;
        private  Node<T> parent;
        private  List<Node<T>> children;
   }
}

Hashing

In hashing there is a hash function that maps keys to some values. But these hashing functions may lead to collisions that two or more keys are mapped to the same value. Chain hashing avoids collision. The idea is to make each cell of the hash table point to a linked list of records that have the same hash function value.

import  java.util.*;
 
class ADDSCJ{
    public static void main( String  args[])
   {
 
        // Create a HashTable to store
        // String values corresponding to integer keys
       Hashtable<Integer, String >
           hm = new Hashtable<Integer, String >();
 
        // Input the values
       hm. put(1, "Appcoachers" );
       hm. put(12, "DataStructure" );
       hm. put(15, "Course" );
       hm. put(3, "in Java" );
 
        // Printing the Hashtable
       System.out. println (hm);
   }
}

Priority Queues (Heaps)

A priority queue in Java is a special type of queue wherein all the elements are ordered as per their natural ordering or based on a custom Comparator supplied at the time of creation.

The front of the priority queue contains the least element according to the specified ordering, and the rear of the priority queue contains the greatest element.

import java.util.PriorityQueue;

 public class CreatePriorityQueueExample  {
    public static void main (String[] args) {
        // Create a Priority Queue
       PriorityQueue<Integer> numbers = new  PriorityQueue<>();

        // Add items to a Priority Queue (ENQUEUE)
       numbers. add(750 );
       numbers. add(500 );
       numbers. add(900 );
       numbers. add(100 );

        // Remove items from the Priority Queue (DEQUEUE)
        while  (!numbers.isEmpty()) {
           System. out.println(numbers.remove ());
       }

   }
}

Sorting

A Sorting Algorithm is used to rearrange a given array or list elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of element in the respective data structure.

import java.util.Arrays;

 

public class Appcoachers {
   public static void main(String[] args)
   {
       int[] arr = { 13,34,54,97, 18,07,34,14, 08,12  };
 
       Arrays.sort(arr);
 
       System.out.printf( "Modified arr[] : %s" ,
                         Arrays.toString(arr));
   }
}

Graphs

Graphs are used to represent many real-life applications: Graphs are used to represent networks. The networks may include paths in a city or telephone network or circuit network. Graphs are also used in social networks like linkedIn, Facebook. For example, in Facebook, each person is represented with a vertex(or node). Each node is a structure and contains information like person id, name, gender and locale. See this for more applications of graph.

import java.util.*;
 
 class Graph  {
     
    // A utility function to add an edge in an
    // undirected graph
    static void addEdge (ArrayList<ArrayList<Integer> > adj,
                        int u, int  v)
   {
       adj. get(u).add (v);
       adj. get(v).add (u);
   }
 
    // A utility function to print the adjacency list
    // representation of graph
    static void printGraph (ArrayList<ArrayList<Integer> > adj)
   {
        for (int i = 0 ; i < adj.size(); i++) {
           System. out.println("\nAdjacency list of vertex"  + i);
            for (int j = 0; j < adj.get (i).size(); j++) {
               System. out.print(" -> "+adj.get(i).get (j));
           }
           System. out .println();
       }
   }
 
    // Driver Code
    public static void main (String[] args)
   {
        // Creating a graph with 5 vertices
        int V = 5 ;
       ArrayList<ArrayList<Integer> > adj
                   = new  ArrayList<ArrayList<Integer> >(V);
         
        for (int i = 0 ; i < V; i++)
           adj. add(new  ArrayList<Integer>());
 
        // Adding edges one by one
       addEdge(adj, 0, 1 );
       addEdge(adj, 0, 4 );
       addEdge(adj, 1, 2 );
       addEdge(adj, 1, 3 );
       addEdge(adj, 1, 4 );
       addEdge(adj, 2, 3 );
       addEdge(adj, 3, 4 );
         
       printGraph(adj);
   }
}

Sets

A Set is a Collection that cannot contain duplicate elements. It models the mathematical set abstraction.

The Set interface contains only methods inherited from Collection and adds the restriction that duplicate elements are prohibited.

Set also adds a stronger contract on the behavior of the equals and hashCode operations, allowing Set instances to be compared meaningfully even if their implementation types differ.

import java.util.*;
public class SetDemo  {

  public static void main (String args[]) {
      int count[] = {34, 22,10 ,60,30,22 };
     Set<Integer> set = new  HashSet<Integer>();
      try  {
        for(int i = 0; i < 5 ; i++) {
            set.add (count[i]);
        }
        System. out.println(set );

        TreeSet sortedSet = new TreeSet<Integer>(set );
        System. out.println("The sorted list is:" );
        System. out .println(sortedSet);

        System. out.println("The First element of the set is: " + (Integer)sortedSet.first());
        System. out.println("The last element of the set is: " + (Integer)sortedSet.last());
     }
      catch (Exception e) {}
  }
}