Constructors in the LinkedList
LinkedList provides several constructors to create and initialize a new instance of the LinkedList class. Here are the available constructors:
LinkedList()
This is the default constructor that creates an empty LinkedList.
LinkedList<Type> list = new LinkedList<>();
LinkedList(Collection<? extends E> c)
This constructor creates a LinkedList containing all the elements from the specified collection, in the order returned by the collection's iterator.
List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5);
LinkedList<Integer> list = new LinkedList<>(numbers);
These constructors provide flexibility in creating a LinkedList, either empty or initialized with elements from another collection.
Methods for Java LinkedList
LinkedList provides a rich set of methods to perform various operations on the list. Here are some commonly used methods:
add(E element)
Appends the specified element to the end of the list.
LinkedList<String> list = new LinkedList<>();
list.add("Apple");
list.add("Banana");
add(int index, E element)
Inserts the specified element at the specified position in the list.
list.add(1, "Orange");
// list now contains ["Apple", "Orange", "Banana"]
get(int index)
Returns the element at the specified position in the list.
String element = list.get(1);
// element = "Orange"
remove(int index)
Removes the element at the specified position in the list.
list.remove(1);
// list now contains ["Apple", "Banana"]
size()
Returns the number of elements in the list.
int size = list.size();
// size = 2
contains(Object o)
Returns true if the list contains the specified element.
boolean containsApple = list.contains("Apple");
// containsApple = true
clear()
Removes all the elements from the list.
list.clear();
// list is now empty
These are just a few examples of the methods available in LinkedList. The LinkedList class also provides methods for iterating over elements, converting to an array, removing the first or last element, and more.
Implementation
To implement a LinkedList in Java, we can create a custom class that represents a node and contains methods for adding, removing, and accessing elements.
For example :
Java
public class LinkedList<E> {
private Node<E> head;
private Node<E> tail;
private int size;
private static class Node<E> {
E data;
Node<E> next;
Node(E data) {
this.data = data;
this.next = null;
}
}
public void add(E element) {
Node<E> newNode = new Node<>(element);
if (head == null) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
size++;
}
public void add(int index, E element) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Invalid index: " + index);
}
if (index == size) {
add(element);
} else {
Node<E> newNode = new Node<>(element);
if (index == 0) {
newNode.next = head;
head = newNode;
} else {
Node<E> prev = getNodeAtIndex(index - 1);
newNode.next = prev.next;
prev.next = newNode;
}
size++;
}
}
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Invalid index: " + index);
}
return getNodeAtIndex(index).data;
}
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Invalid index: " + index);
}
Node<E> removedNode;
if (index == 0) {
removedNode = head;
head = head.next;
if (head == null) {
tail = null;
}
} else {
Node<E> prev = getNodeAtIndex(index - 1);
removedNode = prev.next;
prev.next = removedNode.next;
if (prev.next == null) {
tail = prev;
}
}
size--;
return removedNode.data;
}
private Node<E> getNodeAtIndex(int index) {
Node<E> current = head;
for (int i = 0; i < index; i++) {
current = current.next;
}
return current;
}
public int size() {
return size;
}
}
You can also try this code with Online Java Compiler
In this implementation, we have a `Node` class that represents each node in the LinkedList. The `LinkedList` class contains methods for adding elements (`add()`), inserting elements at a specific index (`add(int index, E element)`), retrieving elements (`get()`), removing elements (`remove()`), and getting the size of the list (`size()`).
The `getNodeAtIndex()` method is a helper method that traverses the list to find the node at a specific index.
This implementation provides the basic functionality of a LinkedList. You can further extend it by adding more methods like `contains()`, `clear()`, and others based on your requirements.
Performing Various Operations on LinkedList
Let's see how to perform various operations on it:
Adding elements
LinkedList<String> list = new LinkedList<>();
list.add("Apple");
list.add("Banana");
list.add(1, "Orange");
// list now contains ["Apple", "Orange", "Banana"]
Updating elements
list.set(1, "Grapes");
// list now contains ["Apple", "Grapes", "Banana"]
Removing elements
list.remove(1);
// list now contains ["Apple", "Banana"]
String removedElement = list.remove(0);
// removedElement = "Apple"
// list now contains ["Banana"]
Iterating over elements:
for (String element : list) {
System.out.println(element);
}
Output:
Banana
To Array()
String[] array = list.toArray(new String[list.size()]);
// array now contains ["Banana"]
Size():
int size = list.size();
// size = 1
remove First()
String firstElement = list.removeFirst();
// firstElement = "Banana"
// list is now empty
remove last()
list.add("Apple");
list.add("Orange");
String lastElement = list.removeLast();
// lastElement = "Orange"
// list now contains ["Apple"]
Advantages of using LinkedList in Java
LinkedList have several advantages over other data structures in certain scenarios, like :
1. Dynamic size: LinkedList allows for dynamic resizing, meaning the size of the list can grow or shrink as needed during runtime. This is particularly useful when the number of elements is not known in advance or when frequent additions or removals are required.
2. Efficient insertion and deletion: LinkedList provides constant-time O(1) performance for insertion and deletion operations at both ends of the list (head and tail). This makes it efficient for scenarios where elements need to be frequently added or removed from the beginning or end of the list.
3. No shifting of elements: Unlike arrays, inserting or removing elements from the middle of a LinkedList does not require shifting the subsequent elements. Each node maintains a reference to the next node, allowing for quick and efficient modifications to the list structure.
4. Flexibility: LinkedList can be used to implement various data structures such as stacks, queues, and associative arrays. Its flexibility allows for creative problem-solving and adapting to different requirements.
5. Memory efficiency: LinkedList allocates memory for each node dynamically, which can be more memory-efficient compared to arrays when dealing with large datasets or when the size of the list is not known in advance.
Disadvantages of using LinkedList in Java
Now, let’s discuss some of the disadvantages of Linkedlist :
1. Random access is slow: Accessing an element at a specific index in a LinkedList requires traversing the list from the head or tail until the desired index is reached. This results in a linear-time O(n) operation, making random access inefficient compared to arrays, which provide constant-time O(1) access to elements by index.
2. Extra memory usage: LinkedList requires extra memory to store the references (pointers) to the next node for each element. This overhead can be significant when storing small elements or when memory is limited. In contrast, arrays store elements contiguously in memory, which can be more memory-efficient.
3. Lack of cache-friendly operations: Arrays have better cache locality because elements are stored contiguously in memory. This allows for efficient cache utilization and faster element retrieval. LinkedList, on the other hand, may have nodes scattered in different memory locations, leading to cache misses and slower performance for certain operations.
4. Overhead for small lists: For small lists or scenarios where the number of elements is known and fixed, using a LinkedList may introduce unnecessary overhead compared to using an array. The additional memory for references and the lack of cache-friendly access can make LinkedList less efficient in such cases.
5. Complexity of implementation: Implementing a LinkedList from scratch requires more code and is more complex compared to using an array. The additional complexity can make the code harder to read, understand, and maintain, especially for beginners.
Frequently Asked Questions
What is the time complexity of inserting or removing elements at the beginning or end of a LinkedList?
The time complexity of inserting or removing elements at the beginning or end of a LinkedList is O(1) or constant time.
Can a LinkedList contain duplicate elements?
Yes, a LinkedList can contain duplicate elements. It allows for multiple occurrences of the same value.
Is it efficient to search for an element in a LinkedList?
Searching for an element in a LinkedList requires traversing the list from the beginning, resulting in a time complexity of O(n) in the worst case. It is not as efficient as searching in an array or other data structures that provide random access.
Conclusion
In this article, we have learned about the LinkedList data structure in Java. We discussed its internal workings, constructors, and methods. We also looked at how to implement a LinkedList and perform various operations such as adding, updating, removing, and iterating over elements. Additionally, we discussed the advantages and disadvantages of using LinkedList in different scenarios.
You can also practice coding questions commonly asked in interviews on Coding Ninjas Code360.
Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.
84+ registered