LinkedList class in Java uses a doubly linked list to store elements and it also provides a linked-list data structure. It implements List, just like ArrayList class, and Deque interfaces. Just like arrays, Linked List is a linear data structure but unlike arrays, the elements in the linked list are linked together using pointers. There is a pointer that points to the first element, usually called “Head”. The last element points to a NULL element. This NULL element means that there are not any more elements in the linked list.
What is important to know about LinkedList in Java
- LinkedList class in Java permits duplicate elements.
- LinkedList class in Java maintains insertion order.
- LinkedList class in Java is non-synchronized.
- LinkedList class in Java allows fast manipulation as there is no shifting needed.
- LinkedList class in Java can be either a list, stack or even a queue.
Limitations of LinkedList
- LinkedList class requires more memory than arrays as the storage is used by their pointers.
- Since we cannot access every single element just by their index, the elements in linked lists are hard to traverse.
Simple illustration of LinkedList
Head here is the pointer that I mentioned above, the pointer that points to the first element. The first element (and every single element in the linked list) has essentially two things — data and next. The data is simply what the specified element contains and next, is the pointer that points to the next element. In the end, we can see on the illustration that D points to NULL and in linked lists, NULL means the end of the list.
Constructors in LinkedList
- LinkedList(): it is used to construct an empty list.
- LinkedList(Collection<? extends E> c): it is used to construct a list containing the elements of the specified collection,in the order, they are returned by the collection’s iterator.
Methods ins LinkedList
- boolean add(E e): adds the specified element to the end of the list.
- void add(int index, E element): adds the specified element to the specified location.
- void clear(): removes all elements from the list.
- Object clone: returns a shallow copy of an ArrayList.
- boolean contains(Object o) returns true if the specified element is in the list.
- Iterator<E> descendingIterator(): returns an iterator over the elements in a deque in reverse sequential order.
- E element(): retrieves the first element from the list.
- E get(int index): returns the element at the specified position in the list.
- int indexOf(Object o) returns the index of the first occurrence of the specified element in the list or -1 if the element is not present.
- boolean offer(E e): adds the specified element as the last element of a list.
- E pop(): pops an element from the stack represented by a list.
- void push(E e): pushes an element onto the stack represented by a list.
- E remove(): used to retrieve and removes the first element of a list.
- E remove(int index): removes the element at the specified position in the list.
- int size(): returns the number of elements in the list.
For documentation for all the methods, you can visit the Oracle official documentation page.
Adding elements to LinkedList using add()
Syntax: boolean add(E e)
import java.io.*;
import java.util.LinkedList;
public class LinkedListExample {
public static void main(String args[]) {
LinkedList animals = new LinkedList();
animals.add("Elephant");
animals.add("Tiger");
System.out.println("The list is:" + animals);
list.add("Lion");
// printing the new list
System.out.println("The new List is:" + animals);
}
}
Output:
The list is:[Elephant, Tiger] The new List is:[Elephant, Tiger, Lion]
Pushing an element to the LinkedList using push()
Syntax: LinkedListObject.push(E e)
import java.util.LinkedList;
public class PushExample {
// Main method
public static void main(String[] args)
{
LinkedList<String> animals = new LinkedList<>();
animals.push("Elephant");
animals.push("Tiger");
animals.push("Lion");
// Printing the complete stack.
System.out.println(animals);
}
}
Output:
[Lion, Tiger, Elephant]
Popping an element from LinkedList using pop()
Syntax: LinkedListObject.pop()
import java.io.*;
import java.util.LinkedList;
public class LinkedListExample {
public static void main(String args[]) {
LinkedList animals = new LinkedList();
/ Pushing an element in the stack
animals.push("Elephant");
// Pushing an element in the stack
animals.push("Tiger");
// Pop an element from stack
String s = animals.pop();
System.out.println(s);
// Pushing an element in the stack
animals.push("Lion");
// Printing the complete stack.
System.out.println(animals);
}
}
Output:
Elephant [Elephant, Lion]
Removing an element from LinkedList using remove()
Syntax: LinkedList.remove()
import java.io.*;
import java.util.LinkedList;
public class LinkedListExample {
public static void main(String args[])
{
LinkedList<String> animals = new LinkedList<String>();
animals.add("Elephant");
animals.add("Tiger");
animals.add("Lion");
System.out.println("LinkedList:" + animals);
// Remove the head using remove()
animals.remove();
// Print the final list
System.out.println("Final LinkedList:" + animals);
}
}
Output:
LinkedList:[Elephant, Tiger, Lion] Final LinkedList:[Tiger, Lion]
Clearing a linked list using clear()
import java.io.*;
import java.util.LinkedList;
public class LinkedListExample {
public static void main(String args[])
{
LinkedList<String> animals = new LinkedList<String>();
animals.add("Elephant");
animals.add("Tiger");
animals.add("Lion");
System.out.println("Before clear:" + animals);
animals.clear();
System.out.println("After clear: " + animals);
// Adding elements after clearing the list
animals.add("Elephant");
animals.add("Tiger");
animals.add("Lion");
System.out.println("After adding elements to empty list:" + animals);
}
}
Output:
Before clear:[Elephant, Tiger, Lion] After clear: [] After adding elements to empty list:[Elephant, Tiger, Lion]
Checking whether an element exists in a LinkedList using contains()
Syntax: LinkedList.contains(Object element)
import java.io.*;
import java.util.LinkedList;
public class LinkedListExample {
public static void main(String args[]) {
LinkedList<String> animals = new LinkedList<String>();
animals.add("Elephant");
animals.add("Tiger");
animals.add("Lion");
System.out.println("\nIs 'Lion' in the linkedlist: "
+ animals.contains("Lion"));
System.out.println("Is'Cat' in the linkedlist: "
+ animals.contains("Cat"));
}
}
Output:
Is 'Lion' in the linkedlist: true Is 'Cat' in the linkedlist: false
Getting the size of a LinkedList using size()
Syntax: LinkedList.size()
import java.io.*;
import java.util.LinkedList;
public class LinkedListExample {
public static void main(String args[])
{
LinkedList<String> animals = new LinkedList<String>();
animals.add("Elephant");
animals.add("Tiger");
animals.add("Lion");
System.out.println("The size of the linked list is: "
+ animals.size());
}
}
Output:
The size of the linked list is: 3
How to loop through linked list
There are 5 ways:
- For Loop
- Enhanced For Loop
- While Loop
- Iterator
- Collection’s stream() util(Java 8)
For Loop
LinkedList<String> linkedList = new LinkedList<>();
for (int i = 0; i < linkedList.size(); i++) {
System.out.println(linkedList.get(i));
}
Enhanced for loop
for (String temp : linkedList) {
System.out.println(temp);
}
While loop
int i = 0;
while (i < linkedList.size()) {
System.out.println(linkedList.get(i));
i++;
}
Iterator
Iterator<String> iterator = linkedList.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
collection stream() util(Java 8)
linkedList.forEach((temp) -> {
System.out.println(temp);
});