Circular Linked List...

Circular Linked List in Data Structure

• Circular Linked List is a little more complicated linked data structure. In the circular linked list we can insert elements anywhere in the list whereas in the array we cannot insert element anywhere in the list because it is in the contiguous memory.
• In the circular linked list the previous element stores the address of the next element and the last element stores the address of the starting element. 
• The elements points to each other in a circular way which forms a circular chain. The circular linked list has a dynamic size which means the memory can be allocated when it is required.

Application of Circular Linked List

• Our personal computers, which run several apps, are an example of a real-world application where the circular linked list is used. All running apps are kept in a circular linked list, and the OS assigns each one a certain time slot to run. The Operating System iterates through the linked list until all of the apps have been completed.
• Multiplayer games are another example. All of the players are kept in a circular linked list, and as each player's chance expires, the pointer moves onward.
• A circular Queue can also be created using a Circular Linked List. In a Queue, we must always retain two pointers in memory, FRONT and REAR, however in a Circular Linked List, only one pointer is necessary.

---

Implementing Circular Linked List

• The main difference is that in a circular linked list, the last Node will have its next point to the Head of the List, whereas in a linear linked list, the last Node would have its next point to the End of the List. In a linear linked list, the last node's next pointer is simply NULL.
• So this will be our Node class, which will be utilized to build the List, as we've already seen in the lecture.

class Node {
  public:
  int data;
  //pointer to the next node
  node* next;
    node() {
    data = 0;
    next = NULL;
  }
  node(int x) {
    data = x;
    next = NULL;
  }
} 

Circular Linked List

• With a few variations in the implementation of class methods, the Circular Linked List class will be nearly identical to the Linked List class we examined in the previous session.

class CircularLinkedList {
  public:
  node *head;
  //declaring the functions
    //function to add Node at front
  int addAtFront(node *n);
  //function to check whether Linked list is empty
  int isEmpty();
  //function to add Node at the End of list
  int addAtEnd(node *n);
  //function to search a value
  node* search(int k);
  //function to delete any Node
  node* deleteNode(int x);
    CircularLinkedList() {
    head = NULL;
  }
}

---

Insertion at the Beginning

Steps to insert a Node at the beginning :

1. The first Node is the Head for any Linked List.
2. When a new Linked List is instantiated, it just has the Head, which is Null.
3. Else, the Head holds the pointer to the first node of the List.
4. When we want to add any Node at the front, we must make the head point to it.
5. And the Next pointer of the newly added Node, must point to the previous Head, whether it be NULL(in case of new List) or the pointer to the first node of the List.
6. The previous Head Node is now the second Node of Linked List because the new Node is added at the front.

int CircularLinkedList :: addAtFront(node *n) {
  int i = 0;
  /* If the list is empty */
  if(head == NULL) {
    n->next = head;
    //making the new Node as Head
    head = n;
    i++;
  }
  else {
    n->next = head;
    //get the Last Node and make its next point to new Node
    Node* last = getLastNode();
    last->next = n;
    //also make the head point to the new first Node
    head = n;
    i++;
  }
  //returning the position where Node is added
  return i;
}

---

Insertion at the End

Steps to insert a Node at the end :

1. If the Linked List is empty then we simply, add the new Node as the Head of the Linked List.
2. If the Linked List is not empty then we find the last node, make it' next to the new Node, and make the next of the Newly added Node point to the Head of the List.

int CircularLinkedList :: addAtEnd(node *n) {
  //If list is empty
  if(head == NULL) {
    //making the new Node as Head
    head = n;
    //making the next pointer of the new Node as Null
    n->next = NULL;
  }
  else {
    //getting the last node
    node *last = getLastNode();
    last->next = n;
    //making the next pointer of new node point to head
    n->next = head;
  } 
}

---

Searching for an Element in the List

• We don't have to do much in terms of searching; we only need to traverse like we did when getting the last node, except this time we'll compare the data of the Node. 
• If we find another Node with the same data, we'll return it; if not, we'll move our pointer to the next node, and so on.

node* CircularLinkedList :: search(int x) {
  node *ptr = head;
  while(ptr != NULL && ptr->data != x) {
    //until we reach the end or we find a Node with data x, we keep moving
    ptr = ptr->next;
  }
  return ptr;
}

---

Deleting a Node from the List

Deleting a node can be achieved in a variety of ways, such as by first searching for the Node with the data we want to delete, and then deleting it. In our method, we'll construct a method that takes the data to be removed as an argument, locates it using the search method, and then removes the Node from the List.

To remove any Node from the list, we need to do the following :

• If the Node to be deleted is the first node, then simply set the Next pointer of the Head to point to the next element from the Node to be deleted. And update the next pointer of the Last Node as well.
• If the Node is in the middle somewhere, then find the Node before it, and make the Node before it points to the Node next to it.
• If the Node is at the end, then remove it and make the new last node point to the head.

node* CircularLinkedList :: deleteNode(int x) {
  //searching the Node with data x
  node *n = search(x);
  node *ptr = head;
  if(ptr == NULL) {
    cout << "List is empty";
    return NULL;
  }
  else if(ptr == n) {
    ptr->next = n->next;
    return n;
  }
  else {
    while(ptr->next != n) {
      ptr = ptr->next;
    }
    ptr->next = n->next;
    return n;
  }
}

---