Intro

Circular Linked List Operations

There are three basic cases to make insertion to a list:

Traversing the list

Text

class Node:
    """Initiate node instance of a list."""
    def __init__(self, data=None, next=None, previous=None):
        self.data = data
        self.next = next
        self.previous = previous

class circularLinkedList(object):
    """Initialize an instance of circular linked list."""
    def __init__(self, head=None, tail=None):
        self.head = head
        self.tail = tail

Inserting new nodes

Text

def insert_head(self, data):
    self.insert_anywhere(0, data)

def insert_tail(self,data):
    self.insert_anywhere(len(self), data)

def insert_anywhere(self, position, data):
    if position < 0 or position > len(self):
        raise IndexError('Index out of range.')
    newNode = Node(data)
    if self.head is None:
        newNode.next = newNode
        self.tail = self.head = newNode
    elif position == 0:  # insert at head
        newNode.next = self.head
        self.head = self.tail.next = newNode
    else:
        temp = self.head
        for _ in range(position - 1):
            temp = temp.next
        newNode.next = temp.next
        temp.next = newNode
        if position == len(self) - 1:
            self.tail = newNode

Deleting nodes

Text

def delete_head(self):
    self.delete_anywhere(0)

def delete_tail(self):
    self.delete_anywhere(len(self) - 1)

def delete_anywhere(self,position):
    if not 0 <= position <= len(self):
        raise IndexError('Index out of range.')
    deleteNode = self.head
    if self.head == self.tail:
        self.head = self.tail = None
    elif position == 0:
        self.tail.next = self.tail.next.next
        self.head = self.head.next
    else:
        temp = self.head
        for i in range(position - 1):
            temp = temp.next
        deleteNode = temp.next
        temp.next = temp.next.next
        if position == len(self) - 1:
            self.tail = temp

Concluding notes

I wrote other blog posts on the implementation of linked lists. Namely:

All code that used in the blog post can be found in this GitHub repo.