A LinkedList is a collection that allows you to store a sequence of elements in a linear fashion. Unlike an ArrayList, which stores elements in a contiguous block of memory, a LinkedList stores elements in individual nodes, where each node contains:
- Data: The value of the element.
- Next: A reference (or link) to the next node in the list.
This structure allows efficient insertion and removal of elements because you don’t need to shift the other elements when adding or removing elements in the middle of the list.
Features
- Doubly Linked: Java’s LinkedList is a doubly linked list, meaning each node has a reference to both the next node and the previous node.
- Dynamic Size: Since a LinkedList doesn’t require pre-defined sizing (unlike arrays), it dynamically grows or shrinks as needed.
- Efficient Insertions/Deletions: Insertions and deletions are fast (constant time) when done at the beginning or middle of the list, as no shifting is required.
Common Operations
- add(): Adds an element at the end of the list or at a specific position.
- get(): Retrieves an element from a specific index.
- remove(): Removes an element by index or by value.
- size(): Returns the number of elements in the list.
- contains(): Checks if a specific element exists in the list.
Example
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
import java.util.LinkedList; public class LinkedListExample { public static void main(String[] args) { // Creating a LinkedList of Strings LinkedList<String> list = new LinkedList<>(); // Adding elements list.add("Java"); list.add("Python"); list.add("C++"); // Displaying the LinkedList System.out.println("LinkedList: " + list); // Removing an element list.remove("Python"); System.out.println("After removing Python: " + list); // Accessing an element String firstElement = list.get(0); System.out.println("First element: " + firstElement); // Checking the size System.out.println("Size of LinkedList: " + list.size()); } } |
Use Cases
- Dynamic Memory Allocation: Ideal when the number of elements isn’t known in advance, such as in dynamic data storage systems.
- Implementation of Other Data Structures: Linked lists are the foundation for more complex structures like stacks, queues, and graphs.
- Real-Time Applications: When frequent memory allocation and deallocation are required, such as in gaming or simulation applications.
- Polynomial Representation: Linked lists can efficiently represent large polynomials where each term is a node.
