For this tutorial, you’ll have to understand functions and classes. In this tutorial, we’ll go over linked lists and binary trees. Linked lists are an important Python Data Structure that consist of a head node, and other nodes being “linked” or pointed at by the node before it. Binary trees are used for hierarchical data, like a linked list, it starts with a head or root node and other nodes being linked or pointed at by the node before it, the key difference is that nodes in binary trees can point to two child nodes.
Python Linked List Implementation
There are two types of linked lists, singly linked lists and doubly linked lists. In this section we’ll just go over singly linked lists. I will cover doubly linked lists at a later date with more advanced data structures. Linked lists are a group of nodes which are all linked from the “root” or “parent” node with pointers. In a singly linked list, each node should contain a value and a pointer to a child node. If you do not already know how to declare Classes and Functions in Python I would recommend learning that first. I will create a post on it and link it in the future.
A simple implementation of a linked list should allow us to append a node, check the size of the list, search for a value, and delete a node. There are many ways to implement linked lists, this is simply one that I found to be most reasonable. Note that I also included a way to traverse the list for simpler printing.
class Node(object):
def __init__(self, data=None, next=None):
self.data = data
self.next = next
def get_data(self):
return self.data
def set_data(self, new_data):
self.data = new_data
def get_next(self):
return self.next
def set_next(self, next_node):
self.next = next_node
class Linked_List(object):
def __init__(self, head=None):
self.head = head
self.size = 0
# append at the end
def append(self, node):
cur = self.head
while cur.next != None:
cur = cur.next
cur.next = node
self.size += 1
def size(self):
return self.size
def search(self, value):
cur = self.head
found = False
while not found:
if cur.data == value:
found = True
return cur
elif cur.next:
cur = cur.next
else:
return ValueError("Value not found")
def delete(self, value):
cur = self.head
if cur.data == value:
self.head = cur.next
else:
while cur.data != value:
cur = cur.next
if cur.next:
cur.data = cur.next.data
cur.next = cur.next.next
else:
cur.next = None
cur.data = None
def traverse(self):
cur = self.head
arr = [cur.data]
while cur.next:
cur = cur.next
arr.append(cur.data)
return arr
node1 = Node(4)
node2 = Node(2)
node3 = Node(6)
node4 = Node(10)
node5 = Node(5)
ll = Linked_List(node1)
print(f"Current linked list is {ll.traverse()}")
ll.append(node2)
ll.append(node3)
print(f"After adding some nodes, we get {ll.traverse()}")
print(f"Now the size of the linked list is {ll.size}")
print(f"If we search for 10, we should see that it is not in the list: {ll.search(10)}")
ll.append(node4)
ll.append(node5)
print(f"However if we append some nodes, and one of them has value 10 like: {ll.traverse()}")
print(f"We should now get a response for searching for 10: {ll.search(10)}")
ll.delete(2)
print(f"After deleting node 2, we get {ll.traverse()}")Python Binary Tree Implementation
Here’s the thing about binary trees, they’re a broad topic. In theory, any structure with a root node and 0, 1, or 2 children per node could be a binary tree. In this Python implementation, we’re going to specifically go over a binary search tree. That means that our left nodes will be less than or equal to the root node, and our right nodes will be greater than the root node. Note that you can also implement a binary search tree that has right nodes that are greater than or equal to the root node, and left nodes that are less than the root node, but here we’ve chosen to include the equality condition on the left side just because we have to pick a side.
The example implementation of a Binary Tree in Python shows how we can append a value, search by value, delete by value, and print an in-order traversal of our binary tree. An in-order traversal is a traversal in which the root node is “visited” in-between its left and right nodes. In our case, it should show the numbers we added to the tree in numerical order.
# val is the value of the node
# right is the right node
# left is the left node
class BinaryTree(object):
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def append_val(self, val):
self.append(BinaryTree(val))
def append(self, node):
_val = node.val
if _val <= self.val:
if self.left:
print(f"moving left to append {_val}")
self.left.append(node)
else:
print(f"setting left {_val}")
self.left = node
else:
if self.right:
print(f"moving right to append {_val}")
self.right.append(node)
else:
print(f"setting right {_val}")
self.right = node
def search(self, val):
if val == self.val:
return True
if val <= self.val and self.left:
self.left.search(val)
elif val > self.val and self.right:
self.right.search(val)
else:
print("Value could not be found")
return False
# returns the parent node and the successor
def find_successor(self, parent):
if self.left:
return self.left.find_successor(self)
else:
return parent, self
def delete(self, val):
print(f"Deleting {val} if it exists")
if self.val == val:
if self.right and self.left:
parent, successor = self.right.find_successor(self)
# split out the successor
if parent.left == successor:
parent.left = successor.right
else:
parent.right = successor.right
# reset left and right nodes of the successor
successor.left = self.left
successor.right = self.right
return successor
else:
if self.left:
return self.left
else:
return self.right
else:
if self.val > val:
if self.left:
self.left = self.left.delete(val)
else:
if self.right:
self.right = self.right.delete(val)
return self
def inorder_print(self):
if self.left:
self.left.inorder_print()
print(self.val)
if self.right:
self.right.inorder_print()
root = BinaryTree(5)
root.inorder_print()
print('\n')
root.append_val(2)
root.append_val(8)
root.append_val(3)
root.inorder_print()
print('\n')
root.append_val(1)
root.append_val(10)
root.append_val(7)
root.inorder_print()
root = root.delete(5)
root.inorder_print()
That’s it for the second installation of a tutorial on Data Structures in Python. There are more tutorials available on the site for self-learners. There will be a post on more advanced Tree structures coming soon.
I run this site to help you and others like you find cool projects and practice software skills. If this is helpful for you and you enjoy your ad free site, please help fund this site by donating below! If you can’t donate right now, please think of us next time.
