What is LinkedList in Java?
- A LinkedList in java is a linear data structure that stores components in a non-contiguous way, meaning the components are not stored in adjoining memory areas.
- Instep, each component in a LinkedList is stored in a node, which contains the information and a reference (or connect) to the another node within the arrangement.
- This structure permits effective additions and deletions, particularly when managing with huge datasets.
- A LinkedList is portion of the Java Collections Framework and is found within the java.util package.
- It actualizes both the List and Deque interfaces, meaning it can work as a list, stack, queue, or deque (double-ended queue).
Key Characteristics of LinkedList
- Non-Contiguous Memory Allotment: Not at all like an array, which uses contiguous memory areas, a LinkedList nodes are scattered all through memory. Each node focuses to the following node, making a “chain.”
- Dynamic Size: A LinkedList can develop or shrink dynamically as components are added or removed. This adaptability contrasts with arrays, which have a fixed size.
- Efficient Insertions/Deletions: Adding or removing components at the starting or middle of the list is more effective than an array since there’s no need to move other components.
- Slower Access: Accessing elements by list is slower compared to an ArrayList, because it requires navigating the list from the head node.
- Memory Overhead: Each node in a LinkedList requires additional memory to store the reference to the another node, making it more memory-intensive than arrays or ArrayLists.
Types of LinkedList
In Java, the LinkedList class supports different configurations based on how components are inserted and removed:
1.Singly LinkedList:
- In a singly linked list, each node contains information and a reference (or interface) to the another node.
- Navigating the list can as it were happen in one direction—from the head to the tail.
- Java’s LinkedList is basically a singly linked list.
- Example:
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
2.Doubly LinkedList:
- In a doubly linked list, each node contains two references : one showing to the following node and another showing to the past node.
- This allows traversal in both directions.
- LinkedList is internally implemented as a doubly linked list.
- Example:
class DoublyNode {
int data;
DoublyNode next;
DoublyNode prev;
DoublyNode(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
3.Circular LinkedList:
- A circular linked list is a variety where the final node points back to the first node rather than having a invalid reference.
- This makes a circular structure, which can be valuable in applications like round-robin planning.
- Example:
class CircularNode {
int data;
CircularNode next;
CircularNode(int data) {
this.data = data;
this.next = null;
}
}
Operations on LinkedList
Java’s LinkedList class gives a few methods for adding, removing, and getting to components. A few of the key operations include:
1.add(E e): Add a component at the end of the list.
Example:
LinkedList<String> fruitsList = new LinkedList<>();
fruitsList.add("Apple");
fruitsList.add("Banana");
2.addFirst(E e): Add a component at the starting of the list.
Example:
 fruitsList.addFirst("Mango");
System.out.println(fruitsList); // [Mango, Apple, Banana]
3.addLast(E e): Add a component at the end of the list (comparable to add(E e)).
Example:
fruitsList.addLast("Grapes");
System.out.println(fruitsList); // [Mango, Apple, Banana, Grapes]
4.removeFirst(): Remove the first component from the list.
Example:
fruitsList.removeFirst(); // Removes Mango
System.out.println(fruitsList); // [Apple, Banana, Grapes]
5.removeLast(): Remove the last component from the list.
Example:
fruitsList.removeLast(); // Removes Grapes
System.out.println(fruitsList); // [Apple, Banana]
6.get(int index): Retrieve the component at the required index.
Example:
System.out.println(fruitsList.get(1)); // Banana
7.size(): Returns the number of components within the list.
Example:
System.out.println(fruitsList.size()); // 2
8.contains(Object o): Checks if a particular component exists within the list.
Example:
System.out.println(fruitsList.contains("Banana")); // true
9.clear(): Removes all components from the list.
Example:
fruitsList.clear();
System.out.println(fruitsList); // []
Illustration Code for LinkedList
Here’s a basic illustration demonstrating the creation and manipulation of a LinkedList in Java:
import java.util.LinkedList;
public class LinkedListExample {
public static void main(String[] args) {
// Create a LinkedList to store String values
LinkedList<String> cities = new LinkedList<>();
// Add elements to the list
cities.add(“New York”);
cities.add(“London”);
cities.add(“Paris”);
cities.addFirst(“Tokyo”); // Adds Tokyo at the beginning
// Print the LinkedList
System.out.println(“Cities: ” + cities); // [Tokyo, New York, London, Paris]
// Access an element by index
System.out.println(“Second city: ” + cities.get(1)); // New York
// Remove elements
cities.removeLast(); // Removes Paris
cities.removeFirst(); // Removes Tokyo
// Print after removals
System.out.println(“After removals: ” + cities); // [New York, London]
// Check if an element exists
System.out.println(“Contains London? ” + cities.contains(“London”)); // true
}
}
Performance Considerations
1.Insertion/Deletion:
- Insertion and deletion of components at the starting or within the middle of a LinkedList are O(1) operations.
- Be that as it may, inserting or deleting components at the end may require navigating the complete list, making it O(n) for the last component if it’s not optimized.
2.Access:
- Getting to an component by index takes O(n) time in a LinkedList since you have got to navigate the list from the head node.
3.Memory Usage:
- Each node in a LinkedList stores both information and a reference (or references, within the case of a doubly linked list), which increments memory utilization compared to other data structures like arrays or ArrayList.