Singly Linked List Algorithm Implementation Java Example

(Last Updated On: November 10, 2017)

Linked list is nothing but having the link of the next node with the current node, this gives lot of advantages like directly doing any manipulation on particular node instead of iterating everything for all the operations like we do in arraylist.

 

Why we need Linked List ?

 

Array does not help us for these things, so forced to go for linked list.

 

1. No dynamic size:

All the time we can’t mention the correct required size, as well as can’t add more size and waste the memory as well, where as in linked lists it can be dynamically managed.

 

Java Stack Implementation Simple Example

 

2. Remove performance inefficiency:

Just to move one value to left/right also needs one more array and this existing array need to be completely iterated and populated in the newly created array. But in linked list it can be handled with the particular node and it’s immediate connected node. In singly linked list it will be more easy and better performance as it has link only forward node.

 

Let’s create a simple node and perform singly linked list (nothing but linking the same object node inside our node class).

 

 

Singly Linked List Algorithm Implementation Java Example:

Node class [Node.java]:

 

We have created a new class named Node with two instance variables value (integer) and Node (same class recursively referred inside).
Here value integer instance variable for our real data store and the recursively used Node for linking the node with forward node.

 


package in.javadomain;

public class Node {
int value;
Node node = null;

}

 

Reversing a string using Stack Implementation

 

Main class [Main.java]:

 

Here we created 5 nodes namely from node 1 to node 5 and all are assigned the values from 1 to 5. But only node1, node2 and node3 are linked to node2, node3 and node4 respectively.

Here node4 and node5 are not linked with any nodes.

I have added getNodeConnectedLength() method just to check the connected length count of the given node. It will print for node 4 and node 5 as 1 only, because it does not linked with any nodes and this node class has internally 1 node, so the count will be only 1. Where as other nodes will return different counts based on the position of the node presence.

 


package in.javadomain;

public class Main {
public static void main(String[] args) {
Node node1 = new Node();
node1.value = 1;

Node node2 = new Node();
node2.value = 2;

Node node3 = new Node();
node3.value = 3;

Node node4 = new Node();
node4.value = 4;

Node node5 = new Node();
node5.value = 5;

node1.node = node2;
node2.node = node3;
node3.node = node4;
Main m = new Main();

// Note node4 and node5's are not linked with any node. so it should print only 1, that is because the default node exist inside the node.

System.out.println(m.getNodeConnectedLength(node1, true));
System.out.println(m.getNodeConnectedLength(node2, true));
System.out.println(m.getNodeConnectedLength(node3, true));
// both node4 and node5 prints 1 only, because node 4 and node 5 is not
// linked with any other nodes.
System.out.println(m.getNodeConnectedLength(node4, true));
System.out.println(m.getNodeConnectedLength(node5, true));

}

int counter = 0;

/**
* Method to retun the count of the linked list for the given node
* @param inputNode - node to be given
* @param isNew - true/false, just to identify the node status for counter handling.
* @return total number of link for the given node.
*/
public int getNodeConnectedLength(Node inputNode, boolean isNew) {
if (isNew) {
counter = 0;
}
if (inputNode != null) {
counter++;
getNodeConnectedLength(inputNode.node, false);
}
return counter;
}
}

 

 

Output:
4
3
2
1
1

 

 

 

Note:

if (inputNode != null) {
}

 

If you add this in getNodeConnectedLength method instead of the above snippet then,

if (inputNode.node != null) {
}

 

then your count will result 3,2,1,0,0 instead of 4,3,2,1,1. This is because we are directly checking the “node inside node” not null or null, which reduces 1 count value. Both actually works counting node and counting connections between the node.

179 total views, 1 views today

Leave a Reply

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