Hello Friends, In today session we are going to see LinkedList in Java collection, Methods of LinkedList, Hierarchy of LinkedList and Internal working of LinkedList etc.
Table of Contents
What is LinkedList?
LinkedList is a class which implements List and Deque interface. This class present in java.util package.
Features of LinkedList Class
- This class accepts duplicate elements.
- This class maintains insertion order.
- This class is non-synchronized.
- Null value is also accepted by LinkedList.
- In this class, manipulation is faster than ArrayList because no shifting is required.
Hierarchy of LinkedList class
In below image we can see hierarchy of LinkedList class.
Why we used LinkedList?
LinkedList uses the doubly LinkedList to store the elements so when we have insertion and deletion operation then use LinkedList because no more shifting is required in insertion/deletion operation, that is why it is faster than ArrayList.
In the LinkedList, data is stored in the form of Node. Each node has an index starting from 0. Each node also stored the address of previous and next element. In below image you can see.
LinkedList Methods in Java
As we know LinkedList implemented the List and Deque Interface so whatever the methods inside the List and Deque, we can use into LinkedList.
In the previous tutorial we have already discussed List methods. Check below link for List methods.
There are some LinkedList specific methods which I have mentioned below.
- addFirst(Object O) – This method will add the object at the beginning of LinkedList.
- addLast(Object O)- This method will add the object at the last of LinkedList.
- removeFirst() – This method will remove first element from the LinkedList.
- removeLast() – This method will remove last element from the LinkedList.
- getFirst() – This method will get first element from the LinkedList.
- getLast() – This method will get Last element from the LinkedList.
Example 1: Sample code of Add, Remove, AddFirst, AddLast, RemoveLast, getFirst, getLast methods of LinkedList:
package DemoPkg;
import java.util.Iterator;
import java.util.LinkedList;
public class LinkedListExp1 {
public static void main(String[] args) {
LinkedList l= new LinkedList();
l.add("John");
l.add(12);
l.add('A');
l.add(true);
l.add(null);
System.out.println(l);
//remove
l.remove(3); // It will remove 3rd index element. We can also directly pass element which we want
//to remove like - l.remove(true)
System.out.println("After removing 3rd index element:"+l);
//inserting/adding element in the middle of list
l.add(3, "Java");
System.out.println("After adding element at index 3:" + l);
// retriving value
System.out.println("getting element of index 1: "+ l.get(1)); // 12
//Change the value using set method
l.set(4, "Welcome");
System.out.println("After replacing value at index 4th:" + l);
//contains
System.out.println(l.contains("John")); // true
System.out.println(l.contains(13)); // false
// Reading LL elements using for loop//
for(int i=0; i<l.size(); i++) {
System.out.println(l.get(i));
}
// Reading LL elements using Iterator method
Iterator it = l.iterator();
while(it.hasNext()) {
System.out.println(it.next());
}
}
}
Output:
[John, 12, A, true, null]After removing 3rd index element:[John, 12, A, null]
After adding element at index 3:[John, 12, A, Java, null]
getting element of index 1: 12
After replacing value at index 4th:[John, 12, A, Java, Welcome]
true
false
John
12
A
Java
Welcome
John
12
A
Java
Welcome
Example 2: One more example in which we will create one LinkedList and add few elements and after this I will add those elements into another LinkedList using addAll() method. Using removeAll() method we can remove element from List.
Sample Code:
package DemoPkg;
import java.util.LinkedList;
public class LinkedListExp2 {
public static void main(String[] args) {
LinkedList<String> l = new LinkedList<String>();
l.add("Java");
l.add("C");
l.add("C++");
l.add("PHP");
LinkedList new_l = new LinkedList();
new_l.addAll(l);
System.out.println(new_l);
new_l.removeAll(l); // It will remove from new_l list.
System.out.println(new_l);
}
}
Output:
[Java, C, C++, PHP] []Example 3: We can sort the LinkedList using sort() method of Collections class.
package DemoPkg;
import java.util.Collections;
import java.util.LinkedList;
public class LinkedListExp3 {
public static void main(String[] args) {
LinkedList<String> l = new LinkedList<String>();
l.add("Java");
l.add("C");
l.add("C++");
l.add("PHP");
System.out.println("Before sorting " + l);
Collections.sort(l);
System.out.println("After Sorting " + l);
}
}
Output:
Before sorting: [Java, C, C++, PHP]
After Sorting: [C, C++, Java, PHP]
Example 4: Reverse Linked List in java
Using reverseOrder() method of Collections class we can reverse the LinkedList.
Sample Code of Reverse linkedlist in java:
package DemoPkg;
import java.util.Collections;
import java.util.LinkedList;
public class LinkedListExp3 {
public static void main(String[] args) {
LinkedList<String> l = new LinkedList<String>();
l.add("Java");
l.add("C");
l.add("C++");
l.add("PHP");
//LinkedList l = new LinkedList();
System.out.println("Before sorting: " + l);
Collections.sort(l);
System.out.println("After sorting: " + l);
// Reverse LinkedList
Collections.sort(l, Collections.reverseOrder());
System.out.println("After reverse: " + l);
}
}
Output:
Before sorting: [Java, C, C++, PHP]
After sorting: [C, C++, Java, PHP]
After reverse: [PHP, Java, C++, C]
Internal working of LinkedList in Java
LinkedList in Java internally uses node to store added elements. Since LinkedList class is implemented as a doubly LinkedList so each node stores the reference of next nodes as well as previous nodes along with added element.
The Node class from Linked List implementation
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
I hope you have enjoyed this tutorial. Happy Learning 🙂