Learn to implement data structures in java

0
28117

In this tutorial we will learn to implement data structures in java, It includes stacks, binary trees, array, linked lists and hash tables etc. The package java.util contains data structure.

  • To learn about concurrency in java just take a brief look on the points given below :

A. Collection Interface, Sets, Lists, Maps, Iterator, List Iterator, Comparable and Comparator Interface: –

  1. Collection Interface : – It is a sub interface of java.lang.Iterable package. It is used to pass around collections of objects. It contains methods int size(), boolean isEmpty(), boolean add(E element), boolean remove(Object element), and Iterator iterator() that perform basic operations. It is one of the root interfaces of the java collection classes. It also supports query operations
  2. int size()
    boolean isEmpty()
    boolean contains(Object o)
    Iterator iterator()

    It also provides bulk operations methods that work on entire collection like addAll, retainAll, containsAll, removeAll and clear. It is the parent interface of the Set and List interfaces. It supports sequential processing of the Collection.

  3. Set Interface : – This contains only methods inherited from Collection and adds the condition that duplicate elements are restricted. Every element in a set must be unique. The java.util.Collection interface subtype is java.util.Set interface. All methods in the Collection interface are also available in the Set interface. java.util.HashSet, java.util.LinkedHashSet, java.util.TreeSet these are the classes implementing Set interfaces.
  4. List Interface : – It is nothing but the ordered collection that can contain duplicate values. It implements ArrayList, LinkedList and Vector. It allows random access and insertion based on position. The java.util.List interface extends the collection interface. The java.util.ArrayList, java.util.LinkedList these classes are implemented List interface.
  5. Map Interface : – This interface does not extend the Collection interface. It is nothing but a collection that maps key objects to value object. It cannot contain duplicate keys. At most one value each key can map. The size(), isEmpty(), remove(J), clear() these method include Map interface. The java.util.HashMap, java.util.LinkedHashMap, java.util.TreeMap these are the classes implement the Map interface.
  6. Example : – Example shows how to implement list, set, map in java class in collection interface.

    //import statements
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.HashSet;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Map;
    import java.util.Set;
    public class CollInterfaceEx 
    {
    public static void main(String[] args) 
    	{
    	//create object of List a & store value of ArrayList
    	List a = new ArrayList();
    	a.add("Pritam");
    	a.add("Poorva ");
    	a.add("Rucha");
    	System.out.println("ArrayList : " + a);//print values of a
    
    List l = new LinkedList();//create object of List l & store value of LinkedList
    l.add("Pritam");
    l.add("Poorva ");
    l.add("Rucha");
    System.out.println("LinkedList: " + l); //print values of l
    Set s = new HashSet();//create object of Set s & store value of HashSet 
    s.add("Pritam");
    s.add("Poorva ");
    s.add("Rucha");
    System.out.println("Set       : " + s);//print values of s
    		    
    Map m = new HashMap();//create object of Map m & store values of HashMap 
    m.put("Pritam", "16");
    m.put("Poorva", "8");
    m.put("Rucha", "13");
    m.put("Krish", "14");
    System.out.println("Map       : " + m);//print values of m
    }
    }
    

    Output :

    ArrayList : [Pritam, Poorva, Rucha]
    LinkedList: [Pritam, Poorva, Rucha]
    Set       : [Rucha, Poorva, Pritam]
    Map       : {Krish=14, Rucha=13, Poorva=8, Pritam=16}
    

  7. Iterator : – It is nothing but to achieve successive elements from a series. Only in one direction you can iterate. It can do only once. It’s done if we reach the end of series. If you want to repeat iteration you must get a new Iterator. In this case iterator interface is to be used. It consist of a method iterator() and returns Iterator. It means if any class implements Iterable will return an iterator. It has a remove() method, which can delete elements from the underlying object. You can use Iterator to go over List, Set and also Map type of objects. Using Iterator you can recapture the elements from Collection object in only forward direction. In this case you cannot add, only remove the elements. Below method declared by Iterator: –
    • a. boolean hasNext(): – Used for return true when there are more elements.
    • b. Object next(): – It is used for returns the next element.
    • c. Void remove(): – It is used for remove the current element.

  8. List Iterator : – It extends iterator to allow bidirectional traversal of a list and the alteration of elements. It can be used to traverse for List type Objects, but not for Set type Objects. In this case hasPrevious() and previous() methods are used. It allows us to alter the list using add() and remove() methods. Below method declared by List Iterator: –
    • 1. Object next(): – It is used for return the next element.
    • 2. int nextIndex() : – It is used for returns the index of the next element.
    • 3. Object previous() : – It is used for return the previous element.
    • 4. int previousIndex() : – It is used for return the index of the previous element.
    • 5. boolean hasNext() : – It is used for return true if there is a next element.
    • Example : This example shows how to implement Iterator and ListIterator in java class.

      //import statements
      import java.util.ArrayList;
      import java.util.Iterator;
      import java.util.ListIterator;
      public class IteratorAndListIterator 
      {
      	public static void main(String args[])
      	{	//create object al of ArrayList
      		ArrayList al = new ArrayList();
      		//add elements into ArrayList using al object
      		al.add("Best");
      		al.add("Better");
      		al.add("Very Good");
      		al.add("Good");
      		al.add("Nice");
      		System.out.println("Iterator using while loop: ");
      		Iterator itr1 = al.iterator(); //assign Iterator to the ArrayList
      		while (itr1.hasNext()) //print till iterator has next values
      		{
      			System.out.println("Next element: " + itr1.next());//print next elements
      		}
      		System.out.println("Iterator using for loop: ");
      		//use for loop for checking condition
      		for (Iterator itr2 = al.iterator(); itr2.hasNext();) 
      		{
      			System.out.println("Next element: " + itr2.next());//print next elements
      		}
      		System.out.println("List iterator (forward iteration): ");
      		ListIterator litr = al.listIterator();
      		while (litr.hasNext())  //use hasNext() method to print litr values
      		{
      			System.out.println("Next element: " + litr.next());//print next elements
      		}
      		System.out.println("List iterator (backward iteration): ");
      		litr = al.listIterator(al.size());
      		while (litr.hasPrevious()) //check whether ListIterator has previous elements
      		{
      		System.out.println("Previous element: " + litr.previous());//print previous elements
      		}
      		litr.next();
      		litr.add("Ossom");//insert one more element
      		System.out.println("Alter list after the insertion of the new element");
      		System.out.println("Index of next element: " + litr.nextIndex());//print index of next elements
      System.out.println("Index of previous element: " + litr.previousIndex());//print  index of previous elements
      		for (litr = al.listIterator(); litr.hasNext();)
      		{
      		System.out.println("Next element: " + litr.next());//print next elements
      		}
      		litr.previous();//invoke previous element
      		litr.remove();//delete previous element
      		System.out.println("Alter list after the removal of an element");
      		for (litr = al.listIterator(); litr.hasNext();)//print the List using for loop
      		{
      			System.out.println("Next element: " + litr.next());//print next elements
      		}
      	}
      }
      

      Output :

      Iterator using while loop: 
      Next element: Best
      Next element: Better
      Next element: Very Good
      Next element: Good
      Next element: Nice
      Iterator using for loop: 
      Next element: Best
      Next element: Better
      Next element: Very Good
      Next element: Good
      Next element: Nice
      List iterator (forward iteration): 
      Next element: Best
      Next element: Better
      Next element: Very Good
      Next element: Good
      Next element: Nice
      List iterator (backward iteration): 
      Previous element: Nice
      Previous element: Good
      Previous element: Very Good
      Previous element: Better
      Previous element: Best
      Alter list after the insertion of the new element
      Index of next element: 2
      Index of previous element: 1
      Next element: Best
      Next element: Ossom
      Next element: Better
      Next element: Very Good
      Next element: Good
      Next element: Nice
      Alter list after the removal of an element
      Next element: Best
      Next element: Ossom
      Next element: Better
      Next element: Very Good
      Next element: Good
      

  9. Comparable Interface : – Comparable object is nothing but the able to comparing itself with another object. This class itself must implements the java.lang.Comparable interface in order to able to compare its objects. In this case class must implement a one abstract method compareTo(). This compareTo() method returns an integer. This is less flexible.
  10. Example : This example shows how to use Comparable interface in java class.

    //import statement
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    public class ComparableEx implements Comparable<ComparableEx>//implement Comparable
    {
        String actors; //define string
        ComparableEx(String a)//create parameterized constructor
        {
            this.actors=a;//refer this to actors
        }
        public String getActors()//use get() method
        {
            return actors;
        }
        public int compareTo(ComparableEx ce)//use compareTo() method to compare 2 objects
        {
            return (this.actors).compareTo(ce.actors);
        }
        public static void main(String[] args)
        {
            List<ComparableEx> al = new ArrayList<ComparableEx>();
            System.out.println("List In Sorted Way :");
            //add values to ArrayList
            al.add(new ComparableEx("Aishwarya"));
            al.add(new ComparableEx("Abhishek"));
            al.add(new ComparableEx("Salman"));
            al.add(new ComparableEx("Arjun"));
            al.add(new ComparableEx("Rittik"));
            al.add(new ComparableEx("Shraddha"));
            al.add(new ComparableEx("Sonam"));
            al.add(new ComparableEx("Amitabh"));
            Collections.sort(al);//Sort values of al
            for(ComparableEx c : al)//check condition
            {
                System.out.println(c.getActors());//get actors name and print
            }
        }
    }
    

    Output :

    List in Sorted Way:
    Abhishek
    Aishwarya
    Amitabh
    Arjun
    Rittik
    Salman
    Shraddha
    Sonam
    

  11. Comparator Interface : – Comparator object is nothing but the able to comparing two different objects. The java.util.Comparator interface must implement comparator class. In this case class implement two methods compare() and equals(). This is more flexible.
  12. Example : This example shows how to implement Comparator interface in java class.

    //import statement
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Comparator;
    import java.util.List;
    
    public class ComparatorEx implements Comparator<ComparatorEx>//class implement Comparator
    {
        String course; //define String variable course
        int student;//define int variable student
        ComparatorEx()//default constructor
        {}
        ComparatorEx(String c, int s)//parameterized constructor
        {
            this.course = c; //this refers to course
            this.student = s; //this refers to student
        }
        public String getCourse()//define getCourse() method
        {
            return course;
        }
        public int getStudent()//define getStudent() method
        {
            return student;
        }
        public int compare(ComparatorEx ce1, ComparatorEx ce2)//use compare method to compare 2 objects
        {
            return ce1.student - ce2.student;
        }
        public static void main(String[] args)
        {
            List<ComparatorEx> al = new ArrayList<ComparatorEx>();//Create al object of ArrayList
            //add values to ArrayList
            al.add(new ComparatorEx("B.E.", 7));
            al.add(new ComparatorEx("L.L.B.", 1));
            al.add(new ComparatorEx("M.E.", 6));
            al.add(new ComparatorEx("B.Sc", 10));
            al.add(new ComparatorEx("M.C.A", 16));
            al.add(new ComparatorEx("M.Sc.", 13));
            al.add(new ComparatorEx("B.C.A.", 4));
            al.add(new ComparatorEx("M.B.A", 2));
            Collections.sort(al, new ComparatorEx());//Sort the values 
            System.out.println("List of Courses in increasing order");
            System.out.println("\tCourse   Student\n");
            for (ComparatorEx c : al)//comparison between c and al
            System.out.println("\t" + c.getCourse() + "\t  " + c.getStudent());//get no of Courses and Students
        }
    }
    

    Output :

    List of Courses in increasing order
    	Course   Student
    
    	L.L.B.  1
    	M.B.A	  2
    	B.C.A.  4
    	M.E.	  6
    	B.E.	  7
    	B.Sc	  10
    	M.Sc.	  13
    	M.C.A	  16
    

    B. Immutable Collections : – It is nothing but the one which is the same data will hold always as long as any reference to it exists. It is nothing but the collections, can never be changed and once created. Through as List it provides an ImmutableList view. It does not allow null elements. It gives concurrency. It can be shared safely across threads. It gives simplicity also. This implementations are more memory efficient than mutable analysis. It cannot be changed at all, they do not wrap another collection and they have their own elements. We cannot have references to an immutable collection which allows changes. It is a form of value object.

  1. Unmodifiable Collections (read-only version of a collection) : – It is nothing but the collections do not support any modification operations. To return a planned look of the defined collection we can use unmodifiableCollection() method. And if we try to modify the collection then output in an UnsupportedOperationException. This is usually read-only view.
  2. Example :This example shows how to implement java.util.Collections.unmodifiableCollection() method in java class.

          import java.util.*; //import java.util.*.
       public class UnmodifiableEx 
       {
       public static void main(String[] args) 
       {
          // create array list of type String.
          List<String> list = new ArrayList<String>();
          // add string in the list.
          list.add("Hi");
          list.add("Bye");
          System.out.println("Original list: "+ list);
          //Use unmodifiableCollection() method.
    Collection<String> immutablelist = Collections.unmodifiableCollection(list);
          // try to alter the list
          immutablelist.add("See You");      
       		   }
    }	
    

    Output :

    Original list: [Hi, Bye]
    Exception in thread "main" java.lang.UnsupportedOperationException
    at java.util.Collections$UnmodifiableCollection.add(Unknown Source)
    		   at UnmodifiableEx.main(UnmodifiableEx.java:15)
    

  3. Immutable objects : – When object state cannot change after it is formulated then it is considered immutable object. In concurrent applications this objects are specifically useful. It can be used in multithreaded applications. Concrete objects and String are mostly expressed as immutable objects to improve runtime efficiency and readability in OOP.
    Some rules for immutable object: –
  4. 1. Don’t grant “setter” method – methods that alter objects or fields.
    2. Compose all fields private and final.
    3. Do not permit subclasses to override methods.
    4. Do not permit methods that alter the mutable objects.
    5. Do not share reference to the mutable objects.

    Example : This example shows how to implement immutable objects in java.

    public final class ImmutableObjectEx //declare class as a final
    {
    			//declare variable as private and final
    			private final String sname;
    			private final String div;
    			private final int rno;
    			
    ImmutableObjectEx(String sname, String div, int rno)//parameterized constructor
    			{//refer this
    			   this.sname = sname;
    			   this.div = div;
    			   this.rno = rno;
    			}
    		
    			//provide getters, no mutators method
    			public String getSname()
    			{ 
    	   			return this.sname;
    			}
    			public String getDiv()
    			{ 
    			   return this.div;
    			}
    			public int getRno()
    			{
    			   return this.rno;
    			}
    
    public static void main(String[] args)
    {	//create object obj of ImmutableObjectEx class
    ImmutableObjectEx obj = new ImmutableObjectEx("Pranjal",“A", 101);
    
    			System.out.println("Student Name: "+obj.getSname());
    			System.out.println("Division: "+obj.getDiv());
    			System.out.println("Roll No: "+obj.getRno());	
    }
    }
    

    Output :

    Student Name: Pranjal
    Division: A
    Roll No: 101
    

    C.Synchronised collections : – These classes are thread-safe collection classes. They have different optimizations and resource. For making a collection thread safe with the following method
    1. Collections.synchronizedList(list)
    2. Collections.synchronizedMap(map)
    3. Collections.synchronizedSet(set)

  1. Collections.synchronizedList(list) : – This method is used to return a synchronized list backed by the defined list. This list must be wrapped in a synchronized list. This method calls return a synchronized look of the defined list.
  2. Collections.synchronizedMap(map) : – This method is used to return a synchronized map backed by the defined map. This method calls return a synchronized look of the defined map.
  3. Collections.synchronizedSet(set) : – This method is used to return a synchronized sorted set backed by the defined sorted set. This method calls returns synchronized view of the defined set.
  4. Example :This example shows how to implement, Collections.synchronizedList(list), Collections.synchronizedMap(map), Collections.synchronizedSet(set) method in java class.

    import java.util.*;
    public class SynchronizedEx 
    {
    		public static void main(String[] args) 
    		{
    			// create vector object 
    			List<String> list = new ArrayList<String>();
    	      	
    			// create the list
    			list.add("0");
    			list.add("1");
    			list.add("2");
    			list.add("3");
    			list.add("4");
    	      
    			// create a synchronized list object
    			List<String> synlist = Collections.synchronizedList(list);
    			
    			System.out.println("Synchronized list :"+synlist);
    				
    			// create map
    			 Map<String,String> map = new HashMap<String,String>();
    	      
    		      // create the map
    		      map.put("2","WRITE"); 
    	      	map.put("16","ARE");
    		      map.put("8","AM");
    	      
    		      // create a synchronized map object synmap
    Map<String,String> synmap = Collections.synchronizedMap(map);
    	     
    	    		System.out.println("Synchronized map :"+synmap);
    	      
    	       	 // create set object of type String
    		      Set<String> set = new HashSet<String>();
    	      
    	      	// create the set
    		      set.add("RED");
    		      set.add("GREEN");
    		      set.add("BLUE");
    		      set.add("SKYBLUE");
    		      
    		      
    		      // create a synchronized set
    		      Set<String> synset = Collections.synchronizedSet(set);
    		     
    		      System.out.println("Synchronized set :"+synset);
    			}
    }	
    

    Output :

    Synchronized list: [0, 1, 2, 3, 4]
    Synchronized map :{ 2=WRITE, 8=AM, 16=ARE}
    Synchronized set : [BLUE, SKYBLUE, GREEN, RED]
    

    D.Common Data Structure Graphs : – A graph is nothing but the collection of nodes, which is called as vertices and a collection of segments called as lines which is connecting pairs of vertices. Graph is either directed or undirected. A directed graph is a graph in which each line has a direction to its successor. The lines in a directed graph are known as arc. In this graph, the flow along the arcs between two vertices can follow only the specified direction. In undirected graph there is no direction on any of the lines which are known as edges.

a.Directed Graph : –
directed graph

b.Undirected Graph : –
unidirected graph

Example :

//import statements
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.Scanner;
class Neighbour//create class Neighbour
{	//define variables
	public int vertexNum;
	public Neighbour next;
	public Neighbour(int vnum, Neighbour nbr)//parameterised constructor
	{
		this.vertexNum=vnum;//refer this
		next=nbr;
	}
}
class Vertex// create class vertex
{	//define variables
	String name;
	Neighbour adjList;
	//create parameterized constructor
	Vertex(String name, Neighbour neighbours) 
	{
		this.name=name;
		this.adjList=neighbours;
	}
}
public class GraphEx1//create class GraphEx1
{
	Vertex[] adjList;
	public GraphEx1(String file) throws FileNotFoundException
	{	//to take file as input use scanner
		Scanner sc = new Scanner(new File(file));
		adjList = new Vertex[sc.nextInt()];
		
		//read vertices
		for (int v=0;v<adjList.length;v++)
		{
			adjList[v] = new Vertex(sc.next(),null);
		}
		//read edges
		while(sc.hasNext())
		{	
			//read vertex name and translate to vertex number
			int v1=indexForName(sc.next());
			int v2= indexForName(sc.next());
			
			//add v2 to front of v1's adjacency list and
			//add v1 to front of v2's adjacency list
	adjList[v1].adjList = new Neighbour(v2,adjList[v1].adjList);
	adjList[v2].adjList = new Neighbour(v2, adjList[v2].adjList);
		}		
	}
	int indexForName(String name)
	{
		for (int v=0;v<adjList.length;v++)
		{
			if(adjList[v].name.equals(name))
			{
				return v;
			}
		}
		return -1;
	}
	public void print()
	{
		System.out.println();
		for (int v=0;v<adjList.length;v++)
		{
		System.out.println(adjList[v].name);
		for (Neighbour nbr = adjList[v].adjList;nbr!=null;nbr=nbr.next)
			{
			System.out.println("-->"+adjList[nbr.vertexNum].name);
			}
			System.out.println("\n");
	}
	}
	public static void main(String[] args) throws IOException
	{
		 Scanner sc = new Scanner(System.in);
		 System.out.println("Enter graph input file name");
		 String file = sc.nextLine();
		 GraphEx1 g = new GraphEx1(file);
		 g.print();//print file text
	}
}

Output :

Enter graph input file name
freind

Priyanka
-->Priyanka
-->Pritam


Pritam
-->Dipali
-->Pritam


Dipali
-->Mandar
-->Dipali


Mandar
-->Sonali
-->Mandar


Sonali
-->Milind
-->Sonali


Milind
-->Priyanka
-->Milind

Thus, in this tutorial we learnt about collection interface, map interface, set interface, list interface, iterator, list iterator, comparable and comparator iterator, immutable collection, immutable objects, synchronized collection, graphs with example.

LEAVE A REPLY

Please enter your comment!
Please enter your name here