Data structures: linear lists

CLASS- XII
PCT-2 UNIT - 1 CHAPTER - 9
Prepared By -
Swati Patil
BE, MCA,PGDHRM
Contact -
8618134279 (Queries only through SMS)
prippython12.blogspot.com

Data structures
Data Structures is a collection of data values,
relationships among them, and the functions or
operations that can be applied to the data.
Data Structures are a way to organize information in
computer’s memory.
Circular
Queue
Double
Ended
Queue
Simple
Queue
graph

Python offers many Built-in Linear Data structures like List, Tuple, Dictionaries, Sets.
Operations on Data structures-
The basic operations that are performed on data structures are as follow:
1. Insertion 4. Traversal- fetching all data elements one by one
2. Deletion 5. Sorting
3. Searching 6. Merging- Combining elements of 2 or more similar data structures to form new
Date Type Data Structure
It defines set of values for input-output
operations.
It is physical implementation of Storing, accessing, manipulating
data stored in a data structure.
For example,
one can not put decimal point in an integer
or two strings can’t be multiplied.
For example,
Data stored in Stack can be accessed and retrieved from one end
only(LIFO).
Data stored in Queue can be accessed and retrieved from two
ends(FIFO)..
Linear DS Non-Linear DS
These are single level DS. These are multilevel DS.
Examples-Stack, Wueue,LinkesList (implemented by
List)
Example- Tree Graphs

Linear Data Structures( Homogeneous )
Elements of Linear Data structures form a sequence. Arrays are one of the simplest
data structures, and operations are easy to perform like Insertion, Deletion,Searching,
Traversal,Sorting etc.
Let us Revise and Implement Linear List Data Structure based on what you have learnt
in XI.
Searching in LL - a> LInear Search b> Binary Search
Insertion in LL - a> LL is unordered b> LL is ordered (traditional & bisect methods)
Deletion from LL - a> LL is unordered b> LL is ordered (traditional & bisect methods)
Traversal in LL
Length / Size of a Linear list(Arrays) calculated as:
Size of LL= UB - LB +1 (UB- Upper Bound, LB- Lower Bound)

Linear Search
1. Input List, L
2. Input ITEM to search
3. Initialize pos=-1
4. Repeat step 5 until ITEM found or counter
reaches to end of the list.
5. If L[i] == ITEM then
pos=i
Goto step 6
1. If pos == -1
Print “ ITEM not found”
Else
Print “ ITEM found “
1. END
# Program
L=eval(input(“Enter elements:”)
ITEM= int(input(“Enter ITEM to search:”)
pos=-1
for i in range(len(L)):
if L[i] == ITEM :
pos=i
break
if( pos == -1):
print(ITEM, “Not found”)
else:
print(ITEM, “ found at position”,
pos)

Binary Search
1. Input List, L
2. Input ITEM to search
3. Initialize pos=-1
4. Initialize beg=0 and last=sizeof(L)
5. Repeat step 6 through 9 until beg >last
6. mid=(beg+last) / 2
7. if L[mid] == ITEM then
pos=i
Goto step 10
1. if L[mid] >ITEM then
last=mid-1
1. if L[mid] < ITEM then
beg=mid+1
1. If pos==-1 then
print “ ITEM not found”
else
print “ ITEM found “
1. END
# Program
L=eval(input(“Enter elements:”)
ITEM= int(input(“Enter ITEM to search:”)
pos=-1
beg=0
last=len(L)
while beg<=last :
mid=(beg+last)/2
if L[mid] == ITEM :
pos=i
break
if L[mid] > ITEM :
last=mid-1
if L[mid] <ITEM :
beg=mid+1
if pos==-1 :
print(ITEM,”Not Found”)
else:
print(ITEM,”Found at
position”,pos)

Insertion in Linear List
# Insertion of new element in unsorted array.
(new element gets inserted at the end of the array)
1. Insert unordered elements in a list, L
2. Read an element to insert into list, ITEM
3. Insert ITEM at end of the list
4. Print list with inserted ITEM
5. END
# Program
L=eval(input(“Enter elements:”))
ITEM=int(input(“Enter an element to insert in list:”))
L.append(ITEM)
print(L)

Insertion in Linear List
# Insertion of new element in sorted array. Using Traditional method, shifting digits of array.
(new element gets inserted at the appropriate position without altering the order)
# Using Traditional Method program
def Findpos(A,ITEM):
if (A[0]>ITEM) :
return 0
else:
pos=-1
for i in range(len(A)):
if(A[i]<=ITEM and ITEM<A[i+1]):
pos=i+1
break
if (pos== -1 and i <=len(A)-1):
pos=len(A)
return pos
def Shift(A,pos):
A.append(None)
size=len(A)
i=size-1
while i>= pos:
A[i]=A[i-1]
i=i-1
L.sort()
ITEM=int(input(“Enter element to insert:”))
pos=Findpos(L,ITEM)
Shift(L,pos)
L[pos]=ITEM
print(“The list after inserting”,ITEM,”is”,L)

Insertion in Linear List Traversal of a List
# Insertion of new element in sorted array.
Using Bisect Module
(new element gets inserted at the appropriate
position without altering the order)
n=int(input(“Enter size of LIst:”))
L=[None] * n
for i in range(len(n)):
L[i]=int(input(“Enter element”+str(i)+”:”))
print(“Traversing the List:”)
for i in range(len(n)):
print(L[i],end=’ ‘)
# Using bisect Module’s insort() function
print(“The list in sorted order:”,L.sort())
ITEM=int(input(“Enter element to insert:”))
pos=bisect.bisect(L,ITEM)
bisect.insort(L,ITEM)
print(“The list after inserting”,ITEM,”at
position”,pos,”is”,L)

Deletion in Sorted Linear List
def bsearch(L,ITEM):
beg=0 last=len(L)
while beg<=last :
mid=(beg+last)/2
if L[mid] == ITEM :
return mid
if L[mid] > ITEM :
last=mid-1
if L[mid] <ITEM :
beg=mid+1
else: return False
ITEM=int(input(“Enter element to delete:”))
pos=bsearch(L,ITEM)
if pos:
del L[pos]
print(“The list after deleting”,ITEM,”is”, L)
else: print(“Element not present in list”)
# direct remove element
ITEM=int(input(“Enter element to delete:”))
L.remove(ITEM)
print(“The list after deleting”,ITEM,”is”, L)

Nested / 2 Dimensional List
(A list that has one more lists as its elements is nested list)
Properties of Regular nested / 2D lists:
1. All elements of 2D list have same shape(i.e same length & width)
2. Length of 2D is no of Rows in it (i.e len(list) )
3. Length of single Row gives the No of Columns (i.e len(list[n]) )
# Traversing a 2D list
print(“ 2D List is= n [ ”)
for i in range(r):
print(‘t [‘,end=’ ‘)
for j in range(c):
print(L[i][j],end=’ ‘)
print(‘]’)
print(‘]’)
#Creating 2D
L=[ ]
r,c=map(int(input(“Enter no of Rows & Columns”))
for i in range(r):
row=[]
for j in range(c):
ele=int(input(“element”+str(i)+’,’+str(j)+’:’))
row.append(ele)
L.append(row)
print(“ 2D List is:”,L)

Ragged List
Properties of Ragged 2D list:
1. All elements of 2D list have different shape(i.e different lengths )
2. Length of 2D is no of Rows in it (i.e len(list) )
3. Length of single Row gives the No of Columns (i.e len(list[n]) )
0
1
2
“Red”
15
7.3
0
1
5000
0 4
1 5
2 6
0 14
1 15
2 16
3 17
4 18
L=[“Red”,15,7.3] L2D=[ [4,5,6] , [14,15,16,17,18] ]
L2D
30500
5000
40000
List slicing:
L2D[1: ] =[14,15,16,17,18]
L2D[1: ] [2: ]=[16,17,18]
L2D[0: ] [ :2] =[4,5]
L2D[0: ] [ :1 ]=
L2D[0: ] [ : ]=
L2D[ :2 ]=
L2D[1: ] [2:4]=

Consider the following code and show how internally the memory is assigned to
these
List1=[2,3] List2= [3,4,5] List3= [List1, List2]
Assume that the numbers 1..10 are stored in the memory addresses 16000 onwards,
each consuming 16 bytes of memory.
1 2 3 64 5 7 8 9
10
16000 16016 16032 16048 16064 16080 16096 16112 16128 16144
0 16016
1 16032
0 16032
1 16048
2 16064
0 50000
1 20000
List1
50000
List2
20000
List3
30000

Data structures: linear lists

Recommended

More Related Content

What's hot (20)

Similar to Data structures: linear lists (20)

More from ToniyaP1 (6)

Recently uploaded (20)

Data structures: linear lists