DATA STRUCTURES THROUGH PYTHON Notes PDF

Data Structures Using Python (R20A0503)LECTURE NOTES B.TECHIIYEAR–I-SEM (R20)(2021-2022) MALLAREDDYCOLLEGEOFENGINEERING&TECHNOLOGY (AutonomousInstitution– UGC,Govt.ofIndia) Recogn...

Data Structures Using Python (R20A0503)LECTURE NOTES B.TECHIIYEAR–I-SEM (R20)(2021-2022) MALLAREDDYCOLLEGEOFENGINEERING&TECHNOLOGY (AutonomousInstitution– UGC,Govt.ofIndia) Recognizedunder2(f)and12(B)ofUGCACT 1956 (AffiliatedtoJNTUH,Hyderabad,ApprovedbyAICTE-AccreditedbyNBA&NAAC –‘A’Grade-ISO9001:2015Certified) Maisammaguda,Dhulapally(PostVia.Hakimpet),Secunderabad–500100,TelanganaState,India 1  SYLLABUS MALLAREDDYCOLLEGEOFENGINEERING ANDTECHNOLOGY IIYearB.Tech CSE-I SEM L T/P/DC 3 -/ -/ -3 (R20A0503)DATA STRUCTURES USING PYTHON COURSE OBJECTIVES: This course will enable students to 1. Implement Object Oriented Programming concepts in Python. 2. Understand Lists, Dictionaries and Regular expressions in Python. 3. Understanding how searching and sorting is performed in Python. 4. Understanding how linear and non-linear data structures works. 5. To learn the fundamentals of writing Python scripts. UNIT – I Oops Concepts- class, object, constructors, types of variables, types of methods. Inheritance: single, multiple, multi-level, hierarchical, hybrid, Polymorphism: with functions and objects, with class methods, with inheritance,Abstraction: abstract classes. UNIT – II Data Structures – Definition,Linear Data Structures,Non-Linear Data Structures Python Specific Data Structures: List,Tuples, Set, Dictionaries, Comprehensions and its Types,Strings,slicing. UNIT -III Arrays - Overview, Types of Arrays, Operations on Arrays, Arrays vs List. Searching -Linear Search and Binary Search. Sorting - Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort. UNIT -IV Linked Lists – Implementation ofSingly Linked Lists, Doubly Linked Lists, Circular Linked Lists. Stacks - Overview of Stack, Implementation of Stack (List & Linked list), Applications of Stack Queues:Overview of Queue, Implementation of Queue(List & Linked list), Applications of Queues, Priority Queues. UNIT -V Graphs -Introduction, Directed vs Undirected Graphs, Weighted vs Unweighted Graphs, Representations, Breadth First Search, Depth First Search. Trees - Overview of Trees, Tree Terminology, Binary Trees: Introduction, Implementation, Applications. Tree Traversals, Binary Search Trees: Introduction, Implementation, AVL Trees: Introduction, Rotations, Implementation. TEXTBOOKS: 1. Data structures and algorithms in python by Michael T. Goodrich 2. Data Structures and Algorithmic Thinking with Python by NarasimhaKarumanchi 2 REFERENCE BOOKS: 1. Hands-On Data Structures and Algorithms with Python: Write complex and powerful code using the latest features of Python 3.7, 2nd Edition by Dr. Basant Agarwal, Benjamin Baka. 2. Data Structures and Algorithms with Python by Kent D. Lee and Steve Hubbard. 3. Problem Solving with Algorithms and Data Structures Using Python by Bradley N Miller and David L. Ranum. 4. Core Python Programming -Second Edition,R. Nageswara Rao, Dreamtech Press COURSE OUTCOMES: The students should be able to: 1. Examine Python syntax and semantics and apply Python flow control and functions. 2. Create, run and manipulate Python Programs using core data structures like Lists, 3. Apply Dictionaries and use Regular Expressions. 4. Interpret the concepts of Object-Oriented Programming as used in Python. 5. Master object-oriented programming to create an entire python project using objects and classes 3  INDEX UNIT TOPIC PAGENO Class ,Objects, Constructors 6-9 Types of Variables 10-12 Types of Methods 12-15 Inheritance & Types 16-21 Polymorphism 22-26 I Abstract Classes 27-28 Introduction to Data Structures, Types 29-31 Python Specific Data Structures 31-43 II Sequences 44-49 Comprehensions-List,Tuples,Set,Dictonary 50-52 String Slicing 53-55 Arrays&operations on Arrays 56-61 Searching: Linear Search, Binary search 62-68 Sorting:Bubble,Selction,Insertion,Merge,Quick 68-77 Sort Techniques III Linked List: Single ,Double, Circular Linked List 78-85 IV Stacks:Operations,Implementation using List 86-92 ,Linked List i Queues:Operations,Implementation using List 93-105 ,Linked List Priority Queues 106-111 4  Introduction to Graphs, Types of Graphs 112-117 Breadth First Search 117-119 Depth First Search 120-122 Introduction to Trees, Types of Trees 123-135 V Binary Search Tree:Operations,Implementation 144-151 AVL Tree : Operations, Implementation 152-159 5  UNIT – I Oops Concepts- class, object, constructors, types of variables, types of methods. Inheritance: single, multiple, multi-level, hierarchical, hybrid, Polymorphism: with functions and objects, with class methods, with inheritance,Abstraction: abstract classes. OOPs in Python OOPs in Python is a programming approach that focuses on using objects and classes as same as other general programming languages. The objects can be any real-world entities. Python allows developers to develop applications using the OOPs approach with the major focus on code reusability. Class A class is a blueprint for the object. We can think of class as a sketch of a parrot with labels. It contains all the details about the name, colors, size etc. Based on these descriptions, we can study about the parrot. Here, a parrot is an object. The example for class of parrot can be : class Parrot: pass Here, we use the class keyword to define an empty class Parrot. From class, we construct instances. An instance is a specific object created from a particular class. Object An object (instance) is an instantiation of a class. When class is defined, only the description for the object is defined. Therefore, no memory or storage is allocated. The example for object of parrot class can be: obj = Parrot() Here, obj is an object of class Parrot. Suppose we have details of parrots. Now, we are going to show how to build the class and objects of parrots. 6 Example: class Parrot: # class attribute species = "bird" # instance attribute def __init__(self, name, age): self.name = name self.age = age # instantiate the Parrot class blu = Parrot("Blu", 10) woo = Parrot("Woo", 15) # access the class attributes print("Blu is a {}".format(blu.__class__.species)) print("Woo is also a {}".format(woo.__class__.species)) # access the instance attributes print("{} is {} years old".format( blu.name, blu.age)) print("{} is {} years old".format( woo.name, woo.age)) Output Blu is a bird Woo is also a bird Blu is 10 years old Woo is 15 years old In the above program, we created a class with the name Parrot. Then, we define attributes. The attributes are a characteristic of an object. These attributes are defined inside the __init__ method of the class. It is the initializer method that is first run as soon as the object is created. Then, we create instances of the Parrot class. Here, blu and woo are references (value) to our new objects. We can access the class attribute using __class__.species. Class attributes are the same for all instances of a class. Similarly, we access the instance attributes using blu.name and blu.age. However, instance attributes are different for every instance of a class. 7 constructor The constructor is a method that is called when an object is created. This method is defined in the class and can be used to initialize basic variables. If you create four objects, the class constructor is called four times. Every class has a constructor, but its not required to explicitly define it. Example: Each time an object is created a method is called. That methods is named the constructor. The constructor is created with the function init. As parameter we write the self keyword, which refers to itself (the object). The process visually is: Inside the constructor we initialize two variables: legs and arms. Sometimes variables are named properties in the context of object oriented programming. We create one object (bob) and just by creating it, its variables are initialized. classHuman: def__init__(self): self.legs = 2 self.arms = 2 bob = Human() print(bob.legs) The newly created object now has the variables set, without you having to define them manually. You could create tens or hundreds of objects without having to set the values each time. python __init__ The function init(self) builds your object. Its not just variables you can set here, you can call class methods too. Everything you need to initialize the object(s). Lets say you have a class Plane, which upon creation should start flying. There are many steps involved in taking off: accelerating, changing flaps, closing the wheels and so on. 8 The default actions can be defined in methods. These methods can be called in the constructor. classPlane: def__init__(self): self.wings = 2 # fly self.drive() self.flaps() self.wheels() defdrive(self): print('Accelerating') defflaps(self): print('Changing flaps') defwheels(self): print('Closing wheels') ba = Plane() To summarize: A constructor is called if you create an object. In the constructor you can set variables and call methods. Default value The constructor of a class is unique: initiating objects from different classes will call different constructors. Default values of newly created objects can be set in the constructor. The example belwo shows two classes with constructors. Then two objects are created but different constructors are called. classBug: def__init__(self): self.wings = 4 classHuman: def__init__(self): self.legs = 2 self.arms = 2 bob = Human() tom = Bug() print(tom.wings) print(bob.arms) 9  But creating multiple objects from one class, will call the same constructor. Python Variable Types: Local & Global There are two types of variables in Python, Global variable and Local variable. When you want to use the same variable for rest of your program or module you declare it as a global variable, while if you want to use the variable in a specific function or method, you use a local variable while Python variable declaration. Let's understand this Python variable types with the difference between local and global variables in the below program. 1. Let us define variable in Python where the variable "f" is global in scope and is assigned value 101 which is printed in output 2. Variable f is again declared in function and assumes local scope. It is assigned value "I am learning Python." which is printed out as an output. This Python declare variable is different from the global variable "f" defined earlier 3. Once the function call is over, the local variable f is destroyed. At line 12, when we again, print the value of "f" is it displays the value of global variable f=101 Python 2 Example # Declare a variable and initialize it f = 101 print f # Global vs. local variables in functions def someFunction(): # global f f = 'I am learning Python' print f 10 someFunction() print f Python 3 Example # Declare a variable and initialize it f = 101 print(f) # Global vs. local variables in functions def someFunction(): # global f f = 'I am learning Python' print(f) someFunction() print(f) While Python variable declaration using the keyword global, you can reference the global variable inside a function. 1. Variable "f" is global in scope and is assigned value 101 which is printed in output 2. Variable f is declared using the keyword global. This is NOT a local variable, but the same global variable declared earlier. Hence when we print its value, the output is 101 3. We changed the value of "f" inside the function. Once the function call is over, the changed value of the variable "f" persists. At line 12, when we again, print the value of "f" is it displays the value "changing global variable" Python 2 Example f = 101; print f # Global vs.local variables in functions def someFunction(): 11  global f print f f = "changing global variable" someFunction() print f Python 3 Example f = 101; print(f) # Global vs.local variables in functions def someFunction(): global f print(f) f = "changing global variable" someFunction() print(f) Types of methods: Generally, there are three types of methods in Python: 1. Instance Methods. 2. Class Methods 3. Static Methods Before moving on with the topic, we have to know some key concepts. Class Variable: A class variable is nothing but a variable that is defined outside the constructor. A class variable is also called as a static variable. Accessor(Getters): If you want to fetch the value from an instance variable we call them accessors. Mutator(Setters): If you want to modify the value we call them mutators. 1. Instance Method This is a very basic and easy method that we use regularly when we create classes in python. If we want to print an instance variable or instance method we must create an object of that required class. If we are using self as a function parameter or in front of a variable, that is nothing but the calling instance itself. As we are working with instance variables we use self keyword. Note: Instance variables are used with instance methods. 12 Look at the code below # Instance Method Example in Python classStudent: def__init__(self, a, b): self.a = a self.b = b defavg(self): return(self.a + self.b)/2 s1 = Student(10,20) print( s1.avg()) Copy Output: 15.0 In the above program, a and b are instance variables and these get initialized when we create an object for the Student class. If we want to call avg() function which is an instance method, we must create an object for the class. If we clearly look at the program, the self keyword is used so that we can easily say that those are instance variables and methods. 2. Class Method classsmethod() function returns a class method as output for the given function. Here is the syntax for it: classmethod(function) The classmethod() method takes only a function as an input parameter and converts that into a class method. 13 There are two ways to create class methods in python: 1. Using classmethod(function) 2. Using @classmethod annotation A class method can be called either using the class (such as C.f()) or using an instance (such as C().f()). The instance is ignored except for its class. If a class method is called from a derived class, the derived class object is passed as the implied first argument. As we are working with ClassMethod we use the cls keyword. Class variables are used with class methods. Look at the code below. # Class Method Implementation in python classStudent: name ='Student' def__init__(self, a, b): self.a = a self.b = b @classmethod definfo(cls): return cls.name print(Student.info()) Copy Output: Student In the above example, name is a class variable. If we want to create a class method we must use @classmethod decorator and cls as a parameter for that function. 14  3. Static Method A static method can be called without an object for that class, using the class name directly. If you want to do something extra with a class we use static methods. For example, If you want to print factorial of a number then we don't need to use class variables or instance variables to print the factorial of a number. We just simply pass a number to the static method that we have created and it returns the factorial. Look at the below code # Static Method Implementation in python classStudent: name ='Student' def__init__(self, a, b): self.a = a self.b = b @staticmethod definfo(): return"This is a student class" print(Student.info()) Copy Output This a student class 15 Types of inheritances: The inheritance is a very useful and powerful concept of object-oriented programming. Using the inheritance concept, we can use the existing features of one class in another class. The inheritance is the process of acquiring the properties of one class to another class. In inheritance, we use the terms like parent class, child class, base class, derived class, superclass, and subclass. The Parent class is the class which provides features to another class. The parent class is also known as Base class or Superclass. The Child class is the class which receives features from another class. The child class is also known as the Derived Class or Subclass. In the inheritance, the child class acquires the features from its parent class. But the parent class never acquires the features from its child class. There are five types of inheritances, and they are as follows. Simple Inheritance (or) Single Inheritance Multiple Inheritance Multi-Level Inheritance Hierarchical Inheritance Hybrid Inheritance The following picture illustrates how various inheritances are implemented. 16  Creating a Child Class In Python, we use the following general structure to create a child class from a parent class. Syntax classChildClassName(ParentClassName): ChildClass implementation.. Let's look at individual inheritance type with an example. Simple Inheritance (or) Single Inheritance In this type of inheritance, one child class derives from one parent class. Look at the following example code. Example classParentClass: deffeature_1(self): print('feature_1 from ParentClass is running...') deffeature_2(self): print('feature_2 from ParentClass is running...') classChildClass(ParentClass): deffeature_3(self): print('feature_3 from ChildClass is running...') obj = ChildClass() obj.feature_1() obj.feature_2() 17 obj.feature_3() When we run the above example code, it produces the following output. Multiple Inheritance In this type of inheritance, one child class derives from two or more parent classes. Look at the following example code. Example classParentClass_1: deffeature_1(self): print('feature_1 from ParentClass_1 is running...') classParentClass_2: deffeature_2(self): print('feature_2 from ParentClass_2 is running...') 18 classChildClass(ParentClass_1, ParentClass_2): deffeature_3(self): print('feature_3 from ChildClass is running...') obj = ChildClass() obj.feature_1() obj.feature_2() obj.feature_3() When we run the above example code, it produces the following output. Multi-Level Inheritance In this type of inheritance, the child class derives from a class which already derived from another class. Look at the following example code. Example classParentClass: 19 deffeature_1(self): print('feature_1 from ParentClass is running...') classChildClass_1(ParentClass): deffeature_2(self): print('feature_2 from ChildClass_1 is running...') classChildClass_2(ChildClass_1): deffeature_3(self): print('feature_3 from ChildClass_2 is running...') obj = ChildClass_2() obj.feature_1() obj.feature_2() obj.feature_3() When we run the above example code, it produces the following output. 20  Hierarchical Inheritance In this type of inheritance, two or more child classes derive from one parent class. Look at the following example code. Example classParentClass_1: deffeature_1(self): print('feature_1 from ParentClass_1 is running...') classParentClass_2: deffeature_2(self): print('feature_2 from ParentClass_2 is running...') classChildClass(ParentClass_1, ParentClass_2): deffeature_3(self): print('feature_3 from ChildClass is running...') obj = ChildClass() obj.feature_1() obj.feature_2() obj.feature_3() When we run the above example code, it produces the following output. 21 Hybrid Inheritance The hybrid inheritance is the combination of more than one type of inheritance. We may use any combination as a single with multiple inheritances, multi-level with multiple inheritances, etc., Polymorphism: Polymorphism is a concept of object oriented programming, which means multiple forms or more than one form. Polymorphism enables using a single interface with input of different datatypes, different class or may be for different number of inputs. In python as everything is an object hence by default a function can take anything as an argument but the execution of the function might fail as every function has some logic that it follows. For example, len("hello")# returns 5 as result len([1,2,3,4,45,345,23,42])# returns 8 as result In this case the function len is polymorphic as it is taking string as input in the first case and is taking list as input in the second case. 22 In python, polymorphism is a way of making a function accept objects of different classes if they behave similarly. Method overriding is a type of polymorphism in which a child class which is extending the parent class can provide different definition to any function defined in the parent class as per its own requirements. Method Overloading Method overriding or function overloading is a type of polymorphism in which we can define a number of methods with the same name but with a different number of parameters as well as parameters can be of different types. These methods can perform a similar or different function. Python doesn't support method overloading on the basis of different number of parameters in functions. Defining Polymorphic Classes Imagine a situation in which we have a different class for shapes like Square, Triangle etc which serves as a resource to calculate the area of that shape. Each shape has a different number of dimensions which are used to calculate the area of the respective shape. Now one approach is to define different functions with different names to calculate the area of the given shapes. The program depicting this approach is shown below: classSquare: side =5 defcalculate_area_sq(self): return self.side * self.side classTriangle: base =5 height =4 defcalculate_area_tri(self): return0.5* self.base * self.height 23 sq = Square() tri = Triangle() print("Area of square: ", sq.calculate_area_sq()) print("Area of triangle: ", tri.calculate_area_tri()) Area of square: 25 Area of triangle: 10.0 The problem with this approach is that the developer has to remember the name of each function separately. In a much larger program, it is very difficult to memorize the name of the functions for every small operation. Here comes the role of method overloading. Now let's change the name of functions to calculate the area and give them both same name calculate_area() while keeping the function separately in both the classes with different definitions. In this case the type of object will help in resolving the call to the function. The program below shows the implementation of this type of polymorphism with class methods: classSquare: side =5 defcalculate_area(self): return self.side * self.side classTriangle: base =5 height =4 defcalculate_area(self): return0.5* self.base * self.height sq = Square() 24 tri = Triangle() print("Area of square: ", sq.calculate_area()) print("Area of triangle: ", tri.calculate_area()) Area of square: 25 Area of triangle: 10.0 As you can see in the implementation of both the classes i.e. Square as well as Triangle has the function with same name calculate_area(), but due to different objects its call get resolved correctly, that is when the function is called using the object sq then the function of class Square is called and when it is called using the object tri then the function of class Triangle is called. Polymorphism with Class Methods What we saw in the example above is again obvious behaviour. Let's use a loop which iterates over a tuple of objects of various shapes and call the area function to calculate area for each shape object. sq = Square() tri = Triangle() for(obj in(sq, tri)): obj.calculate_area() Now this is a better example of polymorphism because now we are treating objects of different classes as an object on which same function gets called. Here python doesn't care about the type of object which is calling the function hence making the class method polymorphic in nature. Polymorphism with Functions Just like we used a loop in the above example, we can also create a function which takes an object of some shape class as input and then calls the function to calculate area for it. For example, find_area_of_shape(obj): obj.calculate_area() 25 sq = Square() tri = Triangle() # calling the method with different objects find_area_of_shape(sq) find_area_of_shape(tri) In the example above we have used the same function find_area_of_shape to calculate area of two different shape classes. The same function takes different class objects as arguments and executes perfectly to return the result. This is polymorphism. Polymorphism with Inheritance Polymorphism in python defines methods in the child class that have the same name as the methods in the parent class. In inheritance, the child class inherits the methods from the parent class. Also, it is possible to modify a method in a child class that it has inherited from the parent class. This is mostly used in cases where the method inherited from the parent class doesn’t fit the child class. This process of re-implementing a method in the child class is known as Method Overriding. Here is an example that shows polymorphism with inheritance: 26 Output: There are different types of birds Most of the birds can fly but some cannot There are different types of bird Parrots can fly There are many types of birds Penguins do not fly These are different ways to define polymorphism in Python. With this, we have come to the end of our article. I hope you understood what is polymorphism and how it is used in Python. Abstraction Abstraction is one of the most important features of object-oriented programming. It is used to hide the background details or any unnecessary implementation. Pre-defined functions are similar to data abstraction. For example, when you use a washing machine for laundry purposes. What you do is you put your laundry and detergent inside the machine and wait for the machine to perform its task. How does it perform it? What mechanism does it use? A user is not required to know the engineering behind its work. This process is typically known as data abstraction, when all the unnecessary information is kept hidden from the users. Code In Python, we can achieve abstraction by incorporating abstract classes and methods. Any class that contains abstract method(s) is called an abstract class. Abstract methods do not include any implementations – they are always defined and implemented as part of the methods of the sub-classes inherited from the abstract class. Look at the sample syntax below for an abstract class: from abc import ABC // abc is a library from where a class ABC is being imported. However, a separate class can also be created. The importing from the library has nothing to do with abstraction. Class type_shape(ABC): The class type_shape is inherited from the ABC class. Let’s define an abstract method area inside the class type_shape: from abc import ABC class type_shape(ABC): // abstract method area def area(self): pass The implementation of an abstract class is done in the sub-classes, which will inherit the class type_shape. We have defined four classes that inherit the abstract class type_shape in the code below 27 Example: from abc import ABC class type_shape(ABC): def area(self): #abstract method pass class Rectangle(type_shape): length = 6 breadth = 4 def area(self): return self.length * self.breadth class Circle(type_shape): radius = 7 def area(self): return 3.14 * self.radius * self.radius class Square(type_shape): length = 4 def area(self): return self.length*self.length class triangle: length = 5 width = 4 def area(self): return 0.5 * self.length * self.width r = Rectangle() # object created for the class 'Rectangle' c = Circle() # object created for the class 'Circle' s = Square() # object created for the class 'Square' t = triangle() # object created for the class 'triangle' print("Area of a rectangle:", r.area()) # call to 'area' method defined inside the class. print("Area of a circle:", c.area()) # call to 'area' method defined inside the class. print("Area of a square:", s.area()) # call to 'area' method defined inside the class. print("Area of a triangle:", t.area()) # call to 'area' method defined inside the class. Output 1.14s Area of a rectangle: 24 Area of a circle: 153.86 Area of a square: 16 Area of a triangle: 10.0 28  UNIT – II Data Structures – Definition,Linear Data Structures,Non-Linear Data Structures,Python Specific Data Structures, List,Tuples, Set, Dictionaries, Comprehensions and its Types,Strings,slicing. Data Structure Organizing, managing and storing data is important as it enables easier access and efficient modifications. Data Structures allows you to organize your data in such a way that enables you to store collections of data, relate them and perform operations on them accordingly. A data structure is classified into two categories: o Linear data structure o Non-linear data structure Now let's have a brief look at both these data structures. What is the Linear data structure? A linear data structure is a structure in which the elements are stored sequentially, and the elements are connected to the previous and the next element. As the elements are stored sequentially, so they can be traversed or accessed in a single run. The implementation of linear data structures is easier as the elements are sequentially organized in memory. The data elements in an array are traversed one after another and can access only one element at a time. The types of linear data structures are Array, Queue, Stack, Linked List. Let's discuss each linear data structure in detail. o Array: An array consists of data elements of a same data type. For example, if we want to store the roll numbers of 10 students, so instead of creating 10 integer type variables, we will create an array having size 10. Therefore, we can say that an array saves a lot of memory and reduces the length of the code. o Stack: It is linear data structure that uses the LIFO (Last In-First Out) rule in which the data added last will be removed first. The addition of data element in a stack is known as a push operation, and the deletion of data element form the list is known as pop operation. o Queue: It is a data structure that uses the FIFO rule (First In-First Out). In this rule, the element which is added first will be removed first. There are two terms used in the queue front end and rear The insertion operation performed at the back end is known ad enqueue, and the deletion operation performed at the front end is known as dequeue. o Linked list: It is a collection of nodes that are made up of two parts, i.e., data element and reference to the next node in the sequence. 29 What is a Non-linear data structure? A non-linear data structure is also another type of data structure in which the data elements are not arranged in a contiguous manner. As the arrangement is nonsequential, so the data elements cannot be traversed or accessed in a single run. In the case of linear data structure, element is connected to two elements (previous and the next element), whereas, in the non-linear data structure, an element can be connected to more than two elements. Trees and Graphs are the types of non-linear data structure. Let's discuss both the data structures in detail. o Tree It is a non-linear data structure that consists of various linked nodes. It has a hierarchical tree structure that forms a parent-child relationship. The diagrammatic representation of a tree data structure is shown below: For example, the posts of employees are arranged in a tree data structure like managers, officers, clerk. In the above figure, A represents a manager, B and C represent the officers, and other nodes represent the clerks. o Graph A graph is a non-linear data structure that has a finite number of vertices and edges, and these edges are used to connect the vertices. The vertices are used to store the data elements, while the edges represent the relationship between the vertices. A graph is used in various real-world problems like telephone networks, circuit networks, social networks like LinkedIn, Facebook. In the case of facebook, a single user can be considered as a node, and the connection of a user with others is known as edges. 30 Python Specific Data Structures: List: It is a general purpose most widely used in data structures List is a collection which is ordered and changeable and allows duplicate members. (Grow and shrink as needed, sequence type, sortable). To use a list, you must declare it first. Do this using square brackets and separate values with commas. We can construct / create list in many ways. Ex: >>> list1=[1,2,3,'A','B',7,8,[10,11]] >>> print(list1) [1, 2, 3, 'A', 'B', 7, 8, [10, 11]] ---------------------- >>> x=list() >>> x [] -------------------------- >>> tuple1=(1,2,3,4) >>> x=list(tuple1) >>> x [1, 2, 3, 4] The list data type has some more methods. Here are all of the methods of list objects: List Operations: Del() Append() Extend() Insert() Pop() Remove() Reverse() Sort() Delete: Delete a list or an item from a list >>> x=[5,3,8,6] >>> del(x) #deletes the index position 1 in a list >>> x 31 [5, 8, 6] ------------ >>> del(x) >>> x # complete list gets deleted Append: Append an item to a list >>> x=[1,5,8,4] >>> x.append(10) >>> x [1, 5, 8, 4, 10] Extend: Append a sequence to a list. >>> x=[1,2,3,4] >>> y=[3,6,9,1] >>> x.extend(y) >>> x [1, 2, 3, 4, 3, 6, 9, 1] Insert: To add an item at the specified index, use the insert () method: >>> x=[1,2,4,6,7] >>> x.insert(2,10) #insert(index no, item to be inserted) >>> x [1, 2, 10, 4, 6, 7] ------------------------- >>> x.insert(4,['a',11]) >>> x [1, 2, 10, 4, ['a', 11], 6, 7] Pop: The pop() method removes the specified index, (or the last item if index is not specified) or simply pops the last item of list and returns the item. >>> x=[1, 2, 10, 4, 6, 7] >>> x.pop() 7 >>> x [1, 2, 10, 4, 6] ----------------------------------- >>> x=[1, 2, 10, 4, 6] >>> x.pop(2) 10 >>> x [1, 2, 4, 6] Remove: The remove() method removes the specified item from a given list. >>> x=[1,33,2,10,4,6] >>> x.remove(33) >>> x [1, 2, 10, 4, 6] >>> x.remove(4) >>> x [1, 2, 10, 6] Reverse: Reverse the order of a given list. >>> x=[1,2,3,4,5,6,7] >>> x.reverse() >>> x 32 [7, 6, 5, 4, 3, 2, 1] Sort: Sorts the elements in ascending order >>> x=[7, 6, 5, 4, 3, 2, 1] >>> x.sort() >>> x [1, 2, 3, 4, 5, 6, 7] ----------------------- >>> x=[10,1,5,3,8,7] >>> x.sort() >>> x [1, 3, 5, 7, 8, 10] Slicing: Slice out substrings, sub lists, sub Tuples using index. [Start: stop: steps] Slicing will start from index and will go up to stop in step of steps. Default value of start is 0, Stop is last index of list And for step default is 1 Example: >>> x='computer' >>> x[1:4] 'omp' >>> x[1:6:2] 'opt' >>> x[3:] 'puter' >>> x[:5] 'compu' >>> x[-1] 'r' >>> x[-3:] 'ter' >>> x[:-2] 'comput' >>> x[::-2] 33 'rtpo' >>> x[::-1] 'retupmoc' List: >>> list1=range(1,6) >>> list1 range(1, 6) >>> print(list1) range(1, 6) >>> list1=[1,2,3,4,5,6,7,8,9,10] >>> list1[1:] [2, 3, 4, 5, 6, 7, 8, 9, 10] >>> list1[:1] >>> list1[2:5] [3, 4, 5] >>> list1[:6] [1, 2, 3, 4, 5, 6] >>> list1[1:2:4] >>> list1[1:8:2] [2, 4, 6, 8] Tuple: >>> list1=(11,12,13,14) >>> list1[:2] (11, 12) To create a slice: >>> print(slice(3)) slice(None, 3, None) >>> print(slice(2)) 34 slice(None, 2, None) >>> print(slice(1,6,4)) slice(1, 6, 4) To get substring from a given string using slice object: >>> pystr='python' >>> x=slice(3) >>> print(pystr[x]) Pyt Using –ve index: >>> pystr='python' >>> x=slice(1,-3,1) >>> print(pystr[x]) >>> yt To get sublist and sub-tuple from a given list and tuple respectively: >>> list1=['m','r','c','e','t'] >>> tup1=('c','o','l','l','e','g','e') >>> x=slice(1,4,1) >>> print(tup1[x]) ('o', 'l', 'l') >>> print(list1[x]) ['r', 'c', 'e'] >>> x=slice(1,5,2) >>> print(list1[x]) ['r', 'e'] >>> print(tup1[x]) ('o', 'l') >>> x=slice(-1,-4,-1) #negative index >>> print(list1[x]) ['t', 'e', 'c'] >>> x=slice(-1,-4,-1) #negative index 35 >>> print(tup1[x]) ('e', 'g', 'e') >>> print(list1[0:3]) #extending indexing syntax ['m', 'r', 'c'] Tuples: A tuple is a collection which is ordered and unchangeable. In Python tuples are written with round brackets. Supports all operations for sequences. Immutable, but member objects may be mutable. If the contents of a list shouldn’t change, use a tuple to prevent items from accidently being added, changed, or deleted. Tuples are more efficient than list due to python’s implementation. We can construct tuple in many ways: X=() #no item tuple X=(1,2,3) X=tuple(list1) X=1,2,3,4 Example: >>> x=(1,2,3) >>> print(x) (1, 2, 3) >>> x (1, 2, 3) ----------------------- >>> x=() >>> x () ---------------------------- >>> x=[4,5,66,9] >>> y=tuple(x) >>> y (4, 5, 66, 9) ----------------------------- >>> x=1,2,3,4 >>> x (1, 2, 3, 4) Some of the operations of tuple are: 36  Access tuple items Change tuple items Loop through a tuple Count() Index() Length() Access tuple items:Access tuple items by referring to the index number, inside square brackets >>> x=('a','b','c','g') >>> print(x) c Change tuple items: Once a tuple is created, you cannot change its values. Tuples are unchangeable. >>> x=(2,5,7,'4',8) >>> x=10 Traceback (most recent call last): File "", line 1, in x=10 TypeError: 'tuple' object does not support item assignment >>> x (2, 5, 7, '4', 8) # the value is still the same Loop through a tuple: We can loop the values of tuple using for loop >>> x=4,5,6,7,2,'aa' >>> for i in x: print(i) 4 5 6 7 2 aa Count ():Returns the number of times a specified value occurs in a tuple >>> x=(1,2,3,4,5,6,2,10,2,11,12,2) >>> x.count(2) 4 Index (): Searches the tuple for a specified value and returns the position of where it was found >>> x=(1,2,3,4,5,6,2,10,2,11,12,2) 37  >>> x.index(2) 1 (Or) >>> x=(1,2,3,4,5,6,2,10,2,11,12,2) >>> y=x.index(2) >>> print(y) 1 Length (): To know the number of items or values present in a tuple, we use len(). >>> x=(1,2,3,4,5,6,2,10,2,11,12,2) >>> y=len(x) >>> print(y) 12 Set: A set is a collection which is unordered and unindexed with no duplicate elements. In Python sets are written with curly brackets. To create an empty set we use set() Curly braces ‘{}’ or the set() function can be used to create sets We can construct tuple in many ways: X=set() X={3,5,6,8} X=set(list1) Example: >>> x={1,3,5,6} >>> x {1, 3, 5, 6} ---------------------- >>> x=set() >>> x set() --------------------- >>> list1=[4,6,"dd",7] >>> x=set(list1) >>> x {4, 'dd', 6, 7} We cannot access items in a set by referring to an index, since sets are unordered the items has no index. But you can loop through the set items using a for loop, or ask if a specified value is present in a set, by using the in keyword. 38  Some of the basic set operations are: Add() Remove() Len() Item in x Pop Clear Add (): To add one item to a set use the add () method. To add more than one item to a set use the update () method. >>> x={"mrcet","college","cse","dept"} >>> x.add("autonomous") >>> x {'mrcet', 'dept', 'autonomous', 'cse', 'college'} ---- >>> x={1,2,3} >>> x.update("a","b") >>> x {1, 2, 3, 'a', 'b'} ---------------- >>> x={1,2,3} >>> x.update([4,5],[6,7,8]) >>> x {1, 2, 3, 4, 5, 6, 7, 8} Remove (): To remove an item from the set we use remove or discard methods. >>> x={1, 2, 3, 'a', 'b'} >>> x.remove(3) >>> x {1, 2, 'a', 'b'} Len (): To know the number of items present in a set, we use len(). >>> z={'mrcet', 'dept', 'autonomous', 'cse', 'college'} >>> len(z) 5 Item in X: you can loop through the set items using a for loop. >>> x={'a','b','c','d'} >>> for item in x: print(item) c d a b pop ():This method is used to remove an item, but this method will remove the last item. Remember that sets are unordered, so you will not know what item that gets removed. 39  >>> x={1, 2, 3, 4, 5, 6, 7, 8} >>> x.pop() 1 >>> x {2, 3, 4, 5, 6, 7, 8} Clear (): This method will the set as empty. >>> x={2, 3, 4, 5, 6, 7, 8} >>> x.clear() >>> x set() The set also consist of some mathematical operations like: Intersection AND & Union OR | Symmetric Diff XOR ^ Diff In set1 but not in set2 set1-set2 Subset set2 contains set1 set1=set2 Some examples: >>> x={1,2,3,4} >>> y={4,5,6,7} >>> print(x|y) {1, 2, 3, 4, 5, 6, 7} ----------------------------- >>> x={1,2,3,4} >>> y={4,5,6,7} >>> print(x&y) {4} ---------------------------- >>> A = {1, 2, 3, 4, 5} >>> B = {4, 5, 6, 7, 8} >>> print(A-B) {1, 2, 3} --------------------------- >>> B = {4, 5, 6, 7, 8} >>> A = {1, 2, 3, 4, 5} >>> print(B^A) {1, 2, 3, 6, 7, 8} Dictionaries: A dictionary is a collection which is unordered, changeable and indexed. In Python dictionaries are written with curly brackets, and they have keys and values. Key-value pairs Unordered 40 We can construct or create dictionary like: X={1:’A’,2:’B’,3:’c’} X=dict([(‘a’,3) (‘b’,4)] X=dict(‘A’=1,’B’ =2) Examples: >>> dict1 = {"brand":"mrcet","model":"college","year":2004} >>> dict1 {'brand': 'mrcet', 'model': 'college', 'year': 2004} ------------------- To access specific value of a dictionary, we must pass its key, >>> dict1 = {"brand":"mrcet","model":"college","year":2004} >>> x=dict1["brand"] >>> x 'mrcet' --------------------- To access keys and values and items of dictionary: >>> dict1 = {"brand":"mrcet","model":"college","year":2004} >>> dict1.keys() dict_keys(['brand', 'model', 'year']) >>> dict1.values() dict_values(['mrcet', 'college', 2004]) >>> dict1.items() dict_items([('brand', 'mrcet'), ('model', 'college'), ('year', 2004)]) ----------------------------------------------- >>> for items in dict1.values(): print(items) mrcet college 2004 >>> for items in dict1.keys(): print(items) brand model year >>> for i in dict1.items(): print(i) ('brand', 'mrcet') ('model', 'college') 41  ('year', 2004) Some of the operations are: Add/change Remove Length Delete Add/change values:You can change the value of a specific item by referring to its key name >>> dict1 = {"brand":"mrcet","model":"college","year":2004} >>> dict1["year"]=2005 >>> dict1 {'brand': 'mrcet', 'model': 'college', 'year': 2005} Remove(): It removes or pop the specific item of dictionary. >>> dict1 = {"brand":"mrcet","model":"college","year":2004} >>> print(dict1.pop("model")) college >>> dict1 {'brand': 'mrcet', 'year': 2005} Delete: Deletes a particular item. >>> x = {1:1, 2:4, 3:9, 4:16, 5:25} >>> del x >>> x Length: we use len() method to get the length of dictionary. >>>{1: 1, 2: 4, 3: 9, 4: 16} {1: 1, 2: 4, 3: 9, 4: 16} >>> y=len(x) >>> y 4 Iterating over (key, value) pairs: >>> x = {1:1, 2:4, 3:9, 4:16, 5:25} >>> for key in x: print(key, x[key]) 11 24 39 4 16 5 25 >>> for k,v in x.items(): print(k,v) 42 11 24 39 4 16 5 25 List of Dictionaries: >>> customers = [{"uid":1,"name":"John"}, {"uid":2,"name":"Smith"}, {"uid":3,"name":"Andersson"}, ] >>>>>> print(customers) [{'uid': 1, 'name': 'John'}, {'uid': 2, 'name': 'Smith'}, {'uid': 3, 'name': 'Andersson'}] ## Print the uid and name of each customer >>> for x in customers: print(x["uid"], x["name"]) 1 John 2 Smith 3 Andersson ##Modify an entry, This will change the name of customer 2 from Smith to Charlie >>> customers["name"]="charlie" >>> print(customers) [{'uid': 1, 'name': 'John'}, {'uid': 2, 'name': 'Smith'}, {'uid': 3, 'name': 'charlie'}] ##Add a new field to each entry >>> for x in customers: x["password"]="123456" # any initial value >>> print(customers) [{'uid': 1, 'name': 'John', 'password': '123456'}, {'uid': 2, 'name': 'Smith', 'password': '123456'}, {'uid': 3, 'name': 'charlie', 'password': '123456'}] ##Delete a field >>> del customers >>> print(customers) [{'uid': 1, 'name': 'John', 'password': '123456'}, {'uid': 3, 'name': 'charlie', 'password': '123456'}] >>> del customers >>> print(customers) [{'uid': 1, 'name': 'John', 'password': '123456'}] 43  ##Delete all fields >>> for x in customers: del x["uid"] >>> x {'name': 'John', 'password': '123456'} Sequences: A sequence is a succession of values bound together by a container that reflects their type. Almost every stream that you put in python is a sequence. Some of them are: String List Tuples Range object String: A string is a group of characters. Since Python has no provision for arrays, we simply use strings. This is how we declare a string. We can use a pair of single or double quotes. Every string object is of the type ‘str’. >>> type("name") >>> name=str() >>> name '' >>> a=str('mrcet') >>> a 'mrcet' >>> a=str(mrcet) >>> a 'c' List: A list is an ordered group of items. To declare it, we use square brackets. >>> college=["cse","it","eee","ece","mech","aero"] >>> college 'it' >>> college[:2] ['cse', 'it'] >>> college[:3] ['cse', 'it', 'eee'] >>> college[3:] ['ece', 'mech', 'aero'] >>> college="csedept" 44  >>> college ['csedept', 'it', 'eee', 'ece', 'mech', 'aero'] Tuple: It is an immutable group of items. When we say immutable, we mean we cannot change a single value once we declare it. >>> x=[1,2,3] >>> y=tuple(x) >>> y (1, 2, 3) >>> hello=tuple(["mrcet","college"]) >>> hello ('mrcet', 'college') Range object: A range() object lends us a range to iterate on; it gives us a list of numbers. >>> a=range(4) >>> type(a) >>> for i in range(1,6,2): print(i) 1 3 5 Some of the python sequence operations and functions are: 1. Indexing 2. Slicing 3. Adding/Concatenation 4. Multiplying 5. Checking membership 6. Iterating 7. Len() 8. Min() 9. Max() 10. Sum() 11. Sorted() 12. Count() 13. Index() 1. Indexing Access any item in the sequence using its index. string List 45  >>> x='mrcet' >>> x=['a','b','c'] >>> print(x) >>> print(x) c b 2. Slicing Slice out substrings, sub lists, sub tuples using index [start : stop : step size] >>> x='computer' >>> x[1:4] 'omp' >>> x[1:6:2] 'opt' >>> x[3:] 'puter' >>> x[:5] 'compu' >>> x[-1] 'r' >>> x[-3:] 'ter' >>> x[:-2] 'comput' >>> x[::-2] 'rtpo' >>> x[::-1] 'retupmoc' 3. Adding/concatenation: Combine 2 sequences of same type using +. string List >>> x='mrcet' + 'college' >>> x=['a','b'] + ['c'] >>> print(x) >>> print(x) Mrcetcollege ['a', 'b', 'c'] 46 4. Multiplying: Multiply a sequence using *. string List >>> x='mrcet'*3 >>> x=[3,4]*2 >>> x >>> x 'mrcetmrcetmrcet' [3, 4, 3, 4] 5. Checking Membership: Test whether an item is in or not in a sequence. string List >>> x='mrcet' >>> x=['a','b','c'] >>> print('c' in x) >>> print('a' not in x) True False 6. Iterating: Iterate through the items in asequence >>> x=[1,2,3] >>> for item in x: print(item*2) 2 4 6 If we want to display the items of a given list with index then we have to use “enumerate” keyword. >>> x=[5,6,7] >>> for item,index in enumerate(x): print(item,index) 05 16 27 7. len(): It will count the number of items in a given sequence. string List 47  >>> x="mrcet" >>> x=["aa","b",'c','cc'] >>> print(len(x)) >>> print(len(x)) 5 4 8. min(): Finds the minimum item in a given sequence lexicographically. string List >>> x="mrcet" >>> x=["apple","ant1","ant"] >>> print(min(x)) >>> print(min(x)) c ant It is an alpha-numeric type but cannot mix types. >>> x=["apple","ant1","ant",11] >>> print(min(x)) Traceback (most recent call last): File "", line 1, in print(min(x)) TypeError: '' not supported between instances of 'int' and 'str' 10. Sum: Finds the sum of items in a sequence >>> x=[1,2,3,4,5] >>> print(sum(x)) 48  15 >>> print(sum(x[-2:])) 9 Entire string must be numeric type. >>> x=[1,2,3,4,5,"mrcet"] >>> print(sum(x)) Traceback (most recent call last): File "", line 1, in print(sum(x)) TypeError: unsupported operand type(s) for +: 'int' and 'str' 11. Sorted(): Returns a new list of items in sorted order but does not change the original list. string List >>> x='college' >>> x=['a','r','g','c','j','z'] >>> print(sorted(x)) >>> print(sorted(x)) ['c', 'e', 'e', 'g', 'l', 'l', 'o'] ['a', 'c', 'g', 'j', 'r', 'z'] 12. Count(): It returns the count of an item string List >>> x='college' >>> x=['a','b','a','a','c','a'] >>> print(x.count('l')) >>> print(x.count('a')) 2 4 >>> 'college'.count('l') 2 13. Index() Returns the index of first occurrence string List >>> x='college' >>> x=['a','b','a','a','c','a'] >>> print(x.index('l')) >>> print(x.index('a')) 2 0 49  Comprehensions: List: List comprehensions provide a concise way to create lists. Common applications are to make new lists where each element is the result of some operations applied to each member of another sequence or iterable, or to create a subsequence of those elements that satisfy a certain condition. For example, assume we want to create a list of squares, like: >>> list1=[] >>> for x in range(10): list1.append(x**2) >>> list1 [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] (or) This is also equivalent to >>> list1=list(map(lambda x:x**2, range(10))) >>> list1 [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] (or) Which is more concise and redable. >>> list1=[x**2 for x in range(10)] >>> list1 [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] Similarily some examples: 50 >>> x=[m for m in range(8)] >>> print(x) [0, 1, 2, 3, 4, 5, 6, 7] >>> x=[z**2 for z in range(10) if z>4] >>> print(x) [25, 36, 49, 64, 81] >>> x=[x ** 2 for x in range (1, 11) if x % 2 == 1] >>> print(x) [1, 9, 25, 49, 81] >>> a=5 >>> table = [[a, b, a * b] for b in range(1, 11)] >>> for i in table: print(i) [5, 1, 5] [5, 2, 10] [5, 3, 15] [5, 4, 20] [5, 5, 25] [5, 6, 30] [5, 7, 35] [5, 8, 40] [5, 9, 45] [5, 10, 50] Tuple: Tuple Comprehensions are special: The result of a tuple comprehension is special. You might expect it to produce a tuple, but what it does is produce a special "generator" object that we can iterate over. For example: >>> x = (i for i in 'abc') #tuple comprehension >>> x >>> print(x) You might expect this to print as ('a', 'b', 'c') but it prints as The result of a tuple comprehension is not a tuple: it is actually a generator. The only thing that you need to know now about a generator now is that you can iterate over it, but 51 ONLY ONCE. So, given the code >>> x = (i for i in 'abc') >>> for i in x: print(i) a b c Create a list of 2-tuples like (number, square): >>> z=[(x, x**2) for x in range(6)] >>> z [(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25)] Set: Similarly to list comprehensions, set comprehensions are also supported: >>> a = {x for x in 'abracadabra' if x not in 'abc'} >>> a {'r', 'd'} >>> x={3*x for x in range(10) if x>5} >>> x {24, 18, 27, 21} Dictionary: Dictionary comprehensions can be used to create dictionaries from arbitrary key and value expressions: >>> z={x: x**2 for x in (2,4,6)} >>> z {2: 4, 4: 16, 6: 36} >>> dict11 = {x: x*x for x in range(6)} >>> dict11 {0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25} 52  String Sliceing in Python If you want to slice strings in Python, it’s going to be as simple as this one line below. res_s =s[ start_pos:end_pos:step ] Here, res_s stores the returned sub-string, s is the given string, start_pos is the starting index from which we need to slice the string s, end_pos is the ending index, before which the slicing operation would end, step is the steps the slicing process would take from start_pos to end_pos. Note: All of the above three parameters are optional. By default, start_pos is set to 0, end_pos is considered equal to the length of the string, and step is set to 1. Now let us take some examples to understand how to slice strings in Python in a better way. Slice Strings in Python – Examples Slicing Python strings can be done in different ways. Usually, we access string elements(characters) using simple indexing that starts from 0 up to n-1(n is the length of the string). Hence for accessing the 1st element of a string string1, we can simply use the below code. s1 =String1 Again, there is another way to access these characters, that is, using negative indexing. Negative indexing starts from -1 to -n(n is the length for the given string). Note, negative indexing is done from the other end of the string. Hence, to access the first character this time we need to follow the below-given code. s1 =String1[-n] Now let us look at some ways following which we can slice a string using the above concept. 1. Slice Strings in Python with Start and End We can easily slice a given string by mentioning the starting and ending indices for the desired sub-string we are looking for. Look at the example given below, it explains string slicing using starting and ending indices for both usual and negative indexing method. #string slicing with two parameters 53  s ="Hello World!" res1 =s[2:8] res2 =s[-4:-1] #using negative indexing print("Result1 = ",res1) print("Result2 = ",res2) Output: Result1 = llo Wo Result2 = rld Here, We initialize a string, s as “Hello World!”, At first, we slice the given string with starting index 2 and ending index as 8. This means that the resultant sub-string would contain the characters from s to s[8-1], Similarly, for the next one, the resultant sub-string should contain characters from s[-4] to s[(-1)-1]. Hence, our output is justified. 2. Slice Strings Using Only the Start or End As mentioned earlier, all of the three parameters for string slicing are optional. Hence, we can easily accomplish our tasks using one parameter. Look at the code below to get a clear understanding. #string slicing with one parameter s1="Charlie" s2="Jordan" res1 =s1[2:] #default value of ending position is set to the length of string res2 =s2[:4] #default value of starting position is set to 0 print("Result1 = ",res1) print("Result2 = ",res2) Output: Result1 = arlie Result2 = Jord Here, We firstly initialize two strings, s1 and s2, For slicing both of them we just mention the start_pos for s1, and end_pos for s2 only, Hence for res1, it contains a sub-string of s1 from index 2(as mentioned) up to the last(by default it is set to n-1). Whereas for res2, the range of the indices lies from 0 upto 4(mentioned). 54  3. Slice Strings in Python with Step Parameter The step value decides the jump the slicing operation would take from one index to the other. Look at the example below carefully. #string slicing with step parameter s="Python" s1="Kotlin" res =s[0:5:2] res1 =s1[-1:-4:-2] #using negative parameters print("Resultant sliced string = ",res) print("Resultant sliced string(negative parameters) = ",res1) Output: Resultant sliced string = Pto Resultant sliced string(negative parameters) = nl In the code above, We initialize two strings s and s1, and try to slice them for the given starting and ending indices as we did for our first example, But this time we have mentioned a step value which was set to 1 by default for the previous examples, For res, having a step size 2 means, that while the traversal to get the substring from index 0 to 4, each time the index would be increased by a value of 2. That is the first character is s (‘P’), the next characters in the sub-string would be s[0+2], and s[2+2], until the index is just less than 5. For the next one i.e. res1, the step mentioned is (-2). Hence, similar to the previous case, the characters in the substring would be s1[-1] , then s1[(-1)+(-2)] or s1[-3] until the index is just less than (-4). 4. Reversing a String using Slicing in Python With the use of negative index string slicing in Python, we can also reverse the string and store it in another variable. For doing so we just need to mention a step size of (-1). Let us see how that works in the example given below. #reversing string using string slicing s="AskPython" rev_s =s[::-1] #reverse string stored into rev_s print(rev_s) Output: nohtyPksA As we can see, the string s is reversed and stored into rev_s. Note: For this case too, the original string remains intact and untouched. 55  UNIT – III Arrays - Array Data Structure Overview, Types of Arrays, Operations on Arrays, Arrays vs List.Searching - Linear Search and Binary Search.Sorting - Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort Python arrays: 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. Following are the important terms to understand the concept of Array. 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. Below is an illustration. Elements Int array = {10, 20, 30, 40, 50, 60, 70, 80, 85, 90} Type Name Size Index 0 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 70 Basic Operations Following are the basic operations supported by an array. 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. 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]) 56 Typecode are the codes that are used to define the type of value the array will hold. Some common typecodes used are: 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 Creating an array: from array import * array1 = array('i', [10,20,30,40,50]) for x in array1: print(x) Output: >>> RESTART: C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/arr.py 10 20 30 40 50 Accessing Array Element We can access each element of an array using the index of the element. from array import * array1 = array('i', [10,20,30,40,50]) print (array1) print (array1) Output: RESTART: C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/arr2.py 10 57 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: ============================================ C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/arr3.py =========================================== 10 60 20 30 40 50 >>> Deletion Operation Deletion refers to removing an existing element from the array and re-organizing 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: ============================================ C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/arr4.py =========================================== 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 using the python in-built index() method. from array import * array1 = array('i', [10,20,30,40,50]) print (array1.index(40)) Output: ============================================ 58  C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/arr5.py =========================================== 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: ============================================ C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/arr6.py =========================================== 10 20 80 40 50 Arrays vs List Both list and array and list are used to store the data in Python. These data structures allow us to indexing, slicing, and iterating. But they have little dissimilarity with each other. Python List A list is a built-in, linear data structure of Python. It is used to store the data in a sequence manner. We can perform several operations to list, such as indexing, iterating, and slicing. The list comes with the following features. o The list elements are enclosed with a square bracket, and each element is separated by a comma (,). o It is a mutable type which means we can modify the list items after their creation. o The lists are ordered, which means items are stored in a specific order. We can use indexing to access the list element. o We can store the items of different data types. We can combine strings, integers, and objects in the same list. Below is an example of a list. Example - 1. list = [31, 60, 19, 12] 59 2. print(list) 3. print(type(list)) Output: [31, 60, 19, 12] Example - 2 1. # creating a list containing elements 2. # belonging to different data types 3. list1 = [1,"Yash",['a','e']] 4. print(list1) Output: [1, 'Yash', ['a', 'e']] In the above list, the first element is an integer; the second is a string and third is a list of characters. Array in Python An array is also a linear data structure that stores the data. It is also ordered, mutable, and enclosed in square brackets. It can store the non-unique items. But there are restrictions to store the different data type values. To work with the Array in Python, we need to import either an array module or a Numpy. 1. import array as arr 2. or 3. import numpy as np Elements are allocated in contiguous memory location that allows us to easy modification, addition, deletion, accessing of element. Moreover, we need to specify the data type. Let's understand the following example. Example - 1. Import array as arr 2. array_1 = arr.array("i", [31, 60,19, 12]) 3. print(array_1) 4. print(type(array_1)) Output: 60  array('i', [31, 60, 19, 12]) Example - 2: Using Numpy array 1. import numpy as np 2. array_sample = np.array(["str", 'sunil', 'sachin', 'megha', 'deepti']) 3. print (array_sample) 4. print(type(array_sample)) Output: ['numbers' 'sunil' 'sachin' 'megha' 'deepti'] We have specified the string type and stored the string value. Difference between Array and List Searching - Linear Search and Binary Search. 61 There are two types of searching - o Linear Search o Binary Search Both techniques are widely used to search an element in the given list. Linear Search What is a Linear Search? Linear search is a method of finding elements within a list. It is also called a sequential search. It is the simplest searching algorithm because it searches the desired element in a sequential manner. It compares each and every element with the value that we are searching for. If both are matched, the element is found, and the algorithm returns the key's index position. Concept of Linear Search Let's understand the following steps to find the element key = 7 in the given list. Step - 1: Start the search from the first element and Check key = 7 with each element of list x. Step - 2: If element is found, return the index position of the key. Step - 3: If element is not found, return element is not present. 62  Linear Search Algorithm There is list of n elements and key value to be searched. Below is the linear search algorithm. 1. LinearSearch(list, key) 2. for each item in the list 3. if item == value 4. return its index position 5. return -1 Python Program Let's understand the following Python implementation of the linear search algorithm. Program 1. def linear_Search(list1, n, key): 2. 3. # Searching list1 sequentially 4. for i in range(0, n): 5. if (list1[i] == key): 6. return i 7. return -1 8. 9. 10. list1 = [1 ,3, 5, 4, 7, 9] 11. key = 7 12. 13. n = len(list1) 14. res = linear_Search(list1, n, key) 15. if(res == -1): 16. print("Element not found") 63 17. else: 18. print("Element found at index: ", res) Output: Element found at index: 4 Explanation: In the above code, we have created a function linear_Search(), which takes three arguments - list1, length of the list, and number to search. We defined for loop and iterate each element and compare to the key value. If element is found, return the index else return -1 which means element is not present in the list. Linear Search Complexity Time complexity of linear search algorithm - o Base Case - O(1) o Average Case - O(n) o Worst Case -O(n) Linear search algorithm is suitable for smaller list () than the next element of the list then swap them. 3. If the current element is less ( --- yes ---- swap and again, so we use loops. If < --- No ---- Do nothing/remains same #Write a python program to arrange the elements in ascending order using bubble sort: list1=[9,16,6,26,0] print("unsorted list1 is", list1) for j in range(len(list1)-1): for i in range(len(list1)-1): if list1[i]>list1[i+1]: list1[i],list1[i+1]=list1[i+1],list1[i] print(list1) else: print(list1) print( ) print("sorted list is",list1) Output: unsorted list1 is [9, 16, 6, 26, 0] [9, 16, 6, 26, 0] [9, 6, 16, 26, 0] [9, 6, 16, 26, 0] [9, 6, 16, 0, 26] [6, 9, 16, 0, 26] [6, 9, 16, 0, 26] [6, 9, 0, 16, 26] [6, 9, 0, 16, 26] [6, 9, 0, 16, 26] [6, 0, 9, 16, 26] [6, 0, 9, 16, 26] [6, 0, 9, 16, 26] [0, 6, 9, 16, 26] [0, 6, 9, 16, 26] [0, 6, 9, 16, 26] [0, 6, 9, 16, 26] sorted list is [0, 6, 9, 16, 26] #If we want to reduce no of iterations/steps in output: C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/bubb.py 69 list1=[9,16,6,26,0] print("unsorted list1 is", list1) for j in range(len(list1)-1,0,-1): for i in range(j): if list1[i]>list1[i+1]: list1[i],list1[i+1]=list1[i+1],list1[i] print(list1) else: print(list1) print( ) print("sorted list is",list1) Output: C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/bubb2.py unsorted list1 is [9, 16, 6, 26, 0] [9, 16, 6, 26, 0] [9, 6, 16, 26, 0] [9, 6, 16, 26, 0] [9, 6, 16, 0, 26] [6, 9, 16, 0, 26] [6, 9, 16, 0, 26] [6, 9, 0, 16, 26] [6, 9, 0, 16, 26] [6, 0, 9, 16, 26] [0, 6, 9, 16, 26] sorted list is [0, 6, 9, 16, 26] # In a different way: list1=[9,16,6,26,0] print("unsorted list1 is", list1) for j in range(len(list1)-1): for i in range(len(list1)-1-j): if list1[i]>list1[i+1]: list1[i],list1[i+1]=list1[i+1],list1[i] print(list1) else: print(list1) print( ) print("sorted list is",list1) Output: C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/bubb3.py 70 unsorted list1 is [9, 16, 6, 26, 0] [9, 16, 6, 26, 0] [9, 6, 16, 26, 0] [9, 6, 16, 26, 0] [9, 6, 16, 0, 26] [6, 9, 16, 0, 26] [6, 9, 16, 0, 26] [6, 9, 0, 16, 26] [6, 9, 0, 16, 26] [6, 0, 9, 16, 26] [0, 6, 9, 16, 26] sorted list is [0, 6, 9, 16, 26] # Program to give input from the user to sort the elements list1=[] num=int(input("enter how many numbers:")) print("enter values") for k in range(num): list1.append(int(input())) print("unsorted list1 is", list1) for j in range(len(list1)-1): for i in range(len(list1)-1): if list1[i]>list1[i+1]: list1[i],list1[i+1]=list1[i+1],list1[i] print(list1) else: print(list1) print( ) print("sorted list is",list1) Output: C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/bubb4.py enter how many numbers:5 enter values 5 77 4 66 30 unsorted list1 is [5, 77, 4, 66, 30] [5, 77, 4, 66, 30] 71 [5, 4, 77, 66, 30] [5, 4, 66, 77, 30] [5, 4, 66, 30, 77] [4, 5, 66, 30, 77] [4, 5, 66, 30, 77] [4, 5, 30, 66, 77] [4, 5, 30, 66, 77] [4, 5, 30, 66, 77] [4, 5, 30, 66, 77] [4, 5, 30, 66, 77] [4, 5, 30, 66, 77] [4, 5, 30, 66, 77] [4, 5, 30, 66, 77] [4, 5, 30, 66, 77] [4, 5, 30, 66, 77] sorted list is [4, 5, 30, 66, 77] #bubble sort program for descending order list1=[9,16,6,26,0] print("unsorted list1 is", list1) for j in range(len(list1)-1): for i in range(len(list1)-1): if list1[i]0: my_list[pos]=my_list[pos-1] pos=pos-1 my_list[pos]=current_element #list1=[3,5,1,0,10,2] 74 #insertionsort(list1) #print(list1) num=int(input("enter how many elements to be in list")) list1=[int(input())for i in range(num)] insertionsort(list1) print(list1) Output: C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/insertdesc.py enter how many elements to be in list 5 8 1 4 10 2 [10, 8, 4, 2, 1] Merge Sort: Generally this merge sort works on the basis of divide and conquer algorithm. The three steps need to be followed is divide, conquer and combine. We will be dividing the unsorted list into sub list until the single element in a list is found. Algorithm: 1. Split the unsorted list. 2. Compare each of the elements and group them 3. Repeat step 2 until whole list is merged and sorted. # Write a python program to arrange the elements in ascending order using Merge sort (with functions) def mergesort(list1): if len(list1)>1: mid=len(list1)//2 left_list=list1[:mid] right_list=list1[mid:] mergesort(left_list) mergesort(right_list) i=0 j=0 k=0 while i