Java Collections Lists (ArrayList LinkedList TreeList) and difference:

The list Interface extends Collection and it stores a sequence of elements as in list , all these elements can be easily accessed with their serial numbers or sequences and any element can be inserted to the list. But we have the situations when we get UnsupportedOperationException if the collection can’t be modified. List interface is implemented by three concrete classes

1) Array List

2) Linked List

3) Tree List

1. ArrayList

This class extends AbstractList and implements the List interface.This class can be said to be the improved version of the arrays as in arrays we have the limitation of the fixed size which has to be known and defined well in advance and the n nothing much can be done with respect to the increase and decrease in the size of the array , so we have got the extended class from collections framework whch gives us the flexibility of having the variable array structure which can be dynamically increased or reduced as per the programmers need. An ArrayList is a variable-length array of object references.

ArrayList has three constructors shown here:

a) Array list ():
This constructor builds an empty array list.

b) ArrayList(Collection c):
This constructor builds an array list that is initialized with the elements of the collection c.

c) ArrayList (int capacity):
This constructor builds an array list that has the specified initial capacity. The capacity grows automatically as elements are added to an array list.

import java.util.ArrayList;
import java.util.List;

public class CreateArrayList {

public static void main(String args[]) {
List list = new ArrayList();
list.add("1");
list.add("2");
list.add("3");
}
}The above code will create an ArrayList object and store three String objects in the ArrayList object.

import java.util.ArrayList;
import java.util.List;


public class DisplayArrayList {

public static void main(String args[]) {
List list = new ArrayList();
list.add("1");
list.add("2");
list.add("3");

for(int i = 0; i < 3; i++) {
System.out.println(list.get(i));
}
}
}Output of the above code

1
2
3
Below code is an example where the arraylist contains many Employee objects. Try this code a see how it works.

import java.util.ArrayList;
import java.util.List;

public class Employees {

public static void main(String args[]) {
List employeesList = new ArrayList();
employeesList.add(new Employee("Sam", 100000));
employeesList.add(new Employee("Rohan", 200000));
employeesList.add(new Employee("John", 300000));
employeesList.add(new Employee("Willey", 400000));

int size = employeesList.size();
for (int i = 0; i < size; i++) {
Employee employee = (Employee) employeesList.get(i);
System.out.println(employee.toString());
}
}
}

class Employee {

private String name;

private long sal;

public Employee(String name, long sal) {
this.name = name;
this.sal = sal;
}

public String getName() {
return name;
}

public long getSal() {
return sal;
}

public String toString() {

return "Name : " + getName() + "\n" + "Salary of " + getName() + ": "
+ getSal();
}
}


2. LinkedList :

LinkedList Class: This Class extends AbsractSequentialList and implements the List Interface. It as it defines automatically by it’s term provides a Linked-list structure.
It has two constructors which are mentioned below:

LinkedList ( ) LinkedList(Collection c)

LinkedList ( ): This constructor builds an empty Linked List. LinkedList(Collection c): This builds a linked list which is initialized with elements of collection .

Try the below code

import java.util.LinkedList;
import java.util.List;


public class LinkedListExample {

public static void main(String args[]) {

List linkedList = new LinkedList();
linkedList.add("1");
linkedList.add("2");
linkedList.add("3");
}
}
3. TreeList :

public class TreeList extends AbstractList (Code)
A List implementation that is optimised for fast insertions and removals at any index in the list.
This list implementation utilises a tree structure internally to ensure that all insertions and removals are O(log n). This provides much faster performance than both an ArrayList and a LinkedList where elements are inserted and removed repeatedly from anywhere in the list.

The following relative performance statistics are indicative of this class:

get add insert iterate remove
TreeList 3 5 1 2 1
ArrayList 1 1 40 1 40
LinkedList 5800 1 350 2 325

ArrayList is a good general purpose list implementation. It is faster than TreeList for most operations except inserting and removing in the middle of the list. ArrayList also uses less memory as TreeList uses one object per entry.
LinkedList is rarely a good choice of implementation. TreeList is almost always a good replacement for it, although it does use sligtly more memory.

Difference between LinkedList ArrayList TreeList:
There are some differences between an java.util.ArrayList and java.util.LinkedList. These differences are not so important for any small applications that processes small amount of data. Then they can very important for any small application that processes huge amount of data. These do affect the performance of a application if not analyzed properly.

An empty LinkedList takes 2-3 times less memory than an empty ArrayList. This becomes important if you plan to keep an adjacency list of nodes for each node in the graph (graph can be like a TreeSet. Tree is a type of graph) and you know beforehand that the nodes will have at most one or two adjacent nodes and the total number of nodes in the graph can be quite large.


Although both ArrayList and LinkedList allow insertion/deletion in the middle through similar operations (ie; by invoking add(int index) or remove(index)), these operations do not offer you the advantage of O(1) insertion/deletion for a LinkedList. For that, you must work through a ListIterator.


The important thing to remember when comparing LinkedList and ArrayList is that linked lists are more faster when inserting and removing at random locations in the list multiple times. If you want to add to the end of the list then an ArrayList would be the best choose.

I will try to supply an answer for the LinkedList vs ArrayList issue. The first thing to do is to look at what interfaces these two implement. This might hint us at their purpose, as Sun usually bound purposes into interfaces.

// lang java
public class ArrayList
extends AbstractList
implements List, RandomAccess, Cloneable, Serializable

public class LinkedList
extends AbstractSequentialList
implements List, Queue, Cloneable, Serializable
We can ignore Cloneable and Serializable as all of the JCF implement those. It’s also quite obvious that both of them implement the List interface, as they need to provide list functionability (backwards iteration, sub listing, etc).
Now for the differences: ArrayList is implementing RandomAccess while LinkedList implementing Queue. You could already tell something about the usage of the two classes.
ArrayList:
Now for some implementation notes. The ArrayList is actually encapsulating an actualy Array, an Object[]. When you instanciate ArrayList, an array is created, and when you add values into it, the array changes its size accordingly. This gives you strengths and weaknesses:
• Fast Random Access
You can perform random access without fearing for performence. Calling get(int) will just access the underlying array.
• Adding values might be slow When you don’t know the amount of values the array will contain when you create it, a lot of shifting is going to be done in the memory space when the ArrayList manipulates its internal array.
• Slow manipulation When you’ll want to add a value randomly inside the array, between two already existing values, the array will have to start moving all the values one spot to the right in order to let that happen.
LinkedList
The LinkedList is implemented using nodes linked to each other. Each node contains a previous node link, next node link, and value, which contains the actual data. When new data is inserted, a node is inserted and the links of the surrounding nodes are updated accordingly. When one is removed, the same happens - The surrounding nodes are changing their links and the deleted node is garbage collected. This, as well, gives strengths and weaknesses:
• Fast manipulation As you’d expect, adding and removing new data anywhere in the list is instantanious. Change two links, and you have a new value anywhere you want it.
• No random access Even though the get(int) is still there, it now just iterates the list until it reaches the index you specified. It has some optimizations in order to do that, but that’s basically it.
Conclusion:
ArrayList is very useful when a well defined set of data is needed in a List interface as opposed to an array. It can be dynamically changed, but try not to do so frequently throughout the life of the application. LinkedList is there for you to do just that: Manipulating it is very easy, and as long as its used for iteration purposes only and not for random accessing, it’s the best solution. Further, if you need random accessing from time to time, I suggest toArray for that specific moment.
Another point I didn’t raise here is the Queue issue. LinkedList implements extended abilities to the normal List interface which allows it to add and remove elements from its beginning and end. This makes the LinkedList perfect for Queue and Stack purposes - Although in Java 5 they already added a Stack class.