Linked List in Java

Linked List in Java
Linked List in Java

Linked List is a data structure which is of linear type. This article will help you learn how to solve it in Java.

It is a collection of data elements and these data elements are not stored in contiguous fashion in the memory instead each data element has a pointer which points to the next data element in the collection.

We must have seen arrays which are also a linear data structure, then why do we need the it or let’s say any other data structure? Arrays have some limitations which restrict the use of an array in some places. Major disadvantages include:

  • Size: Arrays are static in nature. Size of arrays are defined beforehand, we cannot change the size of the array which is a limitation of arrays and it demands of a new data structure and it solves this problem.
  • Memory Allocation: Arrays store the data elements in a contiguous manner in the memory which is again a limitation with arrays as it is always not possible that we have such huge contiguous memory available, it solves this problem too.

Why Linked List?

It offers some amazing features and thus it is of great use, some of the advantages of it include:

  • Dynamic Size: It offers the flexibility to extend the size at runtime and thus we need to worry about the size of data elements beforehand.
  • Ease of Deletion/Insertion: It offers a good and economical way of insertion and deletion of data elements as this insertion and deletion can be costly with the use of arrays.

Structure of Linked List:

Elements in it are not stored in a contiguous manner but we have pointers to store and point the data elements. We have two elements basically that create a node in it.

  • Data
  • Next (pointer containing reference to next node)

Creating a node in Java:

class Node <T>{
T data;
Node<T> next;
Node(T data){
this.data = data;
this.next = null;
}
}

Types of Linked List:

Majorly in types of a linked list includes:

Singly Linked List (SLL):
As discussed there is a node which points to the next node with the help of pointers. Head points to the very first node of the data elements as shown below.

Let’s create a simple singly linked list program in Java:

public class LinkedList{
public static void main(String args[ ]){
Node<Integer> node1 = new Node<Integer>(10);
Node<Integer> node1 = new Node<Integer>(20);
Node<Integer> node1 = new Node<Integer>(30);
node1.next = node2;
node2.next = node3;
Node<Integer> head = node1;
}
}

Traversal In Singly Linked List:

As we have already created a program using three elements. Now the following function will print the elements:

public static void print(Node<Integer> head){
while(head!=null){
System.out.print(head.data+" ");
head = head.next;
}}

Doubly Linked List (DLL):
It is similar to SLL, but we have one extra pointer in it. It contains one-pointer with the name prev along with the next pointer.
It contains the following:

  • Data
  • Next pointer
  • Prev pointer

The very first node will be pointed by a head and the last node by the tail as shown. Prev of the first pointer will be pointing to null only.

Doubly Linked List Node Representation In Java:

class Node <T>{
T data;
Node<T> next;
Node<T> prev;
Node(T data){
this.data = data;
this.next = null;
this.prev = null;
}
}

Advantages of Doubly Linked List:

DLL has some advantage on SLL which includes:

  • In a doubly-linked list, we can traverse back and forth. Traversal in both directions is possible with the help of singly and doubly linked list.
  • Insertion and deletion operations are quite easy as compared to singly-linked lists. In a doubly-linked list with the help of prev pointer, insertion and deletion operations are much easier and smoother.

Ways of inserting an element in the DLL:
There are different ways of inserting an element in a doubly-linked list, it includes:

  • Insertion at the front of DLL
  • Insertion at the end of DLL
  • Insertion before a given node in DLL
  • Insertion after a given node in DLL

Circular Doubly Linked List:
As the name suggests is a combination of circular and a doubly linked list. It can be considered as the DLL in which the last node pointer has the address of the first node and the previous pointer of the first node has the address of the last node.

This circular linked list has lots of real-world examples. One such scenario would include the music player. Suppose we have 10 songs in the queue then after the 10th song it moves back to the 1st song which is possible with the help of circular linked list only.

Advantages of Circular Doubly Linked List:

  • Traversal is easy in a circular doubly linked list.
  • Useful for the implementation of some advanced data structures that include Fibonacci Heaps.

Basic Operation in Linked List:

Basic Operations in the linked list would include:

  • Insertion
  • Deletion
  • Searching and Sorting
  • Traversal

Insertion in Linked List:

Insertion in a linked list can be done in different ways:

  • Insertion at the front
  • Insertion at the end
  • Insertion at the specified location

Insertion at the front:

Insertion can be done from the front using the following function:

public void InsertAtFront(){
Node new_node = new Node(data); //creating a new node
new_node.next = head; //storing next of new node with head address
head = new_node; //storing address of new node in head
}

Insertion at the end:
Insertion at the end can be done using the following functions:

public void InsertAtTheEnd(){
Node new_node = new Node(data); //creating a new node
new_node.next = null;
Node temp = head;
while(temp.next!=null){ //iterating to the last node
temp=temp.next;
}
temp.next=new_node; //storing the address of new node in last node
}

Deletion In Linked List:
Deletion in the linked list can be useful in java as discussed. Let’s see how the deletion is done in a linked list in Java.

public static LinkedListNode<Integer> deleteTheNode (LinkedListNode<Integer> head,
int i){
if(head == null){
return head;
}
if(i==0){
return head.next;
}
int count =0;
LinkedListNode<Integer> temp= head;
while(temp!=null && count< i-1){
temp= temp.next;
count++;
}
if(temp == null){
return head;
}
if(temp.next !=null){
temp.next = temp.next.next;
}
return head;
}

Sorting in Linked List:
In the Linked List, Sorting can be done and it is quite useful in Merge Sort. Merge Sort in Linked List is quite useful and convenient. It is often preferred to sort a linked list in Java.

Inbuilt Operation in Linked List:

There are some inbuilt operation that Linked List provides, some of them includes:

  • removeFirst: It removes the first element of the linked list and it moves the head to the second element of the linked list. Size of the linked list is decreased by one and it returns the deleted element as well.
  • removeLast: It removes the last element of the linked list and it moves the tail to the second last element of the linked list. Size of the linked list is decreased by one and it returns the deleted element as well.
  • removeAt: It removes the element at a particular index if the index is a valid index for the linked list. Size of the linked list is decreased by one. It returns the removed data as well.
  • getFirst: This operation will return the data present at the first node. If we don’t have the size as zero then it returns the head usually.
  • getLast: This operation will return the data present at the last node. If we don’t have the size as zero then it returns the tail usually.
  • getAt: It returns the data present at a specified location only.

Conclusion:
So, the linked list in Java is a very important linear data structure that takes away the worry of the size of the data elements and also provides the operations like insertion and deletion with an economical cost. Also, the variety of linked lists ease the problem to a great level as we have double and circular doubly linked lists as well which are quite useful in real-world applications.

As discussed, to play the songs linked list is a useful data structure. This is an important data structure if we talk about coding interviews as well. One should have good command over this data structure to clear a good coding interview.

Want to read more such articles? Why don’t you check out the Difference between Array, Queue & Stack.

By Deepak Jain