Linked lists are like a series of connected boxes, where each box holds a piece of information and points to the next box. They’re a cool way to organize data in Python. Let’s check out how to use linked lists in Python in a simple and friendly way.
What is a Linked List?
Imagine you have a string of boxes, and each box has a number inside. These boxes are a linked list. Instead of standing in a line like arrays, linked list boxes are scattered around, and each box knows where the next one is.
Also Read: Python HeapQ Explained with Examples
Types of Linked Lists
Singly Linked List:
Imagine a line of people holding hands. Each person (node) holds the hand of the person in front. This is a single link list. Check on the below code illustrating the simple doubly linked list. Please note the cell in the below code represents a node in the link list.
# Creating a singly linked list
cell1 = Cell(1)
cell2 = Cell(2)
cell3 = Cell(3)
cell1.next = cell2
cell2.next = cell3
Doubly Linked List:
Now, picture a line where each person holds hands with the person in front and behind. This is a doubly linked list. The below is a logical representation of a doubly linked list in Python.
# Creating a doubly linked list
cell1 = Cell(1)
cell2 = Cell(2)
cell3 = Cell(3)
cell1.next = cell2
cell2.prev = cell1
cell2.next = cell3
cell3.prev = cell2
Circular Linked List:
Imagine a group of people in a circle, holding hands with the person next to them and the last person holding hands with the first. This is a circular linked list.
Here is a simple demonstration of a circular link list in Python.
# Creating a circular linked list
cell1 = Cell(1)
cell2 = Cell(2)
cell3 = Cell(3)
cell1.next = cell2
cell2.next = cell3
cell3.next = cell1
Must Read: How to Create and Use Arrays in Python
Implementing Linked Lists in Python
Cell (the Node) Class
Firstly, before we start, let’s create a helper, the Cell
class, which represents each node in our linked list.
class Cell:
def __init__(self, value):
self.value = value
self.next = None
Secondly, you’ll see the above class being used all over this tutorial. We’ll use it for creating other link list classes.
Singly Linked List Implementation
Now, let’s create a simple singly linked list that points from one box to the next.
class SinglyLkdList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Cell(data)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
def disp(self):
elements = []
current = self.head
while current:
elements.append(current.data)
current = current.next
print(" -> ".join(map(str, elements)))
Let’s use this linked list:
sin_list = SinglyLkdList()
sin_list.append(1)
sin_list.append(2)
sin_list.append(3)
sin_list.disp()
# Output: 1 -> 2 -> 3
Doubly Linked List Implementation
Now, let’s enhance our linked list to remember the person behind too.
class DoublyLkList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Cell(data)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
new_node.prev = current
def disp(self):
elements = []
current = self.head
while current:
elements.append(current.data)
current = current.next
print(" <-> ".join(map(str, elements)))
Let’s use this doubly linked list:
dob_list = DoublyLkList()
dob_list.append(1)
dob_list.append(2)
dob_list.append(3)
dob_list.disp()
# Output: 1 <-> 2 <-> 3
Circular Linked List Implementation
Lastly, let’s create a circular linked list, a fun loop of holding hands.
class CircularLkdList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Cell(data)
if not self.head:
self.head = new_node
new_node.next = self.head
return
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
new_node.next = self.head
def disp(self):
elements = []
current = self.head
while True:
elements.append(current.data)
current = current.next
if current == self.head:
break
print(" -> ".join(map(str, elements)))
Let’s use this circular linked list:
cir_list = CircularLkdList()
cir_list.append(1)
cir_list.append(2)
cir_list.append(3)
cir_list.disp()
# Output: 1 -> 2 -> 3 -> 1
Common Linked List Operations in Python
In this section, we have provided Python examples to demonstrate the common operations that you can perform on the link lists.
Searching in a Linked List
Imagine finding a person in our line of linked boxes. Let’s create a simple way to search for a specific number.
def search_list(self, key):
current = self.head
while current:
if current.data == key:
return True
current = current.next
return False
Deleting from a Linked List
Imagine removing a person from our line. Let’s create a way to delete a specific number.
def del_list_item(self, key):
current = self.head
prev = None
while current:
if current.data == key:
if prev:
prev.next = current.next
else:
self.head = current.next
return
prev = current
current = current.next
Reversing a Linked List
Imagine flipping our line of people around. Let’s create a way to reverse our linked list.
def rev_list(self):
current = self.head
prev = None
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
self.head = prev
Additional Tips and Insights
Pros and Cons of Linked Lists
Pros:
- Dynamic Size: Linked lists can grow or shrink during runtime.
- Easy Insertion/Deletion: Adding or removing elements is efficient.
Cons:
- Random Access is Slow: Accessing an element at a specific index takes time.
- Extra Memory Usage: Each element requires extra space for the pointer.
Use Cases
- When Size is Unknown: Linked lists are great when you don’t know the size of your data in advance.
- Frequent Insertions/Deletions: If your program involves a lot of adding or removing elements, linked lists can be more efficient than arrays.
Choosing the Right Type
- Singly Linked List: Use when traversal is mainly forward, and memory efficiency is a concern.
- Doubly Linked List: Use when backward traversal is needed or when insertion/deletion at both ends is frequent.
- Circular Linked List: Use when the data needs to be accessed in a loop.
Summary – Python Linked Lists
Linked lists are like a chain of friends holding hands, each knowing the next. We explored different types, implemented them in Python, and learned common operations. As you continue your coding journey, practice with linked lists, and soon you’ll be connecting data in your programs like a pro!
Happy Coding!