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();
}
