ArrayList, LinkedList, Vector & Stack in Java

ArrayList, LinkedList, Vector & Stack in Java | The ArrayList, LinkedList, Vector, and Stack implement the List interface, and indirectly implement the Collection interface. This post will show examples of the List interface implementation classes with constructors, and sample programs.

List(I) 1.2v
- ArrayList 1.2v
- LinkedList 1.2v
- Vector 1.0v
  - Stack 1.0v

ArrayList Class in Java

It is non-synchronized & non-thread-safe.
The underlying data structure is a resizable array or growable array.
Duplicate objects are allowed.
Insertion order is preserved.
Heterogeneous objects are allowed.
Null insertion is possible. We can insert it any number of times.
Default capacity = 10
ArrayList implements the Serializable, Cloneable, and RandomAccess interfaces.

It has dynamic resizing – 50% of the original size. Whenever the ArrayList is full and we try to add more elements then it resizes to 50% of the original size.

Constructors of ArrayList Class in Java

ArrayList list = new ArrayList(); It creates an empty ArrayList object with a default initial capacity of 10. Once ArrayList reaches its max capacity then a new ArrayList object will be created with 50% of the original size.
ArrayList list = new ArrayList(int initialCapacity); It creates an empty ArrayList object with the specified initial capacity.
ArrayList list = new ArrayList(Collection c); It creates an equivalent ArrayList object for the given Collection. It is used to convert one Collection object type to an ArrayList type.

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

public class Test {
   public static void main(String[] args) {
      List<Object> list = new ArrayList<>();
      list.add("A");
      list.add(10); 
      list.add("A");
      list.add(null);
      System.out.println(list); // [A, 10, A, null]

      list.remove(2);
      System.out.println(list); // [A, 10, null]
      
      list.add(2, "M");
      list.add("N");
      System.out.println(list); // [A, 10, M, null, N]
   }
}

When we should go for ArrayList & when ArrayList is the worst choice? ArrayList is the best choice if our frequent operation is a retrieval operation because ArrayList implements the RandomAccess interface. ArrayList is the worst choice if our frequent operation is insertion/deletion in the middle. In that case, we should go for LinkedList.

Array vs ArrayList in Java

Array	ArrayList
The array is static in size.	The array is static in size.
The array is a fixed-length data structure.	ArrayList is a variable length Collection class.
An array can store both objects and primitives-type.	We cannot store primitive type in ArrayList. It automatically converts primitive type to wrapper class object.
It performs fast in comparison to ArrayList because of its fixed size.	1. resize() operation: Automatic resize will slow down the performance as it will use the temporary array to copy elements from the old array to the new array. 2. add() or get() operation: almost same performance, as for ArrayList object these operations run in constant time.
It is mandatory to provide the size of an array while initializing it directly or indirectly.	We can create an instance of ArrayList without specifying its size. Java creates an ArrayList of the default size of 10.
We use for loop or for each loop to iterate over an array.	We can use an iterator also to iterate over ArrayList.
Array provides a length variable that denotes the length of an array.	ArrayList provides the size() method to determine the size of ArrayList.
The array can be multi-dimensional.	ArrayList is always single-dimensional.
The elements are contained in adjacent memory locations.	The objects are incapable of being contained in contiguous locations.
The assignment operator is used for the storage of elements.	The add() method is utilized for the insertion of elements in an ArrayList.
Generics are not compatible with Arrays.	ArrayLists allow the use of Generics.

LinkedList Class in Java

The underlying data structure is a doubly linked list.
Insertion order is preserved.
Duplicate objects are allowed.
Heterogeneous objects are allowed.
Null insertion is possible. We can insert a null value any number of times.
LinkedList is the best choice if our frequent operation is insertion/deletion in the middle.
LinkedList is the worst choice if our frequent operation is a retrieval operation because LinkedList doesn’t implement the RandomAccess interface. In that case, we should go for ArrayList.
LinkedList implements the Serializable & Cloneable interface but not the RandomAccess interface.

Constructors of LinkedList Class in Java

Capacity is not applicable for LinkedList therefore it doesn’t contain such construction.

LinkedList list = new LinkedList(); It creates an empty LinkedList object.
LinkedList list = new LinkedList(Collection c); It creates an equivalent LinkedList object for the given Collection.

LinkedList Class-specific methods:-

Usually, we use LinkedList to develop Stack & Queue. To provide support for this requirement LinkedList class defines the following specific methods:-

void addFirst(Object o)
void addLast(Object o)
Object getFirst()
Object getLast()
Object removeFirst()
Object removeLast()

import java.util.LinkedList;

public class Test {
    public static void main(String[] args) {
        LinkedList<Object> list = new LinkedList<>();
        list.add("Know"); // String
        list.add(30); // number
        list.add(null); // null value
        list.add("Know"); // duplicate value
        System.out.println(list); // [Know, 30, null, Know]

        list.set(0, "Program"); // [Program, 30, null, Know]
        System.out.println(list);

        list.add(0, "Hello");
        list.removeLast();
        list.addFirst("Java");
        System.out.println(list); // [Java, Hello, Program, 30, null]
    }
}

LinkedList vs ArrayList in Java

ArrayList	LinkedList
The underlying data structure is a growable array. ArrayList internally uses a dynamic array to store its elements.	The underlying data structure is a doubly linked list.
In ArrayList, the elements will be stored in consecutive memory locations & hence retrieval operation becomes easy.	In LinkedList, the elements will not be stored in consecutive memory locations, and hence retrieval operation becomes complex.
ArrayList implements the RandomAccess interface.	LinkedList doesn’t implement the RandomAccess interface.
ArrayList implements List.	LinkedList implements List as well as Queue. It can act as a queue as well.
Manipulation with ArrayList is slow because it internally uses an array. If any element is removed from the array, all the other elements are shifted in memory.	Manipulation with LinkedList is faster than ArrayList because it uses a doubly linked list, so no bit shifting is required in memory.
ArrayList is faster in storing and accessing data as internally Array is used which is random access.	LinkedList is slower than ArrayList in storing and accessing data as access requires node-by-node traversal.
There is no descendingIterator() method in ArrayList.	LinkedList can be iterated in the reverse direction using the descendingIterator() method.
If the constructor is not overloaded, then ArrayList creates an empty list of initial capacity 10.	There is no case of default capacity in a LinkedList. Hence an empty list is created when a LinkedList is initialized.
In ArrayList Memory overhead is less as each index only holds the actual object(data).	Memory overhead in LinkedList is more as compared to ArrayList as a node in LinkedList needs to maintain the addresses of the next and previous nodes.
ArrayList is the best choice if our frequent operation is a retrieval operation.	LinkedList is the best choice if our frequent operation is insertion/deletion in the middle.
ArrayList is the worst choice if our frequent operation is insertion or deletion in the middle because internally several shift operations are performed.	LinkedList is the worst choice if our frequent operation is a retrieval operation.

If our application has many retrievals/access compared to manipulation operations (insert/delete/update) in that case ArrayList is better else use LinkedList.

Conclusion: LinkedList element deletion and addition is faster compared to ArrayList.
Reason: LinkedList’s every element maintains two pointers (addresses) which point to both neighbor elements in the list. Hence removal only requires a change in the pointer location in the two neighbor nodes (elements) of the node that is going to be removed. In ArrayList, all the elements need to be shifted to fill out the space created by the removed element.

Hence if there is a requirement for frequent addition and deletion in the application then LinkedList is the best choice and if more search operations requirements, ArrayList would be your best bet.

Vector Class in Java

Every method present in the Vector class is synchronized and hence Vector is threadsafe.
The underlying data structure is a resizable array or growable array.
Duplicate objects are allowed.
Insertion order is preserved.
Heterogeneous objects are allowed.
Null insertion is possible, there is no restriction on the number of nulls.
Default capacity = 10
Like ArrayList, Vector also implements the Serializable, Cloneable, and RandomAccess interfaces.

It has dynamic resizing – 100% of the original size. Whenever the Vector is full and we try to add more elements then it resizes to 100% of the original size.

Constructors of Vector Class in Java

Vector vector = new Vector(); It creates an empty vector object with a default initial capacity of 10, once the vector reaches its maximum capacity then a new vector object will be created with 100% of the original size.
Vector vector = new Vector(int initialCapacity); It creates an empty vector object with a specified initial capacity.
Vector vector = new Vector(int initialCapacity, int incrementalCapacity); It creates an empty vector object with a specified initial capacity. Once the vector reaches its max capacity, it will increase “incremental capacity”.
Vector vector = new Vector(Collection c); It creates an equivalent vector object for the given collection. This constructor is meant for interconversion between collection objects.

Vector Specific Methods

To add objects:-

add(Object o) => from Collection(I)
add(int index, Object o) => from List(I)
addElement(Object o) => from Vector

To remove objects:-

remove(Object o) => from Collection(I)
remove(int index) => from List(I)
removeElement(Object o) => from Vector
removeElementAt(int index) => from Vector
clear() => from Collection
removeAllElements() => from Vector

To get Objects:-

Object get(int index) => from List(I)
Object elementAt(int index) => from Vector
Object firstElement() => from Vector
Object lastElement() => from Vector

Other Methods:-

int size()
int capacity()
Enumeration elements()

import java.util.Vector;

public class Test {
    public static void main(String[] args) {
        Vector<Object> vector = new Vector<>();
        System.out.println(vector.capacity()); // 10
        
        for (int i = 1; i <= 10; i++) {
            vector.addElement(i);
        }
        System.out.println(vector.capacity()); // 10
        
        vector.addElement("A");
        System.out.println(vector.capacity()); // 20
        
        System.out.println(vector); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, A]
    }
}

Stack Class in Java

The stack class represents a last in first out (LIFO) stack of objects. It extends the Vector class with five operations that allow a vector to be treated as a stack. The usual push and pop operations are provided, as well as a method to peek at the top item on the stack. When a stack is first created, it contains no items.

It is the child class of Vector.
It is specially designed for LIFO (Last in first out) order.

Constructor:- Stack stack = new Stack();

Stack Class specific methods:-

Object push(Object o):- To insert an object into the stack.
Object pop():- To remove & return the top of the stack.
Object peek():- To return the top of the stack without removal.
boolean empty():- Returns true if the stack is empty.
int search(Object o):- Returns offset if the element is available otherwise returns -1.

public synchronized int search(Object o):- It returns the 1-based position where an object is on this stack. If an object occurs as an item in this stack, this method returns the distance from the top of the stack. The topmost item on the stack is considered to be at distance 1. The equals method is used to compare o to the items in this stack. If they are not there in the stack it returns -1.

import java.util.Stack;

public class Test {
    public static void main(String[] args) {
        Stack<String> st = new Stack<String>();
        st.push("A");
        st.push("B");
        st.push("C");
        System.out.println(st); // [A, B, C]
        
        System.out.println(st.search("A")); // 3
        System.out.println(st.search("Z")); // -1

    }
}

offset		index
1	C	2
2	B	1
3	A	0

ArrayList vs Vector in Java

ArrayList	Vector
Every method present in the ArrayList is non-synchronized. Programmers prefer ArrayList over Vector because ArrayList can be synchronized explicitly using the Collections.synchronizedList() method.	Every method present in the Vector is synchronized.
At a time multiple threads are allowed to operate on the ArrayList object & hence it is not thread-safe.	At a time only one thread is allowed to operate on the Vector object & hence it is thread-safe.
ArrayList is fast because it is non-synchronized.	Vector is slow because it is synchronized.
Relatively performance is high because threads are not required to wait to operate on ArrayList object.	Relative performance is low because threads are required to wait to operate on the Vector object.
ArrayList is not a legacy class. It is introduced in JDK 1.2	Vector is a legacy class because it was introduced in the 1.0 version.
ArrayList increments 50% of the current array size.	Vector increments of 100% (doubles) of the current array size.
ArrayList uses the Iterator interface to traverse the elements.	A vector uses the Iterator interface or Enumeration interface to traverse the elements.

synchronizedList() in Java

How to get the Synchronized version of the ArrayList object? By default ArrayList is non-synchronized but we can get the synchronized version of the ArrayList object by using the synchronizedList() method of the Collections class. Method signature:- public static List synchronizedList(List l)

List<String> arrayList = new ArrayList<>();
List<String> synchronizedArrayList = Collections.synchronizedList(arrayList);

How to get the synchronized version of the Set object? Using Collections.synchronizedSet(). Method Signature:- public static List synchronizedSet(Set s)
How to get the synchronized version of the Map object? Using Collections.synchronizedMap(). Method Signature:- public static List synchronizedMap(Map m)

RandomAccess Interface

RandomAcess interface present in java.util package & it doesn’t contain any methods. It is a marker interface where the required ability will be provided by the JVM. ArrayList & Vector classes implement the RandomAccess interface for any random element we can access with the same speed.

Usually, we use Collections to hold & transfer objects from one location to another location (container). To provide support for this requirement every collection class by default implements Serializable and Cloneable interfaces.

import java.io.Serializable;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.RandomAccess;

public class Test {
    public static void main(String[] args) {
        List<String> arrayList = new ArrayList<>();
        List<String> linkedList = new LinkedList<>();

        System.out.println(arrayList instanceof Serializable); // true
        System.out.println(linkedList instanceof Cloneable); // true

        System.out.println(arrayList instanceof RandomAccess); // true
        System.out.println(linkedList instanceof RandomAccess); // false
    }
}

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!