Page 1 :
for more updates visit: www.python4csip.com, , DATA STRUCTURE, Group of data and well defined operations

Page 3 :
for more updates visit: www.python4csip.com, , DATA TYPE VS. DATA STRUCTURE, , , , , , DATA TYPE defines the type of values we can store, and operations we can perform. For example in int, data type we cannot store decimal values, we cannot, multiply two string type values. It also specifies, amount of memory it will take., DATA STRUCTURE is physical implementation that, clearly defines a way of storing, accessing and, manipulation of data stored in data structure. Every, data structure has a specific way of insertion and, deletion like STACK work on LIFO i.e. all operation, will take from one end i.e. TOP where as QUEUE, works on FIFO i.e. item inserted first will be removed, first and new item will always added to the end of, QUEUE., In python we will use LIST as a data structure., , VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR, & SACHIN BHARDWAJ, PGT(CS), KV NO.1 TEZPUR, , 

Page 4 :
for more updates visit: www.python4csip.com, , TYPES OF DATA STRUCTURE, Data structure can be classified into following, two types:, , , Simple Data structure : these are built from primitive, data types like integer, float, string or Boolean., Example: Linear List or Array, , , , Complex Data structure : simple data structure can, be combined in various way to form more complex, data structure. It is of two types:, Linear : are single level data structure i.e. in linear fashion, to form a sequence. Example : STACK, QUEUE, LINKED, LIST,  Non-Linear: are multilevel data structure. Example: TREE, and GRAPH., , , VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR, & SACHIN BHARDWAJ, PGT(CS), KV NO.1 TEZPUR, , 

Page 6 :
for more updates visit: www.python4csip.com, , LINEAR LIST ARRAYS, VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR, & SACHIN BHARDWAJ, PGT(CS), KV NO.1 TEZPUR, , Refers to named list of finite number of n similar, data elements. Each of the data elements can be, accessed by its unique index/subscript position, usually 0,1,2,3,…,  For example if the list mylist contains 10, elements then first element will be mylist[0],, second will be mylist[1] and so on.,  Array, can, be, Single, Dimensional, or, Multidimensional. In Python arrays are, implemented through List data types as Linear, List or through NumPy arrays., 

Page 7 :
for more updates visit: www.python4csip.com, , STACK, VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR, & SACHIN BHARDWAJ, PGT(CS), KV NO.1 TEZPUR, , Allow to insert and delete items from one end, only called TOP.,  Stack works on LIFO principle. It means items, added in list will be removed first.,  Real life Example: Stack of Plates, Books,, Bangles,  Computer based examples: Undo Operation,, Function Call etc., 

Page 8 :
for more updates visit: www.python4csip.com, , QUEUE, VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR, & SACHIN BHARDWAJ, PGT(CS), KV NO.1 TEZPUR, , Allows insertion and deletion from different end, i.e. insertion from REAR and deletion from, FRONT,  Queue works on FIFO principle i.e. item added, first will be removed first.,  Real life example: Queue of People for ticket,  Computer based example: Keyboard typing,, Printer etc., 

Page 9 :
for more updates visit: www.python4csip.com, , LINKED LIST, VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR, & SACHIN BHARDWAJ, PGT(CS), KV NO.1 TEZPUR, , It is dynamic data structure i.e. size of Linked, List is not pre-known before the execution of, program. It takes memory as per requirement, during runtime and every item allocated, dynamically will be known as NODE.,  NODE contains 2 parts: (1) INFO part stores the, actual data to store like roll no. name, marks etc., and (2) LINK holds the address of next allocated, node in memory creating chain of linked items,  Singly Linked List hold the address of next node, and last Node will point to NULL whereas, Doubly Linked List holds the address of next as, well as previous node allows both forward and, backward movement., 

Page 11 :
for more updates visit: www.python4csip.com, , OPERATIONS ON DATA STRUCTURE, DESCRIPTION, , INSERTION, , Addition of new data to data structure, , DELETION, , Removal of data element from data structure, , SEARCHING, , Finding specific data element in data structure, , TRAVERSAL, , Processing all data elements one by one, , SORTING, , Arranging data elements in ascending or, descending order, , MERGING, , Combining elements of two similar data, structure to form a new data structure., , VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR, & SACHIN BHARDWAJ, PGT(CS), KV NO.1 TEZPUR, , OPERATIONS

Page 12 :
for more updates visit: www.python4csip.com, , LINEAR LIST, , , , , , , A linear data structure forms a sequence., When elements of linear structure are homogenous and are, represented in memory b means of sequential memory, location are called arrays., An Array stores a list of finite number(s) of homogenous, data elements., When upper bound and lower bound of linear list are given,, its size can be calculated as :,  Size of List = Upper Bound - Lower Bound + 1, Index, , 0, , 1, , 2, , 3, , 4, , 5, , 6, , values, , 10, , 20, , 30, , 40, , 55, , 70, , 45, , , , Size of above list = 6 – 0 + 1 = 7, , VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR, & SACHIN BHARDWAJ, PGT(CS), KV NO.1 TEZPUR, , 

Page 13 :
for more updates visit: www.python4csip.com, , SEARCHING : LINEAR AND BINARY SEARCHING, VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR, & SACHIN BHARDWAJ, PGT(CS), KV NO.1 TEZPUR, , Linear Searching: each element of linear list is, compared with the given item to be searched one, by one. This method traverse the linear list, sequentially to located the given item.,  For Linear Searching item need not be in any, order, it can be performed on random list.,  Linear Searching is suitable for small list only.,  Best Case: when item to be search is at first, position,  Worst Case: when item to be search is at last, position or not present,  Average Case: when item is somewhere in list, other than first or last position., 

Page 16 :
for more updates visit: www.python4csip.com, , BINARY SEARCHING : DIVIDE AND RULE, , , , , , , , , , VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR, & SACHIN BHARDWAJ, PGT(CS), KV NO.1 TEZPUR, , , , Data must be SORTED either in ascending or, descending order to search using binary method, Searching Starts from the middle position. To find, middle position,  Mid = (lower_index + higher_index) / 2, If middle value is equal to search element “SEARCH, SUCCESSFUL”, If middle value if larger than search value,, searching continues towards left of middle position, otherwise towards right side of middle position. [ for, data arranged in ascending order else vice versa ], Takes less time compare to Linear searching, Suitable for LARGE list, Lets Search…

Page 19 :
for more updates visit: www.python4csip.com, , INSERTION IN LINEAR LIST, Insertion of new item can be done by 2 ways:, , , , , , In unsorted list we can add item directly at the end of, list, For sorted array, we have to first find the position, where new items is to be added, then shift all the, elements from that position one place down and, create place for new item and then insert the new, item to that place., Let us take an example…, , VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR, & SACHIN BHARDWAJ, PGT(CS), KV NO.1 TEZPUR, , 

Page 21 :
for more updates visit: www.python4csip.com, , INSERTION USING PYTHON APPROACH, , , , As we can observe Insertion of new item in sorted, array requires shifting of elements to make room and, this is very time consuming when list grows., It should be avoided using better approach like bisect,, available in bisect module., , , , , , The insort() function of bisect module inserts an item, in the sorted array, keeping it sorted., Bisect module offers another function bisect() which, return the appropriate index where new item can be, inserted to keep the order at it is., , , , , bisect.insort(list,newItem), , bisect.bisect(list,element), , Note: bisect module works only on sequence, arranged in Ascending Order only., , VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR, & SACHIN BHARDWAJ, PGT(CS), KV NO.1 TEZPUR, , 

Page 24 :
for more updates visit: www.python4csip.com, , DELETION FROM SORTED LIST:, TRADITIONAL APPROACH, , However in Python, we have to just delete the, item and rest of the work is automatically, handled by Python i.e. Shifting, reducing size etc.,  In Python we will use either remove(), del or, pop() for this purpose, , , VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR, & SACHIN BHARDWAJ, PGT(CS), KV NO.1 TEZPUR, , To Delete item from sorted list we have to first, find the element position in List using Binary, Searching,  Delete the item from list if search successful,  Shift all the items upwards to keep the order of, list undisturbed,  Reduce the List size by 1, 

Page 27 :
for more updates visit: www.python4csip.com, , TRAVERSAL OF LINEAR LIST, It involves processing of all elements one by one, like:, Printing of all items,  Searching item one by one,  Double each value of list etc., , , , , , In nutshell, if we are accessing all elements one, by one for any reason, it is traversing., , VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR, & SACHIN BHARDWAJ, PGT(CS), KV NO.1 TEZPUR, , 

Page 29 :
for more updates visit: www.python4csip.com, , FEW FUNCTIONS: TRAVERSAL (FUNCTION TO, FIND SUM OF EVERY ALTERNATE ELEMENTS), #Function to add element ending with digit 7, , def AddAlternate(Arr):, sum=0, for i in range(len(Arr)):, if i % 2 == 0:, sum+=Arr[i], return sum, , def AddEnding7(Arr):, sum=0, for i in range(len(Arr)):, if Arr[i] % 10 == 7:, sum+=Arr[i], return sum, , #Function to count how many even values in list, , #Function to swap adjacent elements, , def CountEven(Arr):, count=0, for i in range(len(Arr)):, if Arr[i] % 2 == 0:, count+=1, return count, , def SwapAdjacent(Arr):, for i in range(0,len(Arr),2):, Arr[i],Arr[i+1]=Arr[i+1],Arr[i], , VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR, & SACHIN BHARDWAJ, PGT(CS), KV NO.1 TEZPUR, , #Function to add alternate elements

Page 30 :
for more updates visit: www.python4csip.com, , SORTING A LINEAR LIST, , , , , , Sorting means arranging the list items in Ascending or, Descending order., Many Sorting algorithm which we can use for this purpose, like: Bubble, Selection, Insertion, Shell, Quick, Heap,, Merge etc., In Class XI, we have already studied about 2 sorting, methods: Bubble and Insertion (PDF available in Class XI, option of website), , Bubble Sorting,  Insertion Sorting,  Comparison between Bubble and Insertions, , , VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR, & SACHIN BHARDWAJ, PGT(CS), KV NO.1 TEZPUR, , 

Page 31 :
for more updates visit: www.python4csip.com, , LIST COMPREHENSIONS, We have already studied how to create a list i.e., either by assigning comma separated values in, square bracket to list variable or by using, append() in loop., e.g. mylist = [4,8,12,16,20] Or by loop,  There is another method of creating list called, list comprehensions.,  A list comprehension is a shorthand for list, creating for loop in the form of single statement.,  Example, 1: to create list, using list, comprehension:, mylist = [i*4 for i in range(1,6)], print(mylist), , , VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR, & SACHIN BHARDWAJ, PGT(CS), KV NO.1 TEZPUR

Page 33 :
for more updates visit: www.python4csip.com, , LIST COMPREHENSION FOR NESTED FOR LOOP, , Example : using List Comprehension, Arr = [ i + j for i in [10,20,30] for j in [5,10,15]], print(Arr), , VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR, & SACHIN BHARDWAJ, PGT(CS), KV NO.1 TEZPUR, , Example: Nested Loop, Arr = [ ], for i in [10,20,30]:, for j in [5,10,15]:, Arr.append(i+j), print(Arr)

Page 34 :
for more updates visit: www.python4csip.com, , ADVANTAGES OF LIST COMPREHENSIONS, , , , , , Python will allocate the list’s memory before adding, the elements to it, instead of having to resize on, runtime, Also call to append() function gets avoided thus, reducing the function overheads., , VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR, & SACHIN BHARDWAJ, PGT(CS), KV NO.1 TEZPUR, , Code reduction : A code of 3 or more lines gets, reduced to single line.,  Faster code procession : list comprehensions are, executed faster than their equivalent for loops, because:, 

Page 36 :
for more updates visit: www.python4csip.com, , TWO DIMENSIONAL LIST, Is a list having all elements as list of same shape for, e.g., , , Mylist=[[20,40,60],[5,10,15],[9,18,27]], 20, , 40, , 60, , 5, , 10, , 15, , 9, , 18, , 27, , It is a 2 – D List with 3 rows and 3 columns,  First value will be at index [0][0] and last will be [2][2], , , , mylist = [[1,2,3],[4,5,6],[7,8,9]], print(len(mylist)), , # no. of rows, , print(len(mylist[0])), , # no. of columns, , VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR, & SACHIN BHARDWAJ, PGT(CS), KV NO.1 TEZPUR, , 