The LinkedList in Java is a part of the Java Collection Framework and it extends the AbstractList class and implements List and Deque interfaces.
Important Key Points About Java LinkedList Class
Here are some key points about LinkedList:
Data Structure:
LinkedList is based on a doubly-linked list data structure, which means it contains a link to the next node in the list along with a link to the previous node.
Insertion Order:
Java LinkedList maintains the insertion order of the elements.
Dynamic Size:
LinkedList in Java can grow and shrink dynamically as the items are added or removed.
Duplicates and Null Elements:
LinkedList can have duplicate and null values.
Insertion & Deletion:
Insertion and deletion operations are efficient in LinkedList as compared to ArrayList, as shifting is not required. When a new element is added, it gets placed at a specific position based on the reference in the list.
Sequential Access:
Accessing elements is slower compared to ArrayList because it has to traverse from the head of the list to reach the specified node.
Memory Overhead:
Each element in the LinkedList consumes more memory as it holds data as well as address fields for the previous and the next element.
Use Cases:
LinkedList is better for manipulating data, i.e., insertions and deletions, whereas ArrayList is better for storing and accessing data.
Implements Interfaces:
The LinkedList class implements Queue and Deque interfaces. Therefore, It can also be used as a Queue, Deque, or Stack.
Iterator and ListIterator:
LinkedList provides methods to return an Iterator and a ListIterator that can be used to traverse the list in either the forward or the backward direction.
Not a Thread Safe:
Java LinkedList is not thread-safe. You must explicitly synchronize concurrent modifications to the LinkedList in a multi-threaded environment.Create LinkedList
Here is the syntax to create a LinkedList class object:LinkedList<String> linkedList = new LinkedList<>();
Add Elements
We can add new elements to the end of the LinkedList using add() method: // Creating LinkedList of Strings
LinkedList<String> list = new LinkedList<String>();
// Using add() method to add elements in the list
list.add("Java");
list.add("Python");
list.add("JavaScript"); // Adding an element at the specific position in the list
list.add(1, "C++"); // Adding elements at the beginning of the list using addFirst()
list.addFirst("Swift"); // Adding elements at the end of the list using addLast()
list.addLast("Kotlin");import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
// Creating LinkedList of Strings
LinkedList<String> list = new LinkedList<String>();
// Using add() method to add elements in the list
list.add("Java");
list.add("Python");
list.add("JavaScript");
// Displaying the initial LinkedList
System.out.println("Initial LinkedList : " + list);
// Adding an element at the specific position in the list
list.add(1, "C++");
// Displaying the LinkedList after adding an element at position 1
System.out.println("After add(1, \"C++\") : " + list);
// Adding elements at the end of the list using addLast()
list.addLast("Kotlin");
// Displaying the LinkedList after adding an element at the end
System.out.println("After addLast(\"Kotlin\") : " + list);
// Adding elements at the beginning of the list using addFirst()
list.addFirst("Swift");
// Displaying the LinkedList after adding an element at the beginning
System.out.println("After addFirst(\"Swift\") : " + list);
}
}
Output:
Initial LinkedList : [Java, Python, JavaScript]
After add(1, "C++") : [Java, C++, Python, JavaScript]
After addLast("Kotlin") : [Java, C++, Python, JavaScript, Kotlin]
After addFirst("Swift") : [Swift, Java, C++, Python, JavaScript, Kotlin]Access Elements
In order to access elements from a LinkedList in Java, you can use the get(int index), getFirst(), and getLast() methods.
We can access or retrieve an element at a given index using the get() method:
// Creating a LinkedList of Strings
LinkedList<String> list = new LinkedList<String>();
// Adding elements to the LinkedList
list.add("Java");
list.add("Python");
list.add("JavaScript");
list.add("C++");
list.add("Kotlin");
// Accessing elements from the LinkedList
// The get() method throws IndexOutOfBoundsException, if the specified index is out of range
System.out.println("Element returned by get(2): " + list.get(2));We can retrieve the first element from the LinkedList using the getFirst() method:
// The first() method returns the first element in this list
System.out.println("Element returned by first(): " + list.getFirst()); We can retrieve the last element from the LinkedList using the getLast() method:
// The last() method returns the last element in this list
System.out.println("Element returned by last(): " + list.getLast());Here is a complete example with output:
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
// Creating a LinkedList of Strings
LinkedList<String> list = new LinkedList<String>();
// Adding elements to the LinkedList
list.add("Java");
list.add("Python");
list.add("JavaScript");
list.add("C++");
list.add("Kotlin");
// Accessing elements from the LinkedList
// The get() method throws IndexOutOfBoundsException, if the specified index is out of range
System.out.println("Element returned by get(2): " + list.get(2));
// The first() method returns the first element in this list
System.out.println("Element returned by first(): " + list.getFirst());
// The last() method returns the last element in this list
System.out.println("Element returned by last(): " + list.getLast());
}
}
Output:
Element returned by get(2): JavaScript
Element returned by first(): Java
Element returned by last(): KotlinIn the above code, the get(int index) method is used to return the element at the specified position in the list. We get the element at position 2 (0-based indexing) which is "JavaScript". The getFirst() method is used to retrieve the first element from the LinkedList, which is "Java" in our case. The getLast() method is used to retrieve the last element from the LinkedList, which is "Kotlin" in our case.
Remove Elements
In Java, you can remove elements from a LinkedList using a variety of methods such as remove(Object), remove(int index), removeFirst(), removeLast(), and clear().
Here's a simple code example illustrating this, along with comments explaining each operation:
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
// Creating a LinkedList of Strings
LinkedList<String> list = new LinkedList<String>();
// Adding elements to the LinkedList
list.add("Java");
list.add("Python");
list.add("JavaScript");
list.add("C++");
list.add("Kotlin");
// Displaying the LinkedList
System.out.println("Initial LinkedList: " + list);
// The remove(int index) method removes the element at the specified position in this list
list.remove(2);
System.out.println("LinkedList after removing element at index 2: " + list);
// The remove(Object) method removes the first occurrence of the specified element from this list, if it is present
list.remove("Python");
System.out.println("LinkedList after removing 'Python': " + list);
// The removeFirst() method removes and returns the first element from this list
list.removeFirst();
System.out.println("LinkedList after removing first element: " + list);
// The removeLast() method removes and returns the last element from this list
list.removeLast();
System.out.println("LinkedList after removing last element: " + list);
// The clear() method removes all of the elements from this list
list.clear();
System.out.println("LinkedList after calling clear(): " + list);
}
}
Output:
Initial LinkedList: [Java, Python, JavaScript, C++, Kotlin]
LinkedList after removing element at index 2: [Java, Python, C++, Kotlin]
LinkedList after removing 'Python': [Java, C++, Kotlin]
LinkedList after removing first element: [C++, Kotlin]
LinkedList after removing last element: [C++]
LinkedList after calling clear(): []In this code:
- We first create a LinkedList named list of type String and add elements to it.
- Then, we remove the element at position 2 (0-based indexing) from the list using remove(int index).
- After that, we remove the first occurrence of the element "Python" from the list using remove(Object).
- The removeFirst() method is used to remove the first element from the LinkedList.
- The removeLast() method is used to remove the last element from the LinkedList.
- Finally, we clear the entire list using clear().
Search Elements
In Java, you can search for elements in a LinkedList using the contains(Object), indexOf(Object), and lastIndexOf(Object) methods.
Here is an example demonstrating how to use these methods, along with comments explaining each operation:
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
// Creating a LinkedList of Strings
LinkedList<String> list = new LinkedList<String>();
// Adding elements to the LinkedList
list.add("Java");
list.add("Python");
list.add("JavaScript");
list.add("C++");
list.add("Python");
list.add("Kotlin");
// Displaying the LinkedList
System.out.println("LinkedList: " + list);
// The contains(Object) method returns true if this list contains the specified element
boolean found = list.contains("Python");
System.out.println("'Python' is in the list: " + found);
// The indexOf(Object) method returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element
int firstIndex = list.indexOf("Python");
System.out.println("First occurrence of 'Python' is at index: " + firstIndex);
// The lastIndexOf(Object) method returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element
int lastIndex = list.lastIndexOf("Python");
System.out.println("Last occurrence of 'Python' is at index: " + lastIndex);
}
}
Output:
LinkedList: [Java, Python, JavaScript, C++, Python, Kotlin]
'Python' is in the list: true
First occurrence of 'Python' is at index: 1
Last occurrence of 'Python' is at index: 4Iterate or Loop Through LinkedList
In Java, there are several ways to iterate over a LinkedList, including using an iterator, an enhanced for loop, a traditional for loop, and Java 8 features like the forEach method and streams. Let's see some examples for each of these methods:
import java.util.Iterator;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
// Creating a LinkedList of Strings
LinkedList<String> list = new LinkedList<String>();
list.add("Java");
list.add("Python");
list.add("JavaScript");
list.add("C++");
// Using Iterator
System.out.println("Iterating using Iterator:");
Iterator<String> iterator = list.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
// Using Enhanced For loop
System.out.println("Iterating using Enhanced For loop:");
for(String language: list){
System.out.println(language);
}
// Using Traditional For loop
System.out.println("Iterating using Traditional For loop:");
for(int i = 0; i < list.size(); i++){
System.out.println(list.get(i));
}
// Using forEach() method (Java 8)
System.out.println("Iterating using forEach() method:");
list.forEach(language -> {
System.out.println(language);
});
// Using forEach() method with method reference (Java 8)
System.out.println("Iterating using forEach() method with method reference:");
list.forEach(System.out::println);
// Using Streams (Java 8)
System.out.println("Iterating using Streams:");
list.stream().forEach(System.out::println);
}
}
Output:
Iterating using Iterator:
Java
Python
JavaScript
C++
Iterating using Enhanced For loop:
Java
Python
JavaScript
C++
Iterating using Traditional For loop:
Java
Python
JavaScript
C++
Iterating using forEach() method:
Java
Python
JavaScript
C++
Iterating using forEach() method with method reference:
Java
Python
JavaScript
C++
Iterating using Streams:
Java
Python
JavaScript
C++In this code, we first create a LinkedList of String and add some elements to it. Then, we iterate over this list in various ways:
- Iterator: We create an Iterator object and use its hasNext() method to check if there are more elements in the list. If there are, we use next() to get and print the next element.
- Enhanced For loop: This is a more compact form of a loop that automatically iterates over all elements in the list.
- Traditional For loop: Here, we use a counter to manually iterate over each index of the list.
- forEach() method: Introduced in Java 8, this method is a more elegant way to iterate over a collection. We pass a lambda function to it that gets executed for each element in the list.
- forEach() method with a method reference: Instead of a lambda, we can also pass a method reference to the forEach() method. Here, we pass the println method of System.out.
- Streams: Also introduced in Java 8, streams provide a more functional programming style approach. We first convert the list into a stream and then use the forEach method to print each element.
ArrayList vs LinkedList
ArrayList and LinkedList are two commonly used classes in Java that implement the List interface. While both of them can be used to store objects, there are some key differences between the two that make them suited for different scenarios:
Underlying Data Structure:
The most fundamental difference is in the way they store and manage data. An ArrayList uses a dynamic array to store the data, whereas a LinkedList uses a doubly-linked list.
Performance:
ArrayLists are generally faster for lookup operations i.e., when you want to access a specific element because it supports random access and the time complexity is O(1).
On the other hand, LinkedLists have to traverse from the head of the list to the required index, leading to a time complexity of O(n). However, LinkedLists are faster at add and remove operations, because they simply need to change the pointers of the previous and next nodes, whereas ArrayLists need to shift all elements.
Memory Usage:
A LinkedList uses more memory than an ArrayList because, in addition to storing the actual data, each node in a LinkedList also needs to store two references to the next and previous nodes.
Resizable:
Both ArrayList and LinkedList are resizable. But resizing an ArrayList by adding more elements than its initial capacity leads to an expensive operation of resizing the array and copying elements to the new array. LinkedList does not have this problem as elements can be added or removed without the need for resizing.
Use Cases:
If you have a large number of get operations, you should use ArrayList. If you have a large number of add/remove operations (especially not at the end of the list), and you don't know the index of elements, you should use LinkedList.
Overall, the choice between ArrayList and LinkedList depends on the specific requirements of your project, such as the type of operations you need to perform, the number of elements, and memory considerations.
Conclusion
That’s all folks! In this article, you learned what is a LinkedList, the key points about LinkedList, how to create a LinkedList, how to add, remove and search for elements in a LinkedList, how to iterate over a LinkedList, and what are the differences between a LinkedList and an ArrayList.
Comments
Post a Comment
Leave Comment