Question
Program to insert elements in Circular Singly Linked List and Display them.
— Submitted By Ubaid Ahmad
Enter number of elements to be inserted in Circular singly linked list:
5
Enter the Elements
1: -20
2: 3
3: 10
4: 25
5: 1
-20 3 10 25 1
What is Circular 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. The only difference between a singly linked list and a circular singly linked list is that the “next” field of the last node points to the start of the linked list.
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 a binary search with linked lists efficiently with its default implementation.
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 CircularSinglyLinkedList
{
class Node
{
int data;
Node next;
public Node(int data)
{
this.data = data;
}
}
// 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,
// and it points to itself.
if (head == null)
{
head = newNode;
head.next = head;
return;
}
// if not then traverse to the end of the list and add the node there
Node temp = head;
while (temp.next != head)
{
temp = temp.next;
}
temp.next = newNode;
newNode.next = head;
}
// printing the linkedlist
public void printList()
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
if (temp == head)
{
break;
}
}
System.out.println();
}
public static void main(String[] args)
{
// creating a CircularSinglyLinkedList object names linkedList to represent the
// linkedlist
CircularSinglyLinkedList linkedList = new CircularSinglyLinkedList();
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 Circular singly 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;
}
}
Since we are making a circular singly linked list, we make a class called CircularSinglyLinkedList and make a nested class Node in it. This nested class will have two attributes
1. Node next : to store the location of the next node
2. 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,
// and it points to itself.
if (head == null)
{
head = newNode;
head.next = head;
return;
}
// if not then traverse to the end of the list and add the node there
Node temp = head;
while (temp.next != head)
{
temp = temp.next;
}
temp.next = newNode;
newNode.next = head;
}
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 then make that node point to itself 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 linked list, making this new node point to the head node.
// printing the linkedlist
public void printList()
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
if (temp == head)
{
break;
}
}
System.out.println();
}
printList():
In this function, we just traverse till the end of the list by checking if the current node is the head node, if it is, it means we have traversed the linked list from left to right.
public static void main(String[] args)
{
// creating a CircularSinglyLinkedList object names linkedList to represent the
// linkedlist
CircularSinglyLinkedList linkedList = new CircularSinglyLinkedList();
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 Circular singly 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();
}
