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!...