Circular Singly Linked Lists in Python

Circular Singly Linked Lists are ordered data structures implemented using Linked Lists, where the last node points at the first node of the Linked List in a circular manner.

Circular Singly Linked Lists are similar to Singly Linked Lists. The only difference lies in the fact that the last node points at the header node in a circular manner.

Like Singly Linked Lists, they are dynamic data structures, as they can be extended. Any type of data can be stored.
circular-singly-linked-list

A Circular Linked List node consists of two sections; the value field and the link field which holds the link to the next node in the Linked List. The Circular Linked List class consists of the head pointer which holds the first node in the Linked List.

Characteristics of a Circular Linked List

  • Ordered - Elements in a Circular Singly Linked List follow a certain order
  • Mutable - Elements can be added/ deleted/ modified
  • Dynamic - Length of the Circular Linked List is changeable
  • Any data type can be stored
  • The previous element to the current pointer can be accessed

Implementation of a Circular Singly Linked List

Implementation of the Circular Singly Linked List is quite similar to the implementation of a Singly Linked List, except of course when the Nodes in the Linked List are traversed or searched.

When a Circular Singly Linked List is traversed or searched, the pointer starts from the head pointer and traverses till it reaches the previous element of the starting node.

The Python 3 code to implement a Circular Singly Linked List, and its manipulation methods are as follows.

  1. Defining the Node class which actually holds the data as well as the next element link
    class Node:
        def __init__(self, val):
            self.value = val
            self.next = None​
  2. Defining the Circular Singly Linked List class
    class CSLL:​
  3. Initializing the Linked List constructor with head variable
        def __init__(self):
            self.head = None​
  4. Defining the add() method which is used to add elements to the Circular Singly Linked List
    def add(self, val):​
    1. Checking whether or not the Linked List empty
              if self.empty() is True:
                  self.head = Node(val)
                  self.head.next = self.head
                  print("Head value created")
                  return​
    2. Adding a Node to the beginning of the Linked List
              if opt == 1:
                  a = Node(val)
                  a.next = self.head
                  n = self.head
                  while n.next is not self.head:
                      n = n.next
                  n.next = a
                  self.head = a​
    3. Adding a Node to the end of the Linked List
              elif opt == 2:
                  i = self.head
                  while i.next is not self.head:
                      i = i.next
                  i.next = Node(val)
                  i.next.next = self.head​
    4. Adding a Node in the middle of the Linked List
              elif opt == 3:
                  pos = int(input("Enter the position ::"))
                  i = 1
                  n = self.head
                  f = n.next
                  flag = 0
                  while f is not self.head:
                      if i == pos:
                          flag = 1
                          break
                      f = f.next
                      n = n.next
                      i = i + 1
                  if flag == 1:
                      n.next = Node(val)
                      n.next.next = f
                  else:
                      print("Position not found")​
  5. Defining the delete() method which is used to delete elements from the Circular Singly Linked List
    def delete(self):​
    1. Checking whether or not the Linked List is empty or not, or deleting the last element in the Linked List
              if self.empty() is True:
                  print("Linked List empty")
                  return
              elif self.head.next is self.head:
                  self.head = None
                  return​
    2. Deleting the first element of the Linked List
              if opt == 1:
                  n = self.head
                  while n.next is not self.head:
                      n = n.next
                  n.next = self.head.next
                  self.head = self.head.next​
    3. Deleting the last element of the Linked List
              elif opt == 2:
                  n = self.head
                  while n.next.next is not self.head:
                      n = n.next
                  n.next = self.head​
    4. Deleting an element by position or by value
              else:
                  op = int(input("Enter 1 to delete by position\nEnter 2 to delete by value ::"))
                  if op == 1:
                      pos = int(input("Enter the position ::"))
                      i = 1
                      n = self.head
                      f = self.head.next
                      flag = 0
                      while f.next is not self.head:
                          if i == pos:
                              flag = 1
                              break
                          i = i + 1
                          n = n.next
                          f = f.next
                      if flag == 1:
                          n.next = f.next
                      else:
                          print("Position not found")
                          return
                  else:
                      val = int(input("Enter the value you want to delete ::"))
                      n = self.head
                      f = self.head.next
                      flag = 0
                      while f.next is not self.head:
                          if f.value == val:
                              flag = 1
                              break
                          f = f.next
                          n = n.next
                      if flag == 1:
                          n.next = f.next
                      else:
                          print("Value not found")
                          return​
  6. Defining the clear() method which is used to empty the Circular Singly Linked List
        def clear(self):
            self.head = None
            print("Linked List cleared")​
  7. Defining the empty() method which is used to check whether or not the Circular Singly Linked List is empty
        def empty(self):
            if self.head is None:
                return True
            else:
                return False​
  8. Defining the display() method which is used to present the Circular Singly Linked List in a user-comprehendible form
        def display(self):
            if self.empty() is True:
                print("Linked List empty")
                return
            print("THE LINKED LIST")
            print(self.head.value, " <== HEAD")
            n = self.head.next
            while n is not self.head:
                print(n.value)
                n = n.next
            print("Linked List ends")​
  9. After assembling the program, creating an instance, and defining a menu-driven program to manipulate the Circular Singly Linked List

    class Node:
        def __init__(self, val):
            self.value = val
            self.next = None
    
    class CSLL:
        def __init__(self):
            self.head = None
    
        def add(self, val):
            if self.empty() is True:
                self.head = Node(val)
                self.head.next = self.head
                print("Head value created")
                return
            opt = int(input(
                "Enter 1 to add a Node at the beginning\nEnter 2 to add a Node at the end\nEnter 3 to add a Node in the "
                "middle::"))
            if opt == 1:
                a = Node(val)
                a.next = self.head
                n = self.head
                while n.next is not self.head:
                    n = n.next
                n.next = a
                self.head = a
            elif opt == 2:
                i = self.head
                while i.next is not self.head:
                    i = i.next
                i.next = Node(val)
                i.next.next = self.head
            elif opt == 3:
                pos = int(input("Enter the position ::"))
                i = 1
                n = self.head
                f = n.next
                flag = 0
                while f is not self.head:
                    if i == pos:
                        flag = 1
                        break
                    f = f.next
                    n = n.next
                    i = i + 1
                if flag == 1:
                    n.next = Node(val)
                    n.next.next = f
                else:
                    print("Position not found")
    
        def delete(self):
            if self.empty() is True:
                print("Linked List empty")
                return
            elif self.head.next is self.head:
                self.head = None
                return
            opt = int(input("Enter 1 to delete the beginning element\nEnter 2 to delete the last element\nEnter 3 to "
                            "delete elements in between ::"))
            if opt == 1:
                n = self.head
                while n.next is not self.head:
                    n = n.next
                n.next = self.head.next
                self.head = self.head.next
            elif opt == 2:
                n = self.head
                while n.next.next is not self.head:
                    n = n.next
                n.next = self.head
            else:
                op = int(input("Enter 1 to delete by position\nEnter 2 to delete by value ::"))
                if op == 1:
                    pos = int(input("Enter the position ::"))
                    i = 1
                    n = self.head
                    f = self.head.next
                    flag = 0
                    while f.next is not self.head:
                        if i == pos:
                            flag = 1
                            break
                        i = i + 1
                        n = n.next
                        f = f.next
                    if flag == 1:
                        n.next = f.next
                    else:
                        print("Position not found")
                        return
                else:
                    val = int(input("Enter the value you want to delete ::"))
                    n = self.head
                    f = self.head.next
                    flag = 0
                    while f.next is not self.head:
                        if f.value == val:
                            flag = 1
                            break
                        f = f.next
                        n = n.next
                    if flag == 1:
                        n.next = f.next
                    else:
                        print("Value not found")
                        return
    
        def clear(self):
            self.head = None
            print("Linked List cleared")
    
        def empty(self):
            if self.head is None:
                return True
            else:
                return False
    
        def display(self):
            if self.empty() is True:
                print("Linked List empty")
                return
            print("THE LINKED LIST")
            print(self.head.value, " <== HEAD")
            n = self.head.next
            while n is not self.head:
                print(n.value)
                n = n.next
            print("Linked List ends")
    
    LL = CSLL()
    while True:
        option = int(input("Enter 1 to add an element\nEnter 2 to delete an element\nEnter 3 to clear the Linked "
                           "List\nEnter 4 to display the Linked List\nEnter 5 to exit ::"))
        if option == 1:
            value = int(input("Enter the value you want to add ::"))
            LL.add(value)
            continue
        elif option == 2:
            LL.delete()
            continue
        elif option == 3:
            LL.clear()
            continue
        elif option == 4:
            LL.display()
            continue
        elif option == 5:
            print("Goodbye")
            break
        elif option == 6:
            print(LL.empty())
        else:
            print("Wrong option")

    output

    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::2
    Linked List empty
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::1
    Enter the value you want to add ::5
    Head value created
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::1
    Enter the value you want to add ::6
    Enter 1 to add a Node at the beginning
    Enter 2 to add a Node at the end
    Enter 3 to add a Node in the middle::1
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::1
    Enter the value you want to add ::7
    Enter 1 to add a Node at the beginning
    Enter 2 to add a Node at the end
    Enter 3 to add a Node in the middle::2
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::1
    Enter the value you want to add ::8
    Enter 1 to add a Node at the beginning
    Enter 2 to add a Node at the end
    Enter 3 to add a Node in the middle::3
    Enter the position ::1
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::4
    THE LINKED LIST
    6  <== HEAD
    8
    5
    7
    Linked List ends
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::2
    Enter 1 to delete the beginning element
    Enter 2 to delete the last element
    Enter 3 to delete elements in between ::1
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::2
    Enter 1 to delete the beginning element
    Enter 2 to delete the last element
    Enter 3 to delete elements in between ::2
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::2
    Enter 1 to delete the beginning element
    Enter 2 to delete the last element
    Enter 3 to delete elements in between ::3
    Enter 1 to delete by position
    Enter 2 to delete by value ::1
    Enter the position ::1
    Position not found
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::4
    THE LINKED LIST
    8  <== HEAD
    5
    Linked List ends
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::1
    Enter the value you want to add ::6
    Enter 1 to add a Node at the beginning
    Enter 2 to add a Node at the end
    Enter 3 to add a Node in the middle::2
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::4
    THE LINKED LIST
    8  <== HEAD
    5
    6
    Linked List ends
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::2
    Enter 1 to delete the beginning element
    Enter 2 to delete the last element
    Enter 3 to delete elements in between ::3
    Enter 1 to delete by position
    Enter 2 to delete by value ::2
    Enter the value you want to delete ::5
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::4
    THE LINKED LIST
    8  <== HEAD
    6
    Linked List ends
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::3
    Linked List cleared
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::4
    Linked List empty
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::5
    Goodbye

Advantages and Disadvantages of Circular Singly Linked List

Advantages
  • Traversal can be initiated from any node as all the nodes are connected. The pointer goes on till it reaches the starting node
  • Can be used to implement a queue as two; front and rear variables are not required
  • They are used to cycle through an application running list using a Circular Linked List so that each application is given equal amounts of processor time
Disadvantages
  • Are more complex than simple ones
  • Reversing is more complex than a simple one
  • The danger of ending up in an infinite loop

Applications of Circular Singly Linked Lists

  • Used to implement queues
  • Used to maintain cycles between running applications in computers
  • Used by the Operating System to implement the Round-Robin time-sharing mechanism
0 results
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions