A Tutorial on Common Data Structures in Python 2

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
                return ValueError("Value not found")
    def delete(self, value):
        cur = self.head
        if cur.data == value:
            self.head = cur.next
            while cur.next:
                if cur.next.data == value:
                    next_next = cur.next.next
                    cur.next = next_next
                    self.size -= 1

    def traverse(self):
        cur = self.head
        arr = [cur.data]
        while cur.next:
            cur = cur.next
        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()}")
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)}")
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)}")

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):

    def append(self, node):
        _val = node.val
        if _val <= self.val:
            if self.left:
                print(f"moving left to append {_val}")
                print(f"setting left {_val}")
                self.left = node
            if self.right:
                print(f"moving right to append {_val}")
                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:
        elif val > self.val and self.right:
            print("Value could not be found")
            return False
    def delete(self, val):
        if val == self.val:
            if self.left:
                headless = self.right
                self.root = self.left
                return True
            elif self.right:
                self.root = self.right
        elif val < self.val:
        elif val > self.val:
            print("Value could not be found")
            return False
    def inorder_print(self):
        if self.left:
        if self.right:

root = BinaryTree(5)

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.