An Overview on Data Structures and Algorithm in Python

Data structures and algorithms in Python are two of the most fundamental concepts in computer science. They are indispensable tools for any programmer. Data structures in Python deal with the organisation and storage of data in the memory while a program is processing it. On the other hand, Python Algorithm refer to the detailed set of instructions that helps in the processing of data for a specific purpose. 

Alternately, it can be said that different data structures are logically utilised by algorithms to work out a particular problem of data analysis. Be it a real-world problem or a typical coding-related question, an understanding of data structures and algorithms in Python is crucial if you want to come up with an accurate solution. In this article, you will find a detailed discussion of different Python algorithms and data structures.

Why use Python for algorithms?

Python is a suitable programming language for learning about data structures and algorithms. For one, it’s excellent for algorithmic design, as it’s used extensively in data science and machine learning technologies.

Furthermore, it is a high-level programming language that obscures much of the low-level implementation details, such that your pseudo-code will look very similar to Python.

It also has relatively less syntactic sugar than other languages and can be run in any browser. This is very helpful for those who are just beginning to learn about data structures and algorithms, as low-level implementation details force you to learn unrelated topics to data structures and algorithms.

What are data structures in Python? 

Data structures are a way of organizing and storing data; they explain the relationship between data and various logical operations that can be performed on the data. There are many ways in which data structures can be classified. One way is to categorize them into primitive and non-primitive data types. 

While the primitive data types include Integers, Float, Strings and Boolean, the non-primitive data types are Array, List, Tuples, Dictionary, Sets and Files. Some of these non-primitive data types, such as List, Tuples, Dictionaries and Sets, are in-built in Python. There is another category of data structures in Python that is user-defined; that is, users define them. These include Stack, Queue, Linked List, Tree, Graph and HashMap.

Primitive Data Structures:

These are the basic data structures in Python containing pure and simple data values and serve as the building blocks for manipulating data. Let us talk about the four primitive types of Data structures variables

Integers – This data type is used to represent numerical data, that is, positive or negative whole numbers without a decimal point. Say, -1, 3, or 6.

Float – Float signifies ‘floating-point real number.’ It is used to represent rational numbers, usually containing a decimal point like 2.0 or 5.77. Since Python is a dynamically typed programming language, the data type that an object stores is mutable, and there is no need to state the type of your variable explicitly.

String – This data type denotes a collection of alphabets, words or alphanumeric characters. It is created by including a series of characters within a pair of double or single quotes. To concatenate two or more Strings, the ‘+’ operation can be applied to them. Repeating, splicing, capitalizing, and retrieving are some of the other String operations in Python. Example: ‘blue,’ ‘red,’ etc.

Boolean – This data type is useful in comparison and conditional expressions and can take up the values TRUE or FALSE.

In-built non-primitive data structures :

In contrast to primitive data structures, non-primitive data types not only store values, but a collection of values in different formats. Let us have a look at non-primitive data structures in Python:

Lists – This is the most versatile data structure in Python and is written as a list of comma-separated elements enclosed within square brackets. A List can consist of both heterogeneous and homogeneous elements. Some of the methods applicable on a List are index(), append(), extend(), insert(), remove(), pop(), etc. Lists are mutable; that is, their content can be changed, keeping the identity intact.

Tuples – Tuples are similar to Lists but are immutable. Also, unlike Lists, Tuples are declared within parentheses instead of square brackets. The feature of immutability denotes that once an element has been defined in a Tuple, it cannot be deleted, reassigned or edited. It ensures that the declared values of the data structure are not manipulated or overridden.

Dictionaries – Dictionaries consist of key-value pairs. The ‘key’ identifies an item, and the ‘value’ stores the value of the item. A colon separates the key from its value. The items are separated by commas, with the entire thing enclosed within curly brackets. While keys are immutable (numbers, Strings or Tuples), the values can be of any type.

Sets – Sets are an unordered collection of unique elements. Like Lists, Sets are mutable and written within square brackets, but no two values can be the same. Some Set methods include count(), index(), any(), all(), etc.

User-defined data structures in Python :

Next up in our discussion on data structures and algorithms in Python is a brief overview of the different user-defined data structures:

Stacks – Stacks are linear data structures in Python. Storing items in Stacks is based on the principles of First-In/Last-Out (FILO) or Last-In/First-Out (LIFO). In Stacks, the addition of a new element at one end is accompanied by the removal of an element from the same end. The operations ‘push’ and ‘pop’ are used for insertions and deletions, respectively. Other functions related to Stack are empty(), size() and top(). Stacks can be implemented using modules and data structures from the Python library – list and queue.LifoQueue. 

Queue – Similar to Stacks, Queues are linear data structures. However, items are stored based on the First- In/ First- Out (FIFO) principle. In a Queue, the item that is least recently added is removed first. Operations related to Queue include Enqueue (adding elements), Dequeue (deleting elements), Front and Rear. Like Stacks, Queues can be implemented using modules and data structures from the Python library list and queue.

Tree – Trees are non-linear data structures in Python and consist of nodes connected by edges. The properties of a Tree are one node is designated the root node, other than the root, every other node has an associated parent node, and each node can have an arbitrary number of children nodes. A binary Tree data structure is one whose elements have no more than two children.

Linked List – A series of data elements joined together via links is termed as a Linked List in Python. It is also a linear data structure. Each data element in a Linked List is connected to another using pointer. Since the Python Library does not contain Linked Lists, they are implemented using the concept of nodes. Linked Lists have an advantage over Arrays in having a dynamic size, with ease of inserting/deleting elements

Graph – A Graph in Python pictorially represents a set of objects, with some object pairs connected by links. Vertices represent the objects that are interconnected, and the links that join the vertices are termed as edges. The Python dictionary data type can be used to present graphs. In essence, the ‘keys’ of the dictionary represent the vertices, and the ‘values’ indicate the connections or the edges between the vertices. 

HashMaps/Hash Tables – In this type of data structure, a Hash function generates the address or index value of the data element. The index value serves as the key to the data value allowing faster access of data. As in the dictionary data type, Hash Tables have key-value pairs, but a hashing function generates the key.

What are algorithms in Python? 

Python algorithms are a set of instructions that are executed to get the solution to a given problem. Since algorithms are not language-specific, they can be implemented in several programming languages. No standard rules guide the writing of algorithms. They are resource- and problem-dependent but share some common code constructs, such as flow-control (if-else) and loops (do, while, for). In the following sections, we will briefly discuss Tree Traversal, Sorting, Searching, and Graph Algorithms.

                                      Tree Traversal Algorithms 

Traversal is a process of visiting all the nodes of a Tree, starting from the root node. A Tree can be traversed in three different ways:

– In-order traversal involves visiting the subtree on the left first, followed by the root, and then the right subtree. 

– In the pre-order traversal, the first to be visited is the root node, followed by the left subtree, and finally, the right subtree. 

– In the post-order traversal algorithm, the left subtree is visited first, then the right subtree is visited, with the root node being visited last.

Sorting Algorithms 

Sorting algorithms denote the ways to arrange data in a particular format. Sorting ensures that data searching is optimized to a high level and that the data is presented in a readable format. Let us look at the five different types of Sorting algorithms in Python:

Bubble Sort – This algorithm is based on comparison in which there is repeated swapping of adjacent elements if they are in an incorrect order.

Merge Sort – Based on the divide and conquer algorithm, Merge sort divides the Array into two halves, sorts them, and then combines them.

Insertion Sort – This sorting begins with comparing and sorting the first two elements. Then, the third element is compared with the two previously sorted elements and so on.

Shell Sort – It is a form of Insertion sort, but here, far away elements are sorted. A large sub-list of a given list is sorted, and the size of the list is progressively reduced until all the elements are sorted. 

Selection Sort – This algorithm begins by finding the minimum value from a list of elements and puts it into a sorted list. The process is then repeated for each of the remaining elements in the list which is unsorted. The new element entering the sorted list is compared with its existing elements and placed at the correct position. The process goes on until all the elements are sorted.

Searching Algorithms 

Searching algorithms help in checking and retrieving an element from different data structures. One type of searching algorithm applies the method of sequential search where the list is sequentially traversed, and every element is checked (linear search). In another type, the interval search, elements are searched for in sorted data structures (binary search). Let us look at some of the examples:

Linear Search – In this algorithm, each item is sequentially searched one by one.

Binary Search – The search interval is repeatedly divided in half. If the element to be searched is lower than the central component of the interval, the interval is narrowed to the lower half. Otherwise, it is narrowed to the upper half. The process is repeated until the value is found. 

Graph Algorithms 

There are two methods of traversing graphs using their edges. These are:

Depth-first Traversal (DFS) – In this algorithm, a graph is traversed in a depthward motion. When any iteration faces a dead end, a stack is used to go to the next vertex and start a search. DFS is implemented in Python using the set data types.

Breadth-first Traversal (BFS) – In this algorithm, a graph is traversed in a breadthward motion. When any iteration faces a dead end, a queue is used to go to the next vertex and start a search. BFS is implemented in Python using the queue data structure.

Algorithm Analysis 

A Priori Analysis – This represents a theoretical analysis of the algorithm before its implementation. An algorithm’s efficiency is measured by presuming that factors, such as processor speed, are constant and have no consequence on the algorithm.

A Posterior Analysis – This refers to the empirical analysis of the algorithm after its implementation. A programming language is used to implement the selected algorithm, followed by its execution on a computer. This analysis collects statistics, such as the time and space required for the algorithm to run.