Saturday, 8 December 2018

TreeMap in Java

TreeMap in Java is also one of the implementation of the Map interface like HashMap and LinkedHashMap. How TreeMap differs from these other implementations is that the elements in TreeMap are sorted on keys.

The elements in TreeMap are ordered according to the natural ordering of its keys, which is the default sort ordering or a comparator can be provided at map creation time to provide custom ordering (We'll see an example a little later).

How TreeMap is implemented in Java

TreeMap class in Java implements the NavigableMap interface and extends the AbstractMap class.

TreeMap is a Red-Black tree based NavigableMap implementation. This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.

Some of the important points about TreeMap in Java which are discussed in this post are as follows-

  1. TreeMap in Java is a Red-Black tree based NavigableMap implementation.
  2. TreeMap stores its elements in sorted order and sorting is done on keys. By default elements are sorted using their natural ordering.
  3. If you want to sort elments in TreeMap in any other order then you will have to provide a Comparator.
  4. TreeMap doesn’t allow null as key though other Map implementation like HashMap and LinkedHashMap do allow one key as null.
  5. Key in the TreeMap should be unique otherwise the previous stored value for the same key will be overwritten. Duplicate values are allowed though.
  6. TreeMap in Java is not synchronized so it is not thread safe. If TreeMap is accessed concurrently by multiple threads and at least one of the threads modifies the map structurally, then the TreeMap must be synchronized externally.
  7. The iterators returned by the iterator method of the collections returned by all of the TreeMap's "collection view methods" are fail-fast. If the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException.

Java TreeMap Constructors

There are four constructors in the TreeMap class in Java.

  • TreeMap()- Constructs a new, empty tree map, using the natural ordering of its keys.
  • TreeMap(Comparator<? super K> comparator)- Constructs a new, empty tree map, ordered according to the given comparator.
  • TreeMap(Map<? extends K,? extends V> m)- Constructs a new tree map containing the same mappings as the given map, ordered according to the natural ordering of its keys.
  • TreeMap(SortedMap<K,? extends V> m)- Constructs a new tree map containing the same mappings and using the same ordering as the specified sorted map.

Java TreeMap creation and element insertion example

public class TreeMapDemo {

    public static void main(String[] args) {
        Map<String, String> cityTemperatureMap = new TreeMap<String, String>();
        // Storing elements
        cityTemperatureMap.put("Delhi", "24");
        cityTemperatureMap.put("Mumbai", "32");
        cityTemperatureMap.put("Chennai", "35");
        cityTemperatureMap.put("Bangalore", "22" );
        cityTemperatureMap.put("Kolkata", "28");
        cityTemperatureMap.put("Chennai", "36");
  
        // iterating the map
        for(Map.Entry<String, String> me : cityTemperatureMap.entrySet()){
            System.out.println(me.getKey() + " " + me.getValue());
        }
    }
}

Output

Bangalore 22
Chennai 36
Delhi 24
Kolkata 28
Mumbai 32

It can be seen that the elements in TreeMap are sorted according to the natural ordering of its keys which is ascending for String.
Also note that though Chennai is added twice but it is stored only once as trying to store the same key twice will result in overwriting of the old value with the new value (as the calculated hash will be the same for the keys). Thus the last one is displayed while iterating the values.

TreeMap doesn't allow null

Though HashMap and LinkedHashMap allow one null as key, TreeMap in Java doesn't allow null as key. Any attempt to add null in a TreeMap will result in a NullPointerException.

public class TreeMapDemo {

    public static void main(String[] args) {
        Map<String, String> cityTemperatureMap = new TreeMap<String, String>();
        // Storing elements
        cityTemperatureMap.put("Delhi", "24");
        cityTemperatureMap.put("Mumbai", "32");
        cityTemperatureMap.put("Chennai", "35");
        cityTemperatureMap.put("Bangalore", "22" );
        cityTemperatureMap.put("Kolkata", "28");
        // Null key
        cityTemperatureMap.put(null, "36");
        
        // iterating the map
        for(Map.Entry<String, String> me : cityTemperatureMap.entrySet()){
            System.out.println(me.getKey() + " " + me.getValue());
        }
    }
}

Output

Exception in thread "main" java.lang.NullPointerException
 at java.util.TreeMap.put(Unknown Source)
 at org.netjs.prog.TreeMapDemo.main(TreeMapDemo.java:17)

Sorting elements in different order in TreeMap

As already mentioned by default elements are stored in TreeMap using natural ordering. If you want to sort TreeMap is descending order (reverse order) then you need to provide your own Comparator at map creation time. Let's see an example where we sort the TreeMap of Strings in descending order of its keys.

public class TreeMapDemo {

    public static void main(String[] args) {
        Map<String, String> cityTemperatureMap = new TreeMap<String, String>(new TreeComparator());
        // Storing elements
        
        cityTemperatureMap.put("Delhi", "24");
        cityTemperatureMap.put("Mumbai", "32");
        cityTemperatureMap.put("Chennai", "35");
        cityTemperatureMap.put("Bangalore", "22" );
        cityTemperatureMap.put("Kolkata", "28");
        
        // iterating the map
        for(Map.Entry<String, String> me : cityTemperatureMap.entrySet()){
            System.out.println(me.getKey() + " " + me.getValue());
        }
    }
}

//Comparator class
class TreeComparator implements Comparator<String>{
 @Override
 public int compare(String str1, String str2) {
     return str2.compareTo(str1);
 }    
}

Output

Mumbai 32
Kolkata 28
Delhi 24
Chennai 35
Bangalore 22

Here note that a Custom Comparator is implemented with the logic to sort objects in reverse order. That Comparator is passed in the constructor of the TreeMap at map creation time .

TreeMap is not synchronized

TreeMap in Java is not thread safe. In case we need to Synchronize it, it should be synchronized externally. That can be done using the Collections.synchronizedSortedMap method.

SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

TreeMap class' iterator is fail-fast

The iterators returned by TreeMap in Java are fail-fast, if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException.

TreeMap iteration example

In the example we’ll get the Set view of the mapped entries using the entrySet() method. While iterating that Set we’ll try to remove an element from the TreeMap using the Map's remove() method (not the iterator's remove method) which means a structural modification and results in ConcurrentModificationException being thrown.

public class TreeMapItr {

    public static void main(String[] args) {
        Map<String, String> langMap = new TreeMap<String, String>();
        // Storing (key, value) pair to HashMap
        langMap.put("ENG", "English");
        langMap.put("NLD", "Dutch");
        langMap.put("ZHO", "Chinese");
        langMap.put("BEN", "Bengali");
        langMap.put("ZUL", "Zulu");
        langMap.put("FRE", "French");
        // Collection view of the TreeMap
        Set<Map.Entry<String, String>> langSet = langMap.entrySet();
        Iterator<Map.Entry<String, String>> itr = langSet.iterator();
        while (itr.hasNext()) {
            Map.Entry<String, String> entry = itr.next();
            System.out.println("Key is " + entry.getKey() + " Value is " + entry.getValue());    
            // removing value using TreeMap's remove method
            if(entry.getKey().equals("NLD")){
                langMap.remove(entry.getKey());
            }
        }
    }
}

Output

Key is BEN Value is Bengali
Key is ENG Value is English
Key is FRE Value is French
Key is NLD Value is Dutch
Exception in thread "main" java.util.ConcurrentModificationException
 at java.util.TreeMap$PrivateEntryIterator.nextEntry(TreeMap.java:1207)
 at java.util.TreeMap$EntryIterator.next(TreeMap.java:1243)
 at java.util.TreeMap$EntryIterator.next(TreeMap.java:1238)
 at org.netjs.examples.impl.TreeMapItr.main(TreeMapItr.java:23)

If iterator's remove method is used to remove an element from TreeMap while it is iterated then the ConcurrentModificationException is not thrown.

public class TreeMapItr {

    public static void main(String[] args) {
        Map<String, String> langMap = new TreeMap<String, String>();
        // Storing (key, value) pair to HashMap
        langMap.put("ENG", "English");
        langMap.put("NLD", "Dutch");
        langMap.put("ZHO", "Chinese");
        langMap.put("BEN", "Bengali");
        langMap.put("ZUL", "Zulu");
        langMap.put("FRE", "French");
        // Collection view of the TreeMap
        Set<Map.Entry<String, String>> langSet = langMap.entrySet();
        Iterator<Map.Entry<String, String>> itr = langSet.iterator();
        while (itr.hasNext()) {
            Map.Entry<String, String> entry = itr.next();
            // removing value using iterator's remove method
            if(entry.getKey().equals("NLD")){
                itr.remove();
            }
        }
        for(Map.Entry<String, String> lang : langMap.entrySet()) {
            System.out.println("Key- " + lang.getKey() + 
                          " Value- " + lang.getValue());
        }
    }
}

Output

Key- BEN Value- Bengali
Key- ENG Value- English
Key- FRE Value- French
Key- ZHO Value- Chinese
Key- ZUL Value- Zulu

As you can see element from TreeMap is removed when iterator's remove() metod is used and ConcurrentModificationException is not thrown.

That's all for this topic TreeMap in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

Source: https://docs.oracle.com/javase/10/docs/api/java/util/TreeMap.html


Related Topics

  1. How HashMap internally works in Java
  2. How to Sort elements in different order in TreeSet
  3. How to loop through a map in Java
  4. HashMap Vs LinkedHashMap Vs TreeMap in Java
  5. Java Collections Interview Questions

You may also like -

Friday, 7 December 2018

Write to a File in Java

In this post we'll see different ways to write to a file in Java.

Java examples given here to write to a file in Java are based on the following options-

  • BufferedOutputStream- BufferedOutputStream is a wrapper class over the OutputStream class and it adds buffering capability to the output stream.
  • BufferedWriter- Writes text to a character-output stream, buffering characters so as to provide for the efficient writing of single characters, arrays, and strings.
  • Files Class methods- Java 7 onward Files class can be used for writing to a file in Java using Files.write() method. There is also a newBufferedWriter method in the Files class that can be used to write to a file.

Refer How to append to a file in Java to see how to append to an already existing file.

Java program to write to a file using BufferedOutputStream

Though Java provides classes like FileOutputStream and FileWriter to write files using byte stream and character stream respectively but using them directly will slow down the I/O operation considerably.

It is always advisable to use BufferedOutputStream or BufferedWriter to write to a file in Java because that will provide buffering to the output streams and won't cause a call to the underlying system for each byte written. Buffered output streams write data to a buffer, and the native output API is called only when the buffer is full, making I/O operation more efficient.

It is same as reading file using BufferedReader where again you get the advantage of using buffered I/O streams. In case of Buffered input streams data is read from a memory area known as a buffer which makes reading more efficient.

The write method of the BufferedOuputStream takes either a byte array or an int as an argument thus you have to call getBytes() on any String that is passed to the write method. Here one thing to note is– If your file contains character data, the best approach is to use character streams like BufferedWriter. Byte streams should only be used for the most primitive I/O.

Java code

import java.io.BufferedOutputStream;
import java.io.FileOutputStream;
import java.io.IOException;

public class FileWriteDemo {

 public static void main(String[] args) {
  writeFileContent("G:\\test.txt");
 }
 
 /**
  * 
  * @param fileName
  */
 private static void writeFileContent(String fileName){
  BufferedOutputStream bs = null;
  try {
   bs = new BufferedOutputStream(new FileOutputStream(fileName));
   bs.write("Writing one line".getBytes());
   // For windows, only \n for linux
   bs.write("\r\n".getBytes());
   bs.write("Writing second line".getBytes());
   
  } catch (IOException ioExp) {
   // TODO Auto-generated catch block
   ioExp.printStackTrace();
  }finally{
   if(bs != null){
    try {
     bs.close();
    } catch (IOException e) {
     // TODO Auto-generated catch block
     e.printStackTrace();
    }
   }
  }
 }

}

Java program to write to a file using BufferedWriter

BufferedWriter class has two constructors for specifying the buffer size or using the default size while writing to a file.

Constructors

  • BufferedWriter(Writer out)- Creates a buffered character-output stream that uses a default-sized output buffer.
  • BufferedWriter(Writer out, int sz)- Creates a new buffered character-output stream that uses an output buffer of the given size.

Java code

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;

public class FileWrite {

 public static void main(String[] args) {
  writeFileContent("G:\\test1.txt");
 }
 
 /**
  * 
  * @param fileName
  */
 private static void writeFileContent(String fileName){
  //BufferedWriter bw = null;
  // Using try-with-resources here 
  try(BufferedWriter bw = new BufferedWriter(new FileWriter(fileName))) {
   //bw = new BufferedWriter(new FileWriter(fileName));
   bw.write("Writing one line");
   bw.newLine();
   bw.write("Writing second line");
  } catch (IOException e) {
   // TODO Auto-generated catch block
   e.printStackTrace();
  }
 }
}

Note that in this program try-with-resources is used to automatically manage resources. It is available from Java 7 and above.

Java program to write a file using Files class methods

In Java 7 Files class is added which provides write() method to write to a file in Java. There is also a newBufferedWriter method that can be used to write to a file.

Using Files.write() method to write to a file

There are 2 overloaded versions of write method, note that one of them is added in Java 8.

  • public static Path write(Path path, byte[] bytes,OpenOption... options) throws IOException– Write bytes to a file specified by the path. Options varargs specifies whether new file is created for writing or bytes are appended to an already existing file. If no options are present then this method works as if the  CREATE, TRUNCATE_EXISTING, and WRITE options are present.
  • public static Path write(Path path, Iterable<? extends CharSequence> lines, Charset cs, OpenOption... options) throws IOException- Write lines of text to a file. Each line is a char sequence and is written to the file in sequence with each line terminated by the platform's line separator, as defined by the system propertyline.separator. Characters are encoded into bytes using the specified charset.

Example code

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;

public class FileWrite8 {
 public static void main(String[] args) {
  String content = "This is the line to be added.\nThis is another line.";
  try {
   Files.write(Paths.get("G://test.txt"), content.getBytes());
  } catch (IOException e) {
   // TODO Auto-generated catch block
   e.printStackTrace();
  }
 }
}

Here note that String is converted to Byte array and also there is no option parameter which means creating the file if it doesn't exist, or initially truncating an existing regular-file to a size of 0 if it exists.

Using Files.newBufferedWriter method

You can also use Files.newBufferedWriter() method to write to a file in Java.

There are 2 overloaded versions of newBufferedWriter method, note that one of them is added in Java 8.

  • public static BufferedWriter newBufferedWriter(Path path, OpenOption... options) throws IOException - Opens or creates a file for writing, returning a BufferedWriter to write text to the file in an efficient manner. Options parameter specifies whether new file is created for writing or bytes are appended to an already existing file. If no options are present then this method works as if the CREATE,  TRUNCATE_EXISTING, and WRITE options are present.
  • public static BufferedWriter newBufferedWriter(Path path, Charset cs,OpenOption... options) throws IOException - Opens or creates a file for writing, returning a BufferedWriter that may be used to write text to the file in an efficient manner. Here path is the path to the file, cs is the charset to use for encoding and options parameter specifies how the file is opened.

Example Code

import java.io.BufferedWriter;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;

public class FileWrite8 {
 public static void main(String[] args) {
  Path path = Paths.get("G://test.txt");
  try (BufferedWriter writer = Files.newBufferedWriter(path)) {
      writer.write("Hello World");
      writer.newLine();
      writer.write("Hello again");
  } catch (IOException e) {
   // TODO Auto-generated catch block
   e.printStackTrace();
  }
 }
}

Here note that no option parameter is given which means creating the file if it doesn't exist, or initially truncating an existing regular-file to a size of 0 if it exists.

That's all for this topic Write to a File in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. Reading Delimited File in Java Using Scanner
  2. How to Append to a File in Java
  3. How to Read File From The Last Line in Java
  4. Zipping Files in Java
  5. Try-With-Resources in Java Exception Handling

You may also like -

>>>Go to Java Programs Page

Thursday, 6 December 2018

Reading File in Java Using Files.lines And Files.newBufferedReader

You would have used BufferedReader to read files in Java but Java 8 onward there is another way to read files using methods of Files class (Files class itself was added in Java 7).

In this post we'll see examples of reading file in Java using Files.lines() And Files.newBufferedReader() methods.

Reading file using Files.readAllLines

readAllLines(Path) method will read all the lines of the file into a list of String. It is not a very efficient way to read a file as a whole file is stored in a list which means consuming more memory.

public class ReadFile {
    public static void main(String[] args) {
        Path path = Paths.get("G:\\Temp.txt");
        
        try {
            List<String> fileList = Files.readAllLines(path);
            System.out.println("" + fileList);
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }
}

Reading file using Files.lines and Files.newBufferedReader

In Java 8 lines() method has been added in Files class which provides a better way to read files. This method won't read all lines of the file at once but read lines from a file as a Stream line by line.

Another method is newBufferedReader() which returns a BufferedReader to read text from the file in an efficient manner.

import java.io.BufferedReader;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.stream.Stream;

public class ReadFile {

    public static void main(String[] args) {
        Path path = Paths.get("G:\\Temp.txt");
        // Using Lines
        try(Stream<String> stream = Files.lines(path)){
            stream.forEach(System.out::println);
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        
        // Using newBufferedReader
        try(BufferedReader br = Files.newBufferedReader(path)){
            Stream<String> stream = br.lines();
            stream.forEach(System.out::println);
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }
}

Since lines and newBufferedReader methods return Stream so you can also use this functional stream to write a chain of streams doing some extra processing.

As example if file has blank lines and you want to filter those blank lines and display only non-blank lines then it can be written this way in Java.

public class ReadFile {

    public static void main(String[] args) {
        Path path = Paths.get("G:\\Temp.txt");
        
        try(Stream<String> stream = Files.lines(path)){
            // print only if line is not blank
            stream.filter(line->!line.trim().equals(""))
            .forEach(System.out::println);
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }
}

That's all for this topic Reading File in Java Using Files.lines And Files.newBufferedReader. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. Reading File in Java Using Scanner
  2. Writing File in Java
  3. How to Find Last Modified Date of a File in Java
  4. How to Read Properties File in Java
  5. Stream API in Java 8

You may also like -

>>>Go to Java Programs Page

Wednesday, 5 December 2018

How and Why to Synchronize ArrayList in Java

ArrayList is one of the most used Collections and why shouldn't it be? It's easy to use, has many implemented methods to provide all the important functionality and it is fast. But that fast performance comes at a cost, ArrayList is not synchronized. What does that mean? That means sharing an instance of ArrayList among many threads where those threads are modifying (by adding or removing the values) the collection may result in unpredictable behaviour.

So in this post we'll see why we may need to synchronize an ArrayList and how to synchronize an ArrayList in Java.

Why do we need to synchronize an ArrayList

First let's see why do we need to synchronize an ArrayList in Java. To understand that an example is given below where an ArrayList instance is shared among three threads and each thread is trying to insert ten elements in the ArrayList.

Expected output of the example is: Size of ArrayList should be 30 and on looping the list I should get values 0..9 three times. As I said it may give unpredictable result so let's see what happens when we run it.

Example Code

public class SynchroProblem implements Runnable{
    private List<Integer> numList;
    
    //Constructor
    public SynchroProblem(List<Integer> numList){
        this.numList = numList;
    }
    @Override
    public void run() {
        System.out.println("in run method");
        for(int i = 0; i < 10; i++){
            numList.add(i);
            try {
                // introducing some delay
                Thread.sleep(50);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
    
    public static void main(String[] args) {
        List<Integer> numList = new ArrayList<Integer>();
        // Creating three threads
        Thread t1 = new Thread(new SynchroProblem(numList));
        Thread t2 = new Thread(new SynchroProblem(numList));
        Thread t3 = new Thread(new SynchroProblem(numList));
        t1.start();
        t2.start();
        t3.start();
        try {
            t1.join();
            t2.join();
            t3.join();
        } catch (InterruptedException e) {    
            e.printStackTrace();
        }
        System.out.println("Size of list is " + numList.size());
        for(Integer i : numList){
            System.out.println("num - " + i);
        }    
    }
}

Output

in run method
in run method
in run method
Size of list is 27
num - null
num - 0
num - 0
num - 1
num - 1
num - 1
num - 2
num - 2
num - 2
num - 3
num - null
num - 3
num - 4
num - 4
num - 4
num - 5
num - 5
num - 5
num - 6
num - 6
num - 7
num - 7
num - 7
num - 8
num - 9
num - 9
num - 9

It can be seen from the output that size is 27 (not 30) and two of the values are NULL where as 6 is inserted only twice and 8 only one time. So you can see the effect of using an arraylist which is not thread-safe in multi-threaded environment. Note that if you run this program on your system you may get different result. Well it is supposed to be unpredictable!

Options for synchronizing an ArrayList in Java

Now when we know ArrayList is not synchronized and sharing its instance among many threads may give unpredictable result, we can focus on the other part; how to synchronize an ArrayList in Java. The options we have are as following-

  • We can of course use a Vector which is synchronized.
  • Collections class also provide a method synchronizedList(), which returns a synchronized (thread-safe) list backed by the specified list.
  • Another alternative is CopyOnWriteArrayList which is part of the java.util.concurrent Package.

Let's see the same example used above with one change, now Collections.synchronizedList is used to synchronize ArrayList.

public class SynchroProblem implements Runnable{
    private List<Integer> numList;
    
    //Constructor
    public SynchroProblem(List<Integer> numList){
        this.numList = numList;
    }
    @Override
    public void run() {
        System.out.println("in run method");
        for(int i = 0; i < 10; i++){
            numList.add(i);
            try {
                // introducing some delay
                Thread.sleep(50);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
    
    public static void main(String[] args) {
        //List<Integer> numList = new Vector<Integer>();
        // Synchronizing the list
        List<Integer> numList = Collections.synchronizedList(new ArrayList<Integer>());
        // Creating three threads
        Thread t1 = new Thread(new SynchroProblem(numList));
        Thread t2 = new Thread(new SynchroProblem(numList));
        Thread t3 = new Thread(new SynchroProblem(numList));
        t1.start();
        t2.start();
        t3.start();
        try {
            t1.join();
            t2.join();
            t3.join();
        } catch (InterruptedException e) {    
            e.printStackTrace();
        }
        System.out.println("Size of list is " + numList.size());
        for(Integer i : numList){
            System.out.println("num - " + i);
        }    
    }
}

Output

Size of list is 30

Now everytime I get the size of the list as 30. Also elements are displayed properly 0..9 three times (I have omitted the display here).
We can also use the Vector class. It is already there in the code just uncomment the line with the vector and comment the Collections.synchronized line to see how it works with vector class. Note that Vector class is also retrofitted to use List interface that is why List reference is used to hold the Vector class.

Iterating a list in multi-threaded environment

When iterating an arraylist in a multi-threaded environment while one thread is iterating over a list there's a chance that another thread may remove a value which will disrupt the serial access.

In that case also we need to synchronize the list, In order to guarantee serial access, it is critical that all access to the backing list is accomplished through the returned list. It is imperative that the user manually synchronize on the returned list when iterating over it. Failure to follow this advice may result in non-deterministic behavior.
Reference : http://docs.oracle.com/javase/8/docs/api/java/util/Collections.html#synchronizedList-java.util.List-

List list = Collections.synchronizedList(new ArrayList());
      ...
  synchronized (list) {
      Iterator i = list.iterator(); // Must be in synchronized block
      while (i.hasNext())
          foo(i.next());
  }

That's all for this topic How and Why to Synchronize ArrayList in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. How ArrayList works internally in Java
  2. How to sort arraylist of custom objects in Java
  3. How to Remove Elements From an ArrayList in Java
  4. Synchronization in Java multithreading
  5. Java Collections Interview Questions

You may also like -

Shell Sort Program in Java

In this post we’ll see how to write Shell sort program in Java.

Shell sort is based on another sorting algorithm insertion sort and it is developed by Donald L. Shell.

Shell sort – An improvement on insertion sort

In insertion sort the adjacent elements are compared and a swap is done if required (if item on the right is smaller than the item on the left). That way elements are shifted right to move smaller elements to the left.

Consider a scenario where a smaller element is on the far right, lot of shifting has to be done to move this element to its proper place on the left.

In shell sort rather than comparing adjacent elements, elements that are placed some distance from each other are compared and swapped. You start with a gap value and elements at that gap interval are compared. After each iteration gap value is decremented so that the interval is reduced, that is done until the gap value is 1 that is when adjacent elements are compared and shell sort effectively becomes insertion sort in that iteration.

The benefit is that by the last step, when the adjacent elements are compared, elements are almost sorted and no far off shifting of elements is required. For almost sorted elements insertion sort has the complexity of O(N) rather than O(N2).

Shell sort interval sequence calculation

The interval that is used for comparing elements is based on the number of elements. For the calculation of that interval Knuth’s interval sequence is used where the interval sequence is generated using the following formula-

gap = gap*3 + 1

When gap = 1 it gives interval value as 4, for gap =4 interval value as 13 and so on.

For example if you have an array of 20 elements the calculation for the initial interval value is done as follows in the Java program-

while(gap <= arr.length/3){
    gap = (gap * 3) + 1;
}

For decrementing the interval following formula is used-

gap = (gap-1)/3

For example, When gap = 13 then the next interval sequence value will be (13-1)/3 = 4

Shell Sort Java program

public class ShellSort {

    public static void main(String[] args) {
        // Array of 20 elements
        int[] intArr = {47, 85, 620, 3456, 7, 10, 4500, 106, 345, 1000, 67, 80, 5500, 34, 78, 782, 4, 0, 99, 190};
        int[] sortedArray = shellSort(intArr);
        System.out.println("Sorted array is- ");
        for(int num : sortedArray){
            System.out.print(num + " ");
        }
    }

    private static int[] shellSort(int[] intArr){
        int gap = 1;
        int temp;
        // initial gap value calculation
        while(gap <= intArr.length/3){
            gap = (gap * 3) + 1;
        }
        while(gap > 0){    
            for(int i = gap; i < intArr.length; i++){
                temp = intArr[i];
                int j;                
                for(j = i; j > gap - 1 && intArr[j-gap] >= temp; j=j-gap){
                    intArr[j] = intArr[j - gap];                    
                }
                intArr[j] = temp;
            }
            // next gap value calculation
            gap = (gap - 1)/3;
        }
        return intArr;
    }
}

Output

Sorted array is- 
0 4 7 10 34 47 67 78 80 85 99 106 190 345 620 782 1000 3456 4500 5500 

In the Java program for shell sort, since the array length is 20 so the initial gap value is calculated as 13. With that interval here are some values from the inner and outer loops.

In the first iteration value at index 13 is compared with index 0 and swapped too. Then the outer loop value is incremented by 1 (i = 14) at that time value at index 14 is compared with index 1 and swapped too. Same way iteration will happen until the length of the array is reached ( i = 19).

i -- 13
j-- 13 j-gap= 0
 array after inner loop ---- 
34 85 620 3456 7 10 4500 106 345 1000 67 80 5500 47 78 782 4 0 99 190 
i -- 14
j-- 14 j-gap= 1
 array after inner loop ---- 
34 78 620 3456 7 10 4500 106 345 1000 67 80 5500 47 85 782 4 0 99 190 
...
...
i -- 19
j-- 19 j-gap= 6

That’s the array after the iteration is done with gap value as 13.

34 78 620 4 0 10 190 106 345 1000 67 80 5500 47 85 782 3456 7 99 4500 

Then the gap value is reduced as per the formula and the new gap value is 4. With that again the comparison is done.

i -- 4
j-- 4 j-gap= 0
 array after inner loop ---- 
0 78 620 4 34 10 190 106 345 1000 67 80 5500 47 85 782 3456 7 99 4500 

i -- 5
j-- 5 j-gap= 1
 array after inner loop ---- 
0 10 620 4 34 78 190 106 345 1000 67 80 5500 47 85 782 3456 7 99 4500 

..
..

i -- 17
j-- 17 j-gap= 13
j-- 13 j-gap= 9
j-- 9 j-gap= 5
j-- 5 j-gap= 1
 array after inner loop ---- 
0 7 67 4 34 10 85 80 345 47 190 106 3456 78 620 782 5500 1000 99 4500 
i -- 18
j-- 18 j-gap= 14
j-- 14 j-gap= 10
 array after inner loop ---- 
0 7 67 4 34 10 85 80 345 47 99 106 3456 78 190 782 5500 1000 620 4500 

i – 19
That’s the array after the iteration is done with gap value as 4.
0 7 67 4 34 10 85 80 345 47 99 106 3456 78 190 782 5500 1000 620 4500 

Then the gap value is reduced again and it becomes 1. With value as 1 the sorting happens as in insertion sort giving the final sorted array.

Complexity of shell sort

There are various estimates for the time complexity of shell sort based on the interval sequence used and the data used for sorting. But generally the time complexity of shell sort is considered O(N3/2) which means square root of (N)3.

Since shell sort is an in-place comparison sort so no extra space is required thus the space complexity is O(1).

That's all for this topic Shell Sort Program in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. Selection Sort Program in Java
  2. Displaying Prime Numbers - Java Program
  3. Check Whether Given String/Number is a Palindrome or Not - Java Program
  4. Find Duplicate Characters in a String With Repetition Count - Java Program
  5. How to Remove Duplicate Elements From an Array - Java Program

You may also like -

>>>Go to Java Programs Page

Tuesday, 4 December 2018

ArrayList in Java

Java ArrayList is one of the most used collection and most of its usefulness comes from the fact that it grows dynamically. Like array you don't have to anticipate in advance how many elements you are going to store in the ArrayList. As and when elements are added ArrayList keeps growing, if required.

Though internally it is not really some "elastic" array which keeps growing, it is as simple as having an array with an initial capacity (default is array of length 10). When that limit is crossed another array is created which is 1.5 times the original array and the elements from the old array are copied to the new array.

Hierarchy of the ArrayList

To know about the hierarchy of the ArrayList in Java we need to know about 2 interfaces and 2 abstract classes.

  • Collection Interface- Collection interface is the core of the Collection Framework. It must be implemented by any class that defines a collection.
  • List interface- List interface extends Collection interface. Apart from extending all the methods of the Collection interface, List interface defines some methods of its own.
  • AbstractCollection- Abstract class which implements most of the methods of the Collection interface.
  • AbstractList- Abstract class which extends AbstractCollection and implements most of the List interface.

ArrayList extends AbstractList and implements List interface too. Apart from List interface, ArrayList also implements RandomAccess, Cloneable, java.io.Serializable interfaces.

Features of ArrayList

In this post we'll see in detail some of the salient features of the ArrayList in Java which are as follows.

  • ArrayList is a Resizable-array implementation of the List interface. It can grow dynamically if more elements are to be added after the capacity is reached. Same way when the elements are removed from the ArrayList it shrinks by shifting the other elements to fill the space created by the removed element.
  • Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list.
  • In ArrayList insertion order of the elements is maintained.
  • ArrayList in Java can contain duplicate values. Any number of null elements are also allowed.
  • ArrayList in Java is not thread-safe. In a multi-threaded environment if multiple threads access an ArrayList instance concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally.
  • The iterators returned by ArrayList's iterator and listIterator methods are fail-fast. If the list is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException.

Java ArrayList constructors

ArrayList class has the following three constructors.
  • ArrayList()- Constructs an empty list with an initial capacity of ten.
  • ArrayList(Collection<? extends E> c)- Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.
  • ArrayList(int initialCapacity)- Constructs an empty list with the specified initial capacity.

Creating and adding elements to ArrayList

List provides a method add(E e) which appends specified element to the end of the list. Using add(E e) method will mean keep adding elements sequentially to the list.

Apart from that there is another add method -
add(int index, E element)- This method inserts the specified element at the specified position in this list.

There are other variants of add method too that can add the specified collection into the List.

Java example

public class ArrayListDemo {

    public static void main(String[] args) {
        // List with initial capacity as 2
        List<String> cityList = new ArrayList<>(2);
        cityList.add("London");
        cityList.add("Paris");
        cityList.add("Bangalore");
        cityList.add(3, "Istanbul");
        for(String name : cityList){
            System.out.println("City Name - " + name);
        }
    }
}

Output

City Name - London
City Name - Paris
City Name - Bangalore
City Name - Istanbul

In the code you can see that the ArrayList is created with the initial capacity as 2 still 4 elements are added to it. Internally ArrayList has been resized to accommodate more elements. Also from the output you can see that the elements are inserted in the same order as they are added, so the insertion order is maintained.

ArrayList allows duplicates

ArrayList in Java allows duplicate elements to be added.

public class LoopListDemo {

    public static void main(String[] args) {
        // Using Diamond operator, so with ArrayList 
        // don't need to provide String, this option is available from 
        // Java 7 onwards
        List<String> cityList = new ArrayList<>();
        cityList.add("Delhi");
        cityList.add("Mumbai");
        cityList.add("Bangalore");
        cityList.add("Mumbai");
        cityList.add("Mumbai");
                
        // Using for-each loop 
        System.out.println("With for-each loop - Java 5");
        for(String name : cityList){
            System.out.println("City Name - " + name);
        }
    }
}

Output

With for-each loop - Java 5
City Name - Delhi
City Name - Mumbai
City Name - Bangalore
City Name - Mumbai
City Name - Mumbai

Here it can be seen that Mumbai is added 3 times and when I am looping the list and displaying the elements in the list it is showing Mumbai 3 times.

ArrayList allows any number of nulls

In ArrayList any number of nulls can be added. Let's see it with an example.

public class LoopListDemo {
    public static void main(String[] args) {
        // Using Diamond operator, so with ArrayList 
        // don't need to provide String, this option is available from 
        // Java 7 onwards
        List<String> cityList = new ArrayList<>();
        cityList.add("Delhi");
        cityList.add("Mumbai");
        cityList.add("Bangalore");
        cityList.add("Mumbai");
        cityList.add(null);
        cityList.add("Mumbai");
        cityList.add(null);
        
        // Using for-each loop 
        System.out.println("With for-each loop - Java 5");
        for(String name : cityList){
            System.out.println("City Name - " + name);
            //cityList.remove(2);
        } 
    }
}

Output

With for-each loop - Java 5
City Name - Delhi
City Name - Mumbai
City Name - Bangalore
City Name - Mumbai
City Name - null
City Name - Mumbai
City Name - null

It can be seen here that two null elements are added in the AraryList.

Removing elements from an ArrayList

ArrayList provides several methods to remove elements from the List. Since ArrayList internally uses array to store elements, one point to note here is that when an element is removed from the List internally the remaining elements are shifted to fill the gap created in the underlying array.

  • clear() - Removes all of the elements from this list.
  • remove(int index) - Removes the element at the specified position in this list.
  • remove(Object o) - Removes the first occurrence of the specified element from this list, if it is present.
  • removeAll(Collection<?> c) - Removes from this list all of its elements that are contained in the specified collection.
  • removeIf(Predicate<? super E> filter) - Removes all of the elements of this collection that satisfy the given predicate. Note that removeIf is added in Java 8.

Removing element from ArrayList- Java Example

public class ArrayListDemo {

    public static void main(String[] args) {
        // List with initial capacity as 2
        List<String> cityList = new ArrayList<>(2);
        cityList.add("London");
        cityList.add("Paris");
        cityList.add("Bangalore");
        cityList.add("Istanbul");
        cityList.add("Delhi");
        cityList.add("Houston");
        System.out.println("Original List- ");
        for(String name : cityList){
            System.out.println("City Name - " + name);
        }
        // Removing element at index 3
        String cityName = cityList.remove(3);
        System.out.println("Removed from the List- " + cityName);
        // using removeIf with a predicate
        cityList.removeIf((String name )->name.equalsIgnoreCase("Bangalore"));
        
        System.out.println("List after removal of elements-");
        
        for(String name : cityList){
            System.out.println("City Name - " + name);
        }
    }
}

Output

Original List- 
City Name - London
City Name - Paris
City Name - Bangalore
City Name - Istanbul
City Name - Delhi
City Name - Houston
Removed from the List- Istanbul
List after removal of elements-
City Name - London
City Name - Paris
City Name - Delhi
City Name - Houston

Note that parameter for the removeIf is of type Predicate which is a functional interface, so it's method can be implemented using lambda expression.

ArrayList is not synchronized

ArrayList in Java is not synchronized. That means sharing an instance of ArrayList among many threads where those threads are modifying the collection (adding or removing the values) may result in unpredictable behaviour. If we need to synchronize an ArrayList you can use synchronizedList method provided by Collections class, which returns a synchronized (thread-safe) list backed by the specified list.

Iterator for an ArrayList

ArrayList provides iterator to traverse the list in a sequential manner. Since ArrayList implements List interface so it provides ListIterator too which is different from the iterator in a way that it provides iteration in both directions.

One point to note here is that both iterator and listiterator are fail fast, fail-fast iterator fails if the underlying collection is structurally modified at any time after the iterator is created, thus the iterator will throw a ConcurrentModificationException if the underlying collection is structurally modified in any way except through the iterator's own remove or add (if applicable as in list-iterator) methods.

Structurally modifying ArrayList while iterating

public class ArrayListDemo {

    public static void main(String[] args) {
        // List with initial capacity as 2
        List<String> cityList = new ArrayList<>(2);
        cityList.add("London");
        cityList.add("Paris");
        cityList.add("Bangalore");
        cityList.add("Istanbul");
        Iterator<String> itr = cityList.iterator();
        while(itr.hasNext()){
            String city = itr.next();
            if(city.equals("Paris")){
                // removing using remove method 
                // of the ArrayList class
                cityList.remove(city);
            }
        }
    }
}

Output

Exception in thread "main" java.util.ConcurrentModificationException
 at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
 at java.util.ArrayList$Itr.next(ArrayList.java:851)
 at org.netjs.examples.ArrayListDemo.main(ArrayListDemo.java:18)

As you can see ConcurrentModificationException is thrown here as there is an attempt to remove an element from the ArrayList.

Modifying ArrayList using iterator's remove method

public class ArrayListDemo {

    public static void main(String[] args) {
        // List with initial capacity as 2
        List<String> cityList = new ArrayList<>(2);
        cityList.add("London");
        cityList.add("Paris");
        cityList.add("Bangalore");
        cityList.add("Istanbul");
        Iterator<String> itr = cityList.iterator();
        while(itr.hasNext()){
            String city = itr.next();
            if(city.equals("Paris")){
                itr.remove();
            }
        }
        // iterating after removal
        for(String name : cityList){
            System.out.println("City Name - " + name);
        }
    }
}

Output

City Name - London
City Name - Bangalore
City Name - Istanbul

Now ConcurrentModificationException is not thrown as iterator's remove method is used to remove element from the ArrayList.

Performance of ArrayList

  • Adding an element - If you are adding at the end using add(E e) method it is O(1). Even in the case of adding at the last ArrayList may give O(n) performance in the worst case. That will happen if you add more elements than the capacity of the underlying array, as in that case a new array (1.5 times the last size) is created, and the old array is copied to the new one. If you are using add(int index, E element) then it is O(n - index) and it'll become O(n) if every time element is added at the beginning of the list.
  • Retrieving an element - Since ArrayList internally uses an array to store elements so get(int index) means going to that index directly in the array. So, for ArrayList get(int index) is O(1).
  • Removing an element - If you are removing using the remove(int index) method then, in case of ArrayList getting to that index is fast but removing will mean shuffling the remaining elements to fill the gap created by the removed element with in the underlying array. It ranges from O(1) for removing the last element to O(n). Thus it can be said remove(int index) operation is O(n - index) for the arraylist.

That's all for this topic ArrayList in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. How ArrayList Works Internally in Java
  2. How to Remove Duplicate Elements From an ArrayList in Java
  3. How LinkedList Class Works Internally in Java
  4. How to Sort ArrayList of Custom Objects in Java
  5. Java Collections Interview Questions

You may also like -

Monday, 3 December 2018

Insertion Sort Program in Java

In this post we’ll see how to write insertion sort program in Java. Insertion sort is good for sorting a small set of elements.Out of the three simpler sorting algorithms insertion sort, selection sort and bubble sort, insertion sort is considered a better option in most of the scenarios.

How insertion sort works

In insertion sort you take one element at a time and the elements on the left side of the current element are considered temporarily sorted for example if you are at 4th index then elements at index 1..3 are sorted among themselves. But that is not yet the final position because any other element may have to be inserted in between these temporarily sorted elements, which means elements have to be shifted right to make place for the insertion of the element that is why the name insertion sort.

In each iteration the elements on the left of the current element are sorted and current element is compared with all the elements on its left, if it is smaller than any of these elements then it has to be inserted at that index and the elements have to be shifted right to make place for it.

For example if you have an array [5, 2, 6, 1] then you will start with 2 (2nd element) and compare it with elements on its left.

  1. In first iteration 2 is compared with 5. Since it is smaller so it has to be inserted in the place of 5 and other elements have to shifted right. Which gives the array as [2, 5, 6, 1] after first iteration.
  2. In second iteration 6 is compared with 5, since 6 is greater than 5 so nothing needs to be done. So array is still [2, 5, 6, 1].
  3. In third iteration 1 is compared with 6, since it is smaller so elements have to be shifted right which makes the array as [2, 5, 6, 6]. Note that there are more elements on the left to be compared so 1 is still not inserted as its final insertion point is still not sure at this point.
    Then 1 is compared with 5, since 1 is smaller so elements have to be shifted right which makes the array as [2, 5, 5, 6].
    Then 1 is compared with 2, since 1 is smaller so elements have to be shifted right which makes the array as [2, 2, 5, 6].
    At this point left most index is reached so we know that 1 is the smallest element so it is inserted at this index making the array as [1, 2, 5, 6].

Insertion Sort Java program

Logic for writing the insertion sort Java program is as follows-

You take one element (starting from the second element) at a time starting from left to right in the outer loop. Also assign this element to a temporary variable.

In inner loop, which starts at the same number as the outer loop and moves toward left, you compare the temp variable with all the previous elements (element on the left of the current index element).

This comparison goes on till both of these conditions hold true -

  • Elements on the left side are greater than the element at the current index.
  • Leftmost element is reached.

In each iteration with in this inner loop you also have to shift right by assigning the previous element to the element at the current index with in the inner loop.

public class InsertionSort {
    public static void main(String[] args) {
        int[] intArr = {47, 85, 62, 34, 7, 10, 92, 106, 2, 54};
        int[] sortedArray = insertionSort(intArr);
        System.out.println("Sorted array is- ");
        for(int num : sortedArray){
            System.out.print(num + " ");
        }
    }
    
    private static int[] insertionSort(int[] intArr){
        int temp;
        int j;
        for(int i = 1; i < intArr.length; i++){
            temp = intArr[i];
            j = i;
            while(j > 0 && intArr[j - 1] > temp){
                // shifting elements to right
                intArr[j] = intArr[j - 1];
                --j;
            }
            // insertion of the element
            intArr[j] = temp;
        }
        return intArr;
    }
}

Output

Sorted array is- 
2 7 10 34 47 54 62 85 92 106 

Complexity of insertion sort

If you have noticed in the program each time the number of elements that are to compared increases in progression; in first iteration only one element has to be compared, in second iteration two elements have to be compared and so on. Which gives us the number of comparison as–
1 + 2 + 3 + ............ + N-1 = N*(N-1)/2

Which makes the time complexity as O(N2) for insertion sort.

In the best case scenario, if the array is already sorted or almost sorted the while loop condition will return false making the time complexity as O(N) if it already sorted or almost O(N) if the data is almost sorted.

Insertion sort is an in place sorting algorithm so apart from the initial array very little extra memory is required so the auxiliary space requirement for insertion sort is O(1), total space can be considered as O(N).

That's all for this topic Insertion Sort Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. Shell Sort Program in Java
  2. Count Total Number of Times Each Character Appears in a String - Java Program
  3. Fibonacci Series Program in Java
  4. How to Remove Duplicate Elements From an Array - Java Program
  5. How to Create Password Protected Zip File in Java

You may also like -

>>>Go to Java Programs Page