A Linked List is a linear data structure that stores elements as objects in non-contiguous memory regions. A linked list can be constructed in Java using a custom class or the Collection framework found in Java.util package. This LinkedList class implements the interfaces List, Queue, and Deque.
In Java, a Linked List is a linear data structure that stores elements in contiguous locations. It uses addresses and pointers to connect the items, and each element in the linked list comprises the data component and the address part. The data component contains the element's value, and the address part contains the pointers and addresses needed to connect the elements. Each element in the list is referred to as a node.
In Java, the syntax for defining a linked list is as follows:
LinkedList <data_type> linkedlistname = new LinkedList<data_type>();
where data_type is the data type of the linked list components,
The name of the.linked list is linkedlistname.
Using a linked list enables dynamic addition and deletion of linked list elements. Linked lists are chosen over arrays because of this property.
Working on LinkedList in Java
The following is how a linked list works in Java
In Java, a linked list is a dynamic data structure whose size grows as entries are added and shrinks as they are removed.
Containers hold the elements of the linked list.
The first container is linked in the list.
Each container contains a link to the next container in the list.
When you add an element to the list using the add() function, a new container is produced and linked to the existing containers in the list.
The Hierarchy of Linked Lists in Java
The linked list extends the Abstract Sequential List, which implements a list that extends the collection interface, which extends the Iterable interface even further. The Linked list implements the deque interface, which extends the Queue interface, and the collection interface, which extends the Iterable interface even more.
There are several kinds of linked lists. They are as follows:
Singular Linked List
Doubly Linked List
Circular Linked List
Singular Linked List
A singly Linked list is a sort of linked list that consists of a series of nodes, each of which contains data and a link to the next node and may be browsed unidirectionally from the first node of the list (also known as the head) to the last node of the list (also known as the tail).
The diagram above depicts a singly linked list.
Each element in the list is referred to as a node.
A node is made up of two parts: data and a pointer.
The data is the information, and the pointer is the next node in the list.
The first node in the list is known as the list's head.
The tail is the last node in the list, and it points to NULL.
The following is the syntax for defining a node in a solitary linked list:
{
class Node
{
int data;
Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
}
Example:
Java program that shows how to create a singly linked list in Java, insert entries into the list, and then display the list's elements as an output on the screen:
public class SinglyLinkedList
{
//defining a node in a 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 if the list is empty
if(head == null)
{
//if the given list is empty, make the two nodes' head and tail point to the newly created node newNode
head = newNode;
tail = newNode;
}
else
{
//otherwise, the newNode will be added after the tail so that the next pointer of the tail points to the newNode
tail.next = newNode;
tail = newNode;
}
}
//defining display list() 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 as follows: ");
while(current != null)
{
//printing each data in the list and the 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(20);
newList.insert(40);
newList.insert(60);
newList.insert(80);
newList.insert(100);
//Displaying the data in the list by calling displaylist() function
newList.displaylist();
}
}
Output:
The data in the given list are as follows
20 40 60 80 100
Doubly Linked List
This linked list comprises a series of nodes, each containing data and two pointers, the previous pointer pointing to the previous node and the subsequent pointer going to the next node on the list. This is known as a Doubly Linked list because it can be traversed from the first node of the list to the last node and vice versa.
· The diagram above depicts a double-linked list.
· Data is the information stored in the node, and each node comprises two pointers: the previous pointer and the next pointer.
· The previous pointer, as the name implies, links to the previous node in the list.
· The pointer immediately following the current one points to the next node in the list.
The following is the syntax for defining a node in a doubly linked list:
public class DoublyLinkedList
{
class Node
{
int data;
Node previous;
Node next;
public Node(int data)
{
this.data = data;
}
}
}
Example:
Java program that shows how to create a doubly linked list in Java, insert members into the list, and then display the list's elements as an 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 are empty, make both the head and tail of the list point to the newNode
head = tail = newNode;
//the previous head pointer will point to the null
head.previous = null;
//the next tail pointer will point to the null
tail.next = null;
}
else
{
//otherwise, the next pointer of the 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 the 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 as follows: ");
while(current != null)
{
//printing each data in the list and the 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 the insert() function
newList.insert(40);
newList.insert(60);
newList.insert(80);
newList.insert(100);
newList.insert(120);
//displaying the data in the list by calling displaylist() function
newList.displaylist();
}
}
Output:
The data in the doubly linked list are as follows:
40 60 80 100 120
Circular Linked List
Circular Linked List is a sort of linked list that consists of a sequence of nodes, each of which contains data and a link to the next node and the last node in the list (also known as the tail) that points to the first node in the list (also known as head).
The diagram above depicts a circular linked list.
The following is the syntax for defining a node in a circular linked list:
public class CircularLinkedList
{
public class Node
{
int data;
Node next;
public Node(int data)
{
this.data = data;
}
}
}
Example:
Java program that shows how to create a circular linked list in Java, insert members into the list, and then display the list's elements as an output on the screen:
public class CircularLinkedList
{
//defining a node in a 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 the list is empty, make 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 mentioned below: ");
do{
//printing each data in the list and the 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 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();
}
}
Output:
The data in the circular linked list are mentioned below:
10 30 50 70 100
Elements in a Linked list in Java
In Java, you may execute various actions on the elements of a linked list. These are the operations:
Inserting Elements to the List
The elements can be put into a given list at the beginning, end, or specific location.
Insertion at the Start of the List
· A new node is established to store the data.
· The new node's next pointer is set to refer to the top of the list.
· The new node is subsequently promoted to the top of the list.
Insertion at the List's End
· A new node is established to store the data.
· To reach the final node, the complete list is explored.
· The last node's next pointer is changed to point to the new node of the list, making the new node the list's final node.
Insertion at the Specified Position in the List
· A new node is established to store the data.
· The list is traversed to reach the node immediately before the node at the provided place in the list.
· The following pointers are set to point to the new node of the list, making it one of the nodes in the list.
Deleting Elements From the List
Elements can be deleted from a given list starting at the beginning, ending at the end, or starting at a specific location in the list.
Deleting from the List's Beginning
· The list's head is made to point to the second node on the list.
Deleting from the List's End
· To reach the list's second-to-last node, the complete list is traversed.
· The second-to-last node's next pointer is set to null.
Deleting from a Specific Position on the List
· The list is traversed to find the node immediately preceding the node to be deleted at the specified location in the list.
· The pointers after that are modified to remove the node at the specified place in the list.
Constructors in LinkedLis
There are two constructors associated with the Linked List in Java. They are:
LinkedList()
The constructor LinkedList() can build an empty linked list.
The following is the syntax for creating an empty linked list with the LinkedList() constructor
LinkedList listname = new LinkedList();
LinkedList(Collection C)
To produce a list of all the elements from a specific collection C, use the constructor LinkedList(Collection C).
The following is the syntax for creating a linked list created by the members of a specified collection using the LinkedList(Collection C) constructor:
LinkedList listname = new LinkedList(c);
In Java, there are various methods connected with a Linked List. Among them are:
A. add()
To enter elements into a list, use the add() method.
B. addFirst()
The addFirst() method adds elements to the list's beginning.
C. addLast()
To insert elements at the end of a list, use the addLast() method.
D. remove()
To remove elements from a list, use the remove() method.
E. removeFirst()
The removeFirst() method is used to remove elements from the list's beginning.
F. removeLast()
The removeFirst() method is used to remove elements from the list's end.
G. getFirst()
The getFirst() method retrieves elements from the list's beginning.
H. getLast()
The getLast() method retrieves elements from the list's end.
I. clear()
To remove all elements from a list, use the clear() method.
J. clone()
The clone() method returns a shallow copy of the linked list.
K. peek()
The peek() method is used to get the list's head.
L. peekFirst()
The peekFirst() method is used to acquire the first element of the list
M. peekLast()
The peekLast() method is used to acquire the list's last element.
N. poll()
The poll() method retrieves and removes the list's head.
O. pollFirst()
Using the pollFirst() method, the first entry of the list is fetched and removed.
P. pollLast()
Using the pollLast() method, the last element of the list is fetched and removed.
Q. size()
The size() method returns the number of elements in the list.
R. obtain(int index)
The get(int index) method returns the element at the place indicated by the index.
S. element()
Using the element() function, the list's head is retrieved but not removed.
Conclusion
Finally, LinkedList is a sophisticated Java data structure that provides dynamic memory allocation and efficient insertion and deletion operations. It allows for managing collections of pieces that can grow and shrink dynamically, making it useful for various use scenarios.
LinkedList provides constant-time complexity, whether adding or removing elements at the list's beginning or end, making it an excellent choice for building queues or stacks. It also allows for constant-time access to elements in the center of the list, making it helpful in exploring and processing big datasets.
One of the primary advantages of utilizing LinkedList is that, unlike arrays, it does not require contiguous memory allocation, making it suited for handling vast collections of data that may need to be edited or resized regularly. Furthermore, LinkedList enables the simple addition or deletion of members at any point in the list without moving other components, which can be time-consuming in arrays.
However, there are certain disadvantages to using LinkedList. It uses more memory than arrays since it must keep the element value and the pointer/reference to the next element. LinkedList does not also give constant-time random access to elements. Thus, traversing the list may take longer than with arrays.
Thus, LinkedList is a versatile Java data structure with benefits such as dynamic memory allocation and quick insertion and deletion operations. It is appropriate for various use scenarios in which items must be constantly added, removed, or altered, and the order of elements must change dynamically. However, before selecting LinkedList as the data structure for a specific use case, it is critical to thoroughly analyze the application's particular requirements and the trade-offs between the advantages and negatives of the data structure.