Key differences between ArrayList and LinkedList in Java

ArrayList in Java

ArrayList in Java is a resizable array implementation of the List interface, part of the Java Collections Framework. Unlike standard arrays, which have a fixed size, ArrayList can dynamically resize as you add or remove elements, which provides great flexibility when dealing with collections of items. It allows random access to its elements with constant time performance for retrieval, making it an efficient choice for accessing elements frequently. However, adding or removing elements (especially at the beginning or middle) can be slower compared to other list types due to the need for shifting elements. ArrayList manages its capacity internally and increases its size when needed, but it is advisable to specify an initial capacity if the approximate number of elements is known.

Functions of ArrayList in Java:

• add(E e):

Adds an element to the end of the list.

• add(int index, E element):

Inserts the specified element at the specified position in the list.

• remove(Object o):

Removes the first occurrence of the specified element from the list, if it is present.

• remove(int index):

Removes the element at the specified position in the list.

• set(int index, E element):

Replaces the element at the specified position in the list with the specified element.

• get(int index):

Returns the element at the specified position in the list.

• clear():

Removes all of the elements from the list.

• size():

Returns the number of elements in the list.

• isEmpty():

Returns true if the list contains no elements.

• contains(Object o):

Returns true if the list contains the specified element.

• indexOf(Object o):

Returns the index of the first occurrence of the specified element in the list, or -1 if this list does not contain the element.

• lastIndexOf(Object o):

Returns the index of the last occurrence of the specified element in this list, or -1 if the list does not contain the element.

• toArray():

Returns an array containing all of the elements in the list in proper sequence (from first to last element).

• iterator():

Returns an iterator over the elements in this list in proper sequence.

• listIterator():

Returns a list iterator over the elements in this list (in proper sequence).

Example of ArrayList in Java:

This example demonstrates how to create an ArrayList, add elements to it, access elements, and iterate over the list.

import java.util.ArrayList;

public class Example {

    public static void main(String[] args) {

        // Creating an ArrayList of String type

        ArrayList<String> fruits = new ArrayList<>();

        // Adding elements to the ArrayList

        fruits.add(“Apple”);

        fruits.add(“Banana”);

        fruits.add(“Cherry”);

        fruits.add(“Date”);

        // Accessing elements from the ArrayList

        System.out.println(“First fruit: ” + fruits.get(0)); // Outputs: Apple

        System.out.println(“Second fruit: ” + fruits.get(1)); // Outputs: Banana

        // Removing elements from the ArrayList

        fruits.remove(“Date”); // Removes “Date”

        fruits.remove(2); // Removes the element at index 2 (“Cherry”)

        // Iterating over ArrayList elements using enhanced for-loop

        System.out.println(“Remaining fruits:”);

        for (String fruit : fruits) {

            System.out.println(fruit);

        }

        // Checking the size of the ArrayList

        System.out.println(“Total fruits in list: ” + fruits.size()); // Outputs: 2

        // Checking if the ArrayList is empty

        System.out.println(“Is the fruit list empty? ” + fruits.isEmpty()); // Outputs: false

    }

}

In this example, we use an ArrayList to store names of fruits. We add elements to the list, access elements by their indices, remove elements, and use a loop to iterate through the list. We also check the size of the list and whether it is empty or not. This demonstrates some common operations that you might need to perform with an ArrayList.

LinkedList in Java

LinkedList in Java is an implementation of the List interface and part of the Java Collections Framework, but it also implements the Deque interface, providing both list and double-ended queue functionalities. Unlike ArrayList, LinkedList consists of doubly linked nodes, each containing data and references to both the previous and next nodes. This structure allows for efficient insertions and deletions at any point in the list, as these operations do not require element shifting, only pointer adjustments. However, accessing elements in a LinkedList is slower because it requires sequential traversal from the beginning or end to reach the desired element. LinkedList is ideal for scenarios where frequent addition and removal of elements are required, rather than rapid random access.

Functions of LinkedList in Java:

• add(E e):

Adds an element to the end of the list.

• add(int index, E element):

Inserts the element at the specified position in the list.

• addFirst(E e):

Inserts the specified element at the beginning of the list.

• addLast(E e):

Appends the specified element to the end of the list.

• remove(Object o):

Removes the first occurrence of the specified element from this list, if it is present.

• remove(int index):

Removes the element at the specified position in the list.

• removeFirst():

Removes and returns the first element from this list.

• removeLast():

Removes and returns the last element from this list.

• getFirst():

Returns the first element in this list.

• getLast():

Returns the last element in this list.

• get(int index):

Returns the element at the specified position in the list.

• set(int index, E element):

Replaces the element at the specified position in this list with the specified element.

• indexOf(Object o):

Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.

• lastIndexOf(Object o):

Returns the index of the last occurrence of the specified element in this list, or -1 if the list does not contain the element.

• clear():

Clears the list so that it contains no elements.

• size():

Returns the number of elements in this list.

• isEmpty():

Returns true if this list contains no elements.

• contains(Object o):

Returns true if this list contains the specified element.

• toArray():

Returns an array containing all of the elements in this list in proper sequence (from first to last element).

• iterator():

Returns an iterator over the elements in this list in proper sequence.

• listIterator():

Returns a list iterator over the elements in this list (in proper sequence).

Example of LinkedList in Java:

This example demonstrates how to create a LinkedList, add elements to it, access elements, and iterate over the list, along with specific methods provided by the LinkedList class for manipulating both ends of the list.

import java.util.LinkedList;

public class Example {

    public static void main(String[] args) {

        // Creating a LinkedList of String type

        LinkedList<String> animals = new LinkedList<>();

        // Adding elements to the LinkedList

        animals.add(“Dog”);

        animals.add(“Cat”);

        animals.addLast(“Horse”); // Adds to the end of the list

        animals.addFirst(“Snake”); // Adds to the beginning of the list

        animals.add(2, “Rabbit”); // Adds Rabbit at the third position (index starts at 0)

        // Accessing elements from the LinkedList

        System.out.println(“First animal: ” + animals.getFirst()); // Outputs: Snake

        System.out.println(“Last animal: ” + animals.getLast()); // Outputs: Horse

        System.out.println(“Animal at index 2: ” + animals.get(2)); // Outputs: Rabbit

        // Removing elements from the LinkedList

        animals.removeFirst(); // Removes Snake

        animals.removeLast(); // Removes Horse

        animals.remove(“Rabbit”); // Removes Rabbit by object

        // Iterating over LinkedList elements using enhanced for-loop

        System.out.println(“Remaining animals:”);

        for (String animal : animals) {

            System.out.println(animal);

        }

        // Checking the size of the LinkedList

        System.out.println(“Total animals in list: ” + animals.size()); // Outputs: 2

        // Checking if the LinkedList is empty

        System.out.println(“Is the animal list empty? ” + animals.isEmpty()); // Outputs: false

    }

}

In this example, methods like addFirst(), addLast(), getFirst(), getLast(), removeFirst(), and removeLast() are used to manipulate elements at the beginning and end of the LinkedList. This illustrates some of the unique capabilities of LinkedList compared to other List implementations like ArrayList. These capabilities make LinkedList suitable for applications such as queues and double-ended queues (deques).

Key differences between ArrayList and LinkedList in Java

Key Similarities between ArrayList and LinkedList in Java

• List Interface Implementation:

Both ArrayList and LinkedList implement the Java List interface. This means they both provide controlled access to list elements as well as methods for list manipulation, regardless of their internal data structure.

• Duplicate Elements:

Both classes allow duplicate elements in the list, enabling users to add the same object or value multiple times within the same list.

• Null Values:

Both ArrayList and LinkedList support the inclusion of null elements. They can store any number of null references, making them versatile for diverse data storage needs.

• Ordering:

Both types maintain the elements in insertion order. The order in which elements are inserted is the order in which they are iterated, which is crucial for operations requiring order-specific processing.

• Generics Support:

Both ArrayList and LinkedList support generic types, allowing them to store any type of objects, provided the objects conform to Java’s generics rules. This makes them highly flexible and type-safe.

• Sequential Access:

Both lists provide methods for sequential access and manipulation of elements, such as get(int index), set(int index, E element), add(int index, E element), and remove(int index), which can be used to modify the list during iteration.

• Synchronized Wrappers:

Both ArrayList and LinkedList can be synchronized using Collections.synchronizedList(List list) to make them thread-safe. However, the synchronization wrapper does not make them concurrently modifiable without additional synchronization.

• Iterators:

Both offer iterators (Iterator<E> and ListIterator<E>) that allow the traversal of the list in either direction (forward for Iterator, and both directions for ListIterator). These iterators also support remove(), next(), and hasNext() methods, with ListIterator additionally supporting add(E e) and previous().