Saurabh RaiIn the last article, we learned about Object Oriented Programming and had a mountain overview of Python's Magic/Dunder methods.
Object-Oriented Programming (OOP) in Python: This paradigm in Python revolves around creating reusable code. It involves using classes as blueprints for objects. These objects can have attributes (data) and methods (functions) that define their behavior and interactions.
Python's Magic/Dunder Methods: Magic or Dunder (double underscore) methods in Python are special methods with names that start and end with double underscores (e.g., __init__, __str__, __repr__).
You'll be able to read about it here. 👇
Today, we will expand upon it and use the knowledge of Object Oriented Programming to understand and create Linked Lists in Python. And will perform some operation on it.
Open Source Python Project: Swirl
If you're interested in Python, you will 💖 Swirl. Swirl is an open-source search platform which will give you knowledge of the following:
- Python
- Artificial Intelligence
- Integrating Large Language Models in any product
- Learn how to develop a search platform.
Check our GitHub Repository:
Swirl on GitHub
We'll be delighted if you could:
Linked List
Linked lists are an ordered collection of objects. It's a data structure designed to hold data in a non-contiguous memory block.
Unlike arrays or traditional lists that use contiguous memory blocks, linked lists are stored in non-contiguous memory locations. This design allows for efficient insertions and deletions without rearranging the entire data structure.
This design allows for efficient insertions and deletions without the need to rearrange the entire data structure.
Basic Linked List
A basic linked list is a linear data structure where each element, known as a node, contains two parts: data and a reference to the next node in the list. This structure allows for efficient insertion and deletion of elements, as it does not require shifting elements, unlike in an array.
A typical node design:
Data: This contains the data, which can be numeric, address, text, etc.
Next: This points to the next data node or holds the address for the next data node.
The first node is called the head of the list, and the last node, which points to None (in Python) (or Null in other Languages), is known as the tail.
When you collect a lot of nodes together, it becomes a linked list.
Benefits of Linked Lists & Time Complexity of Operations
Linked lists offer several benefits, particularly in dynamic data manipulation scenarios. Here are some key advantages:
- Dynamic Size: Unlike arrays, linked lists can grow or shrink in size dynamically, which is efficient for memory usage.
- Ease of Insertion/Deletion: Inserting or deleting nodes is relatively simple, as it generally only involves changing a few references without shifting elements as in an array.
- Flexibility: They can implement other data structures like stacks, queues, and graph adjacency lists.
| Operation | Time Complexity |
|---|---|
| Access | O(n) |
| Search | O(n) |
| Insertion | O(1) |
| Deletion | O(1) |
Note: We're taking into account a singly linked list.
Implementing a Linked List in Python.
This is the code that will create a Node in Python. Please note, if you are confused about the __repr__ method. Please check the previous article in this series.
class Node:
def __init__(self, data):
self.data = data
self.next = None
def __repr__(self):
return f"Node({self.data})"
Code for the Linked List Class. This utilizes the Node class cleared about to create data and link the all together.
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
def __repr__(self):
nodes = []
current = self.head
while current:
nodes.append(repr(current))
current = current.next
return "->".join(nodes)
This code does two things:
- Append: Append a node at the end of the linked list.
-
__repr__: This method traverses the linked list and prints it in a Pythonic Way.- This can also be done using a method called traverse.
This is the output of print(llist) which called `repr_` method:
Traversing a Linked List.
Traversing a linked list is the process of going through each node and printing it.
def traverse(linked_list):
current = linked_list.head
while current:
print(current.data)
current = current.next
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
print("Traversing the linked list:")
traverse(llist)
Reversing a Linked List
The idea is to iterate through the linked list and, for each node, switch its next pointer to point to the previous node instead of the next one. This will help us reverse the linked list.
def reverse_linked_list(head):
previous = None
current = head
while current:
next_node = current.next
current.next = previous
previous = current
current = next_node
return previous
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
print("Original List:", llist)
new_head = reverse_linked_list(llist.head)
llist.head = new_head
print("Reversed List:", llist)
Inserting Values in a Linked List
We already have an append function that adds a value to the end of the linked list. But what if we want to have a method that adds at a specific location, and if that location is not present then append the value at the end.
class LinkedList:
def insert_after_value(self, data_after, data_to_insert):
if self.head is None:
return
current = self.head
while current:
if current.data == data_after:
new_node = Node(data_to_insert)
new_node.next = current.next
current.next = new_node
return
current = current.next
self.append(data_to_insert)
Deleting a Node in a Linked List
To delete a node from a linked list, create a function that takes the head of the list and the node's data to be deleted as arguments. And traverse the list till the data is found, and then delete it.
class LinkedList:
def delete_node(self, data):
current = self.head
if current is None or current.data == data:
self.head = current.next if current else None
return
while current.next:
if current.next.data == data:
current.next = current.next.next
return
current = current.next
Thank you for reading this far. In future articles in this series, we'll discuss the more intricate details of Python and Python data structures.
Contribute to Swirl
Swirl is an open-source Python project. Contributing to Swirl can help you gain production-level knowledge of Python and improve your skills.
Check our GitHub Repository:
Swirl on GitHub
We'll be delighted if you could:
Thanks for reading,
You all are breathtaking.
