In Python, a linked list is a linear data structure where each element, called a node, contains two parts: the data and a reference (or pointer) to the next node in the sequence. Even though Python has powerful built-in data structures like lists, understanding how to implement a linked list manually can deepen your grasp of algorithms and data structures. In this post, we'll walk through how to create a singly linked list from scratch in Python.
By the end of this tutorial, you'll know:
- How to define a basic linked list structure
- How to insert elements at different positions
- How to display and delete nodes
1. Understanding the Linked List Structure
A singly linked list consists of nodes where each node has two attributes:
- data: The value stored in the node.
- next: A reference to the next node in the list (or
Noneif it’s the last node).
Example of a Node class:
class Node:
def __init__(self, data):
self.data = data # Initialize node data
self.next = None # Initialize next as None
Here, the Node class:
- Stores data in the
dataattribute. - Uses
nextto point to the next node in the linked list, orNoneif it’s the last node.
2. Creating a Linked List
Next, we need a class to represent the LinkedList itself, which will contain a reference to the head node (the first node in the list).
Example:
class LinkedList:
def __init__(self):
self.head = None # Initialize the list with an empty head
Here, the LinkedList class initializes with an empty head, meaning the list starts out empty.
3. Inserting Nodes into the Linked List
You can insert nodes into the list in various ways, including:
- At the beginning: The new node becomes the head of the list.
- At the end: The new node is added after the last node.
a) Inserting at the Beginning
To insert at the beginning, the new node’s next should point to the current head, and the head should be updated to the new node.
def insert_at_beginning(self, data):
new_node = Node(data)
new_node.next = self.head # New node points to current head
self.head = new_node # Head is now the new node
b) Inserting at the End
To insert at the end, we need to traverse the list to find the last node (the node whose next is None), and then update its next to point to the new node.
def insert_at_end(self, data):
new_node = Node(data)
if self.head is None: # If the list is empty, the new node is the head
self.head = new_node
return
last = self.head
while last.next:
last = last.next
last.next = new_node
4. Displaying the Linked List
To display the elements of the linked list, we need to traverse from the head to the last node, printing the data at each step.
Example:
def display(self):
if self.head is None:
print("List is empty")
return
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
In this function:
- We start at the head node and print each node’s
datafollowed by an arrow (->) to represent the link. - We stop when
currentbecomesNone, indicating the end of the list.
5. Deleting a Node
Let’s discuss how to remove a node from the list:
- Deleting the first node (head).
- Deleting a node with a specific value.
a) Deleting the First Node (Head)
To delete the first node, we update the head to point to the second node (i.e., the next node).
def delete_first(self):
if self.head is None:
print("List is empty")
return
self.head = self.head.next # Move head to the next node
b) Deleting a Node by Value
To delete a node by value, we need to search for the node with the matching data, update the previous node’s next pointer to skip over the node being deleted, and free the node.
def delete_node(self, value):
if self.head is None:
print("List is empty")
return
if self.head.data == value: # If the node to be deleted is the head
self.head = self.head.next
return
current = self.head
previous = None
while current is not None and current.data != value:
previous = current
current = current.next
if current is None:
print("Value not found")
return
previous.next = current.next # Unlink the node from the list
6. Complete Example
Now, let’s combine all of the above concepts and implement a complete linked list with the ability to insert, display, and delete nodes.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert_at_beginning(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def insert_at_end(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
last = self.head
while last.next:
last = last.next
last.next = new_node
def display(self):
if self.head is None:
print("List is empty")
return
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
def delete_first(self):
if self.head is None:
print("List is empty")
return
self.head = self.head.next
def delete_node(self, value):
if self.head is None:
print("List is empty")
return
if self.head.data == value:
self.head = self.head.next
return
current = self.head
previous = None
while current and current.data != value:
previous = current
current = current.next
if current is None:
print("Value not found")
return
previous.next = current.next
# Testing the LinkedList
if __name__ == "__main__":
ll = LinkedList()
# Insert elements
ll.insert_at_end(10)
ll.insert_at_end(20)
ll.insert_at_end(30)
print("Initial List:")
ll.display()
# Delete first node
ll.delete_first()
print("After deleting first node:")
ll.display()
# Delete node with value 20
ll.delete_node(20)
print("After deleting node with value 20:")
ll.display()
Conclusion
In this post, you've learned how to manually implement a basic singly linked list in Python, including inserting nodes, displaying the list, and deleting nodes. Linked lists are a fundamental data structure that help you better understand how pointers and memory management work. This knowledge is useful in more advanced algorithms and data structures such as stacks, queues, and graphs.