A linear data structure used to store the elements in contiguous locations is called a Linked List in Java. It has addresses and pointers that are used to link the elements, and each element in the linked list consists of two parts, namely the data part and the address part. The data part is the value of the element, and the address part consists of the pointers and addresses that are used to link the elements. Each element in the list is called a node.
The syntax to define a Linked list in Java is as follows:
LinkedList <data_type> linkedlistname = new LinkedList<data_type>();
where data_type is the data type of the elements to be stored in the linked list,
linkedlistname is the name of the .linked list.
The usage of a linked list allows dynamic insertion and deletion of elements into the linked list. Because of this feature, linked lists are preferred over arrays.
Working Of Linked List in Java Is As Follows:
- A linked list in Java is a dynamic data structure whose size increases as you add the elements and decreases as you remove the elements from the list.
- The elements in the linked list are stored in containers.
- The list holds the link to the first container.
- All the containers have a link to the next container in the list.
- Whenever you add an element to the list using add() operation, a new container is created, and this container is linked to the other containers in the list.
The Hierarchy of Linked Lists Is Explained as Follows:
The linked list extends to the Abstract Sequential List, which in turn implements a list that extends the collection interface, which further extends the Iterable interface. The Linked list implements the deque interface which extends the Queue interface, which then extends the collection interface, which further extends the Iterable interface.
There Are Various Types of Linked List. They Are:
- Singular Linked List
- Doubly Linked List
- Circular Linked List
Singular Linked List
- The type of linked list consisting of a sequence of nodes where each node consists of data and a link to the next node, that can be traversed from the first node of the list (also called as head) to the last node of the list (also called as Tail) and is unidirectional is called Singly Linked list.
- The above figure demonstrates a singly linked list.
- Each element in the list is called a node.
- A node is made of two parts, namely data and pointer.
- Data is the data stored in the and the pointer is the next node in the list.
- The first node in the list is referred to as the head of the list.
- The last node in the list is the tail, and it points to NULL.
The syntax to define a node in a singular linked list is as follows:
public class SinglyLinkedList
{
class Node
{
int data;
Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
}
Example 1:
Java program to demonstrate the creation of a singly Linked list in Java and insertion of elements into the list and then display the elements of the list as the output on the screen:
public class SinglyLinkedList
{
//defining a node in singly linked list
class Node
{
int data;
Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
//defining the head and tail of a singly linked list
public Node head = null;
public Node tail = null;
//defining insert() function to add a node to the list
public void insert(int data)
{
//Creating a new node
Node newNode = new Node(data);
//checking of the list is empty
if(head == null)
{
//if the given list is empty, making the two nodes head and tail to point to the newly created node newNode
head = newNode;
tail = newNode;
}
else
{
//otherwise the newNode will be added after tail so that the next pointer of tail points to the newNode
tail.next = newNode;
tail = newNode;
}
}
//defining displaylist() function to display the data in the list
public void displaylist()
{
//Pointing the head to the node called current
Node current = head;
if(head == null)
{
System.out.println("The given list is empty");
return;
}
System.out.println("The data in the given list are: ");
while(current != null)
{
//printing each data in the list and next pointer pointing to the next node
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args)
{
//creating a new list
SinglyLinkedList newList = new SinglyLinkedList();
//Adding data to the list by calling the insert function
newList.insert(10);
newList.insert(30);
newList.insert(50);
newList.insert(70);
newList.insert(100);
//Displaying the data in the list by calling displaylist() function
newList.displaylist();
}
}
The output of the above program is shown in the snapshot below:
Doubly Linked List
- This type of a linked list consists of a sequence of nodes where each node consists of data and two pointers, namely the previous pointer pointing to the previous node and the subsequent pointer that points to the next node that is part of the list. This can be traversed from the first node of the list to the last node of the list and vice versa, and this is called Doubly Linked list.
- The above figure demonstrates a doubly linked list.
- Data is the data stored in the node and each node consists of two pointers namely the previous pointer and the next pointer.
- The previous pointer points, as the name suggests to the previous node that is part of the list.
- The pointer after the current one, points to the next node on the list.
The syntax to define a node in a doubly linked list is as follows:
public class DoublyLinkedList
{
class Node
{
int data;
Node previous;
Node next;
public Node(int data)
{
this.data = data;
}
}
}
Example 2:
Java program to demonstrate the creation of a doubly Linked list in Java and insertion of elements into the list and then display the elements of the list as the output on the screen:
public class DoublyLinkedList
{
//defining a node in a doubly linked list
class Node
{
int data;
Node previous;
Node next;
public Node(int data)
{
this.data = data;
}
}
//defining the head and tail of the doubly linked list and assigning it to Null
Node head, tail = null;
//defining insert() function to insert the data into the list
public void insert(int data)
{
//creating a new node called newNode
Node newNode = new Node(data);
//checking if the given list is empty
if(head == null)
{
//if the lists empty, making both head and tail of the list to point to the newNode
head = tail = newNode;
//the previous pointer of head will point to null
head.previous = null;
//the next pointer of tail will point to the null
tail.next = null;
}
else
{
//otherwise the next pointer of tail will point to the newNode
tail.next = newNode;
//the previous pointer of the newNode will point to the tail
newNode.previous = tail;
//and the newNode is made the tail of the list
tail = newNode;
//and the next pointer of tail is made to point to null indicating it is the last node of the list
tail.next = null;
}
}
//defining displaylist() function to display the data in the list
public void displaylist()
{
//defining a node called current and assigning the head of the list to it
Node current = head;
//checking if the head/list is empty
if(head == null)
{
System.out.println("The given list is empty");
return;
}
//otherwise printing each element in the list
System.out.println("The data in the doubly linked list are: ");
while(current != null)
{
//printing each data in the list and next pointer pointing to the next node
System.out.print(current.data + " ");
current = current.next;
}
}
public static void main(String[] args)
{
//defining a new doubly linked list
DoublyLinkedList newList = new DoublyLinkedList();
//inserting data into the list by calling insert() function
newList.insert(10);
newList.insert(30);
newList.insert(50);
newList.insert(70);
newList.insert(100);
//displaying the data in the list by calling displaylist() function
newList.displaylist();
}
}
The output of the above program is shown in the snapshot below:
Circular Linked List
It is the type of linked list consisting of a sequence of nodes where each node consists of data and a link to the next node and the last node in the list (also called as tail) that points to the first node in the list (also called as head) is called as Circular Linked List.
The figure above demonstrates a Circular linked list.
The syntax to define a node in a circular linked list is as follows:
public class CircularLinkedList
{
public class Node
{
int data;
Node next;
public Node(int data)
{
this.data = data;
}
}
}
Example 3:
Java program to demonstrate the creation of a circular Linked list in Java and insertion of elements into the list and then display the elements of the list as the output on the screen:
public class CircularLinkedList
{
//defining a node in circular linked list
public class Node
{
int data;
Node next;
public Node(int data)
{
this.data = data;
}
}
//defining the head and tail of the circular linked list and assigning it to Null
public Node head = null;
public Node tail = null;
//defining insert() function to insert the data into the list
public void insert(int data)
{
//creating a new node called newNode
Node newNode = new Node(data);
//checking if the given list is empty
if(head == null)
{
//If list is empty, making both the head and tail point to the newNode and the next pointer of newNode to head
head = newNode;
tail = newNode;
newNode.next = head;
}
else
{
//otherwise the next pointer of the tail is made the newNode
tail.next = newNode;
//and the newNode is made the tail of the list
tail = newNode;
//and the next pointer of the tail is made to point to the head of the list as it is a circular linked list
tail.next = head;
}
}
//defining displaylist() function to display the data in the list
public void displaylist()
{
//defining a node called current and assigning the head of the list to it
Node current = head;
//checking if the head/list is empty
if(head == null)
{
System.out.println("The given list is empty");
}
else
{
//otherwise printing each element in the list
System.out.println("The data in the circular linked list are: ");
do{
//printing each data in the list and next pointer pointing to the next node
System.out.print(" "+ current.data);
current = current.next;
}
while(current != head);
System.out.println();
}
}
public static void main(String[] args)
{
//defining a new circular linked list
CircularLinkedList newList = new CircularLinkedList();
//inserting data into the list by calling insert() function
newList.insert(10);
newList.insert(30);
newList.insert(50);
newList.insert(70);
newList.insert(100);
//displaying the data in the list by calling displaylist() function
newList.displaylist();
}
}
The output of the above program is shown in the snapshot below:
Various operations can be performed on the elements in a Linked list in Java. Those operations are:
1. Insert Elements to the List
The elements can be inserted into a given list at the beginning of the list, at the end of the list, or at a specified position of the list.
Insertion at the Beginning of the List
- A new node to store the data is created
- The next pointer of the new node is made to point to the head of the list
- The new node is then made the head of the list
Insertion at the End of the List
- A new node to store the data is created
- The entire list is traversed to reach the last node of the list
- The next pointer of the last node is made to point to the new node of the list making the new node the last node of the list
Insertion at the Specified Position of the List
- A new node to store the data is created
- The list is traversed to reach the node which is just before the node at the specified position of the list
- The next pointers are made to point to the new node of the list making the new node one of the nodes in the list
2. Delete Elements From the List
The elements can be deleted from a given list from the beginning of the list, from the end of the list, or from a specified position of the list.
Deletion From the Beginning of the List
- The head of the list is made to point to the second node of the list
Deletion From the End of the List
- The entire list is traversed to reach the second last node of the list
- The next pointer of the second last node is made to point to null
Deletion From a Specified Position of the List
- The list is traversed to reach the node which is just before the node to be deleted at the specified position of the list
- The next pointers are changed to remove the node at the specified position of the list
Example 4:
Java program to demonstrate the insertion of an element at the beginning of the list, insertion at the end of the list, insertion at a specified position of the list, deletion from the beginning of the list, deletion from the end of the list and deletion from the specified position of the list and then display the elements of the list as the output on the screen:
public class LinkedList
{
//defining a node in singly linked list
class Node
{
private int data;
private Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
public Node head = null;
//defining a method to insert an element at the beginning of the list
public void insertionatthebeginning(int data)
{
System.out.println("Adding a node at the beginning of the list with data " + data + "\n");
//creating a new node called newNode
Node newNode = new Node(data);
//checking if the given list is empty
if (this.head == null)
{
//if the list is empty, making the newNode as the head of the list
this.head = newNode;
}
else
{
//otherwise the next pointer of the newNode is made the head
newNode.next = this.head;
//and then making the newNode as the head of the list
this.head = newNode;
}
}
//defining a method to insert an element at the end of the list
public void insertionattheend(int data)
{
System.out.println("Adding a node at the end of the list with data " + data + "\n");
//creating a new node called newNode
Node newNode = new Node(data);
//checking if the given list is empty
if (this.head == null)
{
//if the list is empty, making the newNode as the head of the list
this.head = newNode;
}
else
{
//otherwise create a new node called current and assign head of the list to the current node
Node current = this.head;
//and traverse till the end of the list
while (current.next != null)
{
//and assign each node to the current node till the last node is reached
current = current.next;
}
//assigning the next pointer of the last node to the newNode
current.next = newNode;
}
}
//defining a method to insert an element at the specified position of the list
public void insertionatpos(int position, int data)
{
System.out.println("Adding a node at the specified position " + position + " of the list with data " + data + "\n");
//creating a new node called newNode
Node newNode = new Node(data);
//creating two new nodes called current and previous and then assigning head of the list to these two nodes
Node current = this.head;
Node previous = this.head;
//checking if the element to be inserted at position 1
if (position == 1)
{
//then the next pointer of the new node is made to point to the head
newNode.next = head;
//and the new node is made the head of the list
this.head = newNode;
return;
}
//otherwise the entire list is traversed until the specified position is found by assigning current to previous and next pointer of current to current
while (current.next != null && position > 0)
{
previous = current;
current = current.next;
}
//then the new node is inserted at the next pointer of previous node
previous.next = newNode;
// and the next pointer of new node is made the current node
newNode.next = current;
}
//defining a method to delete an element from the beginning of the list
public void deletionfromthebeginning()
{
System.out.println("deleting a node from the beginning of the list: \n");
//checking if the given list is empty
if (this.head == null)
{
System.out.println("The given list is empty.\n");
}
else
{
//otherwise removing head and making the first node as the head of the list
head = head.next;
}
}
//defining a method to delete an element from the end of the list
public void deletionfromtheend()
{
System.out.println("Deleting a node from the end of the list: \n");
//checking if the given list is empty
if (this.head == null)
{
System.out.println("The given list is empty.\n");
}
else
{
//otherwise creating a new node called current and assigning head to it to traverse through the list to reach the second last element of the list and then making its next pointer to point to null
Node current = this.head;
while (current.next.next != null)
{
current = current.next;
}
current.next = null;
}
}
//defining a method to delete an element from the specified position of the list
public void deletionfrompos(int position)
{
System.out.println("Deleting a node from the specified position " + position + "\n");
//checking if the given list is empty
if (this.head == null)
{
System.out.println("The given list is empty.\n");
}
//checking if the given position is 0
else if(position == 0)
{
//removing the head of the list and making the first node of the list as the head of the list
head = head.next;
}
else
{
//otherwise creating a new node called current and making it head of the list
Node current = head;
//then traversing through the list
for(int i =0; current!=null && i < position -1; i++)
{
current = current.next;
//checking if the element is not present at all in the list
if(current == null || current.next == null)
{
System.out.println("The element is not present at the specified position.\n");
}
//removing the node at the specified position of the list and assigning the next pointer of the current node to point to the next to next node
Node temp = current.next.next;
current.next = temp;
}
}
}
//defining displaylist() function to display the data in the list
public void displaylist()
{
//checking if the head/list is empty
if (this.head == null)
{
System.out.println("The given list is empty.\n");
}
else
{
//otherwise printing each element in the list
System.out.println("The elements of the Singly Linked List are : \n");
Node current = this.head;
while (current != null)
{
//printing each data in the list and next pointer pointing to the next node
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("NULL\n");
}
}
public static void main(String[] args)
{
//defining a new linked list
LinkedList newlist = new LinkedList();
//displaying the elements of the list before performing any operation on the list
System.out.println("The elements of the singly linked list before insertion operation are: \n");
newlist.displaylist();
//performing various operations on the list and then displaying the elements of the list
newlist.insertionatthebeginning(1);
newlist.displaylist();
System.out.println("\n");
newlist.insertionatthebeginning(2);
newlist.displaylist();
System.out.println("\n");
newlist.insertionattheend(8);
newlist.displaylist();
System.out.println("\n");
newlist.insertionattheend(9);
newlist.displaylist();
System.out.println("\n");
newlist.insertionatpos(2,3);
newlist.displaylist();
System.out.println("\n");
newlist.insertionatpos(3,4);
newlist.displaylist();
System.out.println("\n");
newlist.insertionatpos(4,5);
newlist.displaylist();
System.out.println("\n");
newlist.deletionfromthebeginning();
newlist.displaylist();
System.out.println("\n");
newlist.deletionfromtheend();
newlist.displaylist();
System.out.println("\n");
newlist.deletionfrompos(3);
newlist.displaylist();
System.out.println("\n");
}
}
The output of the above program is shown in the snapshot below:
There are two constructors associated with the Linked List in Java. They are:
-
LinkedList()
An empty linked list can be created using the constructor LinkedList().
The syntax to create an empty linked list using LinkedList() constructor is as follows:
LinkedList listname = new LinkedList();
Example 5:
Java program to demonstrate the creation of an empty linked list using LinkedList() constructor:
public class LinkedList
{
//defining a node in a linked list
class Node
{
int data;
Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
//defining the head and tail of a linked list
public Node head = null;
public Node tail = null;
//defining insert() function to add a node to the list
public void insert(int data)
{
//Creating a new node
Node newNode = new Node(data);
//checking of the list is empty
if(head == null)
{
//if the given list is empty, making the two nodes head and tail to point to the newly created node newNode
head = newNode;
tail = newNode;
}
else
{
//otherwise the newNode will be added after tail so that the next pointer of tail points to the newNode
tail.next = newNode;
tail = newNode;
}
}
//defining displaylist() function to display the data in the list
public void displaylist()
{
//Pointing the head to the node called current
Node current = head;
if(head == null)
{
System.out.println("The given list is empty");
return;
}
System.out.println("The data in the given list are: ");
while(current != null)
{
//printing each data in the list and next pointer pointing to the next node
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args)
{
//creating a new list
LinkedList newList = new LinkedList();
//Adding data to the list by calling the insert function
newList.insert(10);
newList.insert(30);
newList.insert(50);
//Displaying the data in the list by calling displaylist() function
newList.displaylist();
}
}
The output of the above program is shown in the snapshot below:
-
LinkedList(Collection C)
To create a list made of all the elements from a specific collection C, you need to make use of the constructor LinkedList(Collection C).
The syntax to create the linked list formed by the elements of a specific collection using LinkedList(Collection C) constructor is as follows:
LinkedList listname = new LinkedList(c);
Example 6:
Java program to demonstrate the creation of an empty linked list using LinkedList(Collection C) constructor:
import java.util.*;
import java.util.ArrayList;
import java.util.LinkedList;
//defining a class called demo
public class demo
{
//main method is called
public static void main(String[] args)
{
defining a string arraylist collection
ArrayList<String> collect = new ArrayList<String>();
collect.add("Simplilearn");
collect.add("is");
collect.add("Awesome");
//passing the collection as a parameter to the LinkedList constructor
LinkedList List2 = new LinkedList(collect);
//displaying the elements of the list
System.out.println("The new linked list is: " + List2);
}
}
The output of the above program is shown in the snapshot below:
There are several methods associated with a Linked List in Java. Some of them are:
-
add()
The add() method is used to insert elements into the list.
-
addFirst()
The addFirst() method is used to insert elements to the beginning of the list.
-
addLast()
The addLast() method is used to insert elements at the end of the list.
-
remove()
The remove() method is used to remove the elements from the list.
-
removeFirst()
The removeFirst() method is used to remove the elements from the beginning of the list.
-
removeLast()
The removeFirst() method is used to remove the elements from the end of the list.
-
getFirst()
The getFirst() method is used to get the elements from the beginning of the list.
-
getLast()
The getLast() method is used to get the elements from the end of the list.
-
clear()
The clear() method is used to remove all the elements from the list.
-
clone()
A shallow copy of the linked list is returned using clone() method.
-
peek()
The head of the list is retrieved using peek() method.
-
peekFirst()
The first element of the list is retrieved using peekFirst() method.
-
peekLast()
The last element of the list is retrieved using peekLast() method.
-
poll()
The head of the list is retrieved and removed using poll() method.
-
pollFirst()
The first element of the list is retrieved and removed using pollFirst() method.
-
pollLast()
The last element of the list is retrieved and removed using pollLast() method.
-
size()
The number of elements present in the list is returned using size() method.
-
get(int index)
The element present at the position specified by the index is returned using get(int index) method.
-
element()
The head of the list is retrieved but not removed using element() method.
Conclusion
In this article, you looked into the concept of Linked List in Java, types of linked lists through programming examples to demonstrate them and their outputs, constructors, and methods associated with linked lists. Simplilearn offersPost Graduate Program in Full Stack Web Development designed to help you learn everything in Java to kick start your career in Java and this is a very flexible way to acquire skills in Java.
Do you have questions for us? Please leave them in the comments section, and our experts will get back to you on the same, at the earliest. Happy learning!