A data structure uses different pre-defined methods to store, retrieve, and delete data which culminates in the creation of efficient programs. A linked list is a popular data structure, which consists of a list of nodes that are connected (or linked).
But how do you create a linked list in Java? Let's take a look.
How Does a Linked List Work?
Every linked list begins with a special node that is often referred to as the "head", which has the responsibility of pointing to the start of the list at all times. The head is important because each node in a linked list does not need to follow its successor physically (meaning that a predecessor and a successor don’t have to be physically adjacent).
Like every data structure, the linked list facilitates creation, retrieval, insertion, and destruction through a set of predefined functions that can be used by any developer.
Creating a Linked List in Java
A Java program that is designed to create and manipulate linked lists will have three distinctive sections; the node class, the linked list class, and the driver. Though these three sections can be combining in one file, there’s a design principle in computer science known as "separation of concerns" that every developer should know.
The separation of concerns principle dictates that each section of the code that addresses a specific concern should be separated. This principle will help you to create cleaner (more readable) code and is ideal for creating data structures.
The first step in creating a linked list in Java is to create a node class. A node class should have two attributes; one of the attributes will represent the data portion of the node, while the other attribute will represent the linked portion. A node class should also have a constructor, getters, and setters.
The getters and setters will allow other classes (such as the linked list class) to access the various nodes within the linked list.
Node Class Example
Below is a node class example for you to get an idea of what we mean:
public class Node {
private int Data;
private Node NextNode;
//constructor
public Node() {
Data = 0;
NextNode = null;
}
//getters and setters
public int getData() {
return Data;
}
public void setData(int data) {
Data = data;
}
public Node getNextNode() {
return NextNode;
}
public void setNextNode(Node nextNode) {
NextNode = nextNode;
}
}
In this example, the data attribute will store integer values. Now that you have the node class, it’s time to move on to the linked list.
Linked List Example
Below is an example of a linked list in Java.
public class LinkedList {
private Node Head;
//constructor
public LinkedList() {
Head = null;
}
}
The code above will create a linked list class, however, without its various operations, the class can be seen as the equivalent of an empty shell. The linked list data structure has several operations that can be used to populate it:
- Insert at the front.
- Insert in the middle.
- Insert at the back.
The linked list collection of insertion methods is one reason why a developer might choose to use this data structure over another data structure such as stacks (which only allows insertion and deletion from the top).
Using the Insert at the Front Method
The insert at the front method, as the name suggests, inserts new data (or new nodes) at the front of the linked list.
Insert at the Front Method Example
Below is an example of how you would insert new data at the front of your list.
//insert node at front method
public void insertAtFront(int key) {
//create a new node using the node class
Node Temp = new Node();
//check if the Temp node was successfully created
//assign the data that was provides by the user to it
if(Temp != null) {
Temp.setData(key);
Temp.setNextNode(null);
//check if the head of the linked list is empty
//assign the node that was just created to the head position
if(Head == null) {
Head = Temp;
}
//if a node is already at the head position
//add the new node to it and set it as the head
else {
Temp.setNextNode(Head);
Head = Temp;
}
}
}
The insertAtFront method in the example above allows a user to add new nodes to a given linked list.
Applying the Insert at the Front Example
Below is an example of how you would apply insert at the front.
public class Driver {
//executes the program
public static void main(String[] args) {
//create a new linked list called List
LinkedList List = new LinkedList();
//add each value to the front of the linked list as a new node
List.insertAtFront(10);
List.insertAtFront(8);
List.insertAtFront(6);
List.insertAtFront(4);
List.insertAtFront(2);
}
}
The Driver class (which is the name that is often assigned to the executable class in Java), utilizes the LinkedList class to create a linked list of five even numbers. Looking at the code above it should be easy to see that the number "2" is at the head position in the linked list. But how can you confirm this?
Using the Display All Nodes Method
The display all nodes method is an essential linked list method. Without it, a developer will not be able to see the nodes in a linked list. It travels through the linked list (starting from the head) printing the data stored in each node that forms the list.
Display All Nodes Method Example
Below is an example of using the display all notes method in Java.
//display all nodes method
public void displayAllNodes() {
//create a new node call Temp and assign it to the head of the linked list
//if the head has a null value then the linked list is empty
Node Temp = Head;
if (Head == null){
System.out.println("The list is empty.");
return;
}
System.out.println("The List:");
while(Temp != null) {
//print the data in each node to the console(starting from the head)
System.out.print(Temp.getData() + " ");
Temp = Temp.getNextNode();
}
}
Now that the displayAllNodes method has been added to the LinkedList class you can view the linked list by adding a single line of code to the driver class.
Using the Display All Nodes Method Example
Below, you'll see how you'd use the display all nodes method.
//print the nodes in a linked list
List.displayAllNodes();
Executing the line of code above will produce the following output in the console:
The List:
2 4 6 8 10
Using the Find Node Method
There will be instances when a user will want to find a specific node in a linked list.
For example, it wouldn’t be practical for a bank that has millions of customers to print all customers’ in their database when they only need to see the details of a specific customer.
Therefore, instead of using the displayAllNodes method, a more efficient method is to find the single node containing the required data. This is why the search for a single node method is important in the linked list data structure.
Find Node Method Example
Below is an example of using the find node method.
//search for a single node using a key
public boolean findNode(int key) {
//create a new node and place it at the head of the linked list
Node Temp = Head;
//while the current node is not empty
//check if its data matches the key provided by the user
while (Temp != null) {
if (Temp.getData() == key) {
System.out.println("The node is in the list");
return true;
}
//move to the next node
Temp = Temp.getNextNode();
}
//if the key was not found in the linked list
System.out.println("The node is not in the list");
return false;
}
With the displayAllNodes method, you confirmed that the LinkedList contains 5 even numbers from 2 to 10. The findNode example above can confirm if one of those even numbers is the numeral 4 by simply calling the method in the driver class and providing the number as a parameter.
Using the Find Node Method Example
Below is an example of how you'd use the find node method in practice.
//check if a node is in the linked list
List.findNode(4);
The code above will produce the following output in the console:
The node is in the list
Using the Delete a Node Method
Using the same bank example from above, a customer in the bank’s database might wish to close their account. This is where the delete a node method will be useful. It's the most complex linked list method.
The Delete a Node method searches for a given node, deletes that node, and links the previous node to the one that follows the node that has been deleted.
Delete a Node Method Example
Below is an example of the delete a node method.
public void findAndDelete(int key) {
Node Temp = Head;
Node prev = null;
//check if the head node holds the data
//and delete it
if (Temp != null && Temp.getData() == key) {
Head = Temp.getNextNode();
return;
}
//search the other nodes in the list
//and delete it
while (Temp != null) {
if (Temp.getNextNode().getData() == key ) {
prev = Temp.getNextNode().getNextNode();
Temp.setNextNode(prev);
return;
}
Temp = Temp.getNextNode();
}
}
Using the Delete a Node Method Example
Below is an example of using the delete a node method in practice.
//delete the node that holds the data 4
List.findAndDelete(4);
//print all nodes in the linked list
List.displayAllNodes();
Using the two lines of code above in the pre-existing Driver class will produce the following output in the console:
The List:
2 6 8 10
Now You Can Create Linked Lists in Java
If you made it to the end of this tutorial article, you will have learned:
- How to create a node class.
- How to create a linked list class.
- How to populate a linked list class with its predefined methods.
- How to create a driver class and use the different linked list methods to achieve the desired result.
A linked list is just one of many data structures that you can use to store, retrieve and delete data. Since you've got everything you need to get started, why not try these examples for yourself in Java?