Hands-On Data Structures and Algorithms with Python

Write complex and powerful code using the latest features of Python 3.7, 2nd Edition

Dr. Basant Agarwal, Benjamin Baka

• Éditeur: Packt Publishing
• Année: 2018
• ISBN:
  9781788991933
• Édition: 2
• Sujet: Informatica
• Sous-sujet: Programmazione in Python

Learn to implement complex data structures and algorithms using Python

Key Features

• Understand the analysis and design of fundamental Python data structures
• Explore advanced Python concepts such as Big O notation and dynamic programming
• Learn functional and reactive implementations of traditional data structures

Book Description

Data structures allow you to store and organize data efficiently. They are critical to any problem, provide a complete solution, and act like reusable code. Hands-On Data Structures and Algorithms with Python teaches you the essential Python data structures and the most common algorithms for building easy and maintainable applications.

This book helps you to understand the power of linked lists, double linked lists, and circular linked lists. You will learn to create complex data structures, such as graphs, stacks, and queues. As you make your way through the chapters, you will explore the application of binary searches and binary search trees, along with learning common techniques and structures used in tasks such as preprocessing, modeling, and transforming data. In the concluding chapters, you will get to grips with organizing your code in a manageable, consistent, and extendable way. You will also study how to bubble sort, selection sort, insertion sort, and merge sort algorithms in detail.

By the end of the book, you will have learned how to build components that are easy to understand, debug, and use in different applications. You will get insights into Python implementation of all the important and relevant algorithms.

What you will learn

• Understand object representation, attribute binding, and data encapsulation
• Gain a solid understanding of Python data structures using algorithms
• Study algorithms using examples with pictorial representation
• Learn complex algorithms through easy explanation, implementing Python
• Build sophisticated and efficient data applications in Python
• Understand common programming algorithms used in Python data science
• Write efficient and robust code in Python 3.7

Who this book is for

This book is for developers who want to learn data structures and algorithms in Python to write complex and flexible programs. Basic Python programming knowledge is expected.

Python Data Types and Structures

In this chapter, we are going to examine Python data types in more detail. We have already introduced two data types, the string and list, str() and list(). However, these data types are not sufficient, and we often need more specialized data objects to represent/store our data. Python has various other standard data types that are used to store and manage data, which we will be discussing in this chapter. In addition to the built-in types, there are several internal modules that allow us to address common issues when working with data structures. First, we are going to review some operations and expressions that are common to all data types, and we will discuss more related to data types in Python.

This chapter's objectives are as follows:

• Understanding various important built-in data types supported in Python 3.7
• Exploring various additional collections of high-performance alternatives to built-in data types

Technical requirements

All of the code used in this chapter is given at the following GitHub link: https://github.com/PacktPublishing/Hands-On-Data-Structures-and-Algorithms-with-Python-Second-Edition/tree/master/Chapter02.

Built-in data types

Python data types can be divided into three categories: numeric, sequence, and mapping. There is also the None object that represents Null, or the absence of a value. It should not be forgotten that other objects such as classes, files, and exceptions can also properly be considered types; however, they will not be considered here.

Every value in Python has a data type. Unlike many programming languages, in Python you do not need to explicitly declare the type of a variable. Python keeps track of object types internally.

Python built-in data types are outlined in the following table:

Category	Name	Description
None	None	It is a null object.
Numeric	int	This is an integer data type.
	float	This data type can store a floating-point number.
	complex	It stores a complex number.
	bool	It is Boolean type and returns True or False.
Sequences	str	It is used to store a string of characters.
	liXst	It can store a list of arbitrary objects.
	Tuple	It can store a group of arbitrary items.
	range	It is used to create a range of integers.
Mapping	dict	It is a dictionary data type that stores data in key/value pairs.
	set	It is a mutable and unordered collection of unique items.
	frozenset	It is an immutable set.

None type

The None type is immutable. It is used as None to show the absence of a value; it is similar to null in many programming languages, such as C and C++. Objects return None when there is actually nothing to return. It is also returned by False Boolean expressions. None is often used as a default value in function arguments to detect whether a function call has passed a value or not.

Numeric types

Number types include integers (int), that is, whole numbers of unlimited range, floating-point numbers (float), complex numbers (complex), which are represented by two float numbers, and Boolean (bool) in Python. Python provides the int data type that allows standard arithmetic operators (+, -, * and / ) to work on them, similar to other programming languages. A Boolean data type has two possible values, True and False. These values are mapped to 1 and 0, respectively. Let's consider an example:

>>> a=4; b=5 # Operator (=) assigns the value to variable
>>>print(a, "is of type", type(a))
4 is of type 
<class 'int'>
>>> 9/5 
1.8
>>>c= b/a # division returns a floating point number
>>> print(c, "is of type", type(c))
1.25 is of type <class 'float'>
>>> c # No need to explicitly declare the datatype
1.25

The a and b variables are of the int type and c is a floating-point type. The division operator (/) always returns a float type; however, if you wish to get the int type after division, you can use the floor division operator (//), which discards any fractional part and will return the largest integer value that is less than or equal to x. Consider the following example:

>>> a=4; b=5 
>>>d= b//a
>>> print(d, "is of type", type(d))
1 is of type <class 'int'>
>>>7/5 # true division
1.4
>>> -7//5 # floor division operator
-2

It is advised that readers use the division operator carefully, as its function differs according to the Python version. In Python 2, the division operator returns only integer, not float.

The exponent operator (**) can be used to get the power of a number (for example, x ** y), and the modulus operator (%) returns the remainder of the division (for example, a% b returns the remainder of a/b):

>>> a=7; b=5  
>>> e= b**a # The operator (**)calculates power 
>>>e
78125
>>>a%b
2

Complex numbers are represented by two floating-point numbers. They are assigned using the j operator to signify the imaginary part of the complex number. We can access the real and imaginary parts with f.real and f.imag, respectively, as shown in the following code snippet. Complex numbers are generally used for scientific computations. Python supports addition, subtraction, multiplication, power, conjugates, and so ...