Data Structure – A Linear List Notes
What is Data Structure?
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 Types vs. Data Structure
Data Types
Data types defines a set of values along with well – defined operations which tells about its input-output behavior.
For Example: Integer data can’t contain decimal point. String can’t be multiplied, etc.
Data Structure
Data Structure is a physical implementation that clearly specify a way of storing, accessing, manipulating data, stored in a data structure.
The stored data in a data structure has a specific work pattern. For example:-
In Stack, insertion and deletion takes place at one end only, while in Queue, insertion take place at rear and deletion take place from front.
Different Types of Data Structure
Operations on Data Structure
The basic operations that are performed on data structures are as follows:
Insertion : – Addition of a new data element.
Deletion : – Removal of a data element.
Searching : – Searching for the specified data element.
Traversal : – Processing all the elements one by one.
Sorting : – Arranging data elements in a specified order either ascending or descending.
Merging : – Combining elements of two similar data structure.
Linear List – Data Structure using List
A linear list is a sequence of n>=0 element, where each element has same data type.
The size i.e. length of linear list is calculated by UB – LB + 1 ; where UB means Upper Bound and LB is a Lower bound.
In Python Linear List data structure is implemented through List , a primitive or built in data structure.
Linear List – Searching
Searching can by done in two ways – Linear Search and Binary Search
In linear search, each element of the array or list is compared with the given item to be searched for, one by one. This search is also known as Sequential Search.
Binary Search is work with sorted array only. In Binary Search, the Searched Item is Compared with middle element, If item is bigger than middle element, then search process start with right segment, if ITEM is lower than middle element, then search process start with left segment. If Item found then search successful otherwise search is unsuccessful.
Linear Search – Python Program
def Linear_Search(arr, item): """ For Unsorted Array or Linear List """ for position in range(len(arr)): if arr[position] == item: return position # True - FOUND else: return False # NOT FOUND
Binary Search – Python Program
def Binary_Search(arr, item): """ For Sorted Array or Linear List""" beg = 0 # first element index position end = len(arr)-1 # last element index position while (beg<= end): mid = len(arr)/2 # middle element index position if item == arr[mid]: return mid # True - FOUND elif item > arr[mid]: beg = mid + 1 else: end = mid - 1 else: return False # NOT FOUND
Insertion in a Linear List – Unordered & Ordered
Insertion of new element in array can be done in two ways :-
1.If the array is unordered, the new element can be inserted
a. At the end of the array.
b. At the beginning of array.
c. At the specified position
2. If the array is sorted (ordered) then new element is added at appropriate position without altering the order and to achieve this, rest of the element are shifted.
Insertion in a Linear List – Unordered List
>>> lst = [8, 9, 3, 90 ]
At the end of the array.
>>> lst
[8, 9, 3, 90]
>>> lst.append(78)
>>> lst
[8, 9, 3, 90, 78]
At the beginning of array.
>>> lst
[8, 9, 3, 90, 78]
>>> lst.insert(0,100)
>>> lst
[100, 8, 9, 3, 90, 78]
At the specified position of array.
>>> lst
[100, 8, 9, 3, 90, 78]
>>> lst.insert(4,200)
>>> lst
[100, 8, 9, 3, 200, 90, 78]
Insertion in a Linear List – Ordered
If the array is sorted then new element is added at appropriate position without altering the order and to achieve this, rest of the element are shifted.
Traditional Method [Shifting Element]
lst = [2, 5 , 7 , 9 , 11] num = int(input("Enter Number to insert :: ")) #Finding position for pos in range(len(lst)): if lst[pos] >= num : break if pos==len(lst)-1 and lst[pos]<= num: pos = pos+1 #Shifting lst.append(None) t = len(lst)-1 while t >= pos: lst[t] = lst[t-1] t = t -1 #inserting lst[pos]=num print(lst)
Advanced Method Using Bisect Module
Shifting of elements is an expensive process and should be avoided, if a better algorithm is available.
Insertion in Sorted Array by using bisect module a.bisect( listarr, item ) => returns the correct index value for item. b.insort( listarr, item ) => insert item in the listarr at the appropriate position.
bisect module functions work with sequences arranged in ascending order.
import bisect pos = bisect.bisect(sarr, 5) bisect.insort(sarr, 5)
Deletion of an element from Linear List
Deletion an element from a sorted array, can be done by (i) finding the position of element and then (ii) shifting of elements upward i.e. left side.
But this is a time consuming process if data is too long.
So in python, we can use remove( ) method and del <item_position > statements of list.
With del statement it is necessary to find out the position of the item using linear_search or binary_search.
# 15 is the item value, remove the first occurrence of 15 sarr.remove(15) # find the position of value 15 pos = binary_search(15) # delete item which is available at pos index position, del sarr[pos]
Traversal of a Linear List
Traversal is a process to access each individual elements one by one.
Traversal of Linear List by Index :
for i in range(len(arrlist)): print(arrlist[i], end = ‘ ’) print( )
Traversal of Linear List by Value:
for val in arrlist: print(val, end = ‘ ’) print( )
Traversal for Processing : Increase value of each element by 10 of a list
for i in range(len(arrlist)): arrlist[i] = arrlist[i] + 10 print(arrlist )
List Comprehension
How to Create a List ?
Method-I
lst = [2,4,6,8,10]
Or
lst = [ ]
for n in range(1,6):
lst.append(n*2)
List Comprehension
A list comprehension is short hand for a loop that creates a list. A list comprehension is usually shorter, more readable, and more efficient.
lst = [ n * 2 for n in range(1,6) ]
- CBSE Board Class 12 Answer Key Computer Science 083
- Class 12 Computer Science Ch 11 Data Communication NCERT Book Exercise Solution
- Class 12 Computer Science Answer Key (083) Term 1 Question Paper download pdf
- Class 11 Computer Science Chapter 5 Getting Started with Python NCERT Solution
- Input Output in Python
- Python Data Types
- Class 12 Computer Science File Handling in Python NCERT Exercise solution
- Class 12 Computer Science – Exception Handling in Python NCERT Exercise Solutions
- Python 3 Setup and Installation Guide
- Encoding Schemes and Number Systems NCERT Exercise solutions
- Python Important Programs and Practical’s
- CBSE Annual Exam Question Paper for Class 11 Computer Science Sample Papers
- Ch 2 Emerging Trends NCERT Exercise Solution – Class 11 Computer Science
- 110+ Important Networking Full Form List – Download PDF
- Class 12 Computer Science NCERT Exercise Solution
- Class 11 Computer Science NCERT Exercise Solution
- Computer System: Overview – Notes
- Number Systems & Encoding Scheme – Notes
- Boolean Logics – Notes
- Emerging Trends – Notes