Gallery
Share
Explore

PYTHON Data Structures: creating a circular linked list in Python

Introducing data structures through a hands-on lab will be our lead in to working with MONGO databases and BPEL in PYTHON.
For this lab, we'll focus on creating a circular linked list in Python.
A circular linked list is a sequence of elements in which every element has a link to its next element in the sequence and the last element has a link back to the first element, forming a circle.
This lab will reinforce not just the concept of linked lists but also the idea of object composition (association of objects by object reference), as each node in the linked list is an object that contains data and a reference to another node.

Lab: Implementing a Circular Linked List in Python

#### Objective: Learn to implement basic data structures in Python and understand the concept of object composition through the creation of a circular linked list.
#### Prerequisites: - Basic understanding of Python classes and objects. - Familiarity with fundamental data structure concepts.
#### Tools Required: - Python 3.x installed on your system. - Text editor or IDE.
#### Lab Tasks:

**Part 1: Node Class Implementation**

1. **Creating the Node Class** - Implement a `Node` class with two attributes: `data` and `next`. - The `__init__` method should initialize these attributes.
```python ​class Node: def __init__(self, data): self.data = data self.next = None ```

**Part 2: Circular Linked List Implementation**

1. **Creating the CircularLinkedList Class** - Implement a `CircularLinkedList` class. - It should have a `head` attribute initialized to `None`.
2. **Adding Elements** - Implement an `add` method to add a new `Node` to the list. - This method should handle both an empty list and adding to an existing list.
3. **Making the List Circular** - Modify the `add` method to ensure the last node's `next` points back to the `head`.
class CircularLinkedList: def __init__(self): self.head = None
def add(self, data): new_node = Node(data) if not self.head: self.head = new_node self.head.next = self.head else: current = self.head while current.next != self.head: current = current.next current.next = new_node new_node.next = self.head ```
Part 3: Testing the Circular Linked List**
1. **Creating and Populating the List** - Instantiate a `CircularLinkedList`. - Add nodes containing data from 0 to 9.
2. **Traversing the List** - Implement a method to traverse the list and print each node's data. - Ensure the traversal stops after one full cycle to avoid an infinite loop.
```python def print_list(self): current = self.head if current: while True: print(current.data, end=" ") current = current.next if current == self.head: break print() ```
3. **Display the Circular Linked List** - Call the `print_list` method to display the list.
```python # Testing the Circular Linked List circular_list = CircularLinkedList() for i in range(10): circular_list.add(i)
circular_list.print_list() ```
#### Evaluation: - Review the implementation of the `Node` and `CircularLinkedList` classes. - Ensure that the circular linked list correctly loops back to the beginning. - Test the traversal method to check if it correctly prints all nodes exactly once.
#### Conclusion: This lab provides hands-on experience with one of the fundamental data structures, the linked list, and introduces the concept of circular linked lists. It also reinforces understanding of object composition in Python.
After completing this lab, students should have a good grasp of how linked lists work and how they can be implemented and manipulated in Python.
Want to print your doc?
This is not the way.
Try clicking the ⋯ next to your doc name or using a keyboard shortcut (
CtrlP
) instead.