Python Singly Linked List Implementation
Learn how to implement a singly linked list in Python. Explore dynamic memory allocation, node operations, insertion, traversal, and deletion.
How it Works
A linked list is a linear data structure where elements are not stored in contiguous memory locations. Instead, each element (called a node) is a separate object that contains a reference to the next node in the sequence.
The primary benefit of a linked list over a traditional array is its dynamic sizing and the ability to insert or delete elements in constant O(1) time at the beginning. However, accessing elements by index requires linear traversal, which takes O(n) time.
In Python, we implement a linked list by defining a Node class to store the data and reference pointer, and a LinkedList class to manage the head node, insertions at the head or tail, and deletions.
Source Code
Singly linked list implementation in Python, showcasing node creation, appending, and list traversal.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
last = self.head
while last.next:
last = last.next
last.next = new_node
def delete(self, key):
curr = self.head
if curr and curr.data == key:
self.head = curr.next
curr = None
return
prev = None
while curr and curr.data != key:
prev = curr
curr = curr.next
if not curr:
return
prev.next = curr.next
curr = None
def display(self):
elements = []
curr = self.head
while curr:
elements.append(str(curr.data))
curr = curr.next
print(" -> ".join(elements) + " -> None")
# Instantiate and build the linked list
llist = LinkedList()
llist.append("Node A")
llist.append("Node B")
llist.append("Node C")
print("Initial Linked List:")
llist.display()
print("Deleting 'Node B':")
llist.delete("Node B")
llist.display()Initial Linked List:
Node A -> Node B -> Node C -> None
Deleting 'Node B':
Node A -> Node C -> NoneReal-world Applications
- Implementing undo-redo functionality in text editors
- Building complex data structures like graphs, stacks, and queues
- Managing lists where insertion and deletion frequencies outnumber lookup actions
Frequently Asked Questions
What is the difference between Singly and Doubly Linked Lists?
In a Singly Linked List, each node points only to the next node. In a Doubly Linked List, each node contains references to both the next and the previous node, allowing bidirectional traversal at the cost of extra memory.
Why does Python not have a built-in LinkedList class?
Python arrays (lists) are implemented as dynamic arrays. Because of Python's memory management and CPython optimizations, standard lists are extremely fast and efficient for most tasks, reducing the practical need for a built-in linked list.