Using Circular Linked Lists

00:00 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:34 You could also use it to manage the application life cycle of a given operating system or implement a Fibonacci heap.

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.

00:58 You do have to be careful though. Because the list is circular, you have to make sure you check for the node you started traversing on if you don’t want to traverse the structure indefinitely.

01:11 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.

01:23 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.

01:38 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.

02:05 Finally, because we never yield the final node in the sequence now stored in the node variable, we yield that too.

02:14 We can also create one more method that will print the linked list with arrows representing the links. This is very similar to how we implemented this with the singly linked list.

02:28 I’m here in the interactive shell so I can test out this new linked list. I’ll call it circular_llist. Those methods you saw earlier were stored in a class called CircularLinkedList.

02:44 As you can see, the list starts off empty. Now, we have to create the nodes and link them all manually, making sure that the .next attribute of the last node points to the first node.

02:57 After all, this is a circular linked list. Once all the nodes are created, all that’s left to do is point the head to the first node.

03:10 And now, we can try printing the list.

03:14 If we supply no arguments, it’ll start with the head node, which in this case is a. We can also start traversing at any different point, say b.

03:29 You can see that traversal happens so long as the next element is not b—it stops at a. And that is the circular linked list.