Data Structures – I : Linear Lists
Data Structures in Python
The computer system is used essentially as data manipulation system where ‘Data’ are very important thing for it. The data can be referred to in many ways viz. data, data items, data structures etc. The data being an active participant in the organization’s operations and planning, data are aggregated and summarized in various meaningful ways to form information.
2. Elementary Data Representation
Elementary representation of data can be in forms of raw data, data item, data structures.
- Raw data are raw facts. These are simply values or set of values.
- Data item represents single unit of values of certain type.
Data items are used as per their associated data types.
A Data Structure is a named group of data of different data types which is stored in a specific way and can be processed as a single unit. A data structure has well-defined operations, behavior and properties.
Data Type vs. Data Structure
A Data type defines a set of values along with well-defined operations stating its input-output behavior e.g., you cannot put decimal point in an integer or two strings cannot not be multiplied etc.
On the other hand, a Data structure is physical implementation that clearly defines a way of storing, accessing, manipulation data stored in a data structure. The data stored in a data structure has a specific work pattern e.g., in a stack, all insertions and deletions take place at one end only.
3. Different Data Structures
Data Structures are very important in computer system, as these not only allow the user to combine various data types in a group but also allow processing of the group as a single unit therby making things much simpler and easier. The data structures can be classified into following two types :
1. Simple Data Structures :
Simple data structures can be combined in various ways to form more complex structures called compound data structures. Compound data structures are classified into following two types :
2. Linear data structures
These data structures are single level data structures. A data structure is said to be linear if its elements form a sequence. Following are the examples of linear data structures :
(c) Linked List
2. Non-Linear Data Structures
These are multilevel data structures. Example of non-linear data structure is Tree.
3.1 Linear Lists Arrays
Linear Lists or Arrays refer to a named list of a finite number n of similar data elements. Each of the data elements can be referenced respectively by a set of consecutive numbers, usually 0, 1, 2, 3, …n. If the name of a Linear list of 10 elements if LIL, then its elements will be referenced as shown : Lil, Lil, Lil, Lil, ….. LIL
Arrays can be one dimensional, two dimensional or multi dimensional. In Python, arrays are implemented through List data types as Linear Lists or through NumPy arrays.
Stacks data structures refer to the lists stored and accessed in a special way, where LIFO (Last in First Out) technique is followed. In stacks, insertions and deletions take place only at one end, called the tope. Stack is similar to a stack of plates as show in Fig. . Note that plates are inserted or removed only from the top of stack.
Queues data structures are FIFO (First in First Out) lists, where insertions take place at the “rear” end of the queues and deletions take place at the “front” end of the queues. Queue is much the as line of people [shown in image] waiting for their turn to vote. First person will be the first to vote and a new person can joint the queue, at the rear end of it.
3.4 Linked Lists
Linked lists are special lists of some data elements linked to one another. The logical ordering is represented by having each element pointing to the next element. Each element is called a node, which has two parts. The INFO part which stores the information and the reference-pointer part, which points to i.e., stores the reference of next element. Image show both types of lists (singly linked lists and doubly linked lists).
In singly linked lists, nodes have one reference-pointer (next) pointing to the next node,
whereas nodes of doubly linked lists have two reference-pointer (prev and next).
Prev points to the previous node and next points to the next node in the list.
Trees are multilevel data structures having a hierarchical relationship among its elements called nodes. Topmost node is called the root of the tree and bottom-most nodes are called leaves of the tree.
Each of the nodes has some reference-pointer, pointing to (i.e., storing the reference of) the nodes below it.
4 Operations on data Structures
The basic operations that are performed on data structure are as follows :
1. Insertion :
Insertion means addition of a new data element in a data structure.
2. Deletion :
Deletion means removal of a data element from a data structure. The data element is searched for before its removal.
3. Searching :
Searching involves searching for the specified data element in a data structure.
4. Traversal :
Traversal of a data structure means processing all the data elements of ir, one by one.
6. Merging :
Combining elements of two similar data structure to form a new data structure of same type, is called merging.
5. Linear Lists
A linear data structure is that whose elements form a sequence. When elements of linear structures are homogeneous and are represented in memory by means of sequential memory locations, these linear structure are called arrays. Linear Lists or Arrays are one of the simplest data structures and are very easy to traverse, search, sort etc.
An array stores a list of finite number (n) of homogeneous data elements (i.e., data elements of the same type). The number n is called length or size or range of a linear list.
When upper bound and lower bound of a linear list are given, its size is calculated as follows :
Linear list size(length) = UB – LB +1 (UB – Upper Bound, LB – Lower Bound)
For instance, if a linear list or an array has elements numbered as -7, -6, -5…..0, 1, 2, ….15, then its UB is 15 and LB is -7 and array length is
= 15 -(-7) + 1
= 15 + 7 + 1 = 23
6. Linear List Data Structure
It means that all its implementation functions along with storage details (e.g., size) are clearly defined at one place. In the following lines, we shall first talk about various operations performed on linear list and then finally have a complete program implementing linear lists. Here,
6.1 Searching in a Linear List
There are many different searching algorithms : linear search and binary search.
In linear search, each element of the array/linear list is compared with the given Item to be searched for, one by one. This method, which traverses the array/linear list sequentially to locate the geven Item, is called linear search or sequential search.
Program. Linear Searching in an array (linear list)
#linear search def Lsearch(AR, ITEM) : i = 0 while i<len(AR) and AR[i] != ITEM : i += 1 if i<len(AR) : return i else : return False # ----main ---- N = int(input("Enter desired linear-list size (max. 50) ...")) print("/nEnter elements for Linear List/n") AR =  * N # initalize List of size N with zeros for i in range(N) : AR[i] = int(input("Element to be searched for ...")) index = Lsearch(AR, ITEM) if index : print("/nElement found at index :", index, ", Position :", (index + 1)) else : print("/nSorry!! Given element could not be found. /n")
Sample run of above code :
Enter desired linear-list size (max. 50) ... 7 Enter elements for Linear List Element 0 : 88 Element 1 : 77 Element 2 : 44 Element 3 : 33 Element 4 : 22 Element 5 : 11 Element 6 : 10 Enter Element to be searched for ... 11 Element found at index : 5, Position : 6 Enter Element to be searched for ... 78 Sorry! ! Given element could not be found.
This popular search technique searches the given ITEM in minimum possible comparisons. The binary search requires the array, to be scanned, must be sorted in any order (for instance, say ascending order).
In binary search, the ITEM is searched for in smaller segment (nearly half the previous segment) after every stage. For the first stage, the segment contains the entire array.
Binary search can work for only sorted arrays whereas linear search can work for both sorted as well as unsorted arrays.
Program. Binary Searching in an array.
def Bsearch(AR, ITEM) : beg = 0 last = len(AR) - 1 while(beg <= last) : mid = (beg + last)/2 if (ITEM == AR[mid]) : return mid elif (ITEM > AR[mid]) : beg = mid + 1 else : last = mid -1 else : return False # when ITEM not found #_main_ N = int(input("Enter desired linear-list size (max. 50) ...")) print("/nEnter elements for Linear List in ASCENDING ORDER/n") AR =  * N # initialize List of size N with zeros for i in range(N) : AR[i] = int(input("Element" + str(i)+": ")) ITEM = int(input("/nEnter Element to be searched for ...")) index = Bsearch(AR, ITEM) if index : print("/nElement found at index : ", index, ", Position :", (index + 1)) else : print("/nSorry ! ! Given element could not be found. /n")
Sample run of the above code as shown below :
Enter desired linear-list size (max. 50) ... 8 Enter elements for Linear List in ASCENDING ORDER Element 0 : 11 Element 1 : 15 Element 2 : 18 Element 3 : 21 Element 4 : 23 Element 5 : 25 Element 6 : 27 Element 7 : 29 Enter Element to be searched for ... 29 Element found at index : 7, Position : 8
6.2 Insertion in a Linear List
Insertion of new element in array can be done in two ways : (i) if the array is unordered, the new element is inserted at the end of the array, (ii) if the array is sorted then new element is added at appropriate position without altering the order and to achieve this, rest of the elements are shifted.
Python makes available a better algorithm called bisect, available in bisect module.
So, if you use following statement after importing bisect module :
The insort( ) function of bisect module inserts an item in the sorted sequence, keeping it sorted. The above function offers a better algorithm to insert in a sorted sequence.
But one thing that you must remember is that the bisect module works on a sequence arranged in ascending order only. The bisect module also offers another function bisect( ) that returns the appropriate index where the new item can be inserted to keep the order maintained, e.g.,
will give you index where the new element should inserted.
Program. Inserting an element in a sorted array using traditional algorithm.
def FindPos (AR, item) : size = len(AR) if item < AR : return 0 else : pos = -1 for i in range(size -1) : if (AR[i] <= item and item < AR[i + 1]) : pos = i + 1 break if (pos == -1 and i <= size -1) : pos = size return pos def shift(AR, pos) : AR.append(None) # add an empty element at the end size = len(AR) i = size -1 while i >= pos : AR[i] = AR[i-1] i = i-1 #_main_ mylist = [10, 20, 30, 40, 50, 60, 70] print("The list in sorted order is") print(mylist) ITEM = int(input("Enter new element to be inserted :")) position = Findpos(myList, ITEM) Shift(myList, position) myList[position] = ITEM print("The list after inserting", ITEM, "is") print(myList)
The output produced by above program is
[10, 20, 30, 40, 50, 60, 70] Enter new element to be inserted : 80 The list after inserting 80 is [10, 20, 30, 40, 50, 60, 70, 80]
Program. Insertion in sorted array using bisect module.
import bisect myList = p10, 20, 30, 40, 50, 60, 70] print("The list in sorted order is") print(myList) ITEM = int(imput("Enter new element to be inserted :")) ind = bisect.bisect(myList, ITEM) bisect.insort(myList, ITEM) print(ITEM, "iserted at index", ind) print("The list after inserting new element is") print(myList)
The output produced by above program as shown below :
The list in sorted order is [10, 20, 30, 40, 50, 60, 70] Enter new element to be inserted : 45 45 inserted at index 4 The list after inserting new element is [10, 20, 30, 40, 45, 50, 60, 70]
6.3 Deletion of an Element from a Sorted Linear List
The element to be deleted is first searched for in the array using one of the searched techniques i.e., either linear search or binary search. If the search is successful, the element is removed and rest of the elements shifted so as to keep the order of array undistributed.
Program. Deletion of an element from a sorted linear list.
def Bsearch(AR, ITEM) : beg = 0 last = len(AR) - 1 while(beg <= last) : mid = (beg + last)/2 if(ITEM == AR[mid]) : return mid elif (ITEM > AR[mid]) : beg = mid + 1 else : last = mid - 1 else : # else of loop return False # when ITEM not found #_main_ myList = [10, 20, 30, 40, 50, 60, 70] print("The list in sorted order is") print(myList) ITEM = int(input("Enter element to be deleted :")) position = Bsearch(myList, ITEM) if position : del myList[position] print("The list after deleting", ITEM, "is") print(myList) else : print("SORRY! No such element in the list")
The output produced by above code is :
The list in sorted order is [10, 20, 30, 40, 50, 60, 70] Enter element to be deleted : 45 SORRY! No such element in the list >>> =============RESTART================== The list in sorted order is [10, 20, 30, 40, 50, 60, 70] Enter element to be deleted : 40 The list after deleting 40 is [10, 20, 30, 50, 60, 70]