How do you find the middle element in a circular linked list?

Find middle element of circular linked list in python

Python program for Find middle element of circular linked list. Here problem description and explanation.

Table of Contents Show

Find middle element of circular linked list in python
Find middle element of circular linked list in java
Q. Program to insert a new node at the middle of the circular linked list.
Explanation
Q. Program to delete a new node from the middle of the circular linked list.
Explanation
Circular Linked List
Implementing Circular Linked List

# Python 3 Program # Find middle element in circular linked list class LinkNode : def __init__(self, data) : self.data = data self.next = None class CircularLinkedList : # Class constructor def __init__(self) : self.head = None # Add element at end of circular linked list def insert(self, data) : # Create a new node node = LinkNode(data) if (self.head == None) : self.head = node else : temp = self.head # Find the last node while (temp.next != self.head) : # Visit to next node temp = temp.next # Add node temp.next = node # Connect last node to head node.next = self.head # Display node element of circular linked list def display(self) : if (self.head == None) : print("Empty Linked List") else : temp = self.head # iterate linked list while (temp != None) : # Display node print("", temp.data, end = " ") # Visit to next node temp = temp.next if (temp == self.head) : # Stop iteration return # Find middle node of given circular linked list def findMiddle(self) : if (self.head == None) : print("Empty Linked List") else : if (self.head.next != self.head and self.head.next.next != self.head) : temp = self.head middle = self.head # Find middle node while (temp != None and temp.next != self.head and temp.next.next != self.head) : middle = middle.next temp = temp.next.next print("\n Middle Node is : ", middle.data) else : print("\nLess than three nodes") def main() : cll = CircularLinkedList() # Add linked list nodes cll.insert(1) cll.insert(2) cll.insert(3) cll.insert(4) cll.insert(5) cll.insert(6) cll.insert(7) cll.display() cll.findMiddle() if __name__ == "__main__": main()

Output

1 2 3 4 5 6 7 Middle Node is : 4

Find middle element of circular linked list in java

Java program for Find middle element of circular linked list. Here more information.

// Java Program // Find middle element in circular linked list class LinkNode { public int data; public LinkNode next; public LinkNode(int data) { this.data = data; this.next = null; } } class CircularLinkedList { public LinkNode head; // Class constructor public CircularLinkedList() { this.head = null; } // Add element at end of circular linked list public void insert(int data) { // Create a new node LinkNode node = new LinkNode(data); if (this.head == null) { this.head = node; } else { LinkNode temp = this.head; // Find the last node while (temp.next != this.head) { // Visit to next node temp = temp.next; } // Add node temp.next = node; } // Connect last node to head node.next = this.head; } // Display node element of circular linked list public void display() { if (this.head == null) { System.out.println("Empty Linked List"); } else { LinkNode temp = this.head; // iterate linked list while (temp != null) { // Display node System.out.print(" " + temp.data); // Visit to next node temp = temp.next; if (temp == this.head) { // Stop iteration return; } } } } // Find middle node of given circular linked list public void findMiddle() { if (this.head == null) { System.out.println("Empty Linked List"); } else { if (this.head.next != this.head && this.head.next.next != this.head) { LinkNode temp = this.head; LinkNode middle = this.head; //Find middle node while (temp != null && temp.next != this.head && temp.next.next != this.head) { middle = middle.next; temp = temp.next.next; } System.out.println("\n Middle Node is : " + middle.data); } else { System.out.println("\nLess than three nodes"); } } } public static void main(String[] args) { CircularLinkedList cll = new CircularLinkedList(); // Add linked list nodes cll.insert(1); cll.insert(2); cll.insert(3); cll.insert(4); cll.insert(5); cll.insert(6); cll.insert(7); cll.display(); cll.findMiddle(); } }

Output

1 2 3 4 5 6 7 Middle Node is : 4

Q. Program to insert a new node at the middle of the circular linked list.

Explanation

In this program, we create a circular linked list and insert a new node in the middle of the list. If the list is empty, both head and tail will point to new node. If the list is not empty, then we will calculate the size of the list and divide it by 2 to get the mid-point of the list where the new node needs to be inserted.

After inserting the new node in the middle of the list.

Consider the above diagram; the new node needs to be added to the middle of the list. First, we calculate the size which in this case is 4. So, to get the mid-point, we divide it by 2 and store it in a variable count. We will define two nodes current, and temp such that temp will point to head, and current will point to the node previous to temp. We iterate through the list till mid-point is reached by incrementing temp to temp.next then, insert the new node in between current and temp. Current'next node will be new and the new's next node will be temp.

Algorithm

Define a Node class which represents a node in the list. It has two properties data and next which will point to the next node.
Define another class for creating the circular linked list and it has two nodes: head and tail. Variable size stores the size of the list. It has two methods: addInMid() and display() .
addInMid() will add the node to the middle of the list:
1. It first checks whether the head is null (empty list), then it will insert the node as the head.
2. Both head and tail will point to the newly added node.
3. If the list is not empty, then we calculate size and divide it by 2 to get the mid-point.
4. Define node temp that will point to head and current will point to a node previous to temp.
5. Iterate through the list until the middle of the list is reached by incrementing temp to temp.next.
6. The new node will be inserted after current and before temp such that current will point to the new node and the new node will point to temp.
display() will show all the nodes present in the list.
1. Define a new node 'current' that will point to the head.
2. Print current.data till current will points to head again.
3. Current will point to the next node in the list in each iteration.

Q. Program to delete a new node from the middle of the circular linked list.

Explanation

In this program, we will create a circular linked list and delete a node from the middle of the list. If the list is empty, display the message "List is empty". If the list is not empty, we will calculate the size of the list and then divide it by 2 to get the mid-point of the list. We maintain two pointers temp and current. Current will point to the previous node of temp. We will iterate through the list until mid-point is reached then the current will point to the middle node. We delete middle node such that current's next will be temp's next node.

Circular linked list after deleting node from middle of the list

Consider the above list. Size of the list is 4. Mid-point of the node is 2. To remove C from the list, we will iterate through the list till mid-point. Now current will point to B and temp will point to C. C will be removed when B will point to D.

Algorithm

Define a Node class which represents a node in the list. It has two properties data and next which will point to the next node.
Define another class for creating the circular linked list and it has two nodes: head and tail. It has a variable size and two methods: deleteMid() and display() .
deleteMid() will delete the node from the middle of the list:
1. It first checks whethe the head is null (empty list) then, it will return from the function as there is no node present in the list.
2. If the list is not empty, it will check whether the list has only one node.
3. If the list has only one node, it will set both head and tail to null.
4. If the list has more than one node then, it will calculate the size of the list. Divide the size by 2 and store it in the variable count.
5. Temp will point to head, and current will point to the previous node to temp.
6. Iterate the list till current will point middle node of the list.
7. Current will point to node next to temp, i.e., removes the node next to current.
display() will show all the nodes present in the list.
1. Define a new node 'current' that will point to the head.
2. Print current.data till current will points to head again.
3. Current will point to the next node in the list in each iteration.

Circular Linked List

Circular Linked List is 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

The real life application where the circular linked list is used is our Personal Computers, where multiple applications are running. All the running applications are kept in a circular linked list and the OS gives a fixed time slot to all for running. The Operating System keeps on iterating over the linked list until all the applications are completed.
Another example can be Multiplayer games. All the Players are kept in a Circular Linked List and the pointer keeps on moving forward as a player's chance ends.
Circular Linked List can also be used to create Circular Queue. In a Queue we have to keep two pointers, FRONT and REAR in memory all the time, where as in Circular Linked List, only one pointer is required.

Implementing Circular Linked List

Implementing a circular linked list is very easy and almost similar to linear linked list implementation, with the only difference being that, in circular linked list the last Node will have it's next point to the Head of the List. In Linear linked list the last Node simply holds NULL in it's next pointer.

So this will be oue Node class, as we have already studied in the lesson, it will be used to form the List.

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

Circular Linked List class will be almost same as the Linked List class that we studied in the previous lesson, with a few difference in the implementation of class methods.

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 beginning :

The first Node is the Head for any Linked List.
When a new Linked List is instantiated, it just has the Head, which is Null.
Else, the Head holds the pointer to the fisrt Node of the List.
When we want to add any Node at the front, we must make the head point to it.
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.
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 :

If the Linked List is empty then we simply, add the new Node as the Head of the Linked List.
If the Linked List is not empty then we find the last node, and 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

In searhing we do not have to do much, we just need to traverse like we did while getting the last node, in this case we will also compare the data of the Node. If we get the Node with the same data, we will return it, otherwise we will make our pointer point 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 done in many ways, like we first search the Node with data which we want to delete and then we delete it. In our approach, we will define a method which will take the data to be deleted as argument, will use the search method to locate it and will then remove 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 point 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; } }

← Prev
Next →

C++ Code

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* middleNode(ListNode* head) { int n = 0; ListNode* temp = head; while(temp) { n++; temp = temp->next; } temp = head; for(int i = 0; i < n / 2; i++) { temp = temp->next; } return temp; } };

Solution 2: [Efficient] Tortoise-Hare-Approach

Unlike the above approach, we don’t have to maintain nodes count here and we will be able to find the middle node in a single traversal so this approach is more efficient.

Intuition: In the Tortoise-Hare approach, we increment slow ptr by 1 and fast ptr by 2, so if take a close look fast ptr will travel double than that of the slow pointer. So when the fast ptr will be at the end of Linked List, slow ptr would have covered half of Linked List till then. So slow ptr will be pointing towards the middle of Linked List.

Approach:

Create two pointers slow and fast and initialize them to a head pointer.
Move slow ptr by one step and simultaneously fast ptr by two steps until fast ptr is NULL or next of fast ptr is NULL.
When the above condition is met, we can see that the slow ptr is pointing towards the middle of Linked List and hence we can return the slow pointer.

Code:

C++ Code

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* middleNode(ListNode* head) { ListNode *slow = head, *fast = head; while (fast && fast->next) slow = slow->next, fast = fast->next->next; return slow; } };