Question

Program to insert elements in Singly Linked List and Display them.

— Submitted By Ubaid Ahmad

What is Linked List?

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers.

 

Advantages over arrays

1) Dynamic size 

2) Ease of insertion/deletion

Drawbacks: 

1) Random access is not allowed. We have to access elements sequentially starting from the first node(head node). So we cannot do binary search with linked lists efficiently with its default implementation. Read about it here. 

2) Extra memory space for a pointer is required with each element of the list. 

3) Not cache friendly. Since array elements are contiguous locations, there is locality of reference which is not there in case of linked lists.

Share code with your friends

Share on whatsapp
Share on facebook
Share on twitter
Share on telegram

Code

				
					import java.util.Scanner;
public class SinglyLinkedList {

    class Node
    {
        int data;
        Node next;

        public Node(int data) 
        {
            this.data = data;
            next = null;
        }
    }

    // creating the head of the linkedlist. This represents the first node of the
    // list.
    public Node head = null;
    
    public void insert(int data) 
    {
        Node newNode = new Node(data); // creates a new node and fills it data attribute by the value passed.

        // check if the list is empty, if yes the head of the node becomes the newNode.
        if (head == null)
        {
            head = newNode;
            return;
        }

        // if not then traverse to the end of the list and add the node there
        Node temp = head;
        while (temp.next != null) 
        {
            temp = temp.next;
        }

        temp.next = newNode;

    }

    // printing the linkedlist
    public void printList()
    {
        Node temp = head;
        while (temp != null) 
        {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) 
    {
        // creating a SinglyLinkedList object names linkedList to represent the
        // linkedlist
        SinglyLinkedList linkedList = new SinglyLinkedList();
        int totalElements=0;
        //Taking number of elements that will be inserted in the list 
        Scanner sc=new Scanner(System.in);
        System.out.println("Enter number of elements to be inserted in linked list:");
        totalElements=sc.nextInt();
        System.out.println("Enter the Elements");
        // inserting elements
        for(int i =1;i<=totalElements;i++)
        {
            System.out.print(i+": ");
            int element=sc.nextInt();
            linkedList.insert(element);
        }
        
        // prints the linkedlist
        linkedList.printList();
    }

}

				
			

Coding Store

Code Explanation

				
					    class Node
    {
        int data;
        Node next;

        public Node(int data) 
        {
            this.data = data;
            next = null;
        }
    }

    
				
			

Since we are making a singly linked list, we will make a class called SinglyLinkedList and make a nested class Node in it. This nested class will have two attributes

  • Node next : to store the location of the next node

  • int data : to store the data of the current node.

In the node class we make a constructor that will be used when we instantiate the objects.

				
					public void insert(int data) 
    {
        Node newNode = new Node(data); // creates a new node and fills it data attribute by the value passed.

        // check if the list is empty, if yes the head of the node becomes the newNode.
        if (head == null)
        {
            head = newNode;
            return;
        }

        // if not then traverse to the end of the list and add the node there
        Node temp = head;
        while (temp.next != null) 
        {
            temp = temp.next;
        }

        temp.next = newNode;

    }
				
			

Now, in the SinglyLinkedList class, we make a function that will add the nodes.
insert(int):

The insert function accepts the data to be inserted as an argument and makes an object of class Node.
Now there are two scenarios-

  • The LinkedList is empty:

If it is empty, then we make the new node as the head node and exit from the function

  • The LinkedList has nodes:

If the list is not empty, we traverse to the end of the list and then add the node at the end of the linkedlist.

				
					// printing the linkedlist
    public void printList()
    {
        Node temp = head;
        while (temp != null) 
        {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }
				
			

In printList() function, we just traverse till the end of the list and keep on printing the data field of each object.

				
					public static void main(String[] args) 
    {
        // creating a SinglyLinkedList object names linkedList to represent the
        // linkedlist
        SinglyLinkedList linkedList = new SinglyLinkedList();
        int totalElements=0;
        //Taking number of elements that will be inserted in the list 
        Scanner sc=new Scanner(System.in);
        System.out.println("Enter number of elements to be inserted in linked list:");
        totalElements=sc.nextInt();
        System.out.println("Enter the Elements");
        // inserting elements
        for(int i =1;i<=totalElements;i++)
        {
            System.out.print(i+": ");
            int element=sc.nextInt();
            linkedList.insert(element);
        }
        
        // prints the linkedlist
        linkedList.printList();
    }
				
			

In the main function, we instantiate the object of the SinglyLinkedList class and create the list using the insert() function. After that, we just print the list.

Leave a Reply

Your email address will not be published. Required fields are marked *