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: –
- 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 - 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
• 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.
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}
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
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
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.
- 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.
- 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: –
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)
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)
- 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.
- 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.
- 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.
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.
b.Undirected 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.