Labs / Python OOP

The Most Beginner-Friendly Object Oriented Programming Course on the Whole Network: 45 Implementing Common Data Structures in Python – Linked List, Tree, Hash Table, Graph and Heap

Author: Li Zisheng · Source: FreakStudio open documentation · License: CC BY 4.0

Contents
The Most Beginner-Friendly Object Oriented Programming Course on the Whole Network: 45 Implementing Common Data Structures in Python – Linked List, Tree, Hash Table, Graph and Heap

Abstract:

Data structure is a way of organizing and storing data in computer science, which determines the access method and operation efficiency of data, and the selection and implementation of data structures are crucial to the performance and design of programs. This paper mainly describes how to implement common data structures using the Python language and its built-in libraries.

FreakStudio's Blog

Previous Recommendations:

You who are learning embedded systems, don’t you even know Object Oriented yet? ?!

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 00 Introduction to Object Oriented Design Methodology

The Most Beginner-Friendly Object Oriented Programming Course on the Whole Network: 01 Basic Concepts of Object Oriented Programming

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 02 Python Implementation of Classes and Objects - Creating Classes with Python

The most beginner-friendly Object Oriented programming tutorial across the entire network: 03 Python implementation of classes and objects - adding attributes to custom classes

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 04 Python Implementation of Classes and Objects - Adding Methods to Custom Classes

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 05 Python Implementation of Classes and Objects - PyCharm Code Tab

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 06 Python Implementation of Classes and Objects - Data Encapsulation of Custom Classes

The most beginner-friendly Object Oriented programming tutorial across the entire network: 07 Python implementation of classes and objects - type annotations

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 08 Python Implementation of Classes and Objects - @property Decorator

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 09 Python Implementation of Classes and Objects - Relationships Between Classes

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 10 Python Implementation of Classes and Objects - Class Inheritance and Liskov Substitution Principle

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 11 Python Implementation of Classes and Objects - Subclass Calling Parent Class Methods

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 12 Python Implementation of Classes and Objects - Using Python's logging Module to Output Program Runtime Logs

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 13 Python Implementation of Classes and Objects – Installation and Usage of Sourcetrail, a Visual Code Reading Tool

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 14 Python Implementation of Classes and Objects - Static Methods and Class Methods of Classes

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 15 Python Implementation of Classes and Objects - the __slots__ Magic Method

The Most Beginner-Friendly Object Oriented Programming Tutorial Across the Network: 16 Python Implementation of Classes and Objects - Polymorphism, Method Overriding and Open Closed Principle

The most beginner-friendly Object Oriented programming tutorial on the entire network: 17 Python implementation of classes and objects - duck typing and "file-like object"

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 18 Python Implementation of Classes and Objects - Multiple Inheritance and Serial Port Data Curve Plotting with PyQtGraph

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 19 Python Implementation of Classes and Objects – Using PyCharm to Automatically Generate File Comments and function Comments

The Most Beginner-Friendly Object Oriented Programming Course on the Whole Network: 20 Python Implementation of Classes and Objects – Implementation of Composition Relationship and CSV File Saving

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 21 Python Implementation of Classes and Objects - Multi-File Organization: Module and Package

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 22 Python Implementation of Classes and Objects - Exceptions and Syntax Errors

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 23 Python Implementation of Classes and Objects - Throwing Exceptions

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 24 Python Implementation of Classes and Objects - Exception Catching and Handling

The Most Beginner-Friendly Object Oriented Programming Course on the Whole Network: 25 Python Implementation of Classes and Objects - Python Determines the Type of Input Data

The Most Beginner-Friendly Object Oriented Programming Tutorial Across the Network: 26 Python Implementation of Classes and Objects - Context Managers and the with Statement

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 27 Python Implementation of Classes and Objects - Exception Hierarchy and Custom Exception Class Implementation in Python

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 28 Python Implementation of Classes and Objects - A Comprehensive Summary of Python Programming Principles, Philosophy and Specifications

The Most Beginner-Friendly Object Oriented Programming Course on the Whole Network: 29 Python Implementation of Classes and Objects - Assertions, Defensive Programming and the Usage of the help function

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 30 Python's Built-in Data Types - The object Root Class

The most beginner-friendly Object Oriented programming tutorial across the entire network: 31 Built-in data types in Python - Object and Type

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 32 Python's Built-in Data Types - Class and Instance

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 33 Python's Built-in Data Types – The Relationship Between Object and Type

The Most Beginner-Friendly Object Oriented Programming Course on the Whole Network: 34 Python's Built-in Data Types - Common Composite Data Types in Python: Tuples and Named Tuples

The Most Beginner-Friendly Object Oriented Programming Tutorial Across the Web: 35 Python's Built-in Data Types – Docstrings and the __doc__ Attribute

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 36 Python's Built-in Data Type - Dictionary

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 37 Common Composite Data Types in Python - Lists and List Comprehensions

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 38 Common Composite Data Types in Python – Implementing stack, Queue and Deque with Lists

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 39 Common Composite Data Types in Python – Sets

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 40 Common Composite Data Types in Python - Enumerations and Usage of the enum Module

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 41 Common Composite Data Types in Python - Queues (FIFO, LIFO, Priority Queue, Deque and Circular Queue)

The Most Beginner-Friendly Object Oriented Programming Tutorial Across the Network: 42 Commonly Used Composite Data Types in Python - Collections Container Data Types

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 43 Common Composite Data Types in Python - Extending Built-in Data Types

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 44 Python Built-in functions and Magic Methods – Overriding Magic Methods of Built-in Types

For more exciting content, you can check out:

Speed Up Your Python: A Quick Guide to Python Parallel Computing

Understand the Debugging Principle of CM3 Microcontroller in One Article

After half a month of dedicated work, the ultimate summary of embedded technology stack is now released

The "Martial Arts Manual" for Computer Science Competitions

Avnet ZUBoard 1CG Development Board — A New Choice for Deep learning

SenseCraft deploys models to the Grove Vision AI V2 image processing module

Document and Code Acquisition:

You can download the document via the following link:

https://github.com/leezisheng/Doc

19

This document mainly introduces how to use Python for Object Oriented programming, which requires readers to have a basic understanding of Python syntax and microcontroller development. Compared with other blogs or books that explain Python Object Oriented programming, this document is more detailed and focuses on embedded host computer applications, taking the common serial port data transmission and reception, data processing, dynamic graph drawing and other functions between the host computer and the slave computer as application examples. Meanwhile, it uses the Sourcetrail code software to visualize the code for reading to facilitate readers' understanding.

The link to obtain the relevant sample code is as follows:

https://github.com/leezisheng/Python-OOP-Demo

Body Text

Basic Knowledge of Data Structures

In fact, the queues, lists, sets, dictionaries and other structures mentioned in the previous text all belong to part of data structures. As a type of code structure, the core purpose of data structures is to store and organize data in an orderly manner, so as to simplify the processes of information modification, navigation and access. It not only determines the way data is collected, the functions implemented and the interrelationships between data, but also plays an indispensable role in various fields of computer science and programming, such as operating systems, front-end development and Machine Learning. Data structures are efficient and practical key components for solving problems, and each type of data structure has its unique applicable scenarios and tasks.

Data structures can be divided into two major categories: logical structures and physical structures.

  1. Logical structure: refers to the data organization mode of the logical relationship between data elements. This relationship focuses on the relative positions between elements, and has nothing to do with the actual storage positions of data in a computer.

In the classification of logical structures, they can be divided into linear structures and nonlinear structures:

  1. Physical structure: also known as storage structure, it describes the specific implementation form of the logical structure of data in the computer storage space. The logical structure of data can usually be mapped to multiple physical structures. Physical structure is the specific means to realize the logical relationship between data elements. A logical structure can be converted into multiple physical structures according to actual needs. Common physical structures include:
    • ① Sequential storage is characterized by the fact that the storage order of elements in memory is continuous, and the elements of a linear list are stored through a set of continuous storage units.
    • ② Chained storage: in this method, the storage elements in the memory do not need to be contiguous, and each element node contains a data element and pointer information pointing to adjacent elements.
    • ③ Index storage: in addition to storing node information, it also identifies the memory address of nodes through an additional index table, which consists of multiple index entries.
    • ④ Hash storage, also known as hash storage, in which the storage address of a node is directly determined by the key value of the node.

Next, we will briefly introduce how to use the thinking of Object Oriented programming and Python's built-in data types to implement other data structures. Note that this part is not the focus of this book, so we only give a superficial introduction to data structures here, and the implementation codes are mainly designed to help readers understand rather than for practical application.

Linked List Implementation in Python

A linked list is a non-contiguous and non-sequential storage structure on physical storage units, and it is a linear list formed by arranging data items of many identical data types in a specific order. A linked list consists of a series of nodes. A node refers to each element in the linked list, and each node contains two pieces of data: one is the data field (value) that stores the element, and the other is the pointer field that stores the address of the next node.

The Most Beginner-Friendly Object Oriented Programming Course on the Whole Network: 45 Implementing Common Data Structures in Python – Linked List, Tree, Hash Table, Graph and Heap

The first node in a linked list is called the head node, and the last node is called the tail node, where the next pointer of the tail node points to null. A linked list can be a singly linked list or a doubly linked list, depending on whether each node has only one pointer to the next node or also has another pointer to the previous node. You can visualize a linked list as a chain; each individual link only has a connection to its adjacent links, but all the links together form a larger structure.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None
class SLinkedList:
    def __init__(self):
        self.headval = None
list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2
# Link second Node to third node
e2.nextval = e3

Linked lists have the following advantages: more efficient insertion and deletion of new elements, easier to restructure than arrays, and advanced data structures (such as graphs or trees) are all built on linked lists. Their disadvantages are: the pointer storage of each Data Point increases memory usage, and it is always necessary to traverse the linked list from the head node to find a specific element.

Implementing Trees in Python

A tree is another relationship-based data structure specifically designed to represent hierarchical structures. Like linked lists, trees are also populated by Node objects, each of which contains a data value and one or more pointers that define its relationships to immediate nodes. Every tree has a root node from which all other nodes branch off. The root node holds pointers to all elements directly beneath it, which are referred to as its child nodes. These child nodes can have their own child nodes. Any nodes at the same level are called sibling nodes. Nodes that have no child nodes connected to them are called leaf nodes.

0 4

The binary tree is the data structure we use most frequently in daily practice, and the most common application of binary trees is the binary search tree. Binary search trees excel at searching through large datasets, as their time complexity depends on the depth of the tree rather than the number of nodes. Binary trees have the following characteristics:

lass Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data
    def insert(self, data):
# Compare the new value with the parent node
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data
# Print the tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()
# Use the insert method to add nodes
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
root.PrintTree()

Tree structures feature high search efficiency and are well-suited for storing hierarchical data (such as file locations, etc.), but they only apply to sorted lists; for unsorted data, they degrade to linear search.

Hash Table Implementation in Python

A hash table, also known as a hash map, is a complex data structure that can store large volumes of information and efficiently retrieve specific elements. This structure stores data composed of keys and values, and it is a data structure that directly accesses the storage locations in memory based on the keys.

152

Each input key goes through a hash function, which converts it from its original form into an integer value called a hash. A hash function must always produce the same hash from the same input, be fast to compute, and generate a fixed-length value. Python has a built-in hash () function that speeds up implementation. The table then uses the hash to find the general location of the desired value, known as a bucket. After that, the program only needs to search for the required value within this subgroup instead of scanning the entire data pool. Beyond this general framework, hash tables can vary significantly depending on the specific application.Some may allow keys from different data types, while others may have different bucket settings or different hash functions.

Here is an example of a hash table in Python code:

import pprint
class Hashtable:
    def __init__(self, elements):
        self.bucket_size = len(elements)
        self.buckets = [[] for i in range(self.bucket_size)]
        self._assign_buckets(elements)
    def _assign_buckets(self, elements):
        for key, value in elements: #calculates the hash of each key
            hashed_value = hash(key)
            index = hashed_value % self.bucket_size # positions the element in the bucket using hash
            self.buckets[index].append((key, value)) #adds a tuple in the bucket
    def get_value(self, input_key):
        hashed_value = hash(input_key)
        index = hashed_value % self.bucket_size
        bucket = self.buckets[index]
        for key, value in bucket:
            if key == input_key:
                return(value)
        return None
    def __str__(self):
        return pprint.pformat(self.buckets) # pformat returns a printable representation of the object
if __name__ == "__main__":
     capitals = [
        ('France', 'Paris'),
        ('United States', 'Washington D.C.'),
        ('Italy', 'Rome'),
        ('Canada', 'Ottawa')
    ]
hashtable = Hashtable(capitals)
print(hashtable)
print(f"The capital of Italy is {hashtable.get_value('Italy')}"

A hash table can hide keys of any form as integer indices, which is highly efficient for searching large datasets and is often applied in large databases for frequent queries or keyword-based retrieval systems.

Graph Implementation in Python

A graph is a data structure used to visualize the relationships between data vertices (the nodes of the graph). The links that connect vertices together are called edges. Edges define which vertices are connected, but do not specify the flow direction between them. Each vertex has connections to other vertices, and these connections are stored on the vertex as a comma-separated list. There is also a special type of graph called a directed graph, which defines the direction of relationships, similar to a linked list. Directed graphs are useful when modeling unidirectional relationships or flowchart-like structures.

In Python, the optimal way to implement a graph is to use a dictionary, where each vertex name serves as the key and the corresponding edge list acts as the value.

# Create the dictionary with graph elements
graph = { "a" : ["b","c"],
                 "b" : ["a", "d"],
                 "c" : ["a", "d"],
                  "d" : ["e"],
                  "e" : ["d"]
         }
# Print the graph          
print(graph)

Graphs feature relatively complex and highly efficient algorithms for data storage, with storage structures including adjacency matrices, adjacency lists, orthogonal lists, adjacency multilists, edge set arrays, among others. Common graph traversal algorithms are the breadth-first search and the depth-first search. Graphs are applicable to modeling networks or network-like structures, and can quickly convey visual information via code; however, in large-scale graphs, it is difficult to comprehend the connections between vertices, and parsing data from graphs incurs high time costs.

Heap Implementation in Python

A heap is a special tree-like structure of graphs. It is used to implement "priority queues", which are a type of data structure that allows data to be added freely, but when retrieving data, it must be taken out in order starting from the minimum value. In the tree structure of a heap, each vertex is called a "node", and data is stored in these nodes. Any tree structure that meets the following two characteristics is a heap:

10 15 30 100 40 50

We can use the heapq module to implement a min-heap that works with Python lists:

import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data

heap = []
print('random :', data)
print()

for n in data:
    print('add {:>3}:'.format(n))
    heapq.heappush(heap, n)
    show_tree(heap)

There are two functions that require attention:

347622978