Internal implementation of ArrayList and LinkedList Collections

ArrayList underlying implementation is based on Traditional Array data structure. Read Arrays in Java , for details on Arrays.

This post focuses on internal working of ArrayList and LinkedList Collections.

java.util.ArrayList class, is internally implemented as array.

What is array data structure?

An Array is a simplest data structure, which stores same type of elements, sequentially in memory.

Static Array
Static Array

Advantage of array

Accessing an element is very fast. Since base address of array is known, the required element which need to be fetched, can be retrieved, just by doing some manipulations on base address.

Disadvantage of array

Adding an element in between or in the beginning is very slow. Reason is, other existing elements need to be moved right by one position, and new element can be added, to the free slot created. This hits performance of program, and hence it is not recommendable to use Arrays for such situations.

java.util.LinkedList class is internally implemented using linked list data structure.

What is linked list data structure

linked list is a data structure, whose elements are not stored sequentially in memory, and are scattered in the memory. As shown in below picture, each node has Element, and reference to next and previous nodes.

what is linked list
linked list data structure

Advantage of link list data structure

An element can be added any where in between, just by changing previous and next references, as shown in below picture. This operation is slow in an array, as briefed above in array section.

Size of linked list can shrink or increase, during run time, based on the requirement.

Disadvantage of link list data structure

To Access an element, all elements need to be traversed, until the specific required element is reached. Hence searching an element is slower.

Another disadvantage of linked list is, there will be wastage of small memory, since each node need to store references to previous and next nodes.

You may also like to read:
Create our own linked list
When to use List and Set
Which are non synchronized Collections?
Generic version HashSet example

Purpose of a package, in Java

What is a package?

A Package is set of Classes, interfaces or sub packages.

Advantage of package

Below are advantages of packages
1. To avoid name collisions between classes or interfaces. Using different packages it is possible to have Classes or interfaces with same name.
2. Improves Modularity of Applications. As application development, is done across various Teams spread across various organizations, it is advantage to have each software module or layer in a package, and each sub module may further have sub package.
3. Another advantage of packages is, packages provides one more level of accessibility. Class members or classes with default or no access specifier, are accessible only within, current package.

All public classes and interfaces can be accessed by other packages also.
All classes and interfaces with default or none access specifier, can be accessed only within current package.

Below is diagram showing two packages com.java652 and com.p1. The package com.java652 has two classes WeatherDetails and CityDetails. The package com.p1 has one class StateDetails and an interface. objects of classes in different packages interact with each other, to perform required functionality.

What is Java Package
Java Package

Keywords used for packages





Below are keywords used in packages
1. package
package keyword is used to specify to which package, current java source file belongs to. There can be only package statement in a file. package statement need to be first statement in the file.
2. import
import keyword is used to specify that classes or interfaces of other packages need to be used in current java file. There can be multiple import statements, in a single file.

Also note that a separate folder is created with package name as folder name. And all class and interface files belonging to this package, are in this folder.

Download Package example(Eclipse Project)

For each sub package, one sub folder is created, under the main folder.

How to create package

how to create package, manually

When you develop java project using command line, and simple text editor, you need to manually create the package.
That means you need to manually create folders, and sub folders, for packages and sub packages, accordingly. Place java source file in corresponding folders or sub folders.

How to create package on Eclipse

As shown in below picture,
Right click on project, for which you want to create a package.
Now select New, then select package, then fill the package name like com.java652
To create class in this package, right click on package, select New, then select Class, then fill the class name.

how to create package in eclipse
how to create package in eclipse

How to create package on Netbeans

As shown in below picture,
Right click on project, for which you want to create a package.
Now select New, then select Java Package, then fill package name
To create class in this package, right click on package, select New, then select class.

how to create package in netbeans
how to create package in netbeans

you may also like to read:
How many Access specifiers in Java?
Can a abstract class have static method

Wrapper classes in Java

There are Eight primitive or basic data types in Java. Each of this primitive data type has corresponding Wrapper class. It is possible to convert primitive type to Wrapper class, and vice versa.

Basic Data Type Wrapper Type
int java.lang.Integer
float java.lang.Float
short java.lang.Short
byte java.lang.Byte
long java.lang.Long
double java.lang.Double
char java.lang.Character
boolean java.lang.Boolean

How to convert String to float?


public class HelloWolrd {

	public static void main(String[] args)
	{
		try
		{
		String str ="23.14f";

		float val = Float.parseFloat(str);

		System.out.println("Converted float value is:"+val);
		}
		catch(NumberFormatException nfe)
		{
			System.out.println("Exception:"+nfe.getMessage());
		}
	}
}

You may also like to read:
Autoboxing and Autounboxing
what is assertion in Java?
What are built in exceptions in Java

What is AutoBoxing and Unboxing?

Autoboxing and Unboxing is a feature introduced in Java version 5.

This feature is related to conversion between primitive data types to its corresponding Wrapper class Type.

For example, converting automatically from int to Integer object is considered as Autoboxing, where as automatically converting Integer object to int is called Auto unboxing. No code need to be written, explicitly for this conversion.

public class AutoBoxingUnboxing {
	public static void main(String args[])
	{
	//auto boxing, automatically converts int to Integer
	Integer iObj = 10;

	Integer iObj1 = new Integer(20);

	//auto unboxing, automatically converts
	int i = iObj1;

	display(1.1f, 2.2f);
	}

	static void display(Float val1, Float val2)
	{
	System.out.println("Display(): "+val1+" "+val2);
	}
}

Output:
Display(): 1.1 2.2

Autoboxing and Unboxing happens, when below operations are done
1.during comparison
2.assignment
3.returning from a method

public class AutoBoxing1 {
	public static void main(String args[])
	{
		Integer val1=12;

		//Here val1 is automatically converted to primitive type int
		//after above conversion, comparison is done
		if(val1<6)
		{
			System.out.println("12 is less than 6");
		}
		else
		{
			System.out.println("12 is not less than 6");
		}
	}
}
output:
12 is not less than 6

Auto Boxing and Unboxing occurs between below types

Basic Data Type Wrapper Type
int java.lang.Integer
float java.lang.Float
short java.lang.Short
byte java.lang.Byte
long java.lang.Long
double java.lang.Double
char java.lang.Character
boolean java.lang.Boolean

You may also like to read:
Basic data types in Java
Purpose of Generic Class
How to create Thread using anonymous class

Access Specifier and Scope

Below are Access Specifiers supported in Java.
1. private
2. public
3. protected
4. default or none

private, public, protected are Access specifiers, which can be used only for members(data members and member methods) of a class.

private members can be accessed only within the class.

public members can be accessed with the class, other classes in current package, classes in other package.

protected members can be accessed within the class, and in the immediate derived class.

members with no access specifiers can be accessed within the class, and other classes only within current package.

Lifetime of variables

Lifetime of a variable, depends on the place where it has been declared.

Life time of Data members or instance variables is same as the object, in which they exist. An object is destroyed by garbage collector Java when there are no more reference to that object.

Local Variables:
Local variables are the variables declared in the method body. Local variable are available within method body until method returns.

Arguments or Parameters:
Arguments or Parameters are passed to constructor or methods, and are available until the constructor or method returns.

Also variables can be declared in a block(Eg. if, else block,etc…), within a method. Such variables are available only within the block where they have been declared.

Below is an example code snippet:

class Test1
{
	int i,j; //data members or member variables or instance variables

	Test1()//constructor
	{
	i = 20;
	j = 11;

	System.out.println("Test1() Constructor");
	}

	void add() //member methods
	{
	int k; //local variable i..e not a member variable of Test1 class
	//NOTE: k cannot be accessed from object of Test1 class
	k = i+j;
	System.out.println("Add Result is:"+k);
	}

	void sub()
	{
	int l = i-j; //l is local variable
	System.out.println("Sub Result is:"+l);
	}
}

public class ClassDemo {
//execution starts from here
public static void main(String args[])
{
//obj is local object
	Test1 obj; //declaring object reference
	obj=new Test1(); //creating object of Test1 class
	obj.add(); //invoking add() method of Test1 class, using object obj

	obj.sub();
}
}

You may also like to read:
purpose of static block
what is for each loop, in java

What is a class, in Java?

Basics of Object Oriented Concepts.
A class is basic unit of Object Oriented Languages, and hence in Java.
A class can have or a class encapsulates
1.Data Members or properties or fields
2.Constructors
3.Member Methods or Methods

What are properties, of a class

Data members or Properties is the data required by the member methods, to operate. Data members is one of the way, in which constructors and methods of a class, can share data. A class can have zero or more properties. A property can be of primitive type or user defined type.

What are methods, of a class

Methods is the behavior exposed by this class to external world, using which objects or other classes can interact with this class. A class can have zero or more methods.

What is object, in Java?

An object is an instance of a class. And the process of creating an object, from a class, is called instantiation.

Difference between class and object

To compare, class and object with real world scenarios, a class is just like a bottle moulder, which moulds bottles into a shape. And an object is just like a bottle, which got moulded from moulder.

Just like a moulder can mould any number of bottles, a class can generally have any number of objects, except in special cases, like singleton

What is Constructor, in Java?

A Constructor is a special method, of a class, used to initialize an object.

Below is an example of a class, creating object of a class, and invoking methods of class.

class Test1
{
	int i,j; //data members or member variables

	Test1()//constructor
	{
	i = 20;
	j = 11;

	System.out.println("Test1() Constructor");
	}

	void add() //member methods
	{
	int k; //local variable i..e not a member variable of Test1 class
	//NOTE: k cannot be accessed from object of Test1 class
	k = i+j;
	System.out.println("Add Result is:"+k);
	}

	void sub()
	{
	int l = i-j;
	System.out.println("Sub Result is:"+l);
	}
}

public class ClassDemo {
//execution starts from here
public static void main(String args[])
{
	Test1 obj; //declaring object reference
	obj=new Test1(); //creating object of Test1 class
	obj.add(); //invoking add() method of Test1 class, using object obj

	obj.sub();
}
}

You may also like to read:
invoke constructor from another constructor
what is abstract keyword

Difference between List and Set

Difference between List and Set
List and Set are interfaces and in java.util package.
Base interface for List and Set is java.util.Collection interface.

List can store duplicate object, but Set does not store duplicate objects.

Iterator and ListIterator can be used to traverse thru the elements of List. But only Iterator can be used to
traverse thru the elements of Set.

List stores elements in the same order as they are added. But Set stores the elements in different order, than they are added.

Difference between ListIterator and Iterator

List has two different implementations, ArrayList and LinkedList. ArrayList internal implementation is based on arrays, and LinkedList internal implementation is based on linked list data structure.

Set has two different implementations, HashSet and TreeSet. HashSet internal implementation is based on hashing the elements, TreeSet is based on Red Back Tree data structure.

ArrayList example:


import java.util.*;
public class ArrayListDemo {

	public static void main(String[] args) {

	//List allows duplicate values, stores values in the order given/added
	//Dynamic Arrays, can shrink or increase size dynamically unlike normal arrays
	ArrayList al = new ArrayList();
	al.add("BCD");
	al.add(0, "A1");
	al.add("A2");
	al.add(2, "A3");
	al.add(3, "A4");

	al.add(0, "C1");

	System.out.println("ArrayList is:"+al);

	Iterator itr = al.iterator();
	//using Iterator, we can traverse only in forward direction
	for(;itr.hasNext();)
	{
	String str = (String)itr.next(); //returns Object
	System.out.println(str+" ");
	}

	ListIterator litr = al.listIterator();

	for(;litr.hasNext();)
	{
	String str = (String)litr.next(); //returns Objectr

	//using ListIterator we can traverse backward as well
	//String pstr = (String) litr.previous();

	System.out.println("Next is "+str);
	}

	System.out.println("-------------------------");

	al.remove(2);
	//Getting Array
	Object obj[] = al.toArray();

	for(int i=0;i

output:
ArrayList is:[C1, A1, BCD, A3, A4, A2]
C1
A1
BCD
A3
A4
A2
Next is C1
Next is A1
Next is BCD
Next is A3
Next is A4
Next is A2
-------------------------
C1
A1
A3
A4
A2

HashSet example:


import java.util.*;

public class SetDemo {

public static void main(String args[])
{
//stores unique values only, no guarantee in the order of objects stored
HashSet hs = new HashSet();

hs.add("to");
hs.add("test");
hs.add("random1");
hs.add("string");
hs.add("some");
hs.add("random1");

System.out.println(" :"+hs);

Iterator itr = hs.iterator();

while(itr.hasNext())
{
System.out.println(itr.next());
}

//ListIterator not available for Set

Enumeration enm=Collections.enumeration(hs);

for(;enm.hasMoreElements();)
{
	System.out.println(enm.nextElement());
}

}

}

output:
:[to, test, string, random1, some]
to
test
string
random1
some
to
test
string
random1
some

You may also like to read:
Can a Collection be concurrent
HashSet using Generic class
How many loops are there in Java

operators in Java

Below are Operators supported, in Java

Arithmetic operators

+(addition), -(subtraction), *(multiplication), /(dividedby), %(Modulo – reminder of division)
++(increment) x++; means x = x+1;
–(decrement)

Difference between Pre increment and Post increment

Post increment
x++;
For eg, consider System.out.println(x++);
In above statement, first x is printed, and after that x is incremented

Pre increment
++x;
For eg, consider System.out.println(++x);
In above statement, first x is incremented, and after that x is printed

Similarly, pre and post increment can be used in other arithmetic expressions.

Difference between Pre decrement and Post decrement

Pre decrement and post decrement operator as well, can be used in arithmetic expressions.

Relational Operators or Comparison Operators

Relational or Comparison operators are used to perform comparison check between two variables or constants
x<3 (less than) > (greater than)
<= (less than or equal to) >= (greater than or equal to)
==( checking equal to),
!=(not equal to)

Generally Relational or Comparison expression evaluates to true or false.
Relational or Comparison operators are used with if, loops

Logical Operators

Logical operators are used two combine two or more Relational or Comparison expressions.
&&(Logical and): evaluates to true only if both operands are true
Eg.(y==3)&&(z>20)

||(Logical or): evaluates to true, when either of the operand is true

!(Logical not): Negates logical expression, converts true to false, and vice versa

logical or and not takes two operands, where as logical not takes one operand

Assignment Operators

=, +=(short hand assignment)
-=, *=, /=, %=
x op= y means x=x op y;
For eg. x+=y means x=x+y;
X*=y; means x =x*y;

Conditional Operator or Ternary Operator

?:

Conditional operator takes three arguments
usage:
relational_expression? expression_1 : expression_2;

If relational expression gets evaluated to true, expression_1 is returned, else expression_2 is returned.

Eg. b = (a == 15) ? 21 : 52;
As shown in above example, if value of a is 15, 21 is assigned to b, else 52 is assigned to b

Bitwise Operator

Bitwise operators perform operations on each binary representation
& – bitwise AND
| – bitwise OR
^ – bitwise XOR
<< - bit wise left shift >> – bit wise right shift

16 & 8
0010000(binary representation of 16)
0001000(binary representation of 8)
Result: 00000000

instanceof operator

instanceof example

We cannot overload operators in Java.How ever few operators like + has builtin overloading.

You may also like to read:
Basic data types in Java

Purpose of assert keyword in Java

In Java programs assert keyword evaluates an expression, and if expression gets evaluated to false, AssertionError is thrown by JVM.

Also note that AssertionError is UnChecked Exception. So, it is not compulsory to handle AssertionError with try catch or throws.

Below is an example of using assert keyword. In this example AssertionError gets thrown is val1+val2 is >= 50.

public class AssertDemo{
public static void main(String[] a){
int val1, val2;
val1 = 34;
val2 = 30;
assert (val1+val2)<50 : "Error: Value is greater than 50"; System.out.println("Everything looks OK"); } } Output: Exception in thread "main" java.lang.AssertionError: Error: Value is greater than 50 at AssertDemo.main(AssertDemo.java:6) Also note that, by default Assertions are disabled. Please follow below steps to enable Assertions on Eclipse IDE Windows -> Preferences -> highlight the default JRE -> click Edit-> In the Default VM arguments input box, enter -ea -> click the finish button.

If you are running from command line, you can use java -ea AssertDemo

static method in Abstract class

Can a static method be a member of Abstract Class?

Read here for What is a abstract method? and what is abstract class?

static method is associated with class and not with individual objects of the class.

Yes, an abstract class can have static methods. But a static method cannot be abstract.

Also remember that, static methods take part in inheritance.
But static methods do not take part in polymorphism.

Below example shows that an abstract class, can have static method.


abstract class Abs1{
	int i,j;
	Abs1(){
		super();
		System.out.println("Abs1() Constructor");
	}

	Abs1(int i, int j)
	{
		this();
		this.i = i;
		this.j = j;
		System.out.println("Abs1(int i, int j) Constructor");
	}

	public static void met1()
	{
		System.out.println("met1() method in Abs1 class");
	}
}

public class AbstractDemo extends Abs1{

	AbstractDemo(){
		System.out.println("AbstractDemo() Constructor");
	}
	public static void main(String args[])
	{
		AbstractDemo obj = new AbstractDemo();
		System.out.println("in main() method");

		Abs1.met1();
	}
}

You may also like to read:
Difference between static and non static block
how many keywords or reserved words in java
purpose of static inner class