LinkedList in Java

A LinkedList in Java is a collection class that implements the List interface and is part of the java.util package. It is a data structure consisting of nodes where each node contains a data element and a reference (or link) to the next node in the sequence. Linked lists are dynamic in size, which makes them a good choice for applications that require frequent insertions or deletions.

A LinkedList allows fast insertions and deletions at both ends, but slower access to elements by index compared to an ArrayList because the list needs to traverse the nodes sequentially.

Features of LinkedList:

1. Doubly Linked: In Java, LinkedList is a doubly linked list, meaning each node has a reference to both its next node and its previous node.

2. Dynamic Size: The size of the list can grow and shrink dynamically as elements are added or removed.

3. Insertion/Deletion Efficiency: Insertion and deletion operations (like add, remove, etc.) are generally more efficient compared to an ArrayList because they do not require shifting elements.

4. Slower Random Access: Unlike an ArrayList, accessing elements at a specific index in a LinkedList takes more time because it has to traverse the list.

Basic Syntax and Operations with LinkedList in Java

1. Importing LinkedList Class

import java.util.LinkedList;

2. Creating a LinkedList

You can create a LinkedList of any data type such as Integer, String, or even user-defined classes.

// Creating a LinkedList of StringsLinkedList<String> list = new LinkedList<>();

3. Adding Elements to LinkedList

There are several methods to add elements to a LinkedList:

• add(E e): Adds the element to the end of the list.

• addFirst(E e): Adds the element at the beginning of the list.

• addLast(E e): Adds the element at the end of the list (same as add).

list.add("Apple");         // Adds "Apple" at the endlist.addFirst("Banana");   // Adds "Banana" at the beginninglist.addLast("Cherry");    // Adds "Cherry" at the end

4. Accessing Elements from LinkedList

To access elements in a LinkedList, you can use:

• get(int index): Returns the element at the specified position.

• getFirst(): Returns the first element.

• getLast(): Returns the last element.

String firstElement = list.getFirst();  // Retrieves the first elementString lastElement = list.getLast();    // Retrieves the last elementString elementAtIndex = list.get(1);   // Retrieves element at index 1

5. Removing Elements from LinkedList

You can remove elements from a LinkedList using these methods:

• remove(): Removes and returns the first element of the list.

• removeFirst(): Removes the first element.

• removeLast(): Removes the last element.

• remove(int index): Removes the element at the specified index.

• remove(Object o): Removes the first occurrence of the specified object.

list.remove();           // Removes the first elementlist.removeFirst();      // Removes the first elementlist.removeLast();       // Removes the last elementlist.remove(1);          // Removes the element at index 1list.remove("Apple");    // Removes the first occurrence of "Apple"

6. Checking List Size

To get the number of elements in the list, you can use:

int size = list.size();   // Returns the number of elements in the list

7. Checking if LinkedList is Empty

You can check whether a LinkedList is empty by using:

boolean isEmpty = list.isEmpty();   // Returns true if the list is empty, otherwise false

8. Iterating Over LinkedList

You can iterate over a LinkedList using various methods:

• For-each loop:

  for (String item : list) {    System.out.println(item);}

• Iterator:

  Iterator<String> iterator = list.iterator();while (iterator.hasNext()) {    System.out.println(iterator.next());}

• ListIterator (for traversing both forward and backward):

  ListIterator<String> listIterator = list.listIterator();while (listIterator.hasNext()) {    System.out.println(listIterator.next());}

Example Program: Working with LinkedList

import java.util.LinkedList;public class LinkedListExample {    public static void main(String[] args) {        // Create a LinkedList of Strings        LinkedList<String> list = new LinkedList<>();        // Adding elements        list.add("Apple");        list.addFirst("Banana");        list.addLast("Cherry");        System.out.println("LinkedList after additions: " + list);        // Accessing elements        System.out.println("First Element: " + list.getFirst());        System.out.println("Last Element: " + list.getLast());        // Removing elements        list.remove();           // Removes the first element ("Banana")        list.removeLast();       // Removes the last element ("Cherry")        System.out.println("LinkedList after removals: " + list);        // Iterating over the LinkedList        System.out.println("Iterating over LinkedList:");        for (String item : list) {            System.out.println(item);        }        // Checking size and if empty        System.out.println("Size of the list: " + list.size());        System.out.println("Is list empty? " + list.isEmpty());    }}

Output:

LinkedList after additions: [Banana, Apple, Cherry]First Element: BananaLast Element: CherryLinkedList after removals: [Apple]Iterating over LinkedList:AppleSize of the list: 1Is list empty? false

Advantages of LinkedList:

1. Efficient Insertions and Deletions: Linked lists are efficient for insertion and deletion operations, especially at the beginning or middle of the list. These operations take constant time (O(1)), unlike ArrayList which requires shifting elements for insertions and deletions.

2. Dynamic Size: The size of the LinkedList grows and shrinks dynamically, making it a good choice for collections where the number of elements is not fixed in advance.

3. No Capacity Limitation: Unlike arrays, linked lists do not require pre-allocation of space, making them more flexible for certain types of operations.

Disadvantages of LinkedList:

1. Slower Random Access: Accessing elements by index takes linear time (O(n)) because it requires traversing the list from the beginning or end to reach the desired index. This is slower than an ArrayList, which provides constant time (O(1)) random access.

2. Extra Memory Usage: Each node in a linked list needs to store references to both the next and the previous nodes, which increases memory overhead compared to arrays or ArrayList.

3. Traversal Overhead: Operations like searching or accessing elements by index are slower due to the need to traverse the list.

Conclusion:

LinkedList is a useful data structure for cases where you need efficient insertions and deletions but don't require fast random access. It is particularly useful for implementing queues, stacks, or other data structures where the number of elements can vary dynamically.

Let me know if you need further clarification or examples! ?