Python Data Structures and Algorithms

Benjamin Baka

• Publisher: Packt Publishing
• Year: 2017
• ISBN:
  9781786465337
• Edition: 1
• Topic: Informatica
• Subtopic: Programmazione in Python

Implement classic and functional data structures and algorithms using PythonAbout This Book• A step by step guide, which will provide you with a thorough discussion on the analysis and design of fundamental Python data structures.• Get a better understanding of advanced Python concepts such as big-o notation, dynamic programming, and functional data structures.• Explore illustrations to present data structures and algorithms, as well as their analysis, in a clear, visual manner.Who This Book Is ForThe book will appeal to Python developers. A basic knowledge of Python is expected.What You Will Learn• Gain a solid understanding of Python data structures.• Build sophisticated data applications.• Understand the common programming patterns and algorithms used in Python data science.• Write efficient robust code.In DetailData structures allow you to organize data in a particular way efficiently. They are critical to any problem, provide a complete solution, and act like reusable code. In this book, you will learn the essential Python data structures and the most common algorithms. With this easy-to-read book, you will be able to understand the power of linked lists, double linked lists, and circular linked lists. You will be able to create complex data structures such as graphs, stacks and queues. We will explore the application of binary searches and binary search trees. You will learn the common techniques and structures used in tasks such as preprocessing, modeling, and transforming data. We will also discuss how to organize your code in a manageable, consistent, and extendable way. The book will explore in detail sorting algorithms such as bubble sort, selection sort, insertion sort, and merge sort. By the end of the book, you will learn how to build components that are easy to understand, debug, and use in different applications.Style and approachThe easy-to-read book with its fast-paced nature will improve the productivity of Python programmers and improve the performance of Python applications.

Python Data Types and Structures

In this chapter, we are going to examine the Python data types in detail. We have already been introduced to two data types, the string, str(), and list(). It is often the case where we want more specialized objects to represent our data. 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.

Operations and expressions

There are a number of operations that are common to all data types. For example, all data types, and generally all objects, can be tested for a truth value in some way. The following are values that Python considers False:

• The None type
• False
• An integer, float, or complex zero
• An empty sequence or mapping
• An instance of a user-defined class that defines a __len__() or __bool__() method that returns zero or False

All other values are considered True.

Boolean operations

A Boolean operation returns a value of eighter True or False. Boolean operations are ordered in priority, so if more than one Boolean operation occurs in an expression, the operation with the highest priority will occur first. The following table outlines the three Boolean operators in descending order of priority:

Operator	Example
not x	Returns True if x is False; returns False otherwise.
x and y	Returns True if both x and y are True; returns False otherwise.
x or y	Returns True if either x or y is True; returns False otherwise.

Both the and operator and the or operator use "short-circuiting" when evaluating an expression. This means Python will only evaluate an operator if it needs to. For example, if x is True then in an expression x or y, the y does not get evaluated since the expression is obviously True. In a similar way, in an expression x and y where x is False, the interpreter will simply evaluate x and return False, without evaluating y.

Comparison and Arithmetic operators

The standard arithmetic operators (+, -, *, /) work with all Python numeric types. The // operator gives an integer quotient, (for example, 3 // 2 returns 1), the exponent operator is x ** y, and the modulus operator, given by a % b, returns the remainder of the division a/b. The comparison operators (<, <=, >, >=, ==, and !=) work with numbers, strings, lists, and other collection objects and return True if the condition holds. For collection objects, these operators compare the number of elements and the equivalence operator == b returns True if each collection object is structurally equivalent, and the value of each element is identical.

Membership, identity, and logical operations

Membership operators (in, not in) test for variables in sequences, such as lists or strings do what you would expect, x in y returns True if a variable x is found in y. The is operator compares object identity. For example, the following snippet shows contrast equivalence with object identity:

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 a Null, or absence of a value. It should not be forgotten either 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:

Categ...