Linked List implementation in Java

In this post, we'll see the basic of Linked List, its advantages and implementation in Java. 

Linked List is a data structure used for storing collection of data. It has the following properties:

• Successive element are connected by pointers, in Java we means references.
• Last element of Linked List point to NULL
• Can grow or shrink in size during the execution of a program.
• Can me long as long as required.
• It does not waste memory space.

This is how Singly Linked List look like:

Each record of a linked list is often called an element or node.
The field of each node that contains the address of the next node is usually called the next link or next pointer. The remaining fields are known as the data.
The head of a list is its first node. The tail of a list may refer either to the rest of the list after the head, or to the last node in the list.
Singly linked lists contain nodes which have a data field as well as a next field, which points to the next node in line of nodes.

How the node of a Linked List look like:

How Linked List node look like in Java

How to add elements in a Linked List
There are basic 4 ways to add element in a linked list.

• Insert element at the beginning of the Linked List.
• Insert element at the end of the Linked List.
• Insert element after a specific element in the Linked List.
• Insert element before a specific element in the Linked List.

How to traverse a Linked List

Let us assume that the head pointer point to the first node of the list. To traverse the list we do the following:

• Follow the pointer.
• Display the content of the node as they traversed and move the pointer to next node.
• Stop when next pointer point to NULL

Insert element at the beginning
In this case, a new node is inserted before the current head node. Only one next pointer needs to be modified. It can be done in two steps

• Update the next pointer of new node to point the current head node.
• Update the head pointer point to the next node.

Insert element at the ending

In this case, a new node is inserted at the end of linked list. Only one pointer needs to be modified. It can be done in two steps:

• Move the head pointer (temp counter) to the last node.
• Update the last node next pointer to the new node. 

Insert element before a specific element
In this case, a new node is inserted before a specific node. One pointer will be change if new node has be added before the head node, otherwise two pointer will be change. In this case, we take two pointer one will move behind the current pointer. It can be done in three steps:

• Move the head pointer and previous pointer until specific element is found, else return by saying element not found.
• If new node has be added before head node, update the the next pointer of new node to to head and point head to new node.
• Update the previous pointer to new node and new node pointer to temp.

Insert element after a specific element
In this case, a new node is inserted before a specific node. One pointer will be change if new node has be added at the end, otherwise two pointer will be change. It can be done in three steps:

• Move the head pointer until specific element is found, else return by saying element not found.
• If new node has be added at the end, update the the head pointer of new node to the new node.
• Update the new node pointer to next of current head node and head pointer to new node.

Linked List Insertion operation Demo:

41 40
41 40 43 44
41 40 43 100 44

How to delete elements from a Linked List
There are basic 4 ways to delete element in a linked list.

• Delete element at the beginning of the Linked List.
• Delete element at the end of the Linked List.
• Delete element after a specific element in the Linked List.
• Delete element before a specific element in the Linked List.

Delete element at the beginning
The deletion of head node is done in two steps:

• Create a temporary node that point to same node as head.
• Move the head pointer node to the next node and dispose the temporary node.

Delete element at the end
In this case, last node to be delete from the list. Here we need two pointer, prev and curr where prev pointer stop at the second last node and curr stop at the last node. This can be done in 3 steps:

• Traverse the list and while traversing the list maintain the prev node pointer. By the time we reach at the end one pointer is pointing to the tail node and other is pointing the node before tail node.
• Update the prev node next pointer to NULL.
• Dispose the tail node i.e, curr node.

Delete element before a specific element
Here we take two pointer prev and curr and we iterate until we find the specific element. If prev is point to NULL, means we didn't find the element otherwise we check whether we need to delete the first node or not. It can be done in two steps:

• Move the pointer until we find the specific element else return by saying Element not found for deletion.
• If prev pointer point to first node, simply update the head otherwise go to next step.
• Set the prev node next to the curr node next pointer.

Delete element after a specific element
This procedure is bit complicated, in this case we take two pointer one is currNode and other is nextNode means we move one step forward. If there is one no element or one element, we simply return otherwise we move until nextNode become null. If nextNode is null means we didn't find the element. If nextNode next pointer is null means it is the last node otherwise we point currNodex next pointer to nextNode next pointer.

Delete singly Linked List

While iterating the linked list we store current node in some temporary variable and freeing the current node. After freeing the current node go to the next node with temporary variable and repeat the process.

If you know anyone who has started learning Java, why not help them out! Just share this post with them. Thanks for studying today!...

Find nth node from the end of a linked list in Java

In this post, we'll look into the different approaches of finding the nth node from the end of a linked list.

Let's have a code of linked list before discussing the different approaches:

ListNode

Linked List

This simply create the linked list for understanding approaches to find nth node from the end of a linked list

Note : n the element means counting start from 1 instead of 0 from end.

Approach 1 Brute-Force approach 

In this method, start with the first node and count how many nodes are there after that node. If the number of node are < n then return saying "Fewer no. of nodes". If the number of nodes >n then go to next node. Continue this until the numbers of nodes after current nodes are n

Time Complexity : O(n^2), Space Complexity : O(1)

Approach 2 We can improve the complexity of above approach using HashMap. In this approach, create a hash map whose entries are <position of node, node address>. This means, key is the position of the node in the linked list and value is the address of the node.

By the time we traverse the complete list, we can find the list length. Let's say the list length is M. To find the nth from end of linked list, we can convert this to M-n th from the beginning. Since we already know the length of the list, it's just a matter of returning M-n key value from the hash map.

Time Complexity : O(n) for creating the HashMap, Space Complexity : O(n)

Approach 3 We can solve the above approach without creating a Hash Map. We are using Hash map to find the linked list size. We can find the size of the linked list just bye starting at the head node and traversing the list. So, we can find the length of the list without creating the Hash map. After find the length, compute M-n th and with one more scan we can get the M-n th node from the beginning. This solution need two scans : one for finding the length of linked list and other for finding M-n node from the beginning.

Time Complexity : Time for finding the length=Time for finding the M-n th node from the beginning. Therefore, T(n)=O(n)+O(n)=O(n), Space Complexity : O(1)

Approach 4 We'll solve this problem in one scan. In this approach, use two pointers pNthNode and pTemp. Initially, both points to the head node of the list. pNthNode  start moving only after pTemp made n moves. From there both moves forward until pTemp reaches end of the list. As a result pNthNode point to the nth node from the end of the linked list.

Time Complexity : O(n), Space Complexity : O(1)

Same approach can be use to delete nth element from a linked list.

If you know anyone who has started learning Java, why not help them out! Just share this post with them. 
Thanks for studying today!...