Python Data Structures Tutorial PDF

Python Data Structures i Python Data Structures About the Tutorial Computers store and process data with an extra ordinary speed and accuracy. So, it is highly essential that the data is stored efficiently and can be accessed fast. Also, the processing of data should happen in the smallest possible time, but without losing the accuracy. Data structures deal with how the data is organised and held in the memory, when a program processes it. It is important to note that, the data that is stored in the disk as part of persistent storages (like relational tables) are not referred as data structure here. An Algorithm is step by step set of instruction to process the data for a specific purpose. So, an algorithm utilises various data structures in a logical way to solve a specific computing problem. In this tutorial, we will cover these two fundamental concepts of computer science using the Python programming language. Audience This tutorial is designed for Computer Science graduates as well as Software Professionals who are willing to learn data structures and algorithm programming in simple and easy steps using Python as a programming language. Prerequisites Before proceeding with this tutorial, you should have a basic knowledge of writing code in Python programming language, using any python integrated development environment (IDE) and execution of Python programs. If you are completely new to python, then please refer our Python tutorial to get a sound understanding of the language. Copyright & Disclaimer  Copyright 2020 by Tutorials Point (I) Pvt. Ltd. All the content and graphics published in this e-book are the property of Tutorials Point (I) Pvt. Ltd. The user of this e-book is prohibited to reuse, retain, copy, distribute or republish any contents or a part of contents of this e-book in any manner without written consent of the publisher. We strive to update the contents of our website and tutorials as timely and as precisely as possible, however, the contents may contain inaccuracies or errors. Tutorials Point (I) Pvt. Ltd. provides no guarantee regarding the accuracy, timeliness or completeness of our website or its contents including this tutorial. If you discover any errors on our website or in this tutorial, please notify us at [email protected] ii Python Data Structures Table of Contents About the Tutorial........................................................................................................................................... ii Audience.......................................................................................................................................................... ii Prerequisites.................................................................................................................................................... ii Copyright & Disclaimer.................................................................................................................................... ii Table of Contents........................................................................................................................................... iii 1. Python Data Structures – Introduction...................................................................................................... 1 Data Structures Overview................................................................................................................................ 1 General Data Structures.................................................................................................................................. 1 Python Specific Data Structures...................................................................................................................... 2 2. Python Data Structures – Environment..................................................................................................... 3 Local Environment Setup................................................................................................................................. 3 Getting Python................................................................................................................................................ 3 Installing Python.............................................................................................................................................. 3 Setting up PATH............................................................................................................................................... 5 Python Environment Variables........................................................................................................................ 5 Running Python............................................................................................................................................... 6 3. Python Data Structures – Arrays............................................................................................................... 9 Array Representation...................................................................................................................................... 9 Basic Operations.............................................................................................................................................. 9 Accessing Array Element............................................................................................................................... 11 Insertion Operation....................................................................................................................................... 11 Deletion Operation........................................................................................................................................ 12 Search Operation........................................................................................................................................... 12 Update Operation.......................................................................................................................................... 13 4. Python Data Structures – Lists................................................................................................................ 14 Accessing Values............................................................................................................................................ 14 iii Python Data Structures Updating Lists................................................................................................................................................ 14 Delete List Elements...................................................................................................................................... 15 Basic List Operations..................................................................................................................................... 16 5. Python Data Structures – Tuples............................................................................................................. 17 Accessing Values in Tuples............................................................................................................................ 17 Updating Tuples............................................................................................................................................. 18 Delete Tuple Elements.................................................................................................................................. 18 Basic Tuples Operations................................................................................................................................ 19 6. Python Data Structures – Dictionary....................................................................................................... 20 Accessing Values in Dictionary...................................................................................................................... 20 Updating Dictionary....................................................................................................................................... 21 Delete Dictionary Elements........................................................................................................................... 21 Properties of Dictionary Keys........................................................................................................................ 22 7. Python Data Structures – 2D Array......................................................................................................... 23 Accessing Values............................................................................................................................................ 23 Inserting Values............................................................................................................................................. 24 Updating Values............................................................................................................................................ 25 Deleting the Values....................................................................................................................................... 25 8. Python Data Structures – Matrix............................................................................................................. 27 Accessing Values............................................................................................................................................ 27 Adding a row................................................................................................................................................. 28 Adding a column............................................................................................................................................ 29 Delete a row.................................................................................................................................................. 29 Delete a column............................................................................................................................................ 30 Update a row................................................................................................................................................. 30 9. Python Data Structures – Sets................................................................................................................. 32 Set Operations............................................................................................................................................... 32 Accessing Values in a Set............................................................................................................................... 32 iv Python Data Structures Adding Items to a Set.................................................................................................................................... 33 Removing Item from a Set............................................................................................................................. 33 Union of Sets................................................................................................................................................. 34 Intersection of Sets........................................................................................................................................ 34 Difference of Sets.......................................................................................................................................... 34 Compare Sets................................................................................................................................................. 35 10. Python Data Structures – Maps............................................................................................................... 36 Creating a ChainMap..................................................................................................................................... 36 Map Reordering............................................................................................................................................. 37 Updating Map................................................................................................................................................ 38 11. Python Data Structures – Linked Lists..................................................................................................... 39 Creation of Linked list.................................................................................................................................... 39 Traversing a Linked List................................................................................................................................. 40 Insertion in a Linked List................................................................................................................................ 41 Removing an Item.......................................................................................................................................... 45 12. Python Data Structures – Stack............................................................................................................... 47 PUSH into a Stack.......................................................................................................................................... 47 POP from a Stack........................................................................................................................................... 48 13. Python Data Structures – Queue............................................................................................................. 50 Adding Elements............................................................................................................................................ 50 Removing Element........................................................................................................................................ 51 14. Python Data Structures – Dequeue......................................................................................................... 52 15. Python Data Structutres – Advanced Linked List..................................................................................... 54 Creating Doubly linked list............................................................................................................................. 54 Inserting into Doubly Linked List................................................................................................................... 55 Appending to a Doubly linked list.................................................................................................................. 56 16. Python Data Structures – Hash Table...................................................................................................... 59 Accessing Values in Dictionary...................................................................................................................... 59 v Python Data Structures Updating Dictionary....................................................................................................................................... 59 Delete Dictionary Elements........................................................................................................................... 60 17. Python Data Structures – Binary Tree..................................................................................................... 61 Create Root.................................................................................................................................................... 61 Inserting into a Tree...................................................................................................................................... 62 Traversing a Tree........................................................................................................................................... 63 Tree Traversal Algorithms............................................................................................................................. 63 18. Python Data Structures – Search Tree..................................................................................................... 69 Search for a value in a B-tree........................................................................................................................ 69 19. Python Data Structures – Heaps.............................................................................................................. 71 Create a Heap................................................................................................................................................ 71 Creating a Heap............................................................................................................................................. 71 Inserting into heap........................................................................................................................................ 72 Removing from heap..................................................................................................................................... 72 Replacing in a Heap....................................................................................................................................... 73 20. Python Data Structures – Graphs............................................................................................................ 74 Display graph vertices................................................................................................................................... 75 Display graph edges....................................................................................................................................... 76 Adding a vertex.............................................................................................................................................. 77 Adding an edge.............................................................................................................................................. 78 21. Python Data Structures – Algorithm Design............................................................................................ 80 Characteristics of an Algorithm..................................................................................................................... 80 How to Write an Algorithm?......................................................................................................................... 80 22. Python Data Structures – Divide and Conquer........................................................................................ 83 Binary Search implementation...................................................................................................................... 84 23. Python Data Structures – Recursion........................................................................................................ 86 Binary Search using Recursion....................................................................................................................... 86 24. Python Data Structures – Backtracking................................................................................................... 87 vi Python Data Structures 25. Python Data Structures – Sorting Algorithms.......................................................................................... 88 Bubble Sort.................................................................................................................................................... 88 Merge Sort..................................................................................................................................................... 89 Insertion Sort................................................................................................................................................. 90 Shell Sort........................................................................................................................................................ 90 Selection Sort................................................................................................................................................. 91 26. Python Data Structures – Searching Algorithms...................................................................................... 93 Linear Search................................................................................................................................................. 93 Interpolation Search...................................................................................................................................... 93 27. Python Data Structures – Graph Algorithms........................................................................................... 95 Depth First Traversal..................................................................................................................................... 95 Breadth First Traversal.................................................................................................................................. 96 28. Python Data Structures – Algorithm Analysis.......................................................................................... 98 Algorithm Complexity.................................................................................................................................... 98 Space Complexity.......................................................................................................................................... 98 Time Complexity............................................................................................................................................ 99 29. Python Data Structures – Algorithm Types............................................................................................ 100 Asymptotic Notations.................................................................................................................................. 100 Common Asymptotic Notations.................................................................................................................. 102 30. Python Data Structures – Algorithm Classes......................................................................................... 103 Greedy Algorithms....................................................................................................................................... 103 Divide and Conquer..................................................................................................................................... 103 Dynamic Programming................................................................................................................................ 103 31. Python Data Structures – Amortized Analysis....................................................................................... 105 32. Python Data Structures – Algorithm Justification.................................................................................. 106 vii 1. Python Data Structures – Introduction Python Data Structures Here, we will understand what is data structure with regards to Python programming language. Data Structures Overview Data structures are fundamental concepts of computer science, which helps in writing efficient programs in any language. Python is a high-level, interpreted, interactive and object-oriented scripting language. Hence, by using python language, we can study the fundamentals of data structure in a simpler way as compared to other programming languages. In this chapter, we are going to study a short overview of some frequently used data structures in general and how they are related to some specific python data types. There are also some data structures specific to python which are listed as another category. General Data Structures The various data structures in computer science are divided broadly into two categories as shown below. We will discuss about each of the below data structures in detail in subsequent chapters. Liner Data Structures These are the data structures which store the data elements in a sequential manner.  Array: It is a sequential arrangement of data elements paired with the index of the data element.  Linked List: Each data element contains a link to another element, along with the data present in it.  Stack: It is a data structure, which follows only to specific order of operation. LIFO (last in First Out) or FILO(First in Last Out).  Queue: It is similar to Stack, but the order of operation is only FIFO (First In First Out).  Matrix: It is two dimensional data structure in which, the data element is referred by a pair of indices. Non-Liner Data Structures These are the data structures in which, there is no sequential linking of data elements. Any pair or group of data elements can be linked to each other and can be accessed without a strict sequence. 1 Python Data Structures  Binary Tree: It is a data structure, where each data element can be connected to maximum two other data elements and it starts with a root node.  Heap: It is a special case of Tree data structure, where the data in the parent node is either strictly greater than/ equal to the child nodes or strictly less than its child nodes.  Hash Table: It is a data structure, which is made of arrays associated with each other using a hash function. It retrieves values using keys rather than, index from a data element.  Graph: It is an arrangement of vertices and nodes, where some of the nodes are connected to each other through links. Python Specific Data Structures These data structures are specific to python language and they give greater flexibility in storing different types of data and faster processing in python environment.  List: It is similar to array with the exception, that the data elements can be of different data types. You can have both numeric and string data in a python list.  Tuple: Tuples are similar to lists, but they are immutable which means, the values in a tuple cannot be modified they can only be read.  Dictionary: The dictionary contains Key-value pairs as its data elements. In the next chapters, we are going to learn the details of how each of these data structures can be implemented using Python. 2 2. Python Data Structures – Environment Python Data Structures Python is available on a wide variety of platforms, including Linux and Mac OS X. Let's understand, how to set up our Python environment. Local Environment Setup Open a terminal window and type "python" to find out, if it is already installed and which version is installed.  Unix (Solaris, Linux, FreeBSD, AIX, HP/UX, SunOS, IRIX, etc.)  Win 9x/NT/2000  Macintosh (Intel, PPC, 68K)  OS/2  DOS (multiple versions)  PalmOS  Nokia mobile phones  Windows CE  Acorn/RISC OS  BeOS  Amiga  VMS/OpenVMS  QNX  VxWorks  Psion  Python has also been ported to the Java and.NET virtual machines Getting Python The most up-to-date and current source code, binaries, documentation, news, etc., is available on the official website of Python which is available at https://www.python.org/ You can download Python documentation from this website given herewith, https://www.python.org/doc/. The documentation is available in HTML, PDF, and PostScript formats. Installing Python Python distribution is available for a wide variety of platforms. You need to download only the binary code applicable for your platform and install Python. 3 Python Data Structures If the binary code for your platform is not available, you need a C compiler to compile the source code manually. Compiling the source code offers, more flexibility in terms of choice of features that you require in your installation. Here is a quick overview of installing Python on various platforms. Unix and Linux Installation Here are the simple steps to install Python on Unix/Linux machine.  Open a Web browser and go to https://www.python.org/downloads/.  Follow the link to download zipped source code available for Unix/Linux.  Download and extract files.  Editing the Modules/Setup file, if you want to customise some options.  run./configure script  make  make install This installs Python at standard location /usr/local/bin and its libraries at /usr/local/lib/pythonXX where, XX is the version of Python. Windows Installation Here, are the steps to install Python on Windows machine.  Open a Web browser and go to https://www.python.org/downloads/.  Follow the link for the Windows installer python-XYZ.msi file where, XYZ is the version you need to install.  To use this installer python-XYZ.msi, the Windows system must support Microsoft Installer 2.0. Save the installer file to your local machine and then, run it to find out if your machine supports MSI.  Run the downloaded file. This brings up the Python install wizard, which is really easy to use. Just accept the default settings, wait until the install is finished, and you are done. Macintosh Installation  Recent Macs come with Python installed, but it may be several years out of date. See http://www.python.org/download/mac/ for instructions on getting the current version along with extra tools to support development on the Mac. For older Mac OS's before Mac OS X 10.3 (released in 2003), MacPython is available.  Jack Jansen maintains it and you can have full access to the entire documentation at his website, which is available at http://www.cwi.nl/~jack/macpython.html. You can find complete installation details for Mac OS installation. 4 Python Data Structures Setting up PATH Programs and other executable files can be in many directories, so operating systems provide a search path that, lists the directories that the OS searches for executables. The path is stored in an environment variable, which is a named string maintained by the operating system. This variable contains information available to the command shell and other programs. The path variable is named as PATH in Unix or Path in Windows (Unix is case sensitive; Windows is not). In Mac OS, the installer handles the path details. To invoke the Python interpreter from any particular directory, you must add the Python directory to your path. Setting path at Unix/Linux To add the Python directory to the path for a particular session in Unix, refer the following:  In the csh shell: type setenv PATH "$PATH:/usr/local/bin/python" and press Enter.  In the bash shell (Linux): type export ATH="$PATH:/usr/local/bin/python" and press Enter.  In the sh or ksh shell: type PATH="$PATH:/usr/local/bin/python" and press Enter.  Note: /usr/local/bin/python is the path of the Python directory. Setting path at Windows To add the Python directory to the path for a particular session in Windows, refer the following:  At the command prompt: type path %path%;C:\Python and press Enter.  Note: C:\Python is the path of the Python directory. Python Environment Variables Here in the table below, are important environment variables, which can be recognised by Python. Sr.No. Variable & Description 1 PYTHONPATH It has a role similar to PATH. This variable tells the Python interpreter, where to locate the module files imported into a program. It should include the Python source library directory and the directories containing Python source code. PYTHONPATH is sometimes, preset by the Python installer. 5 Python Data Structures 2 PYTHONSTARTUP It contains the path of an initialisation file containing Python source code. It is executed every time; you start the interpreter. It is named as.pythonrc.py in Unix and it contains commands that load utilities or modify PYTHONPATH. 3 PYTHONCASEOK It is used in Windows to instruct Python, to find the first case-insensitive match in an import statement. Set this variable to any value to activate it. 4 PYTHONHOME It is an alternative module search path. It is usually embedded in the PYTHONSTARTUP or PYTHONPATH directories to make switching module libraries easy. Running Python There are three different ways to start Python, which are as follows: Interactive Interpreter  You can start Python from Unix, DOS, or any other system, that provides you a command - line interpreter or shell window.  Enter python the command line.  Start coding right away in the interactive interpreter. $python # Unix/Linux or python% # Unix/Linux or C:> python # Windows/DOS Here, is the list of all the available command line options, which is as mentioned below: Sr.No. Option & Description 1 -d It provides debug output. 2 -O It generates optimised bytecode (resulting in.pyo files). 6 Python Data Structures 3 -S Do not run import site to look for Python paths on startup. 4 -v verbose output (detailed trace on import statements). 5 -X disable class-based built-in exceptions (just use strings); obsolete starting with version 1.6. 6 -c cmd run Python script sent in as cmd string. 7 file run Python script from given file. Script from the Command-line A Python script can be executed at command line by invoking the interpreter on your application, as in the following: $python script.py # Unix/Linux or python% script.py # Unix/Linux or C: >python script.py # Windows/DOS  Note − Be sure the file permission mode allows execution. Integrated Development Environment (IDE) You can run Python from a Graphical User Interface (GUI) environment as well, if you have a GUI application on your system that supports Python.  Unix − IDLE is the very first Unix IDE for Python.  Windows − PythonWin is the first Windows interface for Python and is an IDE with a GUI. 7 Python Data Structures  Macintosh − The Macintosh version of Python, along with the IDLE IDE is available from the main website, downloadable as either MacBinary or BinHex'd files. If you are not able to set up the environment properly, then you can take help from your system admin. Make sure the Python environment is properly set up and working perfectly fine.  Note − All the examples given in subsequent chapters are executed with Python 2.4.3 version available on CentOS flavor of Linux. We already have set up Python Programming environment online, so that, you can execute all the available examples online at the same time, when you are learning theory. Feel free to modify any example and execute it online. 8 3. Python Data Structures – Arrays Python Data Structures Array is a container, which can hold a fix number of items and these items should be of the same type. Most of the data structures make use of arrays to implement their algorithms. The important terms to understand the concept of Array are as follows:  Element− Each item stored in an array is called an element.  Index − Each location of an element in an array has a numerical index, which is used to identify the element. Array Representation Arrays can be declared in various ways in different languages. An illustration is given below: As per the above illustration, following are the important points to be considered:  Index starts with 0.  Array length is 10, which means it can store 10 elements.  Each element can be accessed via its index. For example, we can fetch an element at index 6 as 9. Basic Operations The basic operations supported by an array are as stated below:  Traverse − Print all the array elements one by one.  Insertion − Adds an element at the given index.  Deletion − Deletes an element at the given index.  Search − Searches an element, using the given index or by the value.  Update − Updates an element at the given index. 9 Python Data Structures Array is created in Python by importing array module to the python program. Then, the array is declared as shown below: from array import * arrayName = array(typecode, [Initializers]) Typecode are the codes that are used to define the type of value the array will hold. Some common typecodes used are as follows: Typecode Value b Represents signed integer of size 1 byte/td> B Represents unsigned integer of size 1 byte c Represents character of size 1 byte i Represents signed integer of size 2 bytes I Represents unsigned integer of size 2 bytes f Represents floating point of size 4 bytes d Represents floating point of size 8 bytes Before looking at various array operations, lets create and print an array using python. The below code creates an array named array1. from array import * array1 = array('i', [10,20,30,40,50]) for x in array1: print(x) Output When we compile and execute the above program, it produces the following result: 10 20 30 10 Python Data Structures 40 50 Accessing Array Element We can access each element of an array, using the index of the element. The below code shows how to access an array element. from array import * array1 = array('i', [10,20,30,40,50]) print (array1) print (array1) Output When we compile and execute the above program, it produces the following result, which shows the element is inserted at index position 1. 10 30 Insertion Operation Insert operation is, to insert one or more data elements into an array. Based on the requirement, a new element can be added at the beginning, end, or any given index of array. Here, we add a data element at the middle of the array, using the python in-built insert() method. from array import * array1 = array('i', [10,20,30,40,50]) array1.insert(1,60) for x in array1: print(x) Output 11 Python Data Structures When we compile and execute the above program, it produces the following result which shows the element is inserted at index position 1. 10 60 20 30 40 50 Deletion Operation Deletion refers to removing an existing element from the array and re-organising all elements of an array. Here, we remove a data element at the middle of the array, using the python in-built remove() method. from array import * array1 = array('i', [10,20,30,40,50]) array1.remove(40) for x in array1: print(x) Output When we compile and execute the above program, it produces the following result, which shows the element is removed from the array. 10 20 30 50 Search Operation You can perform a search for an array element based on its value or its index. Here, we search a data element, by using the python in-built index() method. from array import * 12 Python Data Structures array1 = array('i', [10,20,30,40,50]) print (array1.index(40)) Output When we compile and execute the above program, it produces the following result which shows the index of the element. If the value is not present in the array, then the program returns an error. 3 Update Operation Update operation refers to updating an existing element from the array at a given index. Here, we simply reassign a new value to the desired index we want to update. from array import * array1 = array('i', [10,20,30,40,50]) array1 = 80 for x in array1: print(x) Output When we compile and execute the above program, it produces the following result, which shows the new value at the index position 2. 10 20 80 40 50 13 4. Python Data Structures – Lists Python Data Structures The list is a most versatile datatype available in Python, which can be written as a list of comma-separated values (items) between square brackets. An important thing about the list is that, items in a list need not be of the same type. Creating a list is as simple as putting different comma-separated values between square brackets. For example: list1 = ['physics', 'chemistry', 1997, 2000] list2 = [1, 2, 3, 4, 5 ] list3 = ["a", "b", "c", "d"] Similar to string indices, list indices start at 0, and lists can be sliced, concatenated and so on. Accessing Values To access values in lists, use the square brackets for slicing along with the index or indices to obtain value available at that index. For example: #!/usr/bin/python list1 = ['physics', 'chemistry', 1997, 2000] list2 = [1, 2, 3, 4, 5, 6, 7 ] print "list1: ", list1 print "list2[1:5]: ", list2[1:5] When the above code is executed, it produces the following result: list1: physics list2[1:5]: [2, 3, 4, 5] Updating Lists You can update single or multiple elements of lists, by giving the slice on the left-hand side of the assignment operator, and you can add to elements in a list with the append() method. For example: 14 Python Data Structures #!/usr/bin/python list = ['physics', 'chemistry', 1997, 2000] print "Value available at index 2 : " print list list = 2001 print "New value available at index 2 : " print list  Note − append() method is discussed in subsequent section. When the above code is executed, it produces the following result: Value available at index 2 : 1997 New value available at index 2 : 2001 Delete List Elements To remove a list element, you can use either the del statement, if you know exactly, which element(s) you are deleting or the remove() method, if you do not know. For example: #!/usr/bin/python list1 = ['physics', 'chemistry', 1997, 2000] print list1 del list1 print "After deleting value at index 2 : " print list1 When the above code is executed, it produces following result: ['physics', 'chemistry', 1997, 2000] After deleting value at index 2 : ['physics', 'chemistry', 2000]  Note − remove() method is discussed in subsequent section. 15 Python Data Structures Basic List Operations Lists respond to the + and * operators. Much like strings, they mean concatenation and repetition here too, except that the result is a new list, not a string. In fact, lists respond to all of the general sequence operations we used on strings in the prior chapter. Python Expression Results Description len([1, 2, 3]) 3 Length [1, 2, 3] + [4, 5, 6] [1, 2, 3, 4, 5, 6] Concatenation ['Hi!'] * 4 ['Hi!', 'Hi!', 'Hi!', 'Hi!'] Repetition 3 in [1, 2, 3] True Membership for x in [1, 2, 3]: print x, 123 Iteration 16 5. Python Data Structures – Tuples Python Data Structures A tuple is a sequence of immutable Python objects, just like lists. The differences between tuples and lists are, the tuples cannot be changed unlike lists and tuples use parentheses, whereas lists use square brackets. Creating a tuple is as simple as putting different comma-separated values. Optionally, you can put these comma-separated values between parentheses also. For example: tup1 = ('physics', 'chemistry', 1997, 2000); tup2 = (1, 2, 3, 4, 5 ); tup3 = "a", "b", "c", "d"; The empty tuple is written as two parentheses containing nothing. tup1 = (); To write a tuple containing a single value, you have to include a comma. Even though, there is only one value. tup1 = (50,); Like string indices, tuple indices start at 0, and they can be sliced, concatenated, and so on. Accessing Values in Tuples To access values in tuple, use the square brackets for slicing along with the index or indices to obtain value available at that index. For example: #!/usr/bin/python tup1 = ('physics', 'chemistry', 1997, 2000); tup2 = (1, 2, 3, 4, 5, 6, 7 ); print "tup1: ", tup1; print "tup2[1:5]: ", tup2[1:5]; When the above code is executed, it produces the following result: tup1: physics tup2[1:5]: [2, 3, 4, 5] 17 Python Data Structures Updating Tuples Tuples are immutable, which means you cannot update or change the values of tuple elements. You are able to take portions of existing tuples, to create new tuples as the following example demonstrates: #!/usr/bin/python tup1 = (12, 34.56); tup2 = ('abc', 'xyz'); # Following action is not valid for tuples # tup1 = 100; # So let's create a new tuple as follows tup3 = tup1 + tup2; print tup3; When the above code is executed, it produces the following result: (12, 34.56, 'abc', 'xyz') Delete Tuple Elements Removing individual tuple elements is not possible. There is, of course, nothing wrong with putting together another tuple with the undesired elements discarded. To explicitly remove an entire tuple, just use the del statement. For example: #!/usr/bin/python tup = ('physics', 'chemistry', 1997, 2000); print tup; del tup; print "After deleting tup : "; print tup;  Note: An exception raised, because after del tup, tuple does not exist anymore. This produces the following result: ('physics', 'chemistry', 1997, 2000) 18 Python Data Structures After deleting tup : Traceback (most recent call last): File "test.py", line 9, in print tup; NameError: name 'tup' is not defined Basic Tuples Operations Tuples respond to the + and * operators. Much like strings; they mean concatenation and repetition here too, except that the result is a new tuple, not a string. In fact, tuples respond to all of the general sequence operations, we used on strings in the prior chapter. Python Expression Results Description len((1, 2, 3)) 3 Length (1, 2, 3) + (4, 5, 6) (1, 2, 3, 4, 5, 6) Concatenation ('Hi!',) * 4 ('Hi!', 'Hi!', 'Hi!', 'Hi!') Repetition 3 in (1, 2, 3) True Membership for x in (1, 2, 3): print x, 123 Iteration 19 6. Python Data Structures – Dictionary Python Data Structures In Dictionary each key is separated from its value by a colon (:), the items are separated by commas, and the whole thing is enclosed in curly braces. An empty dictionary without any items is written with just two curly braces, like this: {}. Keys are unique within a dictionary while values may not be. The values of a dictionary can be of any type, but the keys must be of an immutable data type, such as strings, numbers, or tuples. Accessing Values in Dictionary To access dictionary elements, you can use the familiar square brackets along with the key to obtain its value. A simple example is as follows: #!/usr/bin/python dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'} print "dict['Name']: ", dict['Name'] print "dict['Age']: ", dict['Age'] When the above code is executed, it produces the following result: dict['Name']: Zara dict['Age']: 7 If we attempt to access a data item with a key, which is not part of the dictionary, we get an error as follows: #!/usr/bin/python dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'} print "dict['Alice']: ", dict['Alice'] When the above code is executed, it produces the following result: dict['Alice']: Traceback (most recent call last): File "test.py", line 4, in print "dict['Alice']: ", dict['Alice']; KeyError: 'Alice' 20 Python Data Structures Updating Dictionary You can update a dictionary by adding a new entry or a key-value pair, modifying an existing entry, or deleting an existing entry as shown below in the simple example: #!/usr/bin/python dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'} dict['Age'] = 8; # update existing entry dict['School'] = "DPS School"; # Add new entry print "dict['Age']: ", dict['Age'] print "dict['School']: ", dict['School'] When the above code is executed, it produces the following result: dict['Age']: 8 dict['School']: DPS School Delete Dictionary Elements You can either remove individual dictionary elements or clear the entire contents of a dictionary. You can also delete entire dictionary in a single operation. To explicitly remove an entire dictionary, just use the del statement. A simple example is as mentioned below: #!/usr/bin/python dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'} del dict['Name']; # remove entry with key 'Name' dict.clear(); # remove all entries in dict del dict ; # delete entire dictionary print "dict['Age']: ", dict['Age'] print "dict['School']: ", dict['School']  Note that an exception is raised, because after del dict dictionary does not exist anymore. This produces the following result: dict['Age']: Traceback (most recent call last): 21 Python Data Structures File "test.py", line 8, in print "dict['Age']: ", dict['Age']; TypeError: 'type' object is unsubscriptable  Note − del() method is discussed in subsequent section. Properties of Dictionary Keys Dictionary values have no restrictions. They can be any arbitrary Python object, either standard objects or user-defined objects. However, same is not true for the keys. There are two important points to remember about dictionary keys −  More than one entry per key not allowed. Which means, no duplicate key is allowed. When duplicate keys are encountered during assignment, the last assignment wins. For example: #!/usr/bin/python dict = {'Name': 'Zara', 'Age': 7, 'Name': 'Manni'} print "dict['Name']: ", dict['Name'] When the above code is executed, it produces the following result: dict['Name']: Manni Keys must be immutable. Which means you can use strings, numbers or tuples as dictionary keys, but something like ['key'] is not allowed. An example is as follows: #!/usr/bin/python dict = {['Name']: 'Zara', 'Age': 7} print "dict['Name']: ", dict['Name'] When the above code is executed, it produces the following result: Traceback (most recent call last): File "test.py", line 3, in dict = {['Name']: 'Zara', 'Age': 7}; TypeError: list objects are unhashable 22 7. Python Data Structures – 2D Array Python Data Structures Two dimensional array is an array within an array. It is an array of arrays. In this type of array, the position of a data element is referred by two indices instead of one. So, it represents a table with rows and columns of data. In the below example of a two dimensional array, observe that each array element itself is also an array. Consider an example of recording temperatures four times a day, every day. Sometimes, the recording instrument may be faulty and we fail to record data. Such data for four days can be presented as a two dimensional array as below. Day 1 - 11 12 5 2 Day 2 - 15 6 10 Day 3 - 10 8 12 5 Day 4 - 12 15 8 6 The above data can be represented as a two dimensional array as below. T = [[11, 12, 5, 2], [15, 6,10], [10, 8, 12, 5], [12,15,8,6]] Accessing Values The data elements in two dimensional arrays can be accessed using two indices. One index referring to the main or parent array and another index referring to the position of the data element in the inner array. If we mention only one index, then the entire inner array is printed for that index position. The example below illustrates how it works. from array import * T = [[11, 12, 5, 2], [15, 6,10], [10, 8, 12, 5], [12,15,8,6]] print(T) print(T) When the above code is executed, it produces the following result: [11, 12, 5, 2] 10 23 Python Data Structures To print out the entire two dimensional array, we can use python for loop as shown below. We use end of line to print out the values in different rows. from array import * T = [[11, 12, 5, 2], [15, 6,10], [10, 8, 12, 5], [12,15,8,6]] for r in T: for c in r: print(c,end = " ") print() When the above code is executed, it produces the following result: 11 12 5 2 15 6 10 10 8 12 5 12 15 8 6 Inserting Values We can insert new data elements at specific position, by using the insert() method and specifying the index. In an example mentioned below, a new data element is inserted at index position 2. from array import * T = [[11, 12, 5, 2], [15, 6,10], [10, 8, 12, 5], [12,15,8,6]] T.insert(2, [0,5,11,13,6]) for r in T: for c in r: print(c,end = " ") print() When the above code is executed, it produces the following result: 11 12 5 2 15 6 10 0 5 11 13 6 10 8 12 5 12 15 8 6 24 Python Data Structures Updating Values We can update the entire inner array or some specific data elements of the inner array, by reassigning the values using the array index. from array import * T = [[11, 12, 5, 2], [15, 6,10], [10, 8, 12, 5], [12,15,8,6]] T = [11,9] T = 7 for r in T: for c in r: print(c,end = " ") print() When the above code is executed, it produces the following result: 11 12 5 7 15 6 10 11 9 12 15 8 6 Deleting the Values We can delete an entire inner array or some specific data elements of the inner array, by reassigning the values using the del() method with index. But, in case you need to remove specific data elements in one of the inner arrays, then use the update process described above. from array import * T = [[11, 12, 5, 2], [15, 6,10], [10, 8, 12, 5], [12,15,8,6]] del T for r in T: for c in r: print(c,end = " ") print() When the above code is executed, it produces the following result: 11 12 5 2 25 Python Data Structures 15 6 10 10 8 12 5 26 8. Python Data Structures – Matrix Python Data Structures Matrix is a special case of two dimensional array, where, each data element is of strictly same size. So, every matrix is also a two dimensional array but not, vice versa. Matrices are very important data structures for many mathematical and scientific calculations. As we have already discussed, two dimensional array data structure in the previous chapter, we will be focusing on data structure operations specific to matrices in this chapter. We will also use the numpy package for matrix data manipulation. Matrix Example Consider the case of recording temperature for one week measured in the morning, mid- day, evening and mid-night. It can be presented as a 7X5 matrix, using an array and the reshape method available in numpy. from numpy import * a = array([['Mon',18,20,22,17],['Tue',11,18,21,18], ['Wed',15,21,20,19],['Thu',11,20,22,21], ['Fri',18,17,23,22],['Sat',12,22,20,18], ['Sun',13,15,19,16]]) m = reshape(a,(7,5)) print(m) The above data can be represented as a two dimensional array as below: [['Mon' '18' '20' '22' '17'] ['Tue' '11' '18' '21' '18'] ['Wed' '15' '21' '20' '19'] ['Thu' '11' '20' '22' '21'] ['Fri' '18' '17' '23' '22'] ['Sat' '12' '22' '20' '18'] ['Sun' '13' '15' '19' '16']] Accessing Values The data elements in a matrix can be accessed by using the indexes. The access methods are same, as the way data is accessed in two dimensional array. from numpy import * 27 Python Data Structures m = array([['Mon',18,20,22,17],['Tue',11,18,21,18], ['Wed',15,21,20,19],['Thu',11,20,22,21], ['Fri',18,17,23,22],['Sat',12,22,20,18], ['Sun',13,15,19,16]]) # Print data for Wednesday print(m) # Print data for friday evening print(m) When the above code is executed, it produces the following result: ['Wed', 15, 21, 20, 19] 23 Adding a row Use the below mentioned code to add a row in a matrix. from numpy import * m = array([['Mon',18,20,22,17],['Tue',11,18,21,18], ['Wed',15,21,20,19],['Thu',11,20,22,21], ['Fri',18,17,23,22],['Sat',12,22,20,18], ['Sun',13,15,19,16]]) m_r = append(m,[['Avg',12,15,13,11]],0) print(m_r) When the above code is executed, it produces the following result: [['Mon' '18' '20' '22' '17'] ['Tue' '11' '18' '21' '18'] ['Wed' '15' '21' '20' '19'] ['Thu' '11' '20' '22' '21'] ['Fri' '18' '17' '23' '22'] ['Sat' '12' '22' '20' '18'] ['Sun' '13' '15' '19' '16'] ['Avg' '12' '15' '13' '11']] 28 Python Data Structures Adding a column We can add column to a matrix using the insert() method. Here, we have to mention the index, where we want to add the column and an array containing the new values of the columns added. In the below example, we add to a new column at the fifth position from the beginning. from numpy import * m = array([['Mon',18,20,22,17],['Tue',11,18,21,18], ['Wed',15,21,20,19],['Thu',11,20,22,21], ['Fri',18,17,23,22],['Sat',12,22,20,18], ['Sun',13,15,19,16]]) m_c = insert(m,,[,,,,,,],1) print(m_c) When the above code is executed, it produces the following result: [['Mon' '18' '20' '22' '17' '1'] ['Tue' '11' '18' '21' '18' '2'] ['Wed' '15' '21' '20' '19' '3'] ['Thu' '11' '20' '22' '21' '4'] ['Fri' '18' '17' '23' '22' '5'] ['Sat' '12' '22' '20' '18' '6'] ['Sun' '13' '15' '19' '16' '7']] Delete a row We can delete a row from a matrix by using the delete() method. We have to specify the index of the row and also the axis value, which is 0 for a row and 1 for a column. from numpy import * m = array([['Mon',18,20,22,17],['Tue',11,18,21,18], ['Wed',15,21,20,19],['Thu',11,20,22,21], ['Fri',18,17,23,22],['Sat',12,22,20,18], ['Sun',13,15,19,16]]) m = delete(m,,0) print(m) 29 Python Data Structures When the above code is executed, it produces the following result: [['Mon' '18' '20' '22' '17'] ['Tue' '11' '18' '21' '18'] ['Thu' '11' '20' '22' '21'] ['Fri' '18' '17' '23' '22'] ['Sat' '12' '22' '20' '18'] ['Sun' '13' '15' '19' '16']] Delete a column We can delete a column from a matrix using the delete() method. We have to specify the index of the column and also the axis value, which is 0 for a row and 1 for a column. from numpy import * m = array([['Mon',18,20,22,17],['Tue',11,18,21,18], ['Wed',15,21,20,19],['Thu',11,20,22,21], ['Fri',18,17,23,22],['Sat',12,22,20,18], ['Sun',13,15,19,16]]) m = delete(m,s_,1) print(m) When the above code is executed, it produces the following result: [['Mon' '18' '22' '17'] ['Tue' '11' '21' '18'] ['Wed' '15' '20' '19'] ['Thu' '11' '22' '21'] ['Fri' '18' '23' '22'] ['Sat' '12' '20' '18'] ['Sun' '13' '19' '16']] Update a row To update the values in the row of a matrix, we simply re-assign the values at the index of the row. In the below example, all the values for Thursday’s data is marked as zero. The index for this row is 3. from numpy import * m = array([['Mon',18,20,22,17],['Tue',11,18,21,18], 30 Python Data Structures ['Wed',15,21,20,19],['Thu',11,20,22,21], ['Fri',18,17,23,22],['Sat',12,22,20,18], ['Sun',13,15,19,16]]) m = ['Thu',0,0,0,0] print(m) When the above code is executed, it produces the following result: [['Mon' '18' '20' '22' '17'] ['Tue' '11' '18' '21' '18'] ['Wed' '15' '21' '20' '19'] ['Thu' '0' '0' '0' '0'] ['Fri' '18' '17' '23' '22'] ['Sat' '12' '22' '20' '18'] ['Sun' '13' '15' '19' '16']] 31 9. Python Data Structures – Sets Python Data Structures Mathematically, a set is a collection of items not in any particular order. A Python set is similar to this mathematical definition with below additional conditions.  The elements in the set cannot be duplicates.  The elements in the set are immutable (cannot be modified), but the set as a whole is mutable.  There is no index attached to any element in a python set. So they do not support any indexing or slicing operation. Set Operations The sets in python are typically used for mathematical operations like union, intersection, difference and complement etc. We can create a set, access its elements and carry out these mathematical operations as shown below. Creating a set A set is created by using the set() function or placing all the elements within a pair of curly braces. Days=set(["Mon","Tue","Wed","Thu","Fri","Sat","Sun"]) Months={"Jan","Feb","Mar"} Dates={21,22,17} print(Days) print(Months) print(Dates) When the above code is executed, it produces the following result. Please note, how the order of the elements has changed in the result. set(['Wed', 'Sun', 'Fri', 'Tue', 'Mon', 'Thu', 'Sat']) set(['Jan', 'Mar', 'Feb']) set([17, 21, 22]) Accessing Values in a Set We cannot access individual values in a set. We can only access all the elements together as shown above. But, we can also get a list of individual elements, by looping through the set. Days=set(["Mon","Tue","Wed","Thu","Fri","Sat","Sun"]) 32 Python Data Structures for d in Days: print(d) When the above code is executed, it produces the following result: Wed Sun Fri Tue Mon Thu Sat Adding Items to a Set We can add elements to a set by using add() method. Again as discussed, there is no specific index attached to the newly added element. Days=set(["Mon","Tue","Wed","Thu","Fri","Sat"]) Days.add("Sun") print(Days) When the above code is executed, it produces the following result: set(['Wed', 'Sun', 'Fri', 'Tue', 'Mon', 'Thu', 'Sat']) Removing Item from a Set We can remove elements from a set by using discard() method. Again as discussed, there is no specific index attached to the newly added element. Days=set(["Mon","Tue","Wed","Thu","Fri","Sat"]) Days.discard("Sun") print(Days) When the above code is executed, it produces the following result. set(['Wed', 'Fri', 'Tue', 'Mon', 'Thu', 'Sat']) 33 Python Data Structures Union of Sets The union operation on two sets produces a new set containing all the distinct elements from both the sets. In the below example, the element “Wed” is present in both the sets. DaysA = set(["Mon","Tue","Wed"]) DaysB = set(["Wed","Thu","Fri","Sat","Sun"]) AllDays = DaysA|DaysB print(AllDays) When the above code is executed, it produces the following result. Please note the result has only one “wed”. set(['Wed', 'Fri', 'Tue', 'Mon', 'Thu', 'Sat']) Intersection of Sets The intersection operation on two sets produces a new set containing only the common elements from both the sets. In the below example, the element “Wed” is present in both the sets. DaysA = set(["Mon","Tue","Wed"]) DaysB = set(["Wed","Thu","Fri","Sat","Sun"]) AllDays = DaysA & DaysB print(AllDays) When the above code is executed, it produces the following result. Please note the result has only one “wed”. set(['Wed']) Difference of Sets The difference operation on two sets produces a new set containing only the elements from the first set and none from the second set. In the below example, the element “Wed” is present in both the sets so it will not be found in the result set. DaysA = set(["Mon","Tue","Wed"]) DaysB = set(["Wed","Thu","Fri","Sat","Sun"]) AllDays = DaysA - DaysB print(AllDays) When the above code is executed, it produces the following result. Please note the result has only one “wed”. set(['Mon', 'Tue']) 34 Python Data Structures Compare Sets We can check, if a given set is a subset or superset of another set. The result is True or False depending on the elements present in the sets. DaysA = set(["Mon","Tue","Wed"]) DaysB = set(["Mon","Tue","Wed","Thu","Fri","Sat","Sun"]) SubsetRes = DaysA = DaysA print(SubsetRes) print(SupersetRes) When the above code is executed, it produces the following result: True True 35 10. Python Data Structures – Maps Python Data Structures Python Maps also called ChainMap is a type of data structure to manage multiple dictionaries together as one unit. The combined dictionary contains the key and value pairs in a specific sequence eliminating any duplicate keys. The best use of ChainMap is to search through multiple dictionaries at a time and get the proper key-value pair mapping. We also see that these ChainMaps behave as stack data structure. Creating a ChainMap We create two dictionaries and club them using the ChainMap method from the collections library. Then, we print the keys and values of the result of the combination of the dictionaries. If there are duplicate keys, then only the value from the first key is preserved. import collections dict1 = {'day1': 'Mon', 'day2': 'Tue'} dict2 = {'day3': 'Wed', 'day1': 'Thu'} res = collections.ChainMap(dict1, dict2) # Creating a single dictionary print(res.maps,'\n') print('Keys = {}'.format(list(res.keys()))) print('Values = {}'.format(list(res.values()))) print() # Print all the elements from the result print('elements:') for key, val in res.items(): print('{} = {}'.format(key, val)) print() # Find a specific value in the result print('day3 in res: {}'.format(('day1' in res))) print('day4 in res: {}'.format(('day4' in res))) When the above code is executed, it produces the following result: 36 Python Data Structures [{'day1': 'Mon', 'day2': 'Tue'}, {'day1': 'Thu', 'day3': 'Wed'}] Keys = ['day1', 'day3', 'day2'] Values = ['Mon', 'Wed', 'Tue'] elements: day1 = Mon day3 = Wed day2 = Tue day3 in res: True day4 in res: False Map Reordering If we change the order of the dictionaries while clubbing them in the above example, we see that, the position of the elements get interchanged as if, they are in a continuous chain. This again shows the behaviour of Maps as stacks. import collections dict1 = {'day1': 'Mon', 'day2': 'Tue'} dict2 = {'day3': 'Wed', 'day4': 'Thu'} res1 = collections.ChainMap(dict1, dict2) print(res1.maps,'\n') res2 = collections.ChainMap(dict2, dict1) print(res2.maps,'\n') When the above code is executed, it produces the following result: [{'day1': 'Mon', 'day2': 'Tue'}, {'day3': 'Wed', 'day4': 'Thu'}] [{'day3': 'Wed', 'day4': 'Thu'}, {'day1': 'Mon', 'day2': 'Tue'}] 37 Python Data Structures Updating Map When the element of the dictionary is updated, the result is instantly updated in the result of the ChainMap. In the below example, we see that the new updated value reflects in the result without explicitly applying the ChainMap method again. import collections dict1 = {'day1': 'Mon', 'day2': 'Tue'} dict2 = {'day3': 'Wed', 'day4': 'Thu'} res = collections.ChainMap(dict1, dict2) print(res.maps,'\n') dict2['day4'] = 'Fri' print(res.maps,'\n') When the above code is executed, it produces the following result: [{'day1': 'Mon', 'day2': 'Tue'}, {'day3': 'Wed', 'day4': 'Thu'}] [{'day1': 'Mon', 'day2': 'Tue'}, {'day3': 'Wed', 'day4': 'Fri'}] 38 11. Python Data Structures – Linked Lists Python Data Structures A linked list is a sequence of data elements, which are connected together via links. Each data element contains a connection to another data element in form of a pointer. Python does not have linked lists in its standard library. We implement the concept of linked lists using the concept of nodes as discussed in the previous chapter. We have already seen, how we create a node class and how to traverse the elements of a node. In this chapter, we are going to study the types of linked lists known as singly linked lists. In this type of data structure, there is only one link between any two data elements. We create such a list and create additional methods to insert, update and remove elements from the list. Creation of Linked list A linked list is created by using the node class we studied in the last chapter. We create a Node object and create another class to use this node object. We pass the appropriate values through the node object, to point them to the next data elements. The below program, creates the linked list with three data elements. In the next section, we will see how to traverse the linked list. 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 = e3 39 Python Data Structures Traversing a Linked List Singly linked lists can be traversed in only forward direction starting form the first data element. We simply print the value of the next data element by assigning the pointer of the next node to the current data element. class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = None class SLinkedList: def __init__(self): self.headval = None def listprint(self): printval = self.headval while printval is not None: print (printval.dataval) printval = printval.nextval list = SLinkedList() list.headval = Node("Mon") e2 = Node("Tue") e3 = Node("Wed") # Link first Node to second node list.headval.nextval = e2 # Link second Node to third node e2.nextval = e3 list.listprint() When the above code is executed, it produces the following result: Mon Tue Wed 40 Python Data Structures Insertion in a Linked List Inserting element in the linked list involves, reassigning the pointers from the existing nodes to the newly inserted node. Depending on whether the new data element is getting inserted at the beginning or at the middle or at the end of the linked list, we have the below scenarios. Inserting at the Beginning This involves pointing the next pointer of the new data node to the current head of the linked list. So, the current head of the linked list becomes the second data element and the new node becomes the head of the linked list. class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = None class SLinkedList: def __init__(self): self.headval = None # Print the linked list def listprint(self): printval = self.headval while printval is not None: print (printval.dataval) printval = printval.nextval def AtBegining(self,newdata): NewNode = Node(newdata) # Update the new nodes next val to existing node NewNode.nextval = self.headval self.headval = NewNode list = SLinkedList() list.headval = Node("Mon") e2 = Node("Tue") e3 = Node("Wed") 41 Python Data Structures list.headval.nextval = e2 e2.nextval = e3 list.AtBegining("Sun") list.listprint() When the above code is executed, it produces the following result: Sun Mon Tue Wed Inserting at the End This involves pointing the next pointer of the the current last node of the linked list to the new data node. So the current last node of the linked list becomes the second last data node and the new node becomes the last node of the linked list. class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = None class SLinkedList: def __init__(self): self.headval = None # Function to add newnode def AtEnd(self, newdata): NewNode = Node(newdata) if self.headval is None: self.headval = NewNode return laste = self.headval while(laste.nextval): laste = laste.nextval laste.nextval=NewNode 42 Python Data Structures # Print the linked list def listprint(self): printval = self.headval while printval is not None: print (printval.dataval) printval = printval.nextval list = SLinkedList() list.headval = Node("Mon") e2 = Node("Tue") e3 = Node("Wed") list.headval.nextval = e2 e2.nextval = e3 list.AtEnd("Thu") list.listprint() When the above code is executed, it produces the following result: Mon Tue Wed Thu Inserting in between two Data Nodes This involves changing the pointer of a specific node to point to the new node. That is possible by passing in both the new node and the existing node after which, the new node will be inserted. So, we define an additional class which will change the next pointer of the new node to the next pointer of middle node. Then, assign the new node to next pointer of the middle node. class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = None class SLinkedList: 43 Python Data Structures def __init__(self): self.headval = None # Function to add node def Inbetween(self,middle_node,newdata): if middle_node is None: print("The mentioned node is absent") return NewNode = Node(newdata) NewNode.nextval = middle_node.nextval middle_node.nextval = NewNode # Print the linked list def listprint(self): printval = self.headval while printval is not None: print (printval.dataval) printval = printval.nextval list = SLinkedList() list.headval = Node("Mon") e2 = Node("Tue") e3 = Node("Thu") list.headval.nextval = e2 e2.nextval = e3 list.Inbetween(list.headval.nextval,"Fri") list.listprint() When the above code is executed, it produces the following result: Mon Tue Fri 44 Python Data Structures Thu Removing an Item We can remove an existing node using the key for that node. In the below program, we locate the previous node of the node which is to be deleted. Then, point the next pointer of this node to the next node of the node to be deleted. class Node: def __init__(self, data=None): self.data = data self.next = None class SLinkedList: def __init__(self): self.head = None def Atbegining(self, data_in): NewNode = Node(data_in) NewNode.next = self.head self.head = NewNode # Function to remove node def RemoveNode(self, Removekey): HeadVal = self.head if (HeadVal is not None): if (HeadVal.data == Removekey): self.head = HeadVal.next HeadVal = None return while (HeadVal is not None): if HeadVal.data == Removekey: break prev = HeadVal HeadVal = HeadVal.next 45 Python Data Structures if (HeadVal == None): return prev.next = HeadVal.next HeadVal = None def LListprint(self): printval = self.head while (printval): print(printval.data), printval = printval.next llist = SLinkedList() llist.Atbegining("Mon") llist.Atbegining("Tue") llist.Atbegining("Wed") llist.Atbegining("Thu") llist.RemoveNode("Tue") llist.LListprint() When the above code is executed, it produces the following result: Thu Wed Mon 46 12. Python Data Structures – Stack Python Data Structures In the English dictionary, the word stack means arranging objects one over another. It is the same way; memory is allocated in this data structure. It stores the data elements in a similar fashion as a bunch of plates are stored one above another in the kitchen. So, stack data structure allows operations at one end, which can be called top of the stack. We can add elements or remove elements only form this end of the stack. In a stack the element inserted last in sequence, will come out first as we can remove only from the top of the stack. Such feature is known as Last in First Out(LIFO) feature. The operations of adding and removing the elements is known as PUSH and POP. In the following program, we implement it as add and remove functions. We declare an empty list and use the append() and pop() methods, to add and remove the data elements. PUSH into a Stack Let us understand, how to use PUSH in Stack. Refer the program mentioned program below: class Stack: def __init__(self): self.stack = [] def add(self, dataval): # Use list append method to add element if dataval not in self.stack: self.stack.append(dataval) return True else: return False # Use peek to look at the top of the stack def peek(self): return self.stack[-1] AStack = Stack() AStack.add("Mon") AStack.add("Tue") AStack.peek() 47 Python Data Structures print(AStack.peek()) AStack.add("Wed") AStack.add("Thu") print(AStack.peek()) When the above code is executed, it produces the following result: Tue Thu POP from a Stack As we know, we can remove only the top most data element from the stack, we implement a python program which does that. The remove function in the following program returns the top most element. We check the top element by calculating the size of the stack first and then, use the in-built pop() method to find out the top most element. class Stack: def __init__(self): self.stack = [] def add(self, dataval): # Use list append method to add element if dataval not in self.stack: self.stack.append(dataval) return True else: return False # Use list pop method to remove element def remove(self): if len(self.stack) 0: return self.queue.pop() return ("No elements in Queue!") TheQueue = Queue() TheQueue.addtoq("Mon") TheQueue.addtoq("Tue") TheQueue.addtoq("Wed") print(TheQueue.removefromq()) print(TheQueue.removefromq()) When the above code is executed, it produces the following result: Mon Tue 51 14. Python Data Structures – Dequeue Python Data Structures A double-ended queue, or deque, supports adding and removing elements from either end. The more commonly used stacks and queues are degenerate forms of deques, where the inputs and outputs are restricted to a single end. import collections DoubleEnded = collections.deque(["Mon","Tue","Wed"]) DoubleEnded.append("Thu") print ("Appended at right - ") print (DoubleEnded) DoubleEnded.appendleft("Sun") print ("Appended at right at left is - ") print (DoubleEnded) DoubleEnded.pop() print ("Deleting from right - ") print (DoubleEnded) DoubleEnded.popleft() print ("Deleting from left - ") print (DoubleEnded) Appended at right - deque(['Mon', 'Tue', 'Wed', 'Thu']) Appended at right at left is - deque(['Sun', 'Mon', 'Tue', 'Wed', 'Thu']) Deleting from right - deque(['Sun', 'Mon', 'Tue', 'Wed']) 52 Python Data Structures Deleting from left - deque(['Mon', 'Tue', 'Wed']) 53 15. Python Data Structutres – Advanced Linked Python Data Structures List We have already seen Linked List in earlier chapter, in which it is possible only to travel forward. In this chapter we see another type of linked list in which it is possible to travel both forward and backward. Such a linked list is called Doubly Linked List. Following is the features of doubly linked list.  Doubly Linked List contains a link element called first and last.  Each link carries a data field(s) and two link fields called next and prev.  Each link is linked with its next link using its next link.  Each link is linked with its previous link using its previous link.  The last link carries a link as null to mark the end of the list. Creating Doubly linked list We create a Doubly Linked list by using the Node class. Now, we use the same approach as used in the Singly Linked List but, the head and next pointers will be used for proper assignation to create two links in each of the nodes in addition to the data present in the node. class Node: def __init__(self, data): self.data = data self.next = None self.prev = None class doubly_linked_list: def __init__(self): self.head = None # Adding data elements def push(self, NewVal): NewNode = Node(NewVal) NewNode.next = self.head if self.head is not None: self.head.prev = NewNode self.head = NewNode 54 Python Data Structures # Print the Doubly Linked list def listprint(self, node): while (node is not None): print(node.data), last = node node = node.next dllist = doubly_linked_list() dllist.push(12) dllist.push(8) dllist.push(62) dllist.listprint(dllist.head) When the above code is executed, it produces the following result: 62 8 12 Inserting into Doubly Linked List Here, we are going to see how to insert a node to the Doubly Link List using the following program. The program uses a method named insert, which inserts the new node at the third position from the head of the doubly linked list. # Create the Node class class Node: def __init__(self, data): self.data = data self.next = None self.prev = None # Create the doubly linked list class doubly_linked_list: def __init__(self): self.head = None # Define the push method to add elements def push(self, NewVal): 55 Python Data Structures NewNode = Node(NewVal) NewNode.next = self.head if self.head is not None: self.head.prev = NewNode self.head = NewNode # Define the insert method to insert the element def insert(self, prev_node, NewVal): if prev_node is None: return NewNode = Node(NewVal) NewNode.next = prev_node.next prev_node.next = NewNode NewNode.prev = prev_node if NewNode.next is not None: NewNode.next.prev = NewNode # Define the method to print the linked list def listprint(self, node): while (node is not None): print(node.data), last = node node = node.next dllist = doubly_linked_list() dllist.push(12) dllist.push(8) dllist.push(62) dllist.insert(dllist.head.next, 13) dllist.listprint(dllist.head) When the above code is executed, it produces the following result: 62 8 13 12 Appending to a Doubly linked list Appending to a doubly linked list will add the element at the end. 56 Python Data Structures # Create the node class class Node: def __init__(self, data): self.data = data self.next = None self.prev = None # Create the doubly linked list class class doubly_linked_list: def __init__(self): self.head = None # Define the push method to add elements at the begining def push(self, NewVal): NewNode = Node(NewVal) NewNode.next = self.head if self.head is not None: self.head.prev = NewNode self.head = NewNode # Define the append method to add elements at the end def append(self, NewVal): NewNode = Node(NewVal) NewNode.next = None if self.head is None: NewNode.prev = None self.head = NewNode return last = self.head while (last.next is not None): last = last.next last.next = NewNode NewNode.prev = last return # Define the method to print 57 Python Data Structures def listprint(self, node): while (node is not None): print(node.data), last = node node = node.next dllist = doubly_linked_list() dllist.push(12) dllist.append(9) dllist.push(8) dllist.push(62) dllist.append(45) dllist.listprint(dllist.head) When the above code is executed, it produces the following result: 62 8 12 9 45 Please note the position of the elements 9 and 45 for the append operation. 58 16. Python Data Structures – Hash Table Python Data Structures Hash tables are a type of data structure, in which the address or the index value of the data element is generated from a hash function. That makes accessing the data faster, as the index value behaves as a key for the data value. In other words, Hash table stores key-value pairs but the key is generated through a hashing function. So, the search and insertion function of a data element becomes much faster as the key values themselves become the index of the array which stores the data. In Python, the Dictionary data types represent the implementation of hash tables. The Keys in the dictionary satisfy the following requirements.  The keys of the dictionary are hashable, i.e. they are generated by hashing function, which generates unique result for each unique value supplied to the hash function.  The order of data elements in a dictionary is not fixed. So, we see the implementation of hash table by using the dictionary data types as below. Accessing Values in Dictionary To access dictionary elements, you can use the familiar square brackets along with the key to obtain its value. # Declare a dictionary dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'} # Accessing the dictionary with its key print "dict['Name']: ", dict['Name'] print "dict['Age']: ", dict['Age'] When the above code is executed, it produces the following result: dict['Name']: Zara dict['Age']: 7 Updating Dictionary You can update a dictionary by adding a new entry or a key-value pair, modifying an existing entry, or deleting an existing entry as shown below in the simple example: # Declare a dictionary dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'} 59 Python Data Structures dict['Age'] = 8; # update existing entry dict['School'] = "DPS School"; # Add new entry print "dict['Age']: ", dict['Age'] print "dict['School']: ", dict['School'] When the above code is executed, it produces the following result: dict['Age']: 8 dict['School']: DPS School Delete Dictionary Elements You can either remove individual dictionary elements or clear the entire contents of a dictionary. You can also delete entire dictionary in a single operation. To explicitly remove an entire dictionary, just use the del statement. dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'} del dict['Name']; # remove entry with key 'Name' dict.clear(); # remove all entries in dict del dict ; # delete entire dictionary print "dict['Age']: ", dict['Age'] print "dict['School']: ", dict['School'] This produces the following result. Note, that an exception is raised because after del dict dictionary does not exist anymore. dict['Age']: Traceback (most recent call last): File "test.py", line 8, in print "dict['Age']: ", dict['Age']; TypeError: 'type' object is unsubscriptable 60 17. Python Data Structures – Binary Tree Python Data Structures Tree represents the nodes connected by edges. It is a non-linear data structure. It has the following properties:  One node is marked as Root node.  Every node other than the root is associated with one parent node.  Each node can have an arbitrary number of chid node. We create a tree data structure in python by using the concept of node discussed earlier. We designate one node as root node and then add more nodes as child nodes. Below is program to create the root node. Create Root We just create a Node class and add assign a value to the node. This becomes tree with only a root node. class Node: def __init__(self, data): self.left = None self.right = None self.data = data def PrintTree(self): print(self.data) root = Node(10) root.PrintTree() When the above code is executed, it produces the following result: 10

Python Data Structures Tutorial PDF

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue