INTERNET

An Introduction to Using Linked Lists in Java

0

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 4List.findAndDelete(4);//print all nodes in the linked listList.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?

admin

These 3 Features in iOS 15 Are Exclusive to the iPhone 12

Previous article

You Can Now Get 3 Months of Stadia Pro for Free

Next article

You may also like

Comments

Leave a reply

Your email address will not be published. Required fields are marked *

More in INTERNET

Login/Sign up