Concept of Simple Circular List

Question

I wanted to know how this process works that the next pointer of the last element points to the first element of the list?

Answer 1

I wanted to know how this process works from that next pointer of the last element points to the first element of the list?

Here’s how it works: the next element pointer in the list points to the first element in the list.

Jokes aside: first, in general we do not need to implement circular (or other) lists in Python, because the data structures provided by the language are suicidal for the greater majority of real-use cases - the lists, dictionaries, sets and their variants.

Second: in Python there are no "pointers". Although in the reference implementation it is simple to obtain the number that represents the memory address of an object, this number is not used. We talk about objects always. This is easy to tidy up, it is only instead of "pointer" we speak in "reference". The phrase reads "Why the next reference of the last element is again the first element".

Third, the normal Python (list) list is not a linked list - it is a sequential list in memory even. The only thing that is special is a logic to pre-allocate the space occupied by the list according to the amount of elements.

Fourth: We can build our own data structures in Python, which can even behave like sequences or mappings and be used in place of Python lists or dictionaries almost everywhere. It is enough that the class that represents your object has the appropriate "magic methods". There is an implementation that, for use is equivalent to a circular list in the standard Python library which is the "deck" object, is in Collections mode. It allows equally efficient insertions in the last or first elements, and "rotate" the beginning, so that an element that was in the middle becomes the new beginning. I don’t know if the implementation of "deck" is a circular list.

But then, in a "classic" circular list implementation, usually in a lower-level linkage than Python, a list "node" only knows two things: the value that is stored in it, and a reference to the next node. If the last node has an "empty" reference (for Null in C), this would not be a circular list. The last reference being to the first node causes the list to "neither begin nor end": any node you catch allows you to go through the entire list.

In Python, if we create a class to function as a circular list node that has the method __iter__ to iterate the whole list, and a way to insert new elements (for example a .append that inserts something after the current node), we already have a circular list - with some other methods (__repr__, extend, __len__) this object can be functional enough to be used in production code in a pleasant way:

class CircularNode:
    def __init__(self, values, next=None):
        try:
            len(values)
        except TypeError:
            values = list(values)
        self.value = values[0]
        self.next = self if next is None else next
        if len(values) >= 2:
            self.extend(values[1:])

    def __getitem__(self, index):
        if index == 0:
            return self.value
        return self.next.__getitem__(index + (1 if index < 0 else -1))

    def __setitem__(self, index, value):
        if index == 0:
            self.value = value
            return
        return self.next.__setitem__(index + (1 if index < 0 else -1), value)

    def __iter__(self):
        node = self
        while True:
            yield node.value
            node = node.next
            if node is self:
                return

    def __len__(self):
       return sum(1 for _ in self)

    def append(self, value):
        self.next = CircularNode([value], next=self.next)

    def extend(self, values):
        for value in reversed(values):
            self.append(value)

    def __repr__(self):
        return f"<Circular>[{', '.join(repr(item) for item in self)}]"

And this can be used like this (Example in interactive session):

In [9]: a  = CircularNode(range(3))                                                                                               

In [10]: a                                                                                                                        
Out[10]: <Circular>[0, 1, 2]

In [11]: b = a.next.next                                                                                                          

In [12]: b                                                                                                                        
Out[12]: <Circular>[2, 0, 1]

In [13]: b.append(3)                                                                                                              

In [14]: a                                                                                                                        
Out[14]: <Circular>[0, 1, 2, 3]

In [15]: b                                                                                                                        
Out[15]: <Circular>[2, 3, 0, 1]