Data Structures and Algorithms in Python/

...

/

Introduction and Insertion

Introduction and Insertion

In this lesson, you will be introduced to circular linked lists and you will learn how to insert elements into a circular linked list.

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:

Press + to interact
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:

Press + to interact
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 ...