In earlier articles in this series, we thoroughly explored data structures, their significance, real-life applications, and how to select appropriate data structures for different tasks. In this article, you will code various types of data structures. This hands-on tutorial will enhance your practical knowledge of data structures and deepen your understanding of their underlying infrastructure.

To effectively follow through with this tutorial, you should have a basic knowledge of data structures and their types and an understanding of programming concepts like variables, loops, methods, conditional statements, functions, etc. The code will be written in Python, so you should be familiar with the basics of Python programming language.

Other prerequisites:

• VS Code editor

• Python Installed on your device

Setting up your Integrated Development Environment (IDE)

An Integrated Development Environment (IDE) is a software application that provides a comprehensive set of tools for software development in one place. It simplifies tasks like writing, testing, and building programs. Some IDEs are cloud-based, allowing you to work and save projects online, while others are desktop-based, enabling local development on your computer.

You can use any IDE you are familiar with, but I will use Visual Studio Code for this tutorial. This versatile code editor allows you to write, debug, and run your code directly on your local computer without needing an internet connection. If you do not have Visual Studio Code on your system, download it and follow the installation prompts.

You will also need to install Python on your computer. Download [insert link] and follow the installation prompt.

With VS Code and Python successfully installed on your computer, open your command line and type this in:

mkdir data-structure-tutorial

This will create a folder called data-structure-tutorial on your computer. Next, you enter the folder by inputting this in the command line:

cd data-structure-tutorial

Lastly, you type in this command in the command line:

code .

This will open the folder you just created in VS Code automatically.

Implementing Data Structures

Let’s get started with coding data structures! This short tutorial will guide you through using Python to implement 3 data structures with different difficulty levels. You’ll learn how to write and run your code, starting with the most straightforward structures and progressing to the more complicated ones. They include:

1. Arrays (Beginner)

2. Stacks (Intermediate)

3. Trees (Advanced)

Arrays

Arrays are the most basic type of data structure. They are collections of elements organised in a contiguous block of memory.

Implementation Steps

1. Initialise your array: Implementing arrays in most programming languages is straightforward; you initialise a variable and assign it the elements enclosed in square brackets [ ]; for example

    # Creating an array
    array = [10, 20, 30, 40, 50]
   

2. Create methods to perform operations on your array: Python offers various built-in methods for manipulating and organising your array within your file. Methods are built-in functions associated with a specific object, such as an array, that enable you to perform operations on that object. These methods include:

• append(): Adds an element to the end of the array.

• insert(index, value): Inserts a value at the specified index.

• remove(value): Removes the first occurrence of the specified value.

• pop(index): Removes and returns the element at the specified index. If no index is specified, it removes and returns the last element.

• index(value): Returns the index of the first occurrence of the specified value.

• reverse(): Reverses the order of the elements in the array.

3. Run your code in the terminal.

Code Execution

In your VSCode, create a file in the folder you opened. Click the File option in the taskbar and select New File. Name the file array.py. Then, type in the code above to create your array.

In your array.py file, include the following code:

# Creating an array
array = [10, 20, 30, 40, 50]

# Accessing elements
print("First element:", array[0])

# Adding an element (Append)
array.append(60)
print("After appending 60:", array)

# Inserting an element at a specific position
array.insert(2, 25)
print("After inserting 25 at index 2:", array)

# Removing an element (Value-based)
array.remove(30)
print("After removing 30:", array)

# Popping an element (Index-based)
popped_element = array.pop(4)
print(f"After popping element at index 4 ({popped_element}):", array)

# Finding the index of an element
index = array.index(40)
print("Index of 40:", index)

# Slicing an array
sub_array = array[1:4]
print("Sliced array (index 1 to 3):", sub_array)

You create an array with the values [10, 20, 30, 40, 50] and then access the first element by referencing index 0 to print it. You append 60 to the end of the array using the append method and print the updated array. Next, you insert 25 at index 2 with the insert method, which shifts the other elements to the right, and print the result. You remove the element, 30, by using the remove method and then print the modified array. Then, you pop the element at index 4 with the pop method, store the returned value in a variable called popped_element, and print both the popped element and the updated array. You also find the index of 40 using the index method and print that index. Finally, you slice the array from index 1 to 3 (excluding index 4) to create and print a sub-array.

Run your code by clicking the play icon at the top right of your file tab. You should see the following results printed in the terminal:

First element: 10 After appending 60: [10, 20, 30, 40, 50, 60] After inserting 25 at index 2: [10, 20, 25, 30, 40, 50, 60] After removing 30: [10, 20, 25, 40, 50, 60] After popping element at index 4 (50): [10, 20, 25, 40, 60] Index of 40: 3 Sliced array (index 1 to 3): [20, 25, 40]

Stacks

A stack is a last-in, first-out (LIFO) data structure in which the last item added is the first one removed. Unlike arrays, stacks are not built-in, general-purpose containers but specialised data structure operations designed to manage data using the LIFO principle. Stack operations are built on structures like Lists, which offer built-in methods (append and pop) that align perfectly with stack operations.

Implementation Steps

To create a stack:

1. Define a Stack class and initialise an empty stack by creating an empty list within your class. This list will represent the stack, where the last element added to it is considered the top of the stack.

2. Develop methods within your Stack class to manage the LIFO behaviour and operations. These methods will include:

• push(item): This method adds an item to the top of the stack. It utilises the append() method of the list to add the item to the end.

• pop(): This method removes and returns the top element from the stack. It uses the pop() method of the list to remove and return the last element

• peek(): This method returns the top element of the stack without removing it. It accesses the last element of the list using indexing.

• is_empty(): This method checks if the stack is empty. It checks if the length of the list is zero:

• size(): This method returns the number of elements currently in the stack. It simply returns the length of the list

3. Create your example usage to test your stack.

4. Run your code in the terminal.

Code Execution

Create another file in your repository and name it myStack.py, then input the following code:

# Implementing a Stack using a list

class Stack:
    def __init__(self):
        self.stack = []

You create your stack by defining a class Stack, init method initialises a new instance of the Stack class and self.stack = [ ] creates an empty list to represent the stack. This list will store the stack's elements.

Next, you create methods within your Stack class that will define the LIFO behaviour of your stack. Inside your Stack class, add the following code:

# Push method to add an element to the stack
    def push(self, item):
        self.stack.append(item)

    # Pop method to remove and return the top element
    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        return "Stack is empty"

    # Peek method to view the top element without removing it
    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        return "Stack is empty"

    # Method to check if the stack is empty
    def is_empty(self):
        return len(self.stack) == 0

    # Method to get the size of the stack
    def size(self):
        return len(self.stack)

Following the LIFO principle:

1. Your push() method adds an element to the stack by appending the element at the end of the list(which corresponds to the top of the stack). You pass in the instance of the stack (self) and the data you want to add(item) as arguments, and you utilise the in-built append method to append the data(item)

2. Your pop() method removes and returns the top element of the stack. It uses the in-built is_empty method to check if the stack is empty; if not, it uses the in-built pop method to remove the top element.

3. Your peek() method views the top element without removing it. It uses the in-built is_empty method to check if it is empty and utilises Python’s negative indexing to view the top item, where -1 is the last item on the list(top of the list in terms of the stack).

4. Your is_empty() method and size() method check if the stack is empty and the size of the stack respectively, using the in-built len method.

To test your stack implementation, input the following code:

# Example usage
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)

print("Stack after pushes:", stack.stack)
print("Top element (peek):", stack.peek())
print("Removed top element (pop):", stack.pop())
print("Stack after pop:", stack.stack)
print("Is the stack empty?", stack.is_empty())
print("Stack size:", stack.size())

You initialise your Stack class in a stack variable, then use the push methods to add the integers 10, 20, and 30 to your stack. The print statements record the status of the stack after different operation, to your terminal. Run your code, and you should see the following results:

Stack after pushes: [10, 20, 30] Top element (peek): 30 Removed top element (pop): 30 Stack after pop: [10, 20] Is the stack empty? False Stack size: 2

Trees

A tree is a hierarchical data structure representing relationships with nodes connected by edges. It begins with a root node with zero or more children, defining the tree's levels. Each node can have multiple children and one parent (except the root); nodes without children are leaves. Trees organise data hierarchically in file systems, databases, and search operations. Key types include binary trees, with up to two children per node, and binary search trees (BSTs), which allow efficient searching by maintaining sorted order. Implementing trees typically requires a Node class for elements and a Tree or BinaryTree class for management, including traversal, insertion, and deletion operations.

You will be creating a binary tree in this tutorial. A binary tree is a tree data structure in which each node has at most two children. Understanding binary trees provides a solid foundation for learning about more complex structures like AVL trees, red-black trees, and B-trees. Moreover, because each node has at most two children, they are less complex than general trees, making it an excellent example to practice.

Implementation Steps

To create a binary tree:

1. You define a class for your nodes. This will represent each node within the tree. Attributes of this class will include:

• data: To store the value of the node.

• left: A pointer (or reference) to the left child node. Initially, it will be None.

• right: A pointer (or reference) to the right child node. Initially, it will be None.

2. You create methods in your node class that will handle the tree operations. These methods include:

• insert(value): This method adds a new node to the tree while preserving the binary search tree property (values in the left subtree are less than the current node's value, and those in the right subtree are greater). It recursively traverses the tree to locate the appropriate position for the new node.

• search(value): This method searches for a specific value within the tree. It recursively traverses the tree, comparing the target value with the current node's value.

• inorder(), preorder(), and postorder(): These methods perform traversal operations in different orders and return a list of visited node values.

3. You create example usage to test your tree.

4. Run your code in the terminal.

Code Execution

In your folder, open another file and name it myTree.py. Type in the following code to initialise your node classBinaryTreeNode:

class BinaryTreeNode:
    def __init__(self, value):
        self.value = value        # The value stored in the node
        self.left = None          # Left child
        self.right = None         # Right child

The init method initialises a new node in the tree. It assigns the specified value to the node and sets the left and right child pointers to None, indicating that the node begins with no children.

Next, you create methods that will handle operations for your tree. Within your BinaryTreeNode class, input the following code:

def insert(self, value):
        """
        Inserts a new value into the tree following binary search tree rules.
        """
        if value < self.value:
            if self.left is None:
                self.left = BinaryTreeNode(value)
            else:
                self.left.insert(value)
        elif value > self.value:
            if self.right is None:
                self.right = BinaryTreeNode(value)
            else:
                self.right.insert(value)

    def search(self, value):
        """
        Searches for a value in the tree. Returns True if found, otherwise False.
        """
        if self.value == value:
            return True
        elif value < self.value and self.left is not None:
            return self.left.search(value)
        elif value > self.value and self.right is not None:
            return self.right.search(value)
        return False

    def inorder(self):
        """
        Performs an in-order traversal (left, root, right).
        Returns a list of visited node values.
        """
        elements = []
        if self.left:
            elements += self.left.inorder()
        elements.append(self.value)
        if self.right:
            elements += self.right.inorder()
        return elements

    def preorder(self):
        """
        Performs a pre-order traversal (root, left, right).
        Returns a list of visited node values.
        """
        elements = [self.value]
        if self.left:
            elements += self.left.preorder()
        if self.right:
            elements += self.right.preorder()
        return elements

    def postorder(self):
        """
        Performs a post-order traversal (left, right, root).
        Returns a list of visited node values.
        """
        elements = []
        if self.left:
            elements += self.left.postorder()
        if self.right:
            elements += self.right.postorder()
        elements.append(self.value)
        return elements

insert(self, value):

• This method determines the appropriate position for the new value based on the binary search tree property.

• It then creates a new node and inserts it as either the left or right child of the current node or recursively calls itself on the appropriate child.

search(self, value):

• This method compares the target value with the current node's value.

• If a match is found, it returns True.

• Otherwise, it recursively searches the left subtree if the target value is less than the current node's value or the right subtree if the target value is greater.

• If the value is not found, it returns False.

inorder():

• This method first recursively traverses the left subtree, then adds the current node's value, and finally recursively traverses the right subtree.

• It returns the sequence of visited node values.

preorder():

• This method first adds the current node's value, then recursively traverses the left subtree, and finally recursively traverses the right subtree.

• It returns the sequence of visited node values.

postorder():

• This method first recursively traverses the left subtree, then recursively traverses the right subtree, and finally adds the current node's value.

• It returns the sequence of visited node values.

Finally, you create your example usage to test your tree. Outside your class, input the following code:

# Example Usage
if __name__ == "__main__": # This is to prevent the code from running when the module is imported
    # Create a binary tree and insert values
    root = BinaryTreeNode(50)
    root.insert(30)
    root.insert(70)
    root.insert(20)
    root.insert(40)
    root.insert(60)
    root.insert(80)

    # Perform traversals
    print("In-order Traversal:", root.inorder())     # Output: [20, 30, 40, 50, 60, 70, 80]
    print("Pre-order Traversal:", root.preorder())   # Output: [50, 30, 20, 40, 70, 60, 80]
    print("Post-order Traversal:", root.postorder()) # Output: [20, 40, 30, 60, 80, 70, 50]

    # Search for values
    print("Search 40:", root.search(40))   # Output: True
    print("Search 100:", root.search(100)) # Output: False

The code blocks above carry out the following tasks:

Creates a binary tree:

• Initialises a root node with the value 50.

• Inserts values 30, 70, 20, 40, 60, and 80 into the tree, effectively building the binary search tree structure.

Performs traversals:

• Calls the inorder, preorder, and postorder methods on the root node to traverse the tree in each order.

• Prints the resulting sequences of visited node values.

Searches for values:

• Calls the search method on the root node to find the values 40 and 100 within the tree.

• Prints the results of the search operations (True for 40, False for 100).

To run your code, open your terminal and type in the command:

python myTree.py

In your terminal, you should see the following result printed out:

In-order Traversal: [20, 30, 40, 50, 60, 70, 80] Pre-order Traversal: [50, 30, 20, 40, 70, 60, 80] Post-order Traversal: [20, 40, 30, 60, 80, 70, 50] Search 40: True Search 100: False

According to the instructions provided in your example case, the tree was traversed in-order, pre-order, and post-order. The test to check whether the integers 40 and 100 were present in the tree yielded accurate results. Congratulations, you have created your binary tree. You can continue adding more methods and tests for further practice.

Conclusion

To a good extent, this tutorial has explored the fundamental concepts of data structure implementation through the practical examples of arrays, stacks, and binary trees. By understanding how to represent these structures in code, you gain a solid foundation in key data structure principles: efficient memory allocation and access (arrays), abstract data types and their underlying implementations (stacks), and recursive algorithms and hierarchical organisation (binary trees). These concepts are transferable to other data structures, such as linked lists, queues, graphs, etc. Implementing these basic structures provides a hands-on approach to learning about data organisation and manipulation, crucial skills for any programmer.