Search⌘ K
Home
Courses
Data Structures and Algorithms in Python

Introduction and Insertion

Explore the concept of circular linked lists and understand their structure where the tail node points to the head. Learn to implement key methods such as append, prepend, and print in Python. This lesson helps you distinguish circular linked lists from singly linked lists and prepare for solving related coding problems.

We'll cover the following...

Introduction

First of all, let’s talk about what a circular linked list is. It is very similar to a singly linked list except for the fact that the next of the tail node is the head node instead of null.

Below is an illustration to help you visualize a circular linked list:

You can see from the illustration above that the circular linked list contains the same kind of nodes as a singly linked list. As the name circular suggests, the tail node points to the head of the linked list instead of pointing to null which makes the linked list circular. Now let’s implement it in Python:

Python 3.5
class Node:
    def __init__(self, data):
      self.data = data
      self.next = None
class CircularLinkedList:
    def __init__(self):
      self.head = None 
    def prepend(self, data):
      pass
    def append(self, data):
      pass
    def print_list(self):
      pass

The Node class is the same as before. Also, the constructor of CircularLinkedList class is identical to the constructor of the LinkedList class. However, the methods prepend, append, and print_list will be different this time.

append

Appending to a circular linked list implies inserting the new node after the node that was previously pointing to the head of the linked list.

Let’s have a look at the code below for the append method:

Python 3.5
def append(self, data):
  if not self.head:
      self.head = Node(data)
      self.head.next = self.head
  else:
      new_node = Node(data)
      cur = self.head
      while cur.next != self.head:
          cur = cur.next
      cur.next = new_node
      new_node.next = self.head

One case is to append to an empty linked list. In this case, we make the new node the head of the linked list, and its next node is itself. So, we’ll ...