What is a LinkedList in Java?
In Java, a LinkedList is a part of the java.util package, representing a linear data structure. It consists of nodes, where each node holds data and a reference to the next node. LinkedList allows dynamic sizing, making it efficient for insertions and deletions. However, random access is slower compared to arrays. It provides built-in methods for adding, removing, and accessing elements, making it a useful choice for scenarios requiring frequent changes to the collection’s size or order.
Syntax:
// Create a LinkedList of a specific data type
LinkedList<DataType> linkedList = new LinkedList<>();
// Add elements to the LinkedList
linkedList.add(element1);
linkedList.add(element2);
// …
// Access elements in the LinkedList
DataType data = linkedList.get(index);
// Remove elements from the LinkedList
linkedList.remove(index);
Features of LinkedList class:
The LinkedList class in Java, which is a part of the Java Collections Framework, offers several features and methods that facilitate the implementation and manipulation of a doubly linked list. Here are the key features of the LinkedList class:
- Doubly Linked List: The LinkedList class implements a doubly linked list, meaning that each node contains references to both the next and the previous nodes. This design allows for efficient traversal in both directions.
- Dynamic Size: Like other linked lists, the LinkedList class can grow or shrink dynamically as elements are added or removed. It does not require pre-allocating memory with a fixed size.
- Implementation of List and Deque Interfaces: LinkedList class implements both the List and Deque interfaces. As a List, it allows accessing elements by index and supports operations like adding, removing, and searching for elements. As a Deque (double-ended queue), it provides additional methods to add and remove elements from both ends of the list.
- Fast Insertions and Deletions: LinkedList class allows for fast insertions and deletions at both the beginning and the end of the list, as well as at specific positions. These operations typically take constant time (O(1)) when performed on the first or last element.
- Sequential Access: Accessing elements in the middle of the list requires sequential traversal from the beginning or end. As a result, random access to elements (by index) is slower compared to data structures like ArrayList, which provide direct index-based access.
- No Continuous Memory Allocation: Unlike arrays, the LinkedList class does not require continuous memory allocation for storing elements. Each node points to its adjacent nodes using references, making it more memory-efficient when handling frequent insertions and deletions.
- Additional Functionality: Besides the standard List and Deque operations, the LinkedList class also offers specific methods like getFirst(), getLast(), addFirst(), addLast(), removeFirst(), and removeLast() to manipulate the first and last elements efficiently.
- Iterators: LinkedList provides iterators that allow you to iterate through the elements in the list. These iterators provide methods like hasNext(), next(), hasPrevious(), and previous() for traversing the list in both forward and backward directions.
Here’s a simple example demonstrating some of the features of the LinkedList class:
import java.util.LinkedList;
public class LinkedListExample {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<>();
// Adding elements to the linked list
linkedList.add("Apple");
linkedList.add("Banana");
linkedList.add("Orange");
// Removing an element
linkedList.remove("Banana");
// Adding elements to the beginning and end of the list
linkedList.addFirst("Grapes");
linkedList.addLast("Pineapple");
// Accessing elements
String firstElement = linkedList.getFirst();
String lastElement = linkedList.getLast();
System.out.println("Linked List: " + linkedList);
System.out.println("First Element: " + firstElement);
System.out.println("Last Element: " + lastElement);
}
}
In this example, we create a LinkedList instance, add and remove elements, and use methods like addFirst() and addLast() to add elements to the beginning and end of the list, respectively. The getFirst() and getLast() methods are used to access the first and last elements in the list.
ArrayList vs. LinkedList
ArrayList vs. LinkedList: A Comparison of Two Java Collections
1. Data Structure:
- ArrayList: Implements a dynamic array, providing direct access to elements via indexes. Resizes when the capacity is exceeded.
- LinkedList: Uses a doubly linked list, where each element holds references to both the next and previous nodes. Suitable for insertions and deletions.
2. Performance:
- ArrayList: Faster for random access (O(1)) due to direct indexing. Slower for insertions and deletions (O(n)) as elements may need to be shifted.
- LinkedList: Faster for insertions and deletions at the beginning and middle (O(1)). Slower for random access (O(n)) since traversal from the head is required.
3. Memory Efficiency:
- ArrayList: Requires contiguous memory, which can lead to memory wastage during resizing.
- LinkedList: Efficient memory usage since each node only needs to store data and references.
4. Use Cases:
- ArrayList: Ideal for scenarios requiring frequent access or searching of elements, especially when the size is relatively stable.
- LinkedList: Suitable for situations requiring frequent insertions and deletions, such as queue or stack implementations.
5. Java Package:
- ArrayList: java.util.ArrayList
- LinkedList: java.util.LinkedList
In summary, choose ArrayList for fast access and stable-sized collections, while LinkedList is better for frequent insertions and deletions. Consider the specific use case and the expected operations on the collection to determine the most appropriate data structure.
How the LinkedList works:
The LinkedList organizes its elements into “containers,” with each container having a link to the next one in the list. To add an element, it creates a new container and links it to the existing ones. Meanwhile, an ArrayList is used for efficient storage and direct access to elements, while the LinkedList is employed for dynamic manipulation like insertion and deletion.
Methods of Java LinkedList
LinkedList in Java offers a range of methods to perform diverse operations on linked lists. Four commonly used methods are:
1.Add elements:
- addFirst(element): Adds an element to the beginning of the list.
- addLast(element): Adds an element to the end of the list.
- add(index, element): Inserts an element at the specified index.
2.Access elements:
- get(index): Retrieves the element at the specified index.
- getFirst(): Retrieves the first element in the list.
- getLast(): Retrieves the last element in the list.
3.Change elements:
- set(index, element): Replaces the element at the given index with a new one.
4.Remove elements:
- remove(index): Removes the element at the specified index.
- removeFirst(): Removes the first element from the list.
- removeLast(): Removes the last element from the list.
Operations performed in LinkedList
1. Add elements to a LinkedList
import java.util.LinkedList;
public class LinkedListExample {
public static void main(String[] args) {
// Create a new LinkedList to store integers
LinkedList<Integer> linkedList = new LinkedList<>();
// Adding elements to the LinkedList
linkedList.add(10); // Adding an element to the end (tail) of the list
linkedList.add(20); // Adding another element to the end
linkedList.addFirst(5); // Adding an element to the beginning (head) of the list
linkedList.addLast(30); // Adding an element to the end
// Adding an element at a specific position
linkedList.add(2, 15); // Adding 15 at index 2 (between 10 and 20)
// Displaying the elements in the LinkedList
System.out.println("LinkedList: " + linkedList);
}
}
Output:
Explanation of this code:
In this example, we create a LinkedList to store integers. We then use various methods to add elements to the linked list:
- add(10): Adds the element 10 to the end of the list.
- add(20): Adds the element 20 to the end of the list.
- addFirst(5): Adds the element 5 to the beginning of the list.
- addLast(30): Adds the element 30 to the end of the list.
- add(2, 15): Adds the element 15 at index 2, shifting the elements after that index to the right.
2. Access LinkedList elements
import java.util.LinkedList;
public class LinkedListAccessExample {
public static void main(String[] args) {
// Create a LinkedList of strings
LinkedList<String> linkedList = new LinkedList<>();
// Adding elements to the LinkedList
linkedList.add("Apple");
linkedList.add("Banana");
linkedList.add("Orange");
linkedList.add("Mango");
linkedList.add("Grapes");
// Accessing elements by index
String firstElement = linkedList.get(0);
String thirdElement = linkedList.get(2);
String lastElement = linkedList.get(linkedList.size() - 1);
// Accessing the first and last elements
String first = linkedList.getFirst();
String last = linkedList.getLast();
System.out.println("First Element: " + firstElement);
System.out.println("Third Element: " + thirdElement);
System.out.println("Last Element: " + lastElement);
System.out.println("First Element (using getFirst()): " + first);
System.out.println("Last Element (using getLast()): " + last);
// Using enhanced for-loop to access elements
System.out.println("Using enhanced for-loop to access elements:");
for (String element : linkedList) {
System.out.println("Element: " + element);
}
}
}
Output:
First Element: Apple
Third Element: Orange
Last Element: Grapes
First Element (using getFirst()): Apple
Last Element (using getLast()): Grapes
Using enhanced for-loop to access elements:
Element: Apple
Element: Banana
Element: Orange
Element: Mango
Element: Grapes
Explanation of this code:
In this example, we create a LinkedList of strings and add elements to it. We then demonstrate different ways to access the elements:
- get(index): Accessing elements by their index in the LinkedList.
- getFirst(): Accessing the first element of the LinkedList.
- getLast(): Accessing the last element of the LinkedList.
- Using an enhanced for-loop to iterate through the elements in the LinkedList.
By using these methods, you can easily access elements in a LinkedList and retrieve the data you need based on your requirements.
3. Change Elements of a LinkedList
import java.util.LinkedList;
public class LinkedListChangeExample {
public static void main(String[] args) {
// Create a LinkedList of strings
LinkedList<String> linkedList = new LinkedList<>();
// Adding elements to the LinkedList
linkedList.add("Apple");
linkedList.add("Banana");
linkedList.add("Orange");
linkedList.add("Mango");
linkedList.add("Grapes");
System.out.println("Original LinkedList: " + linkedList);
// Changing the value of an element at a specific index
int indexToChange = 2;
String newValue = "Pineapple";
linkedList.set(indexToChange, newValue);
// Changing the first and last elements
linkedList.setFirst("Watermelon");
linkedList.setLast("Kiwi");
System.out.println("LinkedList after changing element at index " + indexToChange + ": " + linkedList);
}
}
Output:
LinkedList after changing element at index 2: [Watermelon, Banana, Pineapple, Mango, Kiwi]
Explanation of this code:
In this example, we create a LinkedList of strings and add elements to it. We then use the following methods to change the elements in the LinkedList:
- set(index, element): This method changes the value of the element at the specified index. In the example, we change the value at index 2 from “Orange” to “Pineapple”.
- setFirst(element): This method changes the value of the first element in the LinkedList. In the example, we change the first element from “Apple” to “Watermelon”.
- setLast(element): This method changes the value of the last element in the LinkedList. In the example, we change the last element from “Grapes” to “Kiwi”.
After changing the elements, the output will show the original LinkedList and the modified LinkedList with the updated values.
4. Remove element from a LinkedList
import java.util.LinkedList;
public class LinkedListRemoveExample {
public static void main(String[] args) {
// Create a LinkedList of strings
LinkedList<String> linkedList = new LinkedList<>();
// Adding elements to the LinkedList
linkedList.add("Apple");
linkedList.add("Banana");
linkedList.add("Orange");
linkedList.add("Mango");
linkedList.add("Grapes");
System.out.println("Original LinkedList: " + linkedList);
// Remove an element by value
String valueToRemove = "Orange";
boolean removed = linkedList.remove(valueToRemove);
System.out.println("Element \"" + valueToRemove + "\" removed: " + removed);
System.out.println("LinkedList after removing \"" + valueToRemove + "\": " + linkedList);
// Remove the first element
String firstElement = linkedList.removeFirst();
System.out.println("Removed first element: " + firstElement);
System.out.println("LinkedList after removing first element: " + linkedList);
// Remove the last element
String lastElement = linkedList.removeLast();
System.out.println("Removed last element: " + lastElement);
System.out.println("LinkedList after removing last element: " + linkedList);
// Remove an element by index
int indexToRemove = 1;
String removedAtIndex = linkedList.remove(indexToRemove);
System.out.println("Removed element at index " + indexToRemove + ": " + removedAtIndex);
System.out.println("LinkedList after removing element at index " + indexToRemove + ": " + linkedList);
}
}
Output:
Element “Orange” removed: true
LinkedList after removing “Orange”: [Apple, Banana, Mango, Grapes]
Removed first element: Apple
LinkedList after removing first element: [Banana, Mango, Grapes]
Removed last element: Grapes
LinkedList after removing last element: [Banana, Mango]
Removed element at index 1: Mango
LinkedList after removing element at index 1: [Banana]
Explanation of this code:
In this example, we create a LinkedList of strings and add elements to it. We then use the following methods to remove elements from the LinkedList:
- remove(Object): This method removes the first occurrence of the specified element from the LinkedList.
- removeFirst(): This method removes and returns the first element from the LinkedList.
- removeLast(): This method removes and returns the last element from the LinkedList.
- remove(index): This method removes and returns the element at the specified index in the LinkedList.
After removing elements, the output will show the original LinkedList and the LinkedList after each removal operation.
Java Array to LinkedList
In this section, we will learn about converting a Java Array into a LinkedList object. There are several approaches to achieve this, but we will focus on one specific method in this example.
import java.util.LinkedList;
import java.util.List;
public class ArrayToLinkedListExample {
public static void main(String[] args) {
Integer[] originalArray = {1, 2, 3, 4, 5};
List<Integer> linkedList = new LinkedList<>();
for (Integer number : originalArray) {
linkedList.add(number);
}
System.out.println("LinkedList: " + linkedList);
}
}
Output:
Explanation of this code:
- An array of Integer, named originalArray, is declared and initialized with values {1, 2, 3, 4, 5}.
- An empty LinkedList of Integer, named linkedList, is created.
- A for-each loop is used to iterate through each element (number) in the originalArray.
- Inside the loop, each element (number) from the originalArray is added to the linkedList using the add() method. The add() method adds the element to the end of the linked list.
- After the loop completes, the content of the linkedList is printed using System.out.println().
The final result is the linked list [1, 2, 3, 4, 5], which holds the elements from the original array in the same order.
Java LinkedList to Array
In this section, we will examine the process of converting a Java LinkedList into an Array. While there are various methods to accomplish this task, we will focus on a particular approach in this example.
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class ConvertLinkedListToArrayDemo {
public static void main(String[] args) {
List<Integer> myList = new LinkedList<>();
myList.add(10);
myList.add(20);
myList.add(30);
myList.add(40);
myList.add(50);
Integer[] array = new Integer[myList.size()];
array = myList.toArray(array);
System.out.println(Arrays.toString(array));
}
}
Output:
Explanation of this code:
- A LinkedList of Integer, named myList, is created and populated with elements 10, 20, 30, 40, and 50 using the add() method.
- An array of Integer, named array, is declared and initialized with a size equal to the size of the myList.
- The myList.toArray(array) method is used to convert the myList into an array. The toArray() method takes an array as an argument and returns an array containing all the elements of the list. If the provided array is large enough to hold all the elements, it will be used; otherwise, a new array will be created.
- The content of the resulting array is printed using System.out.println(Arrays.toString(array)).
The toArray() method provides a convenient way to convert a List (e.g., LinkedList, ArrayList) into an array, which can be useful in certain scenarios where array-based processing is required or when you need to interface with methods that expect arrays as input.
