Java List Node

In Java, List Node is the same as the single linked list, which is the collection of nodes. So, we can say, the list nodes are grouped together to get a linked list.

Generally, ListNode is a class that extends java. lang.Object package. This type of node of singly LinkedList is capable and useful for holding any kind of objects.

Syntax:

class ListNode
{
    protected int data; 
    protected ListNode next;
}

The Listnode is mainly categorized and contains the two fields:

• The first one consists of a data field that contains the value or track of an object
• The second field consists of the next field, which holds the address of the next node, and they are attached with a list or chain; form a linked list.

Constructors Description

1. ListNode():

It helps in creating the completely blank node in the linked list

2. ListNode(java.lang.Object data):

Using this, the node created within the list is a single new node with the specified data type.

3. ListNode(java.lang.Object, ListNode next):

Using this, the node created within the list is a new node with a specified data type with the referencing address of the next node placed in the next field of the new node.

Methods involved in Java ListNode

1. getData ():

This method returns the ListNode data field value of data.

public int getData() 
{
     return data;
 }

2. getNext ():

This method returns the ListNode of the next field in the chain or list of a linked list.

public ListNode getLink() 
{
    return next;
 }

3. setData ():

This method sets the data value to a specified object in the list provided.

public void setData(int d) 
{
    data = d;
}

4. setNext ():

This method is used to set the next field of a node to the references of a linked list provided in the list.

public void setLink(ListNode ns) 
{
      next = ns;
}

Algorithm

We can perform many operations on a single linked list consisting of many nodes with two fields, and we can insert the node into the list at the beginning, at the end, or any position in the list.

Moreover, we can perform the deletion operation on the linked list. We can delete the node at the beginning, at the end, and any position in the list.

So, for inserting a node into the list, we should create a temporary node followed by the following steps.

• Create a temporary node with the two fields involving the data field and the next field, which references the address location of the next node of the current node.
• Create another method or instance or class to start and end attributed nodes.
• Inserting a node into the list:
  • Create a new node with a set of parameters or data values.
  • Then we should check the empty condition, i.e., start == NULL, at that time we should assign a start and end to a newly created node.
  • If the list is not empty, and if we want to insert node at the start, the address/next field of a current node is assigned with the address of the start node, then the link will be established.
  • If we want to insert at the end, then the address/next field of an end node is assigned with the address of the new node then the link will be established.
  • If the position is specified where the node should is inserted, then we should traverse through the list to the previous position and then establish the links.
• Deletion of the nodes from the list:
  • If you want to delete the start node, then directly delete the node and attach the head address to the next node of the start node.
  • If you want to delete the end node, then directly delete the node and make the previous node address of an end node as a NULL.
  • If you want to delete node at any position in the list, then you should traverse through the list and delete the node and establish a connection between the previous node and the next node of a current node(deleted node).
• After performing the insertion and deletion operations count the number of nodes present in the list.
• Then display all the nodes.

Example:

import java.util.Scanner;
import java.util.*;
class ListNode {
    protected int data;
    protected ListNode next;
    public ListNode() {
        next = null;
        data = 0;
    }
    public ListNode(int d,ListNode ns) {
        data = d;
        next = ns;
    }
    public void setLink(ListNode ns) {
        next = ns;
    }
    public void setData(int d) {
        data = d;
    }
    public ListNode getLink() {
        return next;
    }
    public int getData() {
        return data;
    }
}
class LinkedList {
    protected ListNode start;
    protected ListNode end ;
    public int length ;
    public LinkedList() {
        start = null;
        end = null;
        length = 0;
    }
    public boolean isEmpty() {
        return start == null;
    }
    public int getSize() {
        return length;
    }
    public void insertAtBegin(int ele) {
        ListNode temp = new ListNode(ele, null);
        length++ ;
        if(start == null) {
            start = temp;
            end = start;
        } else {
            temp.setLink(start);
            start = temp;
        }
    }
    public void insertAtLast(int ele) {
        ListNode temp = new ListNode(ele,null);
        length++ ;
        if(start == null) {
            start = temp;
            end = start;
        } else {
            end.setLink(temp);
            end = temp;
        }
    }
    public void insertAtPosition(int ele , int pos) {
        ListNode temp = new ListNode(ele, null);
        ListNode curr = start;
        posi = posi - 1 ;
        for (int i = 1; i < length; i++) {
            if (i == posi) {
                ListNode nptr = curr.getLink() ;
                nptr.setLink(temp);
                nptr.setLink(nptr);
                break;
            }
            curr = curr.getLink();
        }
        length++ ;
    }
    public void deleteAtPosition(int pos) {
        if (posi == 1) {
            start = start.getLink();
            length--;
            return ;
        }
        if (posi == length) {
            ListNode st = start;
            ListNode ts = start;
            while (st != end) {
                ts = st;
                st = st.getLink();
            }
            end = ts;
            end.setLink(null);
            length --;
            return;
        }
        ListNode temp = start;
        posi = posi - 1 ;
        for (int i = 1; i < length - 1; i++) {
            if (i == posi) {
                ListNode nptr = temp.getLink();
                nptr = nptr.getLink();
                temp.setLink(nptr);
                break;
            }
            temp = temp.getLink();
        }
        length-- ;
    }
    public void displayList() {
        System.out.print("\nSingly Linked List with all the ListNodes = ");
        if (length == 0) {
            System.out.print("no nodes are present\n");
            return;
        }
        if (start.getLink() == null) {
            System.out.println(start.getData() );
            return;
        }
        ListNode temp = start;
        System.out.print(start.getData()+ "->");
        temp = start.getLink();
        while (temp.getLink() != null) {
            System.out.print(temp.getData()+ "->");
            temp = temp.getLink();
        }
        System.out.print(temp.getData()+ "\n");
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        LinkedList li = new LinkedList();
        System.out.println("Singly Linked List operations\n");
        char cha;
        do {
            System.out.println("\n Operations of Singly Linked List\n");
            System.out.println("1. insert at starting");
            System.out.println("2. insert at last");
            System.out.println("3. insert at given position");
            System.out.println("4. delete at given position");
            System.out.println("5. test empty");
            System.out.println("6. get length");
            int option = sc.nextInt();
            switch (option) {
            case 1 :
                System.out.println("enter the elements you want to insert");
                li.insertAtBegin(sc.nextInt() );
                break;
            case 2 :
                System.out.println("Enter the elements you want to insert");
                li.insertAtLast(sc.nextInt() );
                break;
            case 3 :
                System.out.println("Enter the elements you want to insert");
                int n = sc.nextInt() ;
                System.out.println("position to be placed");
                int pos = sc.nextInt() ;
                if (pos <= 1 || pos > li.getSize() )
                    System.out.println("position incorrect\n");
                else
                    li.insertAtPosition(n, pos);
                break;
            case 4 :
                System.out.println("position required");
                int position=sc.nextInt();
                if (position < 1 || position > li.getSize() )
                    System.out.println("position incorrect\n");
                else
                    li.deleteAtPosition(position);
                break;
            case 5 :
                System.out.println("Empty test = "+ li.isEmpty());
                break;
            case 6 :
                System.out.println("length = "+ li.getSize() +" \n");
                break;
            default :
                System.out.println("incorrect entry \n ");
                break;
            }
            li.displayList();
            System.out.println("\n need to continue (Type y or n) \n");
            cha = sc.next().charAt(0);
        } while (cha == 'Y'|| cha == 'y');
    }
}

Output:

Singly Linked List operations
Operations of Singly Linked List


1. insert at starting
2. insert at last
3. insert at given position
4. delete at given position
5. test empty
6. get length


Empty test = trueSingly Linked List with all the ListNodes = no nodes are present


 need to continue (Type y or n) 


y
Operations of Singly Linked List


1. insert at starting
2. insert at last
3. insert at given position
4. delete at given position
5. test empty
6. get length
1
enter the elements you want to insert
2
Singly Linked List with all the ListNodes = 2


 need to continue (Type y or n) 


y
Operations of Singly Linked List


1. insert at starting
2. insert at last3. insert at given position
4. delete at given position
5. test empty
6. get length
1
enter the elements you want to insert
4
Singly Linked List with all the ListNodes = 4->2
need to continue (Type y or n) 


y
Operations of Singly Linked List
1. insert at starting
2. insert at last
3. insert at given position
4. delete at given position
5. test empty6. get length
1
enter the elements you want to insert7
Singly Linked List with all the ListNodes = 7->4->2
need to continue (Type y or n) 


y
Operations of Singly Linked List


1. insert at starting2. insert at last
3. insert at given position
4. delete at given position
5. test empty
6. get length
2
Enter the elements you want to insert
16
Singly Linked List with all the ListNodes = 7->4->2->16


 need to continue (Type y or n) 


y
Operations of Singly Linked List


1. insert at starting2. insert at last
3. insert at given position
4. delete at given position
5. test empty
6. get length
3
Enter the elements you want to insert
14
position to be placed
0
position incorrect




Singly Linked List with all the ListNodes = 7->4->2->16


 need to continue (Type y or n) 


y
Operations of Singly Linked List


1. insert at starting2. insert at last
3. insert at given position
4. delete at given position
5. test empty
6. get length
4
position required2
Singly Linked List with all the ListNodes = 7->2->16


 need to continue (Type y or n) 


y
Operations of Singly Linked List


1. insert at starting2. insert at last
3. insert at given position
4. delete at given position
5. test empty
6. get length
1
enter the elements you want to insert
1
Singly Linked List with all the ListNodes = 1->7->2->16


 need to continue (Type y or n) 
y
Operations of Singly Linked List


1. insert at starting
2. insert at last
3. insert at given position
4. delete at given position
5. test empty
6. get length
2
Enter the elements you want to insert19
Singly Linked List with all the ListNodes = 1->7->2->16->19


 need to continue (Type y or n) 


y
Operations of Singly Linked List


1. insert at starting2. insert at last
3. insert at given position
4. delete at given position
5. test empty
6. get length
6
length = 5 




Singly Linked List with all the ListNodes = 1->7->2->16->19


 need to continue (Type y or n) 


n

Advantages of LinkedList

1. The operations performed on LinkedList like the insertion, deletion, and searching, are done faster and in an efficient way.
2.  Linked list has efficient memory utilization because we don’t want to pre-allocate memory blocks.
3. The response time is much faster, there is no additional usage of memory, and it can be expandable in a constant or linear time.
4. LinkedList is a dynamic data structure.
5. Depending on the addition and deletion of elements, the run time varies(grows or shrinks).

Applications of LinkedList

1. Add "undo" capability to programs like MS Word, Photoshop, etc.
2. To put into practice data structures like queues and stacks.
3. A linked list can be used to implement graphs as well.
4. Each bucket can be implemented as a linked list for bucket hashing.

Limitations of LinkedList

1. Memory usage is substantially higher than arrays since there is an additional pointer to keep the reference of the subsequent element in each node.
2. The linked list's nodes must always be read from beginning because this data structure can only be accessed strictly sequentially.
3. It is challenging to go backward, particularly the singly-linked lists.
4. The nodes are kept in non-contiguous places, which can increase access time.

Conclusion

LinkedList is used widely because the list nodes are faster. Applications that frequently add or remove items should utilize it since it performs modification operations faster than collections like ArrayList. ArrayList or comparable collections can be utilized in applications with a large amount of read-only data.