Data Structure: Linear List – Notes

Leave a Comment / Class 12 Computer Science Notes / By /

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) ]

Related Posts

Leave a Comment

You cannot copy content of this page

Scroll to Top