Learn to implement data structures in java


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.

    Output :

  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.

      Output :

  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.

    Output :

  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.

    Output :

    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.

    Output :

  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.

    Output :

    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.

    Output :

    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 : –

b.Undirected Graph : –

Example :

Output :

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.


Please enter your comment!
Please enter your name here