1. Data Structure For Testers - Implement Linked List in Java -

Table of Contents

Introduction

As a part of the Data structure for Testers in this post, we will learn to implement a Linked List data structure in Java.

What is Node?

A node is a building block. We can relate it with a brick. When we use multiple bricks together we can create a structure. Similarly, we can use multiple nodes together to create a structure like LinkedList, Tree, etc.

Image Source – Google Image

In the programming world, a node may have two, three, or many compartments. If we talk about a node with two compartments then the first compartment will hold data and the second compartment will be used to store the address of the next node to form a structure.

If we talk about a node with three compartments then the first compartment will store the address of a previous node while the third compartment will have an address of the next node. A middle node will store data.

A node may store multiple data compartments as well.

This feature of Node allows us to create a structure whose nodes or elements are stored in non-contiguous locations.

Java class to represent a Node

Let’s focus on a node with two compartments as of now. So a node can hold any type of data such as int, string, etc. When I say that a Node holds the address of another node i.e. a pointer to the next node.

package ListExamples;

/*
 * A node with two components-  First one is data another one is a pointer to next node.
 * If a node does not point to any other node, it will be NULL or point to NULL.
 */
public class Node {

	// Data component
	int data; 
	// Pointer component
	Node next; 
	
	// A constructor to create a node
	Node(int d) 
	{ 
		data = d; 
		// Since while creating a node we can not say in advance about next node so pointer will be null
		next = null; 
	}
}

package ListExamples;

* A node with two components- First one is data another one is a pointer to next node.

* If a node does not point to any other node, it will be NULL or point to NULL.

public class Node {

// Data component

int data;

// Pointer component

Node next;

// A constructor to create a node

Node(int d)

{

data = d;

// Since while creating a node we can not say in advance about next node so pointer will be null

next = null;

}

What is a Linked List?

A LinkedList is a linear data structure whose elements may not be stored at contagious locations. A linear data structure where elements are arranged in a sequential manner and each element may have its previous or next element information. For example – Array, stack, queue, etc.

As shown above a LinkedList a group of nodes and has head node and tail node. Head node will be starting of List while Tail node is the last node of List. I have represented how a node will point to another node to make a sequnetial node. Please note no other node holds address of Head node which makes a starting point. Last node also does not hold address of any other node to make end of list. This is also called Singly Linked List.

Implementing a Linked List in Java

Let’s think of a logic to build a LinkedList.

A LinkedList will have a head and tail.
When list is empty then Head and Tail will point to null.
If there is only one node then both Head and Tail will point to the same node.

Logic to add a new Node

If List is empty then simple Head will point to new node and since there is only one element so Tail will also point to same new node like Head.

If list is not empty, then the existing Tail Node will not point to NULL any more and will point to new Node. This logic can be understand from below diagram:-

Java Program

Below is a self explantory Java program:-

package ListExamples;

/*
 * A single linked list consists of zero or more nodes.
 * First node in LinkedList is called Head and last node in a LinkedList
 * is called a tail.
 */
public class LinkedList {

	private Node headNode; // start of list
	private Node tailNode; // end of list

	// To add a new node in LinkedList
	public LinkedList addNode(LinkedList list, int data) {
		// Create a new node with given data
		Node newNode = new Node(data);
		newNode.next = null;

		/*
		 * before adding a new node, check if list is empty. If list is empty, head and
		 * tail will be same.
		 */
		if (list.headNode == null) {
			list.headNode = newNode;
			list.tailNode = newNode;
		}
		// if list is not empty then set next of last node to new node from NULL
		// and new node will have already null from constructor
		else {
			list.tailNode.next = newNode;
			list.tailNode = newNode;
		}

		// Return the list by head
		return list;
	}

	// To print a LinkedList
	public void printList(LinkedList list) {

		// Get the hold of starting node
		Node currNode = list.headNode;
		System.out.print("Nodes in LinkedList are: ");
		// Traverse through the LinkedList till current node becomes null
		while (currNode != null) {
			// Print the data at current node
			System.out.print(currNode.data + " ");
			// Go to next node
			currNode = currNode.next;
		}
	}

}

package ListExamples;

* A single linked list consists of zero or more nodes.

* First node in LinkedList is called Head and last node in a LinkedList

* is called a tail.

public class LinkedList {

private Node headNode; // start of list

private Node tailNode; // end of list

// To add a new node in LinkedList

public LinkedList addNode(LinkedList list, int data) {

// Create a new node with given data

Node newNode = new Node(data);

newNode.next = null;

* before adding a new node, check if list is empty. If list is empty, head and

* tail will be same.

if (list.headNode == null) {

list.headNode = newNode;

list.tailNode = newNode;

}

// if list is not empty then set next of last node to new node from NULL

// and new node will have already null from constructor

else {

list.tailNode.next = newNode;

list.tailNode = newNode;

}

// Return the list by head

return list;

}

// To print a LinkedList

public void printList(LinkedList list) {

// Get the hold of starting node

Node currNode = list.headNode;

System.out.print("Nodes in LinkedList are: ");

// Traverse through the LinkedList till current node becomes null

while (currNode != null) {

// Print the data at current node

System.out.print(currNode.data + " ");

// Go to next node

currNode = currNode.next;

}

Output

Nodes in LinkedList are: 1 2 3 4 5

1	Nodes in LinkedList are: 1 2 3 4 5

You can download/clone the above sample project from here.

You can subscribe to my YouTube channel RetargetCommon to learn from video tutorials.

If you have any doubt, feel free to comment below.
If you like my posts, please like, comment, share and subscribe.
#ThanksForReading
#HappyLearning

Find all Selenium related posts here, all API manual and automation related posts here, and find frequently asked Java Programs here.

Many other topics you can navigate through the menu.

Author: Amod Mahajan

A software Tester who is paid to judge products developed by others. Writing technical posts and creating YouTube videos are my hobbies.

1. Data Structure For Testers – Implement Linked List in Java