Introduction
Linked lists are one of the most fundamental data structures in computer science. They provide an alternative to arrays for storing sequential elements. Unlike arrays, linked lists are not contiguous blocks of memory but rather a collection of discrete nodes, each node holding data and a reference to the next node in the sequence.
In this guide, we’ll explore how to implement singly linked list and doubly linked list in Python programming language.
Anatomy of a Singly Linked List
A linked list is essentially a chain of nodes. A single node contains:
- Data: The value stored in the node.
- Next: A reference to the next node in the list.
The first node is referred to as the “head” of the list, and the last node is the “tail”.
The Node Class
First, we’ll implement the Node class for a singly linked list.
class SNode:
def __init__(self, data):
self.data = data
self.next = NoneThe SinglyLinkedList Class
Next, we implement the SinglyLinkedList class with the required methods.
class SinglyLinkedList:
def __init__(self):
self.head = None
def add(self, data):
new_node = SNode(data)
new_node.next = self.head
self.head = new_node
def remove(self, data):
if self.head is None:
return "List is empty."
if self.head.data == data:
self.head = self.head.next
return
prev_node = None
cur_node = self.head
while cur_node and cur_node.data != data:
prev_node = cur_node
cur_node = cur_node.next
if cur_node is None:
return "Data not found."
prev_node.next = cur_node.next
def find(self, data):
cur_node = self.head
while cur_node:
if cur_node.data == data:
return True
cur_node = cur_node.next
return False
def size(self):
count = 0
cur_node = self.head
while cur_node:
count += 1
cur_node = cur_node.next
return countUsing Singly Linked List
sll = SinglyLinkedList()
sll.add(1)
sll.add(2)
sll.add(3)
print(sll.find(2)) # Output: True
print(sll.size()) # Output: 3
sll.remove(2)
print(sll.find(2)) # Output: False
Anatomy of a Doubly Linked List
Each node in a doubly linked list contains three components:
- Data: The value stored in the node.
- Next: A reference to the next node in the list.
- Prev: A reference to the previous node in the list.
The Node Class
Let’s create a Node class for our doubly linked list.
class DNode:
def __init__(self, data):
self.data = data
self.next = None
self.prev = NoneThe DoublyLinkedList Class
Now, we implement the DoublyLinkedList class.
class DoublyLinkedList:
def __init__(self):
self.head = None
def add(self, data):
new_node = DNode(data)
if self.head is not None:
self.head.prev = new_node
new_node.next = self.head
self.head = new_node
def remove(self, data):
cur_node = self.head
while cur_node:
if cur_node.data == data:
if cur_node.prev:
cur_node.prev.next = cur_node.next
else:
self.head = cur_node.next
if cur_node.next:
cur_node.next.prev = cur_node.prev
return
cur_node = cur_node.next
return "Data not found."
def find(self, data):
cur_node = self.head
while cur_node:
if cur_node.data == data:
return True
cur_node = cur_node.next
return False
def size(self):
count = 0
cur_node = self.head
while cur_node:
count += 1
cur_node = cur_node.next
return countUsing Doubly Linked List
dll = DoublyLinkedList()
dll.add(1)
dll.add(2)
dll.add(3)
print(dll.find(2)) # Output: True
print(dll.size()) # Output: 3
dll.remove(2)
print(dll.find(2)) # Output: FalseIs there a in-built Linked List data structure in Python?
Python doesn’t have a built-in linked list data structure in its standard library like it has for lists, dictionaries, and sets. Python’s collections module has a deque class which can serve as a doubly-ended queue. It offers all the methods necessary to simulate doubly linked list behavior.
Conclusion
We have successfully implemented both singly and doubly linked lists in Python with basic methods like add, remove, find, and size.
If you find this guide useful, please share with others, and spread the knowledge!