Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is a Linked List?
3.
What is a Generic Linked List in Java?
4.
Implementation
4.1.
Java
4.2.
Explanation
5.
Frequently Asked Questions
5.1.
What is Java?
5.2.
What is a Linked List?
5.3.
What is the advantage of using a Generic LinkedList in Java?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

Generic LinkedList in Java

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

Java is a programming language. It is a high-level language, object-oriented, and class-based. It is a secure, reliable, and fast programming language. It is used to build many applications and has a wide range of uses in development. In Java, many data structures can be used for implementing various functions. We will look at one of the essential data structures, linked lists.

Generic LinkedList in Java

In this article, we will study Generic LinkedList in Java.

Read more, how to run java program

What is a Linked List?

Linked List is a data structure linear in nature consisting of nodes. A node is the building block of a linked list consisting of two parts. One part is the one containing the value stored in it. The second part is a pointer, which points to the next node of the linked list—the last node points to the NULL value. We can illustrate a linked list as follows:

linked list representation
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

What is a Generic Linked List in Java?

A Generic Linked List is a type in which the data type for the storage value is not defined and is generic. It means that the data type is not fixed. It can be created using templates or generic classes in programming languages such as C++ or Java. 

The idea behind a generic linked list is to give a reusable and flexible data structure that can store elements of various data types without the requirement of creating a separate linked list for every data type. This permits us to code reusability, and the implementation of algorithms is also simplified. In the following example, we will see that <T> is used to represent the type of data that will be stored in the linked list.

Implementation

Now, let us implement a Generic LinkedList in Java programming language as follows:

  • Java

Java

import java.io.*;


class Node<T> {
   T data;
   Node<T> next;


   Node(T val){
       this.data=val;
       this.next=null;
   }
}


class linkedlist<T> {
   Node<T> head;
   int l=0;
   linkedlist(){
       this.head=null;
   }


   void addat(int pos, T value){
       if(head==null){
           if(pos!=0){
               System.out.println("Invalid position");
           }
           else{
               Node<T> t=new Node<T>(value);
               head=t;
               l+=1;
           }
           return;
       }
       if(pos>l){
           System.out.println("Invalid position");
           return;
       }
       if(pos<0){
           System.out.println("Invalid position");
           return;
       }
       if(pos==0){
           Node<T> temp=new Node<T> (value);
           temp.next=this.head;
           this.head=temp;
           l+=1;
           return;
       }
       int i=0;
       Node<T> t=head;
       while(i!=pos-1){
           i+=1;
           t=t.next;
       }
       Node<T> y=t.next;
       Node<T> res=new Node<T>(value);
       res.next=y;
       t.next=res;
       l+=1;
       return;
   }


   void deleteat(int pos){
       if(pos==0){
           head=head.next;
           l-=1;
           return;
       }
       if(pos>=l){
           System.out.println("Invalid position");
           return;
       }
       if(pos<0){
           System.out.println("Invalid position");
           return;
       }
       int i=0;
       Node<T> temp=head;
       while(i!=pos-1){
           i+=1;
           temp=temp.next;
       }
       if(temp.next==null){
           return;
       }
       l-=1;
       temp.next=temp.next.next;
   }
   void length(){
       System.out.println(l);
   }
   boolean empty(){
       if(head==null){
           return true;
       }
       return false;
   }
   void printlist(){
       Node<T> temp=head;
       while(temp!=null){
           System.out.print(temp.data + " ");
           temp=temp.next;
       }
   }
}


class Solution {
   public static void main(String[] args) {
       linkedlist<Integer> list=new linkedlist<>();
       list.addat(0,5);
       list.addat(0,8);
       list.addat(0,10);
       list.deleteat(1);
       list.addat(1,4);
       list.printlist();
       System.out.print("\nLength of the linked list: ");
       list.length();
       boolean v=list.empty();
       System.out.print("Is the linked list empty? " + v);
   }
}

 

OUTPUT

output for generic linkedlist in java

TIME COMPLEXITY

The time complexity of adding, deleting, and printing the nodes is O(n). For the rest of the two operations, it is O(1).

Explanation

We can see that we used <T> for the class Node. We did this so the programmer could call for any defined data type for their linked list. A Node has two values: its data and the next pointer to point to another node or NULL. We define a parameterized constructor taking a value, initializing a Node with the passed value, and pointing to NULL.

Then, we create our class: linkedlist. We define a Node named head and initialize a variable l denoting the length of the linked list, with 1. We also create a default constructor, which makes the head NULL. Then, we create our functions inside our class.

In this example, we have opted for the integer data type. Note that we have used 0-based indexing for our code.

The following five functions are used in the above code:

  • addat:- It takes two parameters: the position at which the node is to be added and the value for the node to be added. Firstly, we check that if the head is NULL, a node can only be inserted in the first place. Secondly, the position at which the node is to be inserted must be from 0 to the length of the current linked list. Then, we check whether the position is 0. If so, we create a new node, point its next pointer to the current head, and update the head to this newly created node. Finally, if none of the above conditions is true, it adds the node by taking a temporary node at the head and initializing a temporary variable(i) to 0. Then, we increment the value of the variable ‘i’ till it is not at the previous location of where the node is to be inserted. Then, we create a node and insert it at the respective position. After inserting a node, we increment the variable ‘l’ value by 1.
     
  • deleteat:- It takes only one parameter. It takes the position where the node is to be deleted. It removes the node at that position. It checks if the node to be deleted is the first node; we update the head node to its next node. Further, the node's position to be deleted must be from 0 to the length of the current linked list. Then, we apply the same temporary node and variable method we applied while adding a node and replace the next pointers to achieve node deletion. After deleting a node, we decrement the value of 'l' by 1.
     
  • length:- It prints the length of the linked list. It simply returns the value of the variable l.
     
  • empty:-  It returns a boolean value. If the linked list is empty, it returns true. Else, it returns false. It checks it by checking the value of the head node. If it is NULL, the linked list is empty; otherwise, it is not.
     
  • printlist:- It prints the content of the linked list in an orderly manner. It achieves this by creating a temporary node starting at the head. Then, it points it to the next node till it is not NULL. It prints each node's value during the traversal.

Also see, Java Ioexception

Frequently Asked Questions

What is Java?

Java is a programming language. It is a high-level language, object-oriented, and class-based. It is a secure, reliable, and fast programming language. It is used to build many applications and has a wide range of uses in development.

What is a Linked List?

A linked list is a data structure linear in nature consisting of nodes. A node is the building block of a linked list consisting of two parts. One part is the one containing the value stored in it. The second part is a pointer pointing to the linked list's next node.

What is the advantage of using a Generic LinkedList in Java?

The advantage of using a Generic LinkedList in Java is that with its use, the programmer can use any defined data type when calling for the linked list implementation class. There is no need to define different classes of linked lists with different data types; a single class can do it.

Conclusion

A linked list is an essential linear data structure. It has two parts: the value to be stored and a pointer for the next node.  In this article, we studied Generic LinkedList in Java. We started with its definition and concept, then looked at its implementation and the output with its explanation.

If you want to dive deeper into its concept, read the following articles:-

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Codestudio. Also, you can enroll in our courses and check out the mock tests and problems available. Please check out our interview experiences and interview bundle for placement preparations. 

Happy Coding!

Previous article
Regular Expressions in Java
Next article
Java @SuppressWarnings Annotation
Live masterclass