This Tutorial Explains What is a Linked List Data Structure in Java and How to Create, Initialize, Implement, Traverse, Reverse and Sort a Java Linked List:
In Java, a LinkedList is a data structure that stores elements in a non-contiguous location. It is a linear data structure.
Each data item is called a ‘Node’ and each node has a data part and an address part. The address part stores the link to the next node in the LinkedList.
=> Visit Here To See The Java Training Series For All.
Table of Contents:
LinkedList In Java
Given below is the general Layout of LinkedList:
As shown in the above representation of LinkedList, each item in the LinkedList is the “Node”. Each node has two parts, the first part stores the data and the second part has a reference or pointer or address of the next node in the LinkedList.
This arrangement is necessary as the data in LinkedList is stored in non-contiguous locations, unlike Arrays.
The “Head” of the LinkedList is a pointer that contains the address of the first element in the LinkedList. The last node in the LinkedList is the tail. As shown in the figure above, the address part of the last node in the LinkedList is set to ‘Null’ indicating the end of the LinkedList.
The above diagram represents a “Singly-linked List” that stores the address of only the next node in the LinkedList.
There is another version known as “Doubly Linked List” whose each node has three parts:
- Address or reference or pointer to the previous element in the LinkedList.
- Data part
- Address or reference or pointer to the next element in the LinkedList.
The previous address of the first element in the LinkedList will be set to Null while the next pointer of the Last element in the LinkedList is set to Null.
Representation Of Doubly Linked List:
As shown in the above representation, each node in the doubly linked list has pointers to its previous and next node (thus represented without arrows). The previous pointer of the first node points to null while the next pointer of the last node points to null.
In this LinkedList tutorial, we will deal mostly with the singly linked list. We will discuss the doubly linked list in our next tutorial.
Java LinkedList Class
In Java, the linked list is implemented by the “LinkedList” class. This class belongs to the “java.util” package. The LinkedList class implements the List and Deque interfaces and inherits the AbstractList class.
Given below is the class hierarchy of the LinkedList class.
The above diagram shows the hierarchy of the LinkedList class. As shown, LinkedList class implements the List and Deque interfaces.
As already mentioned, LinkedList class is a part of the “java.util” package. Hence you should be able to use the LinkedList class in your program by including one of the following statements in your program.
import java.util.*;
Or
import java.util.LinkedList;
So based on the above hierarchy, a typical definition of LinkedList class is as follows:
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, Serializable
Enlisted below are some of the characteristics of the LinkedList class that you should remember:
- This class is not synchronized.
- It allows duplicate values.
- Retains the insertion order.
- As elements are not required to be shifted while moving, the manipulation of elements in it is faster.
- This class can be used to implement a stack, queue, and list.
How To Create A Linked List In Java
Before we move on to creating a linkedlist in Java, let’s first discuss a linked list node in Java.
As already discussed, a linked list consists of nodes. Thus in Java, we can represent a LinkedList as a class with its Node as a separate class. Hence this class will have a reference to the Node type.
This is shown as below:
class LinkedList { Node head; // list head //node - linkedlist class Node { int data; Node next; Node(int d) { data = d; } //constructor to create a new node } }
To create an object of type LinkedList, there are two main constructors as follows:
#1) LinkedList()
The general syntax for this constructor is:
LinkedList<type> linkedList = new LinkedList<>();
The above statement creates an empty LinkedList.
For example,
LinkedList<Integer> l_list = new LinkedList<>();
This will create an empty linked list named l_list.
#2) LinkedList(Collection c)
The general syntax is:
LinkedList<type> linkedList = new LinkedList<> (Collection<? extends E> c);
The above statement creates a LinkedList with elements from the collection c as its initial elements.
Like other list data structures that we have already seen, the linked list can also be initialized using the add method, Arrays.asList () method or by using the constructor with the collection as an argument.
Linked List Implementation In Java
Given below is a simple example of a LinkedList data structure in Java. In this example of implementation, we will use the add method and asList method to initialize the LinkedList objects.
import java.util.*; public class Main{ public static void main(String[] args) { //create a LinkedList object and initialize it with Array elements converted to list LinkedList<Integer> intList = new LinkedList<>(Arrays.asList(10,20,30,40,50)); //print the LinkedList just created System.out.println("Contents of first LinkedList: " + intList); //create an empty list LinkedList<String> colorsList = new LinkedList<>(); //add elements to the linkedList using add method. colorsList.add("Red"); colorsList.add("Green"); colorsList.add("Blue"); colorsList.add("Cyan"); colorsList.add("Magenta"); // print the LinkedList System.out.println("\nContents of second LinkedList: " + colorsList); } }
Output:
Contents of first LinkedList: [10, 20, 30, 40, 50]
Contents of second LinkedList: [Red, Green, Blue, Cyan, Magenta]
The above program shows the creation and initialization of the LinkedList. First, we create a LinkedList of type Integer and provide an array of Integers converted to list using the asList method as initial values for the LinkedList.
Next, we create an empty LinkedList of type String and then using the add method, we add values to the LinkedList.
Finally, we display both the LinkedList objects as a string.
Traverse/Print Linked List In Java
To print the contents or carry out any operations on the elements of the LinkedList, you need to traverse through its elements. We have already seen these methods in our previous tutorials. In this section, we will discuss the examples of each with respect to LinkedList.
Using for loop
import java.util.LinkedList; class Main { public static void main(String[] args) { // Create a LinkedList and initialize it LinkedList<String> colorList = new LinkedList<>(); colorList.add("Red"); colorList.add("Green"); colorList.add("Blue"); // Using for loop,print the contents of the LinkedList System.out.println("LinkedList elements using for loop:"); for(int i=0; i < colorList.size(); i++) { System.out.print(colorList.get(i) + " "); } } }
Output:
LinkedList elements using for loop:
Red Green Blue
Using forEach Loop
import java.util.LinkedList; class Main { public static void main(String[] args) { // Create a LinkedList and initialize it LinkedList<String> colorList = new LinkedList<>(); colorList.add("Red"); colorList.add("Green"); colorList.add("Blue"); // Using forEach loop,print the contents of the LinkedList System.out.println("LinkedList elements using forEach loop:"); for(String color:colorList) { System.out.print(color + " "); } } }
Output:
LinkedList elements using forEach loop:
Red Green Blue
Using Iterator
import java.util.*; public class Main{ public static void main(String args[]){ //declare a LinkedList object LinkedList<String> l_list=new LinkedList<String>(); //Add elements to LinkedList l_list.add("Red"); l_list.add("Green"); l_list.add("Blue"); l_list.add("Yellow"); //declare an iterator for the LinkedList Iterator<String> itr=l_list.iterator(); System.out.println("The contents of Linked List:"); //Iterate through the LinkedList using Iterator and print its elements while(itr.hasNext()){ System.out.print(itr.next() + " "); } } }
Output:
The contents of Linked List:
Red Green Blue Yellow
LinkedList Methods
LinkedList class provides API that supports various methods to manipulate the Linked list. We have tabularized the methods in LinkedList API below.
We will discuss the main operations/methods in the following section.
Method | Prototype | Description |
---|---|---|
Add | boolean add (E e) | Add a specified element to the LinkedList |
void add (int index, E element) | Add element at the given index in LinkedList | |
AddAll | boolean addAll (Collection < ? extends E > c) | Adds the elements of given collection c at the end of the LinkedList. |
boolean addAll (int index, Collection < ? extends E > c) | Adds the elements of given collection c at the specified index in the LinkedList | |
addFirst | void addFirst (E e) | Add the given element as the first element to the LinkedList. |
addLast | void addLast (E e) | Append the given element at the end of the list. |
Clear | void clear () | Deletes all the elements from the list. |
Clone | Object clone () | Makes a shallow copy of LinkedList |
Contains | Boolean contains (Object o) | Checks if the list contains specified elements; if yes returns true. |
descendingIterator | Iterator < E > descendingIterator () | Returns a reverse ordered iterator for the LinkedList. |
Element | E element () | Returns the element at the head of the list. |
Get | E get (int index) | Gets the element at the specified index. |
getFirst | E getFirst () | Retrieves the first element in the LinkedList. |
getLast | E getLast () | Retrieves the last element in the LinkedList. |
indexOf | Int indexOf (Object o) | Find the index of the first occurrence of the given elements in the list and return the index. -1 if element not found. |
lastIndexOf | Int lastIndexOf (Object o) | Returns the position of the last occurrence of the given element in the LinkedList;-1 if given element is not present |
listIterator | ListIterator < E > listIterator (int index) | Returns the listIterator from the specified index in the linkedlist. |
Offer | boolean offer (E e) | Adds the given element as the last element (tail) in the LinkedList. |
offerFirst | Boolean offerFirst (E e) | Adds the given element as the first element in the LinkedList. |
offerLast | Boolean offerLast (E e) | Add given element e at the end of the LinkedList. |
Peek | E peek () | Returns the head of the list without removing it. |
peekFirst | E peekFirst () | Returns the first element in the list. returns null if the list is empty. |
peekLast | E peekLast () | Returns the last element or null if the list is empty. It does not delete the element. |
Poll | E poll () | Returns the head of the LinkedList and also removes it. |
pollFirst | E pollFirst () | Returns and deletes the first element in the list; returns null if the list is empty. |
pollLast | E pollLast () | Returns and deletes the last element in the list; returns null if the list is empty. |
Pop | E pop () | Pops the element from the stack representation of LinkedList. |
Push | Void push (E e) | Pushes or inserts an element into the stack representation of the LinkedList. |
Remove | E remove () | Removes and returns the head of the LinkedList. |
E remove (int index) | Deletes the element at the given index from the LinkedList. | |
boolean remove (Object o) | Deletes the first occurrence of the given element from the LinkedList. | |
removeFirst | E removeFirst () | Returns and deletes the first element from the list. |
removeFirstOccurence | boolean removeFirstOccurrence (Object o) | Deletes the first occurrence of the given element from the list when the list is being traversed from head to tail. |
removeLast | E removeLast () | Returns the last element in the LinkedList and also deletes it. |
removeLastOccurence | boolean removeLastOccurrence (Object o) | Removes the last occurrence of the given element from the LinkedList when traversed from head to tail |
Set | E set (int index, E element) | Sets the given element at the given index. Replaces the current element with new. |
Size | Int size () | Returns size or number of elements in the LinkedList |
toArray | Object[] toArray () | Converts the LinkedList to an array containing all list elements in proper sequence |
< T > T [] toArray( T [] a) | Converts LinkedList to an array with runtime type same as argument a. |
The below Java program demonstrates the various methods that we listed above.
import java.util.*; public class Main { public static void main(String args[]) { //create a linked list LinkedList<String> l_list = new LinkedList<String>(); // Add elements to linkedList using various add methods l_list.add("B"); l_list.add("C"); l_list.addLast("G"); l_list.addFirst("A"); l_list.add(3, "D"); l_list.add("E"); l_list.add("F"); //print the linkedList System.out.println("Linked list : " + l_list); //Create and initialize an ArrayList ArrayList<String> aList = new ArrayList<>(); aList.add("H"); aList.add("I"); //add the ArrayList to linkedList using addAll method l_list.addAll(aList); //print the linkedList System.out.println("Linked list after adding ArrayList contents: " + l_list); // use various remove methods to remove elements from linkedList l_list.remove("B"); l_list.remove(3); l_list.removeFirst(); l_list.removeLast(); //print the altered list System.out.println("Linked list after deletion: " + l_list); // use contains method to check for an element in the linkedList boolean ret_value = l_list.contains("G"); //print the results of contains method if(ret_value) System.out.println("List contains the element 'G' "); else System.out.println("List doesn't contain the element 'G'"); // use size methods to return Number of elements in the linked list int size = l_list.size(); System.out.println("Size of linked list = " + size); // Get and set elements from linked list Object element = l_list.get(3); System.out.println("Element returned by get() : " + element); l_list.set(3, "J"); System.out.println("Linked list after change : " + l_list); //convert linkedList to Array using toArray methods String [] list_array = l_list.toArray(new String[l_list.size()]); System.out.println("Array obtained from linked List:" + Arrays.toString(list_array)); } }
Output:
Linked list : [A, B, C, D, G, E, F]
Linked list after adding ArrayList contents: [A, B, C, D, G, E, F, H, I]
Linked list after deletion: [C, D, E, F, H]
List doesn’t contain the element ‘G’
Size of linked list = 5
Element returned by get() : F
Linked list after change : [C, D, E, J, H]
Array obtained from linked List:[C, D, E, J, H]
The above program demonstrates various methods of LinkedList class. First, we declare a LinkedList of type String. Then we use various versions of add method like add, andFirst, addLast, addAll, etc. to populate the LinkedList with values.
Here we can add the element directly at the end of the list or add the element at a specified position in the list.
We also use the addFirst method to add an element at the beginning of the list and addLast to add an element at the end of the list. Then we perform remove operations on the LinkedList like remove, removeFirst, removeLast, etc.
For remove method, we can either specify the element to be removed or we can specify the index or the position in the LinkedList at which the element is to be removed. The methods removeFirst and removeLast remove the first and last element in the list respectively.
Then we search the list for a particular element using the contains method. Next, we use the size() method to retrieve the size or length of the LinkedList. Then we use get /set methods to retrieve the value at a particular index in the list and then replace a value at a specified position in the list.
Finally, we convert the LinkedList to an Array using the toArray method.
Reverse Linked List In Java
To reverse a linked list in Java, we use the “descendingIterator ()” method that returns a reverse iterator for the list. We can then use this iterator to traverse through the list and display elements.
The below program reverses the linked list using the descendingIterator () method.
import java.util.*; public class Main{ public static void main(String args[]){ //create a LinkedList object LinkedList<String> l_list=new LinkedList<String>(); l_list.add("Pune"); l_list.add("Mumbai"); l_list.add("Nagpur"); System.out.println("Linked List : " + l_list); System.out.println("Linked List in reverse order:"); //use descendingIterator method to get a reverse iterator Iterator iter=l_list.descendingIterator(); //traverse the list using iterator and print the elements. while(iter.hasNext()) { System.out.print(iter.next() + " "); } } }
Output:
Linked List : [Pune, Mumbai, Nagpur]
Linked List in reverse order:
Nagpur Mumbai Pune
In the above program, we declare a linked list and then print it. Then we get a reverse iterator and then step through the list using it and display each element. The output shows the linked List contents, first in the order the elements are added and then the output shows the contents in reverse order.
Sort A Linked List In Java
LinkedList class objects can be sorted using Collections.sort () method. This method provides two versions with or without using a comparator. When the Collections.sort () method is called without a comparator, the collection is sorted in the natural order.
When the comparator is used with this method, we can define our own sorting criteria by overriding the compareTo method.
The below Java program sorts a LinkedList using Collections.sort (). Here we sort arrays using natural ordering as well as using a comparator.
import java.util.*; public class Main{ public static void main(String args[]) { // create and initialize the LinkedList object LinkedList<String> l_list = new LinkedList<>(); l_list.add("Jan"); l_list.add("Feb"); l_list.add("Mar"); l_list.add("Apr"); l_list.add("May"); l_list.add("Jun"); //print original unsorted linkedlist System.out.println("Original LinkedList (unsorted): " + l_list); // sort LinkedList with Collecitons.sort() method in natural order Collections.sort(l_list); System.out.println("\nLinkedList (sorted in natural order): " + l_list); // sort LinkedList using Collection.sort() and Comparator in Java Collections.sort(l_list, new Comparator<String>() { @Override public int compare(String s1, String s2) { return s1.length() - s2.length(); } } ); System.out.println("LinkedList (sorted using Comparator): " + l_list); } }
Output:
Original LinkedList (unsorted): [Jan, Feb, Mar, Apr, May, Jun]
LinkedList (sorted in natural order): [Apr, Feb, Jan, Jun, Mar, May]
LinkedList (sorted using Comparator): [Apr, Feb, Jan, Jun, Mar, May]
Remove Duplicates
To remove duplicates, you need to traverse each node and compare it with the next node. If both nodes are the same then we skip one node and move to the next.
In this manner, after traversing each and every node and getting rid of duplicate nodes, we will get the resultant list that is without any duplicate elements.
Given below is a Java program to remove duplicates.
class LinkedList_Duplicate { //A class to represent node in linkedlist class Node{ int data; Node next; public Node(int data) { this.data = data; this.next = null; } } //Initially the head and tail of the linked list set to null public Node head = null; public Node tail = null; //add a new node to the linkedlist public void addNode(int data) { //Create new node Node newNode = new Node(data); //If list is empty set head and tail to new node if(head == null) { head = newNode; tail = newNode; } else { // add newNode after the tail tail.next = newNode; //newNode is now the tail or last element tail = newNode; } } //scans the linkedlist and removes duplicate nodes public void removeDuplicateNodes() { //Head is the current node Node current = head, index = null, temp = null; //head = null means list is empty if(head == null) { return; } //traverse through the list else { while(current != null){ //temp node points to previous node to index. temp = current; //Index will point to node next to current index = current.next; while(index != null) { //Check if current node's data is equal to index node's data if(current.data == index.data) { //since node is duplicate skip index and point to next node temp.next = index.next; } else { //Temp will point to previous node of index. temp = index; } index = index.next; } current = current.next; } } } //print the linked list public void print() { //Node current will point to head Node current = head; if(head == null) { System.out.println("List is empty"); return; } while(current != null) { //Print each node by incrementing pointer System.out.print(current.data + " "); current = current.next; } System.out.println(); } }class Main{ public static void main(String[] args) { LinkedList_Duplicate l_List = new LinkedList_Duplicate(); //Add data to the list l_List.addNode(1); l_List.addNode(1); l_List.addNode(2); l_List.addNode(3); l_List.addNode(5); l_List.addNode(2); l_List.addNode(1); l_List.addNode(1); //print the original list System.out.println("Original Linkedlist: "); l_List.print(); //Removes duplicate nodes l_List.removeDuplicateNodes(); //print the altered list without duplicates System.out.println("LinkedList after removing duplicates: "); l_List.print(); } }
Output:
Original Linkedlist:
1 1 2 3 5 2 1 1
LinkedList after removing duplicates:
1 2 3 5
In the above program, we have a linked list class created to remove duplicates. We also have a class to define each node. In other words, the nodes in the list are the objects of this class node. We have a method to add the node to a linked list.
Then in the removeDuplicate method, we traverse through each node in the linked list starting from the head and compare each subsequent node for the duplicate. If a duplicate is found, we skip that node and proceed to the next node.
This way the ist is built by skipping the duplicate nodes and the changed list is printed using the print () method.
Circular Linked List In Java
A circular linked list is a list that has its tail or last node connected back to the head or the first node.
The below diagram shows the Circular Linked List In Java.
As shown in the above diagram, the address part of the last node or tail of the linked list is not set to null. Instead, it points back to the first node or head of the list thus forming a circular linked list.
The below program implements a circular linked list wherein we have to manipulate individual nodes of the linked list.
class CircularLinkedList { //Node definition for circular linked list public class Node{ int data; Node next; public Node(int data) { this.data = data; } } //Initially head and tail pointers point to null public Node head = null; public Node tail = null; //add new node to the circular linked list public void add(int data){ //Create new node Node newNode = new Node(data); //check if list is empty if(head == null) { //head and tail point to same node if list is empty head = newNode; tail = newNode; newNode.next = head; } else { //tail points to new node if list is not empty tail.next = newNode; //New node becomes new tail. tail = newNode; //tail points back to head tail.next = head; } } //Display the nodes in circular linked list public void displayList() { Node current = head; if(head == null) { System.out.println("The List is empty"); } else { System.out.println("Circular linked list nodes: "); do{ //Print each node of the linked list System.out.print(current.data + " "); current = current.next; }while(current != head); System.out.println(); } } } class Main{ public static void main(String[] args) { //create a CircularLinkedList object CircularLinkedList c_list = new CircularLinkedList(); //Add data to the list c_list.add(10); c_list.add(20); c_list.add(30); c_list.add(40); //Display the nodes in circular linked list c_list.displayList(); } }
Output:
Circular linked list nodes:
10 20 30 40
Java 8 LinkedList
Though there are no more features added specifically to LinkedList class in Java 8, it still introduced streams to manipulate data.
The below program shows the use of Java 8 stream to display LinkedList.
import java.util.LinkedList; import java.util.List; public class Main { public static void main(String[] args) { //create a LinkedList and initialize it to values List<String> colorsList = new LinkedList<>(); colorsList.add("Red"); colorsList.add("Green"); colorsList.add("Blue"); colorsList.add("Cyan"); colorsList.add("Magenta"); //convert List to stream & print it System.out.println("The contents of LinkedList:"); colorsList.stream().forEach(System.out::println); } }
Output:
The contents of LinkedList:
Red
Green
Blue
Cyan
Magenta
Frequently Asked Questions
Q #1) When is the Linked List used in Java?
Answer: As it is faster than collections like ArrayList in modification operations, it should be used in applications that require frequent addition/deletion operations. For applications that have mostly read-only data, ArrayList or similar collections can be used.
Q #2) What is ListNode?
Answer: A ListNode is a basic class associated with a linked list in Java and represents information associated with a single element or a node. Each ListNode consists of data and a pointer or reference to the next element.
Q #3) Does the Linked List allow null values?
Answer: Yes, the linked list allows any number of null values.
Q #4) What are the Advantages of a Linked List?
Answer: Some of the advantages are:
- Manipulation operations like addition, deletion are faster in it.
- There is no need to pre-allocate memory for a linked list and thus it results in efficient memory utilization.
- It provides faster access time and without additional overhead for memory, and can be expanded in constant time.
- It is a dynamic data structure
- Grows and shrinks at run time depending on values added or deleted.
Q #5) What is the Application of the Linked List?
Answer: It is used mostly in the following applications:
- To implement ‘undo’ functionality in software like MS-Word, Photoshop, etc.
- To implement data structures like stack and queue.
- We can also implement graphs using a linked list.
- For bucket hashing, each bucket can be implemented as a linked list.
Q #6) What are the Limitations of a Linked List?
Answer: Some of the limitations are:
- With an additional pointer to hold the reference of the next element in each node, memory utilized is much more than arrays.
- This is a strictly sequentially accessed data structure hence nodes of the linked list must always be read from the beginning.
- It is difficult to traverse it backward especially the singly-linked lists.
- Since the nodes are stored in non-contiguous locations, the time required for access can be high.
Conclusion
In this tutorial, we have learned the basic linked list data structure. Then we moved on java.util.LinkedList class provided in Java. We discussed this class in detail including its constructors, methods, etc.
We also have discussed some special operations related to Linked lists like sorting, reversing a list, removing duplicates, circular linked list, etc.
In our next tutorial, we will discuss specific features of the doubly linked list.
=> Check Out The Complete Java Training Guide Here.