class Node {
String data;
Node next;
Node(String data) {
this.data = data;
next = null;
}
}
public class LinkedList {
Node headNode;
public void insertFirst(String value) {
Node node = new Node(value);
node.next = headNode;
headNode = node;
}
public void insertNode(String value) {
Node newNode = new Node(value);
if (headNode == null) {
headNode = newNode;
}
else {
Node nextNode = headNode;
while (nextNode.next != null) {
nextNode = nextNode.next;
}
nextNode.next = newNode;
}
}
public void insertNext(Node previousNode, String value) {
Node node = new Node(value);
node.next = previousNode.next;
previousNode.next = node;
}
public void deleteFirst() {
if (headNode == null)
return;
else
headNode = headNode.next;
}
void deleteNode(int position) {
if (headNode == null)
return;
if (position == 0) {
headNode = headNode.next;
return;
}
Node node = headNode;
for (int i = 1; node != null && i < position; i++)
node = node.next;
if (node == null || node.next == null)
return;
Node next = node.next.next;
node.next = next;
}
public void displayLinkedList() {
Node node = headNode;
while (node != null) {
System.out.println(node.data);
node = node.next;
}
}
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.insertNode("John");
linkedList.insertNode("Pradeep");
linkedList.insertNode("Andrew");
linkedList.insertNode("Beck");
linkedList.displayLinkedList();
linkedList.deleteNode(1);
System.out.println("--------");
linkedList.displayLinkedList();
}
}
We have seen that a List that is Linked to each other is a 'Linked List'.
Now, we will learn a new term. i.e. Each item in a 'Linked List' is called a 'Node'.
And we can see there are four records in the above 'Linked List'.
Say, for example, the below record is a 'Node'.
So, far we have seen, there were two records in a 'Node'. First record is the actual data or name (In the above example i.e. John). And the second record contains the pointer to the next 'Node' (The second record of John i.e. '9' in the above case was referring to the location of 'Pradeep').
Even in our Code, we have created a class called 'Node'.
class Node {
String data;
Node next;
Node(String data) {
this.data = data;
next = null;
}
}The above class 'Node' has two attributes :
The first attribute 'String data' is fine. It can hold the name "John" or "Pradeep". But what about the second attribute i.e. Node next?
Don't you think, the second attribute should have an Integer type variable ?So that it can store the pointer to the next Node(i.e. '9' in the above case was referring to the location of 'Pradeep').
Well ! In this case we are trying something different. i.e. We will let java decide the next 'Node'.
Sounds Complex ?
Stay with me. Things will become easy with each line.
Let us go to the 'Node' class. And as we can see, there is a constructor in the 'Node' class.
Node(String data) {
this.data = data;
next = null;
}So, when we create a 'Node' object, we simply, pass the data or name(Say "John").
Node node1 = new Node("John");}And the constructor creates a 'Node' object for us, with 'John' as the actual data and 'next' as 'null'. Because it is not referring to any 'Node' object yet.
Then the next time, when we create the 'Node' object with 'Pradeep',
Node node2 = new Node("Pradeep");
We will make 'node1' object point to node2 by replacing 'null' with 'node1'.
Fair enough !
Now, let us see the Code explanation for 'Linked List'.
So, there are five methods that we have used in the 'Linked List' :
Now, let us see the 'Linked List' in action.
So, in the first line we insert the value 'John',
linkedList.insertNode("John");By using the 'insertNode(String value)' method.
public void insertNode(String value) {
Node newNode = new Node(value);
if (headNode == null) {
headNode = newNode;
}
else {
Node nextNode = headNode;
while (nextNode.next != null) {
nextNode = nextNode.next;
}
nextNode.next = newNode;
}
}So, what we are doing in the 'insertNode(String value)' method is, we are creating a new 'Node' object.
Node newNode = new Node(value);
And as we have seen there is a constructor in the 'Node' class that helps in initialising the values to the 'Node' object.
And the below 'Node' object is created.
Now, just remember, we have a variable 'Node headNode', that always points to the first element in the 'Linked List'. And since, this is the first time we are creating the 'Linked List'. The 'headNode' would be initialised.
if (headNode == null) {
headNode = newNode;
}
And we don't go to the 'else' part.
Similarly, we try inserting 'Pradeep'.
linkedList.insertNode("Pradeep");And the 'insertNode(String value)' method is called.
And the same way, we are creating a new 'Node' object.
Node newNode = new Node(value);
And as we have seen there is a constructor in the 'Node' class that helps in initialising the values to the 'Node' object.
And the below 'Node' object is created.
Now since, 'headNode' is not null
if (headNode == null)
And we come to the 'else' part .
else {
Node nextNode = headNode;
while (nextNode.next != null) {
nextNode = nextNode.next;
}
nextNode.next = newNode;
}In the 'else' part, we create a 'Node' called 'newNode' and initialise it with 'headNode'.
Node nextNode = headNode;
And Since the 'headNode' is the Node where 'John' resides.
Then we run a 'while' loop to reach the end of the 'Linked List'.
while (nextNode.next != null) {
nextNode = nextNode.next;
}In this case 'nextNode.next' is equal the null. So, we do not get into the 'while' loop.
And we know 'newNode' contains 'Pradeep'.
And make the 'nextNode' (i.e. The 'Node' containing 'John') point to 'newNode'.
So, the Linked List is formed with two elements.
Similar way, all the other elements are added to the 'Linked List'.
The 'next' is put as 'next' as the linking will be decided by java internally.
Now, let us see how do we delete an element from a specific location.
linkedList.deleteNode(1);
So, we will be deleting the second element as the count starts from '0'.
And the 'deleteNode(int position)' method is called,
void deleteNode(int position) {
if (headNode == null)
return;
if (position == 0) {
headNode = headNode.next;
return;
}
Node node = headNode;
for (int i = 1; node != null && i < position; i++)
node = node.next;
if (node == null || node.next == null)
return;
Node next = node.next.next;
node.next = next;
}The first 'if' statement checks, if the 'headNode' is null or not. i.e. If the 'headNode' is null, then there are no elements in the 'Linked List'. And we stop the execution.
if (headNode == null)
return;The next 'if' statement checks, if we are asking to remove the first element.
if (position == 0) {
headNode = headNode.next;
return;
}We initialise the 'headNode' with 'headNode.next' i.e. null. And the 'Linked List' becomes empty.
If the above two 'if' statement are not satisfied then we come to the next line.
Node node = headNode;
Where we declare a 'Node' named 'node' and initialise with the 'headNode' Node.
Now since, 'headNode' contains the details of 'John'. node' is initialised with 'John'.
Then we run a 'for' loop until we reach a position just before the node that is asked to be deleted.
In this case the second element is asked to be deleted(i.e. 1).
for (int i = 1; node != null && i < position; i++)
node = node.next;So, we exit the 'for' loop, when we are at the second node.
Then we do a check to see if the first node is null or is it not pointing to any element?
if (node == null || node.next == null)
return;If so we stop the execution.
Then we create a Node called 'next'. And initialise the 'Node' with it that contains 'Andrew'.
Node next = node.next.next;
And finally, we make the Node of 'John' point to the Node that contains 'Andrew'.
node.next = next;
And we get the 'Linked List' that doesn't have the the second Node. i.e. The node that contained 'Pradeep'.
