How to Create a Circular LinkedList

Question

I know how to create the Link and LinearLinkedList classes, but I just cannot for the life of me figure out how to modify them into a creating circularlinkedlist.

I have already read the answer to this question. However, I do not understand how if the head is None, then how can a None-type object have a next attribute? I just can't seem to grasp the concept.

If someone could show me the __init__ function of a sample CircularLinkedList and a simple explanation as to how it works, I think I would be able to comprehend it.

Thanks for any and all help

Edit: I only need the list to be traversed forwards. If that is the case, will the logic behind it need to be drastically changed?

Answer 1

            class Node:
                def __init__(self, d=None, n=None, p=None):
                    self.data = d
                    self.next_node = n
                    self.p_node = p
            
                def __str__(self):
                    return '(' + str(self.data) + ')'
            
            
            class CircularlinkedList:
                def __init__(self, r=None):
                    self.root = r
                    self.size = 0
            
                def add(self, d):
                    if self.size == 0:
                        self.root = Node(d)
                        self.root.next_node = self.root
                    else:
                        new_node = Node(d, self.root.next_node)
                        self.root.next_node = new_node
                    self.size += 1
            
                def find(self, d):
                    this_node = self.root
                    while True:
                        if this_node.data == d:
                            return d
                        elif this_node.next_node == self.root:
                            return False
                        this_node = this_node.next_node
            
                def remove(self, d):
                    this_node = self.root
                    prev_node = None
                    while True:
                        if this_node.data == d:
                            if prev_node is not None:
                                prev_node.next_node = this_node.next_node
                            else:
                                while this_node.next_node != self.root:
                                    this_node = this_node.next_node
                                this_node.next_node = self.root.next_node
                                self.root = self.root.next_node
                            self.size -= 1
                            return True
                        elif this_node.next_node == self.root:
                            return False
                        prev_node = this_node
                        this_node = this_node.next_node
            
                def print_list(self):
                    if self.root is None:
                        return
                    this_node = self.root
                    print(this_node, end='->')
                    while this_node.next_node != self.root:
                        this_node = this_node.next_node
                        print(this_node, end='->')
                    print()
            

           

cll = CircularlinkedList()

for i in [5, 7, 3, 8, 9]:

    cll.add(i)

print('Size='+str(cll.size))

print(cll.find(8))

print(cll.find(12))

my_node = cll.root

 for i in range(8):

    my_node = my_node.next_node

    print(my_node,end='->')

print()

cll.print_list()

cll.remove(8)

print(cll.remove(15))

print('Size='+str(cll.size))

cll.remove(5)

cll.print_list()

Answer 2

#Linked List Program to Add and Delete Node Form Head, Tail, in Between Nodes.
class Node:
    """ Node Class having the data and pointer to the next Node"""
    def __init__(self,value):
        self.value=value
        self.nextnode=None
        
class CircularLinkedList(object):
    """ Linked List Class to point the value and the next nond"""
    def __init__(self):
        self.head=None

    def add_head_node(self,value):
        node=Node(value)
        if self.head is None:
            self.head=node
            self.head.nextnode=self.head
            
        crnt_node=node
        crnt_node.nextnode=self.head        
        first_node=self.head
        while first_node.nextnode is not self.head:
            first_node=first_node.nextnode          
        first_node.nextnode=crnt_node
        self.head=crnt_node

    #Adding elements in linked list to the tail.
    def add_tail_node(self,value):
        node=Node(value)
        if self.head is None:
            self.head=node
            self.head.nextnode=self.head
        crnt_node=node
        last_node=self.head
        while last_node.nextnode is not self.head:
            last_node=last_node.nextnode
        #pointing  head's last element to given node
        last_node.nextnode=crnt_node
        #pointing last node next to head nodes of element
        crnt_node.nextnode=self.head

    #Adding elements in linked after given Node.
    def add_after_node(self,after_value,value):
        node=Node(value)
        if self.head is None:
            self.head=node
            self.head.nextnode=self.head
        new_node=node
        after_node=Node(after_value)
        head_node=self.head
        while head_node.value !=after_node.value:
            head_node=head_node.nextnode
            last_node=head_node.nextnode
        head_node.nextnode=new_node
        new_node.nextnode=last_node
        head_node=head_node.nextnode

    #Adding elements in linked before given Node.
    def add_before_node(self,bfr_value,value):
        node=Node(value)
        if self.head is None:
            self.head=node
            self.head.nextnode=self.head
        new_node=node
        bfr_node=Node(bfr_value)
        head_node=self.head
        while head_node.nextnode.value!=bfr_node.value:
            head_node=head_node.nextnode
            last_node=head_node.nextnode
        head_node.nextnode=new_node
        new_node.nextnode=last_node
        head_node=head_node.nextnode
        #self.head=head_node.nextnode

    #deleting Head Node of Linked List
    def del_head_node(self):
        if self.head is None:
            print('Can not delete elements from Empty Linked List')
            return
        crnt_node=self.head.nextnode
        pointer_head=self.head.nextnode
        while pointer_head.nextnode.value!=self.head.value:
            pointer_head=pointer_head.nextnode
        pointer_head.nextnode=crnt_node
        self.head=crnt_node
        
    #deleting tail Node of Linked List
    def del_tail_node(self):
        if self.head is None:
            print('Can not delete elements from Empty Linked List')
            return
        crnt_node=self.head.nextnode
        #head_node=self.head
        while crnt_node.nextnode.nextnode.value!=self.head.value:
            crnt_node=crnt_node.nextnode
        crnt_node.nextnode=self.head

    #delete beteween node from Linked List
    def del_bw_node(self,value):
        node=Node(value)
        if self.head is None:
            print('Can not delete elements from Empty Linked List')
            return
        crnt_node=self.head
        while crnt_node.nextnode.value!=node.value:
            crnt_node=crnt_node.nextnode
            last_node=crnt_node.nextnode.nextnode
        crnt_node.nextnode=last_node

    #Function to print linked list node 
    def print_list(self):
        crnt_node=self.head
        while True:
            print(f'{crnt_node.value}->',end='')
            if crnt_node.nextnode is self.head:
                print(f'{self.head.value}',end='')
                break
            crnt_node = crnt_node.nextnode
        print()


cir_llist=CircularLinkedList()
cir_llist.add_head_node(1)
cir_llist.print_list()
cir_llist.add_head_node(2)
cir_llist.print_list()
cir_llist.add_head_node(3)
cir_llist.print_list()
cir_llist.add_head_node(4)
cir_llist.print_list()
cir_llist.add_head_node(5)
cir_llist.print_list()
cir_llist.add_tail_node(6)
cir_llist.print_list()
cir_llist.add_tail_node(8)
cir_llist.print_list()
cir_llist.add_after_node(6,7)
cir_llist.print_list()
cir_llist.add_before_node(6,0)
cir_llist.print_list()
cir_llist.add_before_node(0,10)
cir_llist.print_list()
cir_llist.del_head_node()
cir_llist.print_list()
cir_llist.del_head_node()
cir_llist.print_list()
cir_llist.del_tail_node()
cir_llist.print_list()
cir_llist.del_tail_node()
cir_llist.print_list()
cir_llist.del_bw_node(10)
cir_llist.print_list()
cir_llist.del_bw_node(0)
cir_llist.print_list()

Answer 3

Often in a circular linked list, you have a special link that doesn't contain meaningful data. Instead, it's a "sentinel" letting you know where the beginning (and end) of the list is. This link will exist even when the list is empty, so your algorithms will work on all lists, without lots of special cases needing special code.

class Link:
    def __init__(self, data, next):
        self.data = data
        self.next = next

class CircularLinkedList:
    def __init__(self):
        self.head = Link(None, None) # this is the sentinel node!
        self.head.next = self.head   # link it to itself

    def add(self, data):             # no special case code needed for an empty list
        self.head.next = Link(data, self.head.next)

    def __contains__(self, data):    # example algorithm, implements the "in" operator
        current = self.head.next
        while current != self.head:
            if current.data == data: # element found
                return True
            current = current.next
        return False

Answer 4

Indeed; if there are no nodes, then there can be no next/previous pointers:

root
 |
 v
None

If there is one node, it links backwards and forwards to itself:

    root
     |
     v
+-> Node <-+
|   next---+
+---prev

If there are two nodes:

      root
       |
       v
  +-> Node   +-> Node <--+
  |   next---+   next--+ |
+-|---prev <-----prev  | |
| +--------------------+ |
+------------------------+

Answer 5

The crucial step here is that the head is not None. Only the data of the head's Link node is None, and it points to itself via its next attribute. As mentioned in the answer you linked to, that would look something like this:

def __init__(self):
    self.head = Link(None, None)
    self.head.next = self.head