Using Circular Linked Lists
Another more advanced type of linked list is the circular linked list. This linked list looks just like the singly linked list, except instead of the tail node pointing to
None, it points to the head.
00:15 This creates a circular structure where we can traverse the nodes indefinitely. There are a few uses for a data structure like this. For one, you could use it to simulate going around each player’s turn in a multiplayer game, like a game of cards.
00:44 One advantage of the circular linked list is that you can traverse the whole list starting at any node. You can create a pointer to any node in the list, and you know that all of the nodes are still accessible to you.
Let’s look at some code to implement this. This kind of linked list uses nodes with a reference to data, as well as a reference to the next node. The
.__init__() method is pretty straightforward.
We create an instance attribute called
head, which starts out pointing to
None. We can create a
.traverse() method that will yield all of the elements in the linked list, being careful not to get stuck in an infinite loop.
If the user doesn’t supply a starting point, we set the starting point equal to the head. Then, we create a new variable called
node that will hold the current node we’re working on. While the
node is not
None and the
.next attribute is not the starting point—which would mean that we’re at the beginning of the list, again—we yield the
node and set it equal to the next node in the sequence.
Become a Member to join the conversation.