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

Arrays in Java

An array is simple data structure to store same type of elements stored sequentially in memory.

One Dimensional Arrays
Declaration: Below is syntax to declare an one dimensional float array of size 10

float arr[] = new float[10];

Below is an example to reverse an one dimensional array

public class ReverseArray {
public static void main(String args[])
{
	int marks[] = {10,20,30,40,50,60};

	int tmp, n = marks.length;

	for(int i=0;i<n/2;i++)
	{
		tmp = marks[i];
		marks[i] = marks[n-i-1];
		marks[n-i-1] = tmp;
	}

	for(int i=0;i<n;i++)
	{
		System.out.print(marks[i]+" ");
	}
}
}
Output:
60 50 40 30 20 10

Below is an example showing how to store objects in an array

class A2{
	private String city;
	private float temperature;

	public A2(String mycity, float mytemperature)
	{
		city = mycity;
		temperature = mytemperature;
	}

	public String getCity()
	{
		return city;
	}

	public float getTemperature()
	{
		return temperature;
	}
}

public class ArrayDemo {

	public static void main(String[] args) {

	A2 arr[] = new A2[3];

	A2 oa = new A2("Bangalore",34.3f);
	arr[0] = oa;

	arr[1] = new A2("Chennai",36.3f);

	arr[2] = new A2("Mumbai",35.3f);

	for(int i=0;i<arr.length;i++)
	{
		System.out.println(arr[i].getCity()+" "+arr[i].getTemperature());
	}

	}

}

Two or Multi dimensional Arrays
Declaration: Below is syntax to declare two dimensional double array of 5 rows and 10 columns

double darr[][] = new double[5][10];

initialize two dimensional arrays
int abc[][] = {{1,2},{3,4},{5,6}};

abc.length gives number of rows
abc[0].length gives number of columns

You may also like to read:
How to store configuration settings in Java
What is Comparable in Java?
Example of Comparator
What is Generic class, and how it can be used with HashSet