Is there any node containing NULL in next field of circular linked list?

If you are not familiar with the LinkedList, I would highly recommend having a look at my blog:

Introduction to Linked List


In this tutorial, we will learn circular linked list in-depth by dividing topics in the following manner:

  1. Definition of circular linked list.
  2. Types of Circular linked list
  3. Basic Operations on circular linked list

    a) Searching/Traversal
    b) Insertion
    c) Deletion

  4. Singly linked list as a circular linked list.

  5. Doubly linked list as a circular linked list.

  6. Applications of circular linked list

  7. Implementation of circular linked list.


Definition of circular linked list

In a circular linked list, elements are stored in random memory locations.
Similar to a singly linked list, each node of a circular linked list (I meant singly circular linked list) contains two fields:

  1. data stored at that particular address.
  2. Pointer which contains the address of the next node.

Circular Linked List

Unlike, singly linked list in which the last node of the contains a pointer to null to represent the termination of a linked list, in circular linked list, last node of linked list will point to the first node of the linked list.


Types of Circular Linked List:

There are two types of Circular linked list. i.e. we can make a circular linked list by modifying the Singly linked list as well as Doubly linked list.

1. Singly circular linked list

Singly Linked List

The above diagram is an example of a singly linked list in which the last node(Tail) points to NULL to represent the termination of the linked list.
To make it a singly circular linked list, you just need to modify the link of the last node.
Instead of pointing it to NULL, We are going to link it with the first(head) node.

Circular Linked List

Now, one question which might come into your mind is, how do we get to know termination condition, right?
Because, if we dont apply termination condition our program will run into an infinite loop. Confused?

Well, one thing you might do is, keep a track of head node and whenever we encounter it again, we say that we have traversed our whole linked list and Now it is time to terminate.
You could have taken a temp=head->next and start traversing linked list and check for whether our temp is head or not.

if (temp==head) ===> We have traversed whole linked list.
Well, it was just a brief explanation, we will see it via code in detail, later in this tutorial.


2. Doubly circular linked list

Doubly Linked List

The above diagram is an example of doubly linked list in which the prev of head points to NULL and last node(Tail) points to NULL to represent the termination of linked list.
To make it a Doubly Circular Linked List, you just need to modify the link of the last node.
Instead of pointing next of last node (lastNode->next) to NULL, We are going to link it with first(head) node.
Moreover, the prev of first node (head->prev) will point to the last node.

Doubly circular linked list

In this case, keep a track of head node and whenever we encounter it again, we say that we have traversed whole linked list and now it is time to terminate.

You could have taken a temp=head->next and start traversing linked list and check for whether our temp is head or not.
if temp==head —–> We have traversed whole linked list.


Operations on Circular linked list


A. Traversal

Traversal in Circular linked list is similiar to singly or doubly linked list, we just need to take care of termination condition. In this case termination condition would be, If we reach again to our head node.

To perform this task do the following:
Take a temp node and store head ->next into it, now run a loop untill temp!=head and search for given element.
If we reach head ===> (temp==head): terminate loop.

Node *temp=head->next;
while(temp!=head)
{
if(temp->data==ElementToFind) {
coutnext;
}

Enter fullscreen mode Exit fullscreen mode


B. Insertion

Insertion in Circular linked list will be exactly same as in singly linked list except inseting node at front and at last position.

  • Inserting node in Between two nodes

Inserting node in Between two nodes

To insert a node at front, We need to know about the last node of linked list.
Hence we will traverse the whole linked list and reach to end of it.

Insert at front

Create a new node and link it with exisiting list as mentioned below:

LastNode->next=newNode;
newNode->next=head;

Enter fullscreen mode Exit fullscreen mode

After, linking nodes, we need to update the head of linked list as we are inserting at the front and front node represent the head of linked list.
In our case, newNode would be our new head now.

head=newNode;

Enter fullscreen mode Exit fullscreen mode

It is similiar to inserting node at front. The only difference is that we don’t need to update head in this case.

Insert at last


C. Deletion

To delete in between node, find prev and next node of the node which needs to be deleted.

Delete node in between

curr = head;
while(curr!=nodetoDelete) {
prev = curr;
curr = curr->next;
}
prev->next=curr->next;
delete curr;

Enter fullscreen mode Exit fullscreen mode

To delete a Node from front, We need to know about the last node of linked list.
Hence we will traverse the whole linked list and reach to end of it.

Delete node from front

ptr = head;
while(ptr ->next != head) {
ptr = ptr->next;
}
temp = head;
ptr -> next = temp->next;
// update head node
head =head->next;
delete temp;

Enter fullscreen mode Exit fullscreen mode

It is similiar to deleting node at front. The only difference is that we won’t be updating head in this case.

Delete last node

ptr = head;
while(ptr ->next != head) {
preptr=ptr;
ptr = ptr->next;
}
preptr->next = ptr -> next;

Enter fullscreen mode Exit fullscreen mode


D. Advantages of Circular linked list

  1. In a circular linked list, there is no requirement for a NULL assignment in the code. The good thing about a circular linked list is that It never points to a NULL pointer unless fully deallocated.

  2. Circular linked lists are always good and advantageous for the end operations since the beginning and the end of circular linked list coincide with each other.

  3. Many algorithms such as the Round Robin scheduling which uses queue can efficiently and easily eliminate processes that are queued in a circular way or fashion without encountering any dangling pointers or NULL-referential
    pointers.

  4. The biggest advantage with a circular linked list is that It also performs all regular functions of a singly/doubly linked list along with additional features.


E. Disadvantage of circular linked list

  1. Insertion at all positions (first node, last node, and In-between) takes O(n) time while in singly linked list insertion at first node takes O(1) time.

  2. Deletion at all positions (first Node, Last Node, and In-between) takes O(n) time while in singly linked list deletion at first node takes O(1) time.

  3. If we dont apply the termination condition properly, our code might lead to infinite loop.


F. Applications of Circular linked list

  1. If I talk about the real-life application of a circular linked list, It would be none other than our personal computers, which are capable of running multiple applications at a time. Computers process all applications in this manner that all running applications are kept in a queue which is implemented using a circular linked list and the operating system gives a fixed time(could be an example of Round Robin CPU Scheduling Process) slot know as time quantum to all for running processes.
    The operating system keeps on iterating over the
    circular linked list and keeps executing processes and removing them from waiting for queue until all the applications are executed/completed successfully.

  2. We can also take an example multiplayer games in which all the players are kept in a queue which is implemented via a circular linked list and the pointer keeps on moving forward as the chance of a particular player ends.

  3. We can also take an example of the circular linked list which can also be used to create a circular queue.
    The problem with a given queue is that we need to keep two pointers one for FRONT and another for REAR in memory all the time to implement a queue.
    But with the help of a Circular linked list we can do this task easily and efficiently because, in a circular linked list, only one pointer is required.

  4. Circular linked list is also used in token rings scheduling in computer networks.

  5. Circular linked list is used to display units like shop boards that require continuous traversal of data.


G. Implementation

#include
using namespace std;
class NodeTaslim {
public:
int data;
NodeTaslim *next;
NodeTaslim() {
data = 0;
next = NULL;
}
NodeTaslim(int x) {
data = x;
next = NULL;
}
};

class CircularLinkedList {
public:
NodeTaslim *head;

/* Insert at front */
int addAtFront(int value);

/* check list is empty or not */
int isEmpty();

/* Insert at end */
int addAtEnd(int value);

/* Search for an element in list */
NodeTaslim *search(int k);

/* Delete a node */
NodeTaslim *deleteNode(int x);

CircularLinkedList() {
head = NULL;
}
};

/* Find last Node of Linked List */
NodeTaslim *getLastNode(NodeTaslim *head) {
NodeTaslim *temp = head;
while (temp->next != head) {
temp = temp->next;
}
return temp;
}

/* Add a Node at Front */
int CircularLinkedList ::addAtFront(int value)
{
int i = 0;
NodeTaslim *n = new NodeTaslim(value);
/* Check list is empty or not */
if (head == NULL) {
n->next = head;
head = n;
i++;
}
else {
NodeTaslim *last = getLastNode(head);
n->next = head;
last->next = n;
head = n;
i++;
}
return i;
}

/* Add a Node at Last */
int CircularLinkedList ::addAtEnd(int value) {
NodeTaslim *n = new NodeTaslim(value);
if (head == NULL) {
head = n;
n->next = NULL;
}
else {
NodeTaslim *last = getLastNode(head);
last->next = n;
n->next = head;
}
}

/* Search an Element in List */
NodeTaslim *CircularLinkedList ::search(int x) {
NodeTaslim *ptr = head;
while (ptr != NULL && ptr->data != x) {
ptr = ptr->next;
}
return ptr;
}

/* Remove Node from List */
NodeTaslim *CircularLinkedList ::deleteNode(int x) {
NodeTaslim *n = search(x);
NodeTaslim *ptr1 = head;
if (ptr1 == NULL) {
cout next = n->next;
return n;
}
else {
while (ptr1->next != n) {
ptr1 = ptr1->next;
}
ptr1->next = n->next;
return n;
}
}

Enter fullscreen mode Exit fullscreen mode

Video liên quan

admin