CS 250

Data Structures & Algorithms

(Week 2, Lecture 4)
Dr. Muhammad Kamran Khan
Assistant Professor

Department of Electrical Engineering

Military College of Signals
National University of Sciences and Technology (NUST)

1
Last Lecture Summary
 Introduction to Algorithms
 What is an Algorithm?
 Computer Algorithm and Program
 Favorite and Efficient Algorithm
 Measuring Efficiency
 Running Time of an Algorithm
 Analyzing an Algorithm with Simple Example
 Algorithm History
 Algorithm Applications

2
Python Arrays
 An array is a collection of items stored at contiguous
memory locations.
 The idea is to store multiple items of the same data type
together.
 This makes it easier to calculate the position of each
element by simply adding an offset to a base value, i.e.,
the index location of the first element of the array
(generally denoted by the name of the array).

3
Python Arrays

4
Python Arrays
 The array can be handled in Python by a module named
array.
 They can be useful when we have to manipulate only
specific data type values e.g. integers, float, char
 If you create arrays using the array module, all elements of
the array must be of the same type.
 A user can treat lists as arrays. However, the user cannot
constrain the type of elements stored in a list.

5
Example (Python Arrays)
# Python program to demonstrate creation of Array
# importing "array" for array creations
import array as arr

# creating an array with integer type

a = arr.array ('i', [1, 2, 3])

# printing original array

print ("The new created array is : ", end=" ") output
for i in range(0, 3): The new created array is : 1 2 3
print(a[i], end=" ")
print() The new created array is : 2.5 3.2 3.3
# creating an array with double type
b = arr.array('d', [2.5, 3.2, 3.3])

# printing original array

print("\n The new created array is : ", end=" ")
for i in range(0, 3):
print(b[i], end=" ")

6
 Memory Allocation
 Memory allocation can be classified as either:
o Contiguous
o Linked

 Prototypical examples:
o Contiguous allocation: arrays
o Linked allocation: linked lists

7
 Memory Allocation
 An array stores n objects in a single contiguous space
of memory
Unfortunately, if more memory is required, a request for
new memory usually requires copying all information into
the new memory
 In general, you cannot requestr the operating
system to allocate to you the next n memory
locations

8
 List (ADT) in Python
 Python does not have built-in support for Arrays,
but Python Lists can be used instead.

9
 The LIST Data Structure

 The List is among the most generic of data

structures.

 Real life:

a. shopping list,
b. groceries list,
c. list of people to invite to dinner
d. List of presents to get

10
 List

 A list is collection of items that are all of the same or

different type (grocery items, integers, names)

 The items, or elements of the list, are stored in some

particular order

 It is possible to insert new elements into various

positions in the list and remove any element of the
list

11
 List
 List is a set of elements in a linear order.

For example, data values a1, a2, a3, a4 can be arranged in a

list:
[a3, a1, a2, a4]
In this list, a3, is the first element, a1 is the second element,
and so on

 The order is important here; this is not just a random

collection of elements, it is an ordered collection

12
 Lists in Python
 List is a sequence of values called items or
elements.
 The elements can be of any data type.
 The list is a most versatile data type available in
Python which can be written as a list of comma
separated values (items) between square brackets.
 List are mutable, meaning, their elements can be
changed.

13
 Lists in Python
 In Python programming, a list is created by
placing all the items (elements) inside a square
bracket [ ], separated by commas.

 It can have any number of items and they may be

of different types (integer, float, string etc.).

14
Syntax

15
 Lists in Python
 Index operator [] is used to access an item in a
list. Index starts from 0.

 For Example
marks = [90,80,50,70,60]
print(marks[0])
Output: 90

16
 Negative Indexing
 Python allows negative indexing for its sequences.

 The index of -1 refers to the last item, -2 to the

second last item and so on..

 my_list = ['p','r','o','b','e']
# Output: e
print(my_list[-1])
#Output: p
print(my_list[-5])

17
 Implementation of Lists
pyLists = [1,23,4,33,10]
 The above statement will call the list() constructor
to create a list object with the given values

 When the list() constructor is called an array

structure is created to store the items of list

 The array is initially created bigger than needed,

leaving the capacity for future expansion

18
 Implementation of Lists
Abstract View

1 23 4 33 10
0 1 2 3 4

Physical View subarray

Length 5
Capacity 8
Array 1 23 4 33 10 . . .
0 1 2 3 4 5 6 7

The length of subarray is obtained by len()

19
 Appending Item to List
 pyLists.append(50)

pyLists
1 23 4 33 10 50 . .
0 1 2 3 4 5 6 7

 The array is initially created bigger than needed,

leaving the capacity for future expansion

20
Expansion of List (When there isn’t any capacity)
1. A new array is created with the additional capacity

2. Items from the original array are copied to the new

array

3. The new larger array is set as the data structure for

the list

4. The original smaller array is destroyed

21
 Extending a List
 A list can be appended to a second list using extend()
method
 Example
 pyListA = [34,12]
 pyListB=[4, 5, 7, 11, 5]
 pyListA.extend(pyListB)

22
 Inserting Item
 pyList.insert(position, value)
pyList.insert(3,79)-- insert 79 at index position 3

 Elements are shifted to create a space for the

incoming element

23
Example of Append()

list1.append(2)
list1.append(3)
list1.append(4)

24
list1.insert(1,5)

25
 Removing an element
 Pop(0)---- Remove the First element

 Pop()--- Remove the last element

 Pop(index)- Remove the element at the index

passed as an argument

 Remove(item)- remove the particular item

26
Example

Output

27
Example
mylist = [1,2,3] mylist.insert (10,709)
print("initial List") print("after inserting 709 at index 10")
print(mylist) print(mylist)

x =int (input("enter range")) mylist.pop()

for i in range(x): print("after poping the last element")
mylist.append(i*i) print(mylist)
print("Appending for 1st time")
print(mylist) mylist.pop(0)
print("after poping the 1st element")
y=int(input("enter range")) print(mylist)
for i in range(y):
mylist.append(i*i) mylist.pop(3)
print("Appending for 2nd time") print("after poping the 3rd element")
print(mylist) print(mylist)
print("length of list",len(mylist))

28
Output

29
Operations on Lists
 append()
 extend()
 insert()
 sort()
 pop()
 copy()

30
More Methods
 More Methods
• list.count(element) –> returns number of times element occurs
in the list
• list.sort –> sorts the element in place
• list.reverse –> reverses the element in place

 Slicing – can get a sub list of a list

<name>[<first index inclusive> : <second index not-inclusive>]
list = [4, 23, 16, 7, 29, 56, 81]
list[3:6] => [16, 7, 29]

 Length of lists
len(list) => 7

31
Arrays vs. Lists in Python
Arrays Lists
Need to import Built in support in python
Can only hold same type of Python lists are very
objects flexible and can hold
arbitrary data types.
Can not be resized Can be resized
Since arrays stay the same Lists consume more
size that they were when memory as they are
they were first initialized, allocated a few extra
they are compact. elements to allow for
quicker appending of items.

32
Time Cost
 To execute a single statement unit time is required which
is denoted as O(1)-----means constant time
a =10 ------- O(1)

 If the same statement is repeated n times then will be of

order O(n)
for i in range(n):
print(i) ----------O(n), as it will be repeated n times

33
Time Cost for different Operations in Lists
Operations Iterations Worst Time
copy Need to traverse the whole list, item by item O(n)
Append Last item is known, so the new item is inserted in just O(1)
a single statement without iteration

Insert Shifting is required to make a room for the incoming O(n)

element, so again iteration is required

Pop(last) As last element is known, so it is done in a single O(1)

statement

Pop(other May require shifting to remove the intermediate cell O(n)

than last)

34
Motivation for Linked Structures
 An array is the most basic sequence container used to store
and access a collection of data
 It provides easy and direct access but are limited in their
functionality
 Python list is an abstract sequence type implemented using
an array structure
 Insertion and deletion requires shifting, so are bit costly
 Expansion (in size) is also time consuming
 For large arrays, a large contiguous block may not be
available
 Lists can grow in size thus require much larger block
memory

35
THANK YOU

36