Contents
- Abstract:
- Original Link:
- Previous Recommendations:
- For more exciting content, you can check out:
- Document and Code Acquisition:
- Body Text
- Basic Knowledge of Data Structures
- Linked List Implementation in Python
- Implementing Trees in Python
- Hash Table Implementation in Python
- Graph Implementation in Python
- Heap Implementation in Python

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.
Original Link:
Previous Recommendations:
You who are learning embedded systems, don’t you even know Object Oriented yet? ?!
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
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

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.
- 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:
- ① A linear structure is a data structure in which there exists a one-to-one linear relationship between elements, with each node having at most one predecessor node and one successor node. Typical linear structures include arrays, queues, linked lists and stacks;
- ② Elements in a nonlinear structure have complex correspondence relationships, and a single node may correspond to multiple predecessor nodes and successor nodes. Multidimensional arrays, generalized lists, tree structures, graph structures, etc. , all fall into the category of nonlinear structures.
- 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 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 = e3Linked 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.

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:
- The left subtree only contains nodes whose elements are smaller than the root.
- The right subtree only contains nodes whose elements are greater than the root.
- The left and right subtrees must also be binary search trees, and they must follow the above rules with their respective roots.
- There must be no duplicate nodes, meaning no two nodes can have the same value.
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.

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:
- A heap is a complete binary tree (a complete binary tree means that all layers except the last one have a full number of nodes).
- The value of every node in a heap must be greater than or equal to, or less than or equal to, the value of every node in its subtree.

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:
heapq.heappush (heap, item): Push the value item onto the heap, maintaining the heap invariant.heapq_showtree.show_tree (heap): Used to display tree structures.
