Introduction to Data Structures and Algorithms With Python

Understanding data structures and algorithms

Algorithms and data structures are the most fundamental concepts in computing. They are the building blocks from which complex software is built. Three characteristics to look out for;

1. How algorithms manipulate the information contained within data structures
2. How data is arranged in memory
3. What the performance characteristics of particular data structures are

Measuring an algorithm's performance involves understanding how each increase in data size affects operations on that data. When we are working on large datasets or real-time applications, it is essential that our algorithms and structures are as efficient as they can be. Python has several built-in data structures, including lists, dictionaries, and sets, that we use to build customized objects.

A) Lists

Lists are probably the most used built-in data structures in Python because they can be composed of any number of other data types. They are a simple representation of arbitrary objects. Like strings, they are indexed by integers starting with zero.

lst = [a,b,c,d]

The following table contains the most commonly used list methods and their descriptions: Method Description

Tuples

Tuples are immutable sequences of arbitrary objects. They are indexed by integers greater than zero. Tuples are hashable, which means we can sort lists of them and they can be used as keys to dictionaries. Syntactically, tuples are just a comma-separated sequence of values; however, it is common practice to enclose them in parentheses:

tpl= ('a', 'b', 'c')

It is important to remember to use a trailing comma when creating a tuple with one element, for example: t = ('a',) Without the trailing comma, this would be interpreted as a string. We can also create a tuple using the built-in function tuple(). With no argument, this creates an empty tuple. If the argument to the tuple()

Dictionaries

Dictionaries are arbitrary collections of objects indexed by numbers, strings, or other immutable objects. Dictionaries themselves are mutable; however, their index keys must be immutable The following table contains all the dictionary methods and their descriptions: Method Description

Python dictionaries are the only built-in mapping type and they are similar to hash tables or associative arrays found in other languages. They can be thought of as a mapping from a set of keys to a set of values. They are created using the syntax {key: value}.

Sets

Sets are unordered collections of unique items. Sets are themselves mutable, we can add and remove items from them; however, the items themselves must be immutable. An important distinction with sets is that they cannot contain duplicate items. Sets are typically used to perform mathematical operations such as intersection, union, difference, and complement. Unlike sequence types, set types do not provide any indexing or slicing operations. There are also no keys associated with values, as is the case with dictionaries. Sets are created using comma-separated values within curly braces. By the way, we cannot create an empty set using a={}, because this will create a dictionary. To create an empty set, we write either a=set() or a=frozenset().

Principles of Algorithms

Algorithms, in their simplest form, are just a sequence of actions, a list of instructions. It may just be a linear construct of the form do x, then do y, then do z, then finish. However, to make things more useful we add clauses to the effect of, x then do y, in Python the if-else statements.

Essentially, we can say that algorithms are composed of the following four elements: Sequential operations

• Actions based on the state of a data structure
• Iteration, repeating an action a number of times
• Recursion, calling itself on a subset of inputs

Singly-linked list class

A list is clearly a separate concept from a node. Creating a very simple class to hold our list, starting with a constructor that holds a reference to the very first node in the list. Since this list is initially empty, then start by setting this reference to None:

**Append operation

Appending items to the list, This operation is sometimes called an insert operation. Users of the list class should really never have to interact with Node objects. These are purely for internal use. The first shot at an append() method may look like this:

We encapsulate data in a node so that it now has the next pointer attribute. From here we check if there are any existing nodes in the list (that is, does self.tail point to a Node). If there is none, we make the new node the first node of the list; otherwise, find the insertion point by traversing the list to the last node, updating the next pointer of the last node to the new node.

     >>>words = SinglyLinkedList()
     >>> words.append('egg')
     >>> words.append('ham')
     >>> words.append('spam')

List traversal will work more or less like before. You will get the first element of the list from the list itself:

>>> current = words.tail
>>> while current:
 print(current.data)
 current = current.next