Complexity Of an Algorithm

The complexity of an algorithm is a function f (n) which measures the time and space used by an algorithm in terms of input size n.

  • In computer science, the complexity of an algorithm is a way to classify how efficient an algorithm is, compared to alternative ones.
  • The focus is on how execution time increases with the data set to be processed.
  • The computational complexity and efficient implementation of the algorithm are important in computing, and this depends on suitable data structures.
  • A complexity of any algorithm tells you how much resources will the execution use over some input size n.

What effects run time of an algorithm?

  1. (a) computer used, the hardware platform
  2. (b) representation of abstract data types (ADT’s)
  3. (c) efficiency of compiler
  4. (d) competence of implementer (programming skills)
  5. (e) complexity of underlying algorithm
  6. (f) size of the input

We will show that of those above (e) and (f) are generally the most significant.

What do we measure?

In analysing an algorithm, rather than a piece of code, we will try and predict the number of times “the principle activity” of that algorithm is performed. For example, if we are analysing a sorting algorithm we might count the number of comparisons performed, and if it is an algorithm to find some optimal solution, the number of times it evaluates a solution. If it is a graph colouring algorithm we might count the number of times we check that a coloured node is compatible with its neighbours.

A function of input. However, we will attempt to characterize this by the size of the input. We will try and estimate the WORST CASE, and sometimes the BEST CASE, and very rarely the AVERAGE CASE.

What is worst Case?

The maximum run time, over all inputs of size n, ignoring effects (a) through (d) above. That is, we only consider the “number of times the principle activity of that algorithm is performed”.

What is Best Case?

In this case we look at specific instances of input of size n. For example, we might get best behaviour from a sorting algorithm if the input to it is already sorted.

What is Average Case?

Arguably, average case is the most useful measure. It might be the case that worst case behaviour is pathological and extremely rare, and that we are more concerned about how the algorithm runs in the general case.

Unfortunately this is typically a very difficult thing to measure. Firstly, we must in some way be able to define by what we mean as the “average input of size n”. We would need to know a great deal about the distribution of cases throughout all data sets of size n. Alternatively we might make a possibly dangerous assumption that all data sets of size n are equally likely.

Time for an algorithm to run t(n)

Time complexity can be seen as the measure of how fast or slow an algorithm will perform for the input size. Time complexity is always given with respect to some input size (say n). Here’s an example to clear the text :

11 people are standing in a row in ascending order with respect to their heights. Now you are asked to tell the median of their heights. You have 2 methods to do it :

  1. Starting from the first(smallest) person, you record the height of every person in the line and then calculate the median of the data. Notice, in this method, we asked (compute) heights of all 11 men. That means we did the work given to us in the order of total men standing in the line. What if there were n men ? then our computation would have been n. So we can say that time complexity is directly related to n or O(n).
  2. You act smartly this time. You knew that everyone is standing in ascending order so its not required to go to every person. You then go the the person standing on the 6th position and asked his height. He tell you his height and you declare the answer. In this approach, it didn’t matter if there were 10 or 100 men, you would just go the the middle person and get the answer. So here you had to work only once, or we can say that the time complexity is independent of the input size and can be written as O(1).

So which method would you prefer ? Clearly the second one.

Space complexity can be seen as the amount of extra memory you require to execute your algorithm. Like the time complexity, it is also given with respect to some input size (n). Another example :

10 bags are to be transported from one site to another. Again you have two options.

  1. You choose a small vehicle which has only one seat and you cannot keep more than one bag on the seat. So you take a bag and transport it. You make 10 trips (time complexity) but only one seat (space complexity). Similarly if you had n bags and you intend to transport them with the same medium, then also you will need only one seat. So you can say that space complexity for this solution will be constant or independent of the input size (number of bags) or O(1).
  2. Now you were fed up making a lot of trips between the two sites. You choose a bus with exactly same seats as the number of bags. You keep one bag per seat in the bus. Here, we have to make only one trip (time complexity) but we have used 10 seats (space complexity). Here you can say that number of seats (extra memory) is directly proportional to the input size (number of bags). So the space complexity is O(n).

You can observe the time-space trade off in this example.

Complexity of algorithm O(1) : Constant

The complexity O(1) states that no matter what the input size, the effort to get the output is always constant.
Example : Finding the median of a sorted list is always the middle of list i.e n/2 position.

Complexity of algorithm O(n) : Linear

The complexity O(n) states that the effort to get the output is directly proportional to the input size.

Complexity of algorithm O(log n) : Logarithmic

The log here is the log with the base 2 and not with the base 10 like calculus, in computer science log is by default log with the base 2.
log n can be reprsented as 2 ^? = n.
Example log 8 is 2 ^ x = 8. and the x is 3 here.
In short log n means here that we are using a dividing out input n into half everytime and trying to find the result. Binary Search has a complexity of O(log n).

Complexity of algorithm O(n^2) : Quadratic

Bubble sort algorithm has the worst case scenario of O(n^2). So how bubble sort works is, the highest value in the array in bubbled down to the bottom of the array, and for next iteration last element is not compared since it is the highest element in the array.
Bubble sort requires : 2 loops(a loop inside a loop i.e nested loop) and a swap, Since the two loops are nested loop hence the time complexity is O(n^2) since number of inputs n * n times and a swap has time complexity of O(1) since it is constant i.e independent of input n. Hence in total the complexity is O(n^2).
Insertion sort also has the same time complexity.

Primitive and non primitive data type in java

Quick Reference :

  • Rules for the name of identifiers
  • Default initialization values of primitives on local and global scope
  • Numeric Promotion
    • Rule 1 : If two values have different data types, Java will automatically promote one of the values to the larger of the two data types.
    • Rule 2 : If one of the values is integral and the other is floating-point, Java will automatically promote the integral value to the floating-point value’s data type.
    • Rule 3 : Smaller data types, namely byte , short , and char , are first promoted to int any time they’re used with a Java binary arithmetic operator, even if neither of the operands is int .
    • Rule 3 : After all promotion has occurred and the operands have the same data type, the resulting value will have the same data type as its promoted operands.
  • Overflow and Underflow
    • Overflow
      • short y = (short)1921222;
      • // Stored as 20678 overflow example
      • System.out.print(2147483647+1);
    • Underflow
      • Underflow is the opposite of overflow. While we reach the upper limit in case of overflow, we reach the lower limit in case of underflow. Thus after decrementing 1 from Integer.MIN_VALUE, we reach Integer.MAX_VALUE.
    • JVM does not throw any exception in case Overflow or underflow occurs, it simply changes the value. Its programmer responsibility to check the possibility of an overflow/underflow condition and act accordingly. 
  • Max Value int,float,byte,char,short,double & long can store
    • byte = 8-bit integer
    • int = 32-bit integer
    • long = 64-bit integer
    • short = 16-bit integer
    • float – 32 bits
    • double – 64 bits
    • boolean – 1 bit
    • char – 16 bits
  • Always consider the max size of Integer variable, if long is possible for it or not

To do :

  • System.out.println(10*20*30*500000000*60.0);//1.79999999E14 what does E signify
  • Type casting, widening data type (https://docs.oracle.com/javase/specs/jls/se7/html/jls-5.html#jls-5.2)
  • int amount = 0b101;
  • Object type and primitive type which is better and which situations.
  • memory allocated in case of non primitive
  • Speed of access for non primitive data type
  • Precision of float and double
  • Why we need to added f and l at the end of float and long respectively.
  • How to add two bytes a = 100 and b = 200 will result into -56 ? (cause of 2nd compliment)
  • You can add _ in numerical literals to make it more readable
    int million2 = 1_000_000;
    System.out.println(56); // 56
    System.out.println(0b11); // 3
    System.out.println(017); // 15
    System.out.println(0x1F); // 31
TypeSize in bits(in Ram)Min ValueMax ValuePrecisionExample
booleanJVM specific(1 bit)--true or falseboolean x =true;
byte8-128127+127 or -127
byte b = 120;
char1602^16 -1All unicode characterschar c ='A';
char c = 65;
short16-2^152^15-1+32,767 to -32,768short s = 30000;
int32-2^312^31-1+2,147,483,647 to -2,147,483,648int i = 10;
long64-2^632^63-1+9,223,372,036,854,775,807 to -9,223,372,036,854,775,808long l = 90;
float322^-149(2-2^-23).2^1273.402,823,5 E+38 to 1.4 E-45 float f = 65f;
double642^-1074(2-2^-52).2^10231.797,693,134,862,315,7 E+308 to 4.9 E-324double d = 65.55;
  • Java has eight built-in data types, referred to as the Java primitive types.
  • These eight data types represent the building blocks for Java objects, because all Java objects are just a complex collection of these primitive data types.

Difference between Primitive and Non primitive data type is :

  • Primitive data hold a value and cannot be set to null while non primitive can do that.
  • When a non primitive data type reference is not null then a method of that class can be called using that object reference but primitive data type cannot do that.

Identifiers :

  • Java has precise rules about identifier names.
  • Luckily, the same rules for identifies apply to anything you are free to name, including variables, methods, classes, and fields.

There are only three rules to remember for legal identifiers:

  • The name must begin with a letter or the symbol $ or _ .
  • Subsequent characters may also be numbers.
  • You cannot use the same name as a Java reserved word.

Legal Identifiers :

okidentifier
$OK2Identifier
_alsoOK1d3ntifi3r
__SStillOkbutKnotsonice$
$$hell_o__

IIlegal identifiers :

3DPointClass // identifiers cannot begin with a number
hollywood@vine // @ is not a letter, digit, $ or _
*$coffee // * is not a letter, digit, $ or _
public
// public is a reserved word

Default initialization of variables :

Note : A local variable no matter the data type, be it primitive or non primitive or object they cannot be set to default value on the other hand global variable can have a default value, note a compile time error is thrown when a local variable is not initialized and expected to perform operations on it default value.

Using an uninitialized local variable :

  • Local variables are those variable which are defined with in a method.
  • If a local variable is not initialized after declaration then java compiler will throw a compile time error saying that the variable is not initialized
  • Compile is also smart enough to identify a variable if they are only initalized in one of the if variable

Example 1 :

	public static void main(String[] args) {
		int x = 10;
		int y ;
		int z = x + y; //Compile time error : The local variable y may not have been initialized
	}

Example 2 : Compiler is also smart to identify complex initializations

	public static void main(String[] args) {
		int x = 10;
		int y ;
		if(Boolean.parseBoolean(args[0])) {
			y = 10;
		}
		int z = x + y;//The local variable y may not have been initialized
	}

Using an uninitialized class variable and instance variable :

  • Instance variables are declared in a class, but outside a method, constructor or any block.
  • Class variables also known as static variables are declared with the static keyword in a class, but outside a method, constructor or a block.
  • Instance variables are created when an object is created with the use of the keyword ‘new’ and destroyed when the object is destroyed.
  • Static variables are created when the program starts and destroyed when the program stops.
  • Instance variables can be accessed directly by calling the variable name inside the class, but inside static method they should be called obj.instance way i.e fully qualified way.
  • Static variables can be accessed by calling with the class name ClassName.VariableName.
  • Instance variable has a copy for each object.
  • Class variable has only one copy across class.

Below are the default value of uninitialized class and instance variable :

Variable TypeDefault Initialization value
booleanfalse
byte, short, int, long0
float, double0.0
char‘\u0000’ (null)
All object refenrencenull

Numeric Promotion in java

Rules of Numeric Promotion

  1. If two values have different data types, Java will automatically promote one of the values to the larger of the two data types.
  2. If one of the values is integral and the other is floating-point, Java will automatically promote the integral value to the floating-point value’s data type.
  3. Smaller data types, namely byte , short , and char , are first promoted to int any time they’re used with a Java binary arithmetic operator, even if neither of the operands is int .
  4. After all promotion has occurred and the operands have the same data type, the resulting value will have the same data type as its promoted operands.

Example :

public class NumericPromotionDemo {
	public static void main(String[] args) {
		//Rule #1
		{
			int x = 10;
			long y = 20;
			long z = x+y;// x automatically promoted to long
		}
		//Rule #2
		{
			int x = 10;
			float f = 20.2f;
			float z = x + f; // x is automatically promoted to float
		}
		//Rules #3
		{
			byte b = 10;
			short s = 20;
			int x = b + s; 
			//be it byte,char,short they are automatically promoted to int when arithmatic operator is applied
		}
		//Rule #4
		{
			byte b = 10;
			short s = 20;
			int i = 30;
			long l = 5;
			float f = 60;
                        //X automatically promoted to float
			float x = b + s * + i + l + f;
			System.out.println(x);
		}
	}
}

Overflow and Underflow

short y = (short)1921222;
// Stored as 20678 overflow example
System.out.print(2147483647+1);
// -2147483648 the integer wrapped around since int can store value more than that

The expressions in the previous example now compile, although there’s a cost. The sec-
ond value, 1,921,222 , is too large to be stored as a short , so numeric overfl ow occurs
and it becomes 20,678 . Overfl ow is when a number is so large that it will no longer fi t
within the data type, so the system “wraps around” to the next lowest value and counts
up from there. There’s also an analogous underfl ow, when the number is too low to fi t in
the data type

Adding Optional Labels

A label is an optional pointer to the head of a statement that allows the application fl ow to jump to it or break from it. It is a single word that is proceeded by a colon ( : ). For example,

int[][] myComplexArray = {{5,2,1,3},{3,9,8,9},{5,7,12,7}};
OUTER_LOOP: for(int[] mySimpleArray : myComplexArray) {
INNER_LOOP: for(int i=0; i<mySimpleArray.length; i++) {
System.out.print(mySimpleArray[i]+"\t");
}
System.out.println();
}

PrintWriter

  • It is the most enhanced writer to write character data to the file.
  • The main advantage of print writer is we can write any Type of Primitive Type Data Directly to the file.
  • bw.write(true)//compile timer error because boolean is not accepted by BufferWriter
  • bw.write(100)//will print the letter d, so to print 100 we have to cast it to string
  • bw.write(10.5)//compile time error because it does not support double.
  • Every time we need to use primitive data type with BufferWriter we need to cast it to String to use it, and casting every type to string will eat up the system memory and reduce the system performance.
  • Using BufferReader for new line we have to call a separate method bw.newLine() which adds an extra line of code and in FileWrite adding “\n” every time make the code unreadable now in print writer println method automatically adds the breakline at the end of the line.
  • All the above problems are addressed in print and println method of PrintWriter class

Constructors:

PrintWriter pw = new PrintWriter(String fileName);
PrintWriter pw = new PrintWriter(File f);
PrintWriter pw = new PrintWriter(Writer w);

Note : PrintWriter can communicate either directly to the file or via some writer object also.

Methods of PrintWriter :

write(int ch);
write(char[] ch);
write(String s);
flush();
close();

print(char ch);
print(int i);
print(double d);
print(boolean b);
print(String s);

println(char ch);
println(int i);
println(double d);
println(boolean b);
println(String s);

Below program show an example of PrintWriter

package com.fileDemo;

import java.io.FileNotFoundException;
import java.io.PrintWriter;

public class Demo {
	public static void main(String[] args) throws FileNotFoundException {
		PrintWriter pw = new PrintWriter("/home/tyson/Desktop/temp/file3");
		pw.write(100);
		pw.print(100);
		pw.println(700);
		pw.println(true);
		pw.println('K');
		pw.println("Tyson");
		pw.flush();
		pw.close();
	}
}

Output :

d100700
true
K
Tyson

What is the difference betwen pw.write(100) and pw.print(100) in the above code ?

  • In the case of pw.write(100) the character d will be written into file.
  • In case of pw.print(100) the string 100 will be written into the file.

BufferedReader

  • We can use BufferedReader to Read Character Data(text data) from file.
  • The main advantage of BufferedReader over FileReader is we can Read Data Line by line in addition to Character by Character, which is more convenient to the programmer.

Constructors :

BufferedReader br = new BufferedReader(Reader r);
BufferedReader br = new BufferedReader(Reader r, int bufferSize);

Note : BufferedReader cannot directly communicate with the file, it has to communicate via some reader object.

Methods :

int read();
int read(char[] ch);
void close();
String readLine();
  • It attempts to read next line from the file and returns it, if it is available.
  • It next line is not available, then it will return null.

Sample program to read line using buffered reader :

package com.fileDemo;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;

public class Demo {
	public static void main(String[] args) throws IOException {
		File f = new File("/home/tyson/Desktop/temp/file2");
		FileReader fr = new FileReader(f);
		BufferedReader br = new BufferedReader(fr);
		String line = br.readLine();
		while(line!=null) {
			System.out.println(line);
			line = br.readLine();
		}
		br.close();
	}
}

Note :

  • We need not close FileReader object, while closing BufferedReader object the FileReader object is closed implicitly.
  • Most enhanced reader to read data from the file is BufferedReader

BufferedWriter

Use of FileReader and FileWriter is not recommended because :

  • While Writing Data by FileWriter we have to insert line separator manually, which is varied from System to System. It is difficult to the programmer.
  • While Reading Data by using FileReader we can read data character by character which is not convenient to the programmer.

To overcome these limitations we should go for BufferedWriter and BufferedReader.

Constructor :

BufferedWriter bw = new BufferedWriter(Write w);
BufferedWriter bw = new BufferedWriter(Write w, int buffersie);

Note : BufferedWriter can’t communicate directly with a file , it has to communicate via some Writer object only.

Which of the following are valid?

BufferedWriter bw = new BufferedWriter("abc.txt");//Not Valid
BufferedWriter bw = new BufferedWriter(new File("abc.txt"));//Not Valid
BufferedWriter bw = new BufferedWriter(new FileWriter("abc.txt"));//Valid
BufferedWriter bw = new BufferedWriter(new BufferedWriter(new FileWriter("abc.txt")));//Valid and called 2 level buffering

Methods of BufferedWriter:

write(int ch);
write(char[] ch);
write(String s);
flush();
close();
newLine();//To insert a line Separator

Writing to a file using BufferedWriter :

package com.fileDemo;

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

public class Demo {
	public static void main(String[] args) throws IOException {
		File f = new File("/home/tyson/Desktop/temp/file2");
		FileWriter fw = new FileWriter(f);
		BufferedWriter bw = new BufferedWriter(fw);
		bw.write("Hello");
		bw.write("World");
		bw.newLine();
		bw.write("You are writing a java program");
		bw.flush();
		bw.close();//No need to flush(), close() will call flush() internally
		//fw.close(); //file Writer object is closed automatically closed by buffered writer close method
	}
}

Note :

  • It is recommended to close buffered writer object and buffered writer object automatically closes the file writer.
  • It is not recommended to close fileWriter object.
  • flush() method of buffered writer is automatically closed while calling buffered writer’s close() method call

FileReader

We can use FileReader to Read Character Data from the file.

Constructors :

FileReader fr = new FileReader(String fileName);
FileReader fr = new FileReader(File fileReference);

Note : If the file does not exist then, FileReader will throw java.io.FileNotFoundException

Methods :

int read(); //returns unicode value of character
int read(char[] ch); //returns number of characters copied from file to array
void close();

Example of : int read() method

package com.fileDemo;

import java.io.File;
import java.io.FileReader;

public class Demo {
	public static void main(String[] args) throws Exception {
		File f = new File("/home/tyson/Desktop/temp/file1"); //throws exception if file is not present
		FileReader fr = new FileReader(f);
		int x = fr.read();
		while(x!=-1) {
			System.out.print((char)x); //need to type cast to convert unicode to its character value 
			x = fr.read();
		}
                fr.close();
	}
}

Example of : int read(char []) method

package com.fileDemo;

import java.io.File;
import java.io.FileReader;
import java.io.IOException;

public class Demo {
	public static void main(String[] args) throws IOException {
		File f = new File("/home/tyson/Desktop/temp/file1");
		char[] ch = new char[(int)f.length()];
		FileReader fr =	new FileReader(f);
		fr.read(ch);
		for(char c : ch) {
			System.out.print(c);
		}
		fr.close();
	}
}

Note : Line by line reading is not possible in FileReader hence the concept of BufferedReader.

FileWriter

We can use File Writer Object to write Character Data(text data) to the File.

Constructors :

FileWriter fw = new FileWriter(String fileName)
FileWriter fw = new FileWriter(File fileReference)

Above constructors will by default override the file name mentioned but to append the data to the file below constructors can be used.

FileWriter fw = new FileWriter(String fileName, boolean append)
FileWriter fw = new FileWriter(File fileReference, boolean append)

Note : If the file mentioned in the above constructors are not available then all FileWrite constructor will create the a new file to write into it.

Methods of FileWriter Class :

write(int ch); //to Write a single character into the file using its UNICODE
write(char[] ch);
write(String s);
flush(); //To save/write the data into the file we use flush method
close();

Example of FileWriter in java :

package com.fileDemo;

import java.io.File;
import java.io.FileWriter;
import java.io.IOException;

public class Demo {
	public static void main(String[] args) throws IOException {
		File f = new File("/home/tyson/Desktop/temp/file1");
		FileWriter fw = new FileWriter(f);
		fw.write("Hello World \nThis is java example");
		fw.flush();
		fw.close();
	}
}

Note : The problem with FileWriter is we have to insert line separator (\n) manually, which is varied from System to System. It is very difficult to the programmer. Hence the concept of BufferdWriter and PrintWriter came into picture

File Class in java

File f = new File("abc.txt");
  • The above line won’t create a physical file but it will check if file is available with that name.
  • If the file is available the object f will point to that file.
  • If the files doesn’t exist then it just creates a java File object to represent a file name ‘abc.txt’ but it won’t actually create any physical line

How to create a new file in java?

File f = new File("abc.txt");
f.createNewFile();

How to create a new directory in java?

File f = new File("/home/tyson/HelloWorld");
f.mkdir();

How to check if a file or a directory exist in java?

File f1 = new File("abc.txt");
File f2 = new File("/home/tyson");
f1.exist()
f2.exist()

Note : Java IO Concept is implemented based on the UNIX OS concept and in unix everything is treated as a File.Hence we can use java file object to represent both file and directories.

File Class Constructors :

File f1 = new File(String name);
//Creates f1 object representing file or directory
File f2 = new File(String subDir, String name);
//Creates f2 object within a subdirectory
File f3 = new File(File subDir, String name);

File Class important methods :

boolean exist();
boolean createNewFile();
boolean mkdir();
boolean isFile();
boolean isDirectory();
String[] list(); //returns names of all files and directory present in a directory
long length(); //returns number of characters present in the specified file.
boolean delete(); //deletes a file or directory.

Program to print the list of files and directories in a directory in java :

package com.fileDemo;

import java.io.File;

public class ListOfFilesDemo {
	public static void main(String[] args) {
		File f = new File("/home/tyson/Desktop/temp");
		String[] listOfFiles = f.list();
		for(String name : listOfFiles) {
			System.out.println(name);
		}
	}
}

ArrayList

Complexity of ArrayList:

Array ListTime ComplexitySpace Complexity
Adding ElementO(1) – resize O(log(n))
Removing ElementO(n)
Iterating ElementsO(n)
Retreving Element at PositionO(1)
  • ArrayList is one of the implementation of List interface.
  • Underlying data structure of ArrayList is Resizable Array or Growable Array.
  • Underlying data structure of ArrayList is array, i.e data is stored inside an array.
  • ArrayList are equivalent to Vector but ArrayList are not synchronized.
  • All operations run in around O(n) time complexity.
  • But if you want to remove items, this operation is not so efficient, we have to shift each item in our list O(n), instead we should use linked list.
  • Capacity of an ArrayList should be defined during instantiation when ever possible (List<Object> l = new ArrayList<>(5000)), this may reduce the amount of incremental reallocation.
  • Implements RandomAccess Interface(Only Array List and Vector), Clonable Interface and Serializable Interface
  • Note : Except TreeSet and TreeMap heterogeneous objects are allowed.

Features of ArrayList :

  • Best choice if reading at random index is required.
  • Worst choice if adding and deleting in middle of list has to be performed.(Use Linkedlist)
  • Duplicates are allowed
  • Insertion order is preserved.
  • Resizable or Growable
  • Store heterogeneous object
  • null insertion is possible
  • Default initial capacity of arraylist is 10
  • New capacity of arraylist will be (currentcapacity * 1.5)+1 (Default capacity increment will be 10, 16, 25…)
  • Implements RandomAccess Interface which helps to access all the index of an array with the same speed as be it 1st element or 1000th element.

When to use ArrayList ?

  • ArrayList provides constant time for search operation.
  • it is better to use ArrayList if searching is more frequent operation than add and remove operation.

Constructors of ArrayList :

ArrayList<Object> l = new Arraylist<>(); //size 10 by default
ArrayList<Object> l = new Arraylist<>(int initialCapacity); //predefined capacity
ArrayList<Object> l = new Arraylist<>(Collection c); //create equivalent array list

Example :

public class ArrayListDemo {
	public static void main(String[] args) {
		ArrayList<String> l = new ArrayList<>();
		l.add("A");
		l.add("B");
		l.add(null);
		System.out.println(l);
		l.remove(2);
		System.out.println(l);
		l.add("M");
		l.add("N");
		System.out.println(l);
	}
}

Questions :

  • Remove duplicates from ArrayList in Java

Collections Framework

Advantage of Collections over Arrays

  • Collections are Grow-able in Nature
  • Collection can hold heterogeneous data type. (An Interface type of Collection can be created)
  • Collections are created based on some standard data structure

9 Key Interfaces of Collection Framwork

  1. Collection
  2. List
  3. Set
  4. SortedSet
  5. NavigableSet
  6. Queue
  7. Map
  8. SortedMap
  9. NavigableMap

Collection Interface

  • Most common methods applicable for almost all Interface is inside Collection Interface

Methods

  • Query Methods
    • size()
    • contains()
    • iterator()
    • toArray()
  • Modification Methods
    • add()
    • remove()
  • Bulk Operations
    • containsAll()
    • addAll()
    • removeAll()
    • removeIf()
    • retainAll()
    • clear()
  • Comparison and Hashing
    • equals()
    • hashcode()

Collection vs Collections

  • Collection is an Interface (Root interface of collections)
  • Collections is a Utility class used for collections. It contains method like searching and sorting
Collection interface - BenchResources.Net
  • Collection<I>
    • List<I>
      • ArrayList
      • LinkedList
      • Vector (Legacy)
        • Stack(Legacy)
    • Set<I>
      • HashSet
      • LinkedHashSet
      • SortedSet<I>
        • NavigableSet<I>
          • TreeSet
    • Queue<I>
      • Priority Queue
      • Blocking Queue<I>
        • PriorityBlockingQueue
        • LinkedBlockingQueue
  • Map<I>
    • HashMap
      • LinkedHashMap
    • WeakHashMap
    • IdentityHashMap
    • Hashtable(Legacy)
      • Properties(Legacy)
    • SortedMap<I>
      • NavigableMap<I>
        • TreeMap

Other Classes :

  • Sorting
    • Comparable<I>
    • Comparator<I>
  • Cursor
    • Enumeration(Legacy)
    • Iterator
    • ListIterator
  • Utility Classes
    • Collections
    • Arrays

Description :

  • The java collections Framework defines several classes and interfaces which can be used to represent a group of individual object as a single entity.
  • These classes and interface implement the collection data structures.
  • For Example : list, stack, queue or maps.
  • The collection framework was designed and developed primarily by Joshua Bloch
  • It was introduced in JDK 1.2
  • Why to use these collections?
    • We don’t have to implement every algorithm and data structure from the scratch, its already written into java.
    • It is already been tested.
  • Almost all Collections are derived from the java.utils.Collection interface
  • The main advantage of Collections over array is that collections are grow-able in size, i.e we need not know the size of elements in advance.
  • toArray() method can transform any collection into one dimensional array.
  • The Collection interface extends the java.lang.Iterable interface, this is why we can use for-each loop.

We write for each loop like below example :

for(String fruits : listOfFruits){
   System.out.println(fruits);
}

After compilation of .java file, .class file contains below code :

for (Iterator<String> i = listOfFruits.iterator(); i.hasNext();) {
   String fruits = i.next();
   System.out.println(fruits);
}

1) Collection(I): If we want to represent a group of individual objects as a single entity then we should go for collection.

  • The collection interface defines the most common methods which are applicable for any collection object.
  • In the general collection, the interface is considered as the root interface of the collection framework.
  • There is no concrete class that implements collection interface directly

Difference between collection and collections

  • The collection is an interface. If we want to represent a group of the individual object as a single entity then we should go for the collection
  • Collections is a utility class present in java. Util package to define several utility methods for collection object(like sorting, searching, etc)

2) List(I): It is the child interface of collection. If we want to represent a group of individual objects as a single entity where duplicates are allowed and insertion order must be preserved then we should go for List.

List(I) - Framework collection

You can learn this in detail in our institute which provides advanced Java training in Delhi and Core java training in Delhi.

Note:- in 1.2version vector and stack classes are re-engineered to implement List Interface.

3) Set(I): It is the child interface of collection. If we want to represent a group of individual objects as a single entity where duplicates are not allowed and insertion order not required then we should go for set Interface

Set(I) - Framework collection

4) SortedSet(I): It is the child interface of the set. If we want to represent a group of individual objects as a single entity where duplicates are not allowed and all objects should be inserted according to some sorting order, then we should go for a sorted set.

5) NavigableSet(I): It is the child interface of the sorted set. It contains several methods for navigation purposes.

NavigableSet(I)- Framework collection

6) Queue(Interface): it is the child interface of collection. If we want to represent a group of individual objects prior to processing then we should go for the queue. Usually, the queue follows first in first out the order but based on our requirement we can implement our own priority order also.

Queue (Interface)- Framework collection

7) Map(Interface): Map is not the child interface of Collection.

  • If we want to represent a group of objects as key-value pairs then we should go for a map.
  • Both keys and values are objects only duplicate keys are not allowed but values can be duplicated.
Map (Interface) - Framework collection

8) SortedMap(Interface): It is a child interface of a map.

  • If we want to represent a group of key-value pairs according to some sorting order of keys Then we should go for a sortedmap.
  • In a sortedmap, the sorting should be based on key but not based on value.

9) NavigableMap(Interface): It is the child Interface of sorted maps it defines several methods for navigation purposes.

NavigableMap (Interface) - Framework collection