LinkedList in Java

LinkedList in Java -A LinkedList is a data structure in Java that consists of a sequence of elements, where each element is linked to its predecessor and successor. It’s part of the Java Collections Framework and implements the List and Deque interfaces, which means it can be used both as a list and a double-ended queue (deque).

Characteristics of LinkedList in Java

• Node Structure: Each element in a LinkedList is contained in a node. A node has two parts: the data and references (links) to the next and previous nodes.
• Dynamic Size: The size of a LinkedList can grow and shrink dynamically as elements are added or removed.
• Insertion and Deletion: These operations are efficient because you only need to update the links in the nodes. There’s no need to shift elements, as is the case with arrays.
• Traversal: Traversing a LinkedList is slower compared to an ArrayList because it requires moving from one node to the next sequentially.

Example of LinkedList in Java

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        
        // Adding elements
        list.add("Element1");
        list.add("Element2");
        list.add("Element3");
        
        // Inserting element at specific position
        list.add(1, "Element4");
        
        // Removing elements
        list.remove("Element2");
        list.remove(2);
        
        // Iterating over elements
        for(String element : list) {
            System.out.println(element);
        }
    }
}

Difference between LinkedList and ArrayList

Both LinkedList and ArrayList implement the List interface, but they have different underlying data structures and characteristics:

• Underlying Data Structure:
  • LinkedList: Uses a doubly-linked list data structure.
  • ArrayList: Uses a dynamic array data structure.
• Performance:
  • Insertion/Deletion: LinkedList is more efficient for insertion and deletion operations, especially when adding/removing elements at the beginning or middle of the list. This is because it only requires updating the links in the nodes.
  • Access/Traversal: ArrayList is more efficient for accessing and iterating over elements because it provides constant-time random access to elements using an index.
• Memory Usage:
  • LinkedList: Consumes more memory due to the storage of additional references (next and previous links) in each node.
  • ArrayList: Consumes less memory compared to LinkedList because it only stores the elements and doesn’t need extra space for node links.
• Internal Implementation:
  • LinkedList: Elements are stored as nodes in a doubly-linked list.
  • ArrayList: Elements are stored in a dynamically resizing array.
• Use Cases:
  • LinkedList: Suitable for applications where frequent insertion and deletion of elements are required.
  • ArrayList: Suitable for applications where frequent access and traversal of elements are required.

Example of ArrayList in Java

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        
        // Adding elements
        list.add("Element1");
        list.add("Element2");
        list.add("Element3");
        
        // Inserting element at specific position
        list.add(1, "Element4");
        
        // Removing elements
        list.remove("Element2");
        list.remove(2);
        
        // Iterating over elements
        for(String element : list) {
            System.out.println(element);
        }
    }
}

In summary, the choice between LinkedList and ArrayList depends on the specific requirements of the application, particularly regarding the frequency of insertion, deletion, and access operations.