Data Structures

Data Structures#

1. Lists#

What are Lists?
Lists Vs Arrays
Characterstics of a List
How to create a list
Access items from a List
Editing items in a List
Deleting items from a List
Operations on Lists
Functions on Lists

What are Lists#

List is a data type where you can store multiple items under 1 name. More technically, lists act like dynamic arrays which means you can add more items on the fly.

Why Lists are required in programming?

Characterstics of a List#

Ordered
Changeble/Mutable
Hetrogeneous
Can have duplicates
are dynamic
can be nested
items can be accessed
can contain any kind of objects in python

L = [1,2,3]
L1 = [3,2,1]

L == L1

False

Creating a List#

# Empty
# print([])
# # 1D -> Homo
# print([1,2,3,4,5])
# # 2D
# print([1,2,3,[4,5]])
# # 3D
# print([[[1,2],[3,4]],[[5,6],[7,8]]])
# # Hetrogenous
# print([1,True,5.6,5+6j,'Hello'])
# # Using Type conversion
print(list('hello'))

['h', 'e', 'l', 'l', 'o']

Accessing Items from a List#

# Indexing
L = [1,2,3,4,5,6]
#positive
# print(L[1])
# # Negative
print(L[-3])

# Indexing
L = [1,2,3,[4,5,6]]
#positive
# print(L[3][2])
# Negative
print(L[-1][-2])

# Indexing
L = [[[1,2],[3,4]],[[5,6],[7,8]]]
#positive
# print(L[0][1][0])

# Slicing
L = [1,2,3,4,5,6]

print(L[1:3])

[2, 3]

Adding Items to a List#

# append (insert at the end of the list 1 item)
L = [1,2,3,4,5]
L.append('hello')
print(L)

[1, 2, 3, 4, 5, 'hello']

# extend (insert at the end of the list multiple items)
L = [1,2,3,4,5]
L.extend([6,7,8])
print(L)

[1, 2, 3, 4, 5, 6, 7, 8]

L = [1,2,3,4,5]
L.append([6,7,8])
print(L)

[1, 2, 3, 4, 5, [6, 7, 8]]

L = [1,2,3,4,5]
L.extend('True')
print(L)

[1, 2, 3, 4, 5, 'T', 'r', 'u', 'e']

# insert
L = [1,2,3,4,5]
L.insert(5,100)
print(L)

[1, 2, 3, 4, 5, 100]

Editing items in a List#

L = [1,2,3,4,5]

# editing with indexing
# L[1] = 500
# print(L)
# editing with slicing
L[1:4] = [200,300,400]
print(L)

[1, 200, 300, 400, 5]

Deleting items from a List#

# del
L = [1,2,3,4,5]

# indexing
# del L[1]
# print(L)
# slicing
del L[1:3]
print(L)

[1, 4, 5]

# remove
L = [1,2,3,4,5]
L.remove(2)
print(L)

[1, 3, 4, 5]

# pop
L = [1,2,3,4,5]
# L.pop(1) # remove the item at index 0 from the list 
L.pop()  # remove the last item from the list (default is to remove the last item)
print(L)

[1, 2, 3, 4]

# clear
L = [1,2,3,4,5]
L.clear()
print(L)

[]

Operations on Lists#

Arithmetic
Membership
Loop

# Arithmetic (+ ,*)

L1 = [1,2,3,4]
L2 = [5,6,7,8]

# Concatenation/Merge
print(L1 + L2)

[1, 2, 3, 4, 5, 6, 7, 8]

print(L1*3)

[1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4]

L1 = [1,2,3,4,5]
L2 = [1,2,3,4,[5,6]]

print(5 not in L1)
print([5,6] in L2)

False
True

# Loops
L1 = [1,2,3,4,5]
L2 = [1,2,3,4,[5,6]]
L3 = [[[1,2],[3,4]],[[5,6],[7,8]]]

for i in L3:
  print(i)

[[1, 2], [3, 4]]
[[5, 6], [7, 8]]

List Functions#

# len/min/max/sorted
L = [2,1,5,7,0]

print(len(L))
print(min(L))
print(max(L))
print(sorted(L,reverse=True))

5
0
7
[7, 5, 2, 1, 0]

# count
L = [1,2,1,3,4,1,5]
L.count(2)

# index (returns the index of the first occurence)
L = [1,2,1,3,4,1,5]
L.index(3)

# reverse
L = [2,1,5,7,0]
# permanently reverses the list
L.reverse()
print(L)

[0, 7, 5, 1, 2]

# sort (vs sorted)
L = [2,1,5,7,0]
print(L)
print(sorted(L))
print(L)
L.sort()
print(L)

[2, 1, 5, 7, 0]
[0, 1, 2, 5, 7]
[2, 1, 5, 7, 0]
[0, 1, 2, 5, 7]

# copy -> shallow
L = [2,1,5,7,0]
print(L)
print(id(L))
L1 = L.copy()
print(L1)
print(id(L1))

[2, 1, 5, 7, 0]
1552892242624
[2, 1, 5, 7, 0]
1552892243392

List Comprehension#

List Comprehension provides a concise way of creating lists.

newlist = [expression for item in iterable if condition == True]

Advantages of List Comprehension

More time-efficient and space-efficient than loops.
Require fewer lines of code.
Transforms iterative statement into a formula.

# Add 1 to 10 numbers to a list
L = []

for i in range(1,11):
  L.append(i)

print(L)

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

L = [i for i in range(1,11) if i != 5]
print(L)

[1, 2, 3, 4, 6, 7, 8, 9, 10]

# scalar multiplication on a vector
v = [2,3,4]
s = -3
# [-6,-9,-12]

[s*i for i in v]

[-6, -9, -12]

# Add squares
L = [1,2,3,4,5]

[i**2 for i in L]

[1, 4, 9, 16, 25]

Disadvantages of Python Lists#

Slow
Risky usage
eats up more memory

a = [1,2,3]
b = a.copy()

print(a)
print(b)

a.append(4)
print(a)
print(b)

# lists are mutable

[1, 2, 3]
[1, 2, 3]
[1, 2, 3, 4]
[1, 2, 3]

Tuples#

A tuple in Python is similar to a list. The difference between the two is that we cannot change the elements of a tuple once it is assigned whereas we can change the elements of a list.

In short, a tuple is an immutable list. A tuple can not be changed in any way once it is created.

Characterstics

Ordered
Unchangeble
Allows duplicate

Plan of Learning#

Creating a Tuple
Accessing items
Editing items
Adding items
Deleting items
Operations on Tuples
Tuple Functions

Creating Tuples#

# empty
t1 = ()
print(t1)
print(type(t1))
# # create a tuple with a single item
t2 = ('hello',)
print(t2)
print(type(t2))
print(type(t2))
# homogeneous
t3 = (1,2,3,4)
print(t3)
# hetrogeneous
t4 = (1,2.5,True,{2,7},[1,2,3])
print(t4)
# tuple in tuple
t5 = (1,2,3,(4,5))
print(t5)
# using type conversion
t6 = tuple('hello',)
print(t6)

()
<class 'tuple'>
('hello',)
<class 'tuple'>
<class 'tuple'>
(1, 2, 3, 4)
(1, 2.5, True, {2, 7}, [1, 2, 3])
(1, 2, 3, (4, 5))
('h', 'e', 'l', 'l', 'o')

Accessing Items#

Indexing
Slicing

t3 = (1,2,3,4)
print(t3)
print(t3[0])
print(t3[-1])

(1, 2, 3, 4)
1
4

t5 = (1,2,3,(4,5))
t5[-1][0]

Editing items#

print(t3)
t3[0] = 100
# immutable just like strings

(1, 2, 3, 4)

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[34], line 2
      1 print(t3)
----> 2 t3[0] = 100
      3 # immutable just like strings

TypeError: 'tuple' object does not support item assignment

Adding items#

print(t3)
# not possible

(1, 2, 3, 4)

Deleting items#

print(t3)
del t3
print(t3)

(1, 2, 3, 4)

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In[42], line 3
      1 print(t3)
      2 del t3
----> 3 print(t3)

NameError: name 't3' is not defined

print(t5)
del t5[-1]

(1, 2, 3, (4, 5))

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[43], line 2
      1 print(t5)
----> 2 del t5[-1]

TypeError: 'tuple' object doesn't support item deletion

Operations on Tuples#

# + and *
t1 = (1,2,3,4)
t2 = (5,6,7,8)

print(t1 + t2)

print(t1*3)

# iteration
for i in t1:
  print(i)

(1, 2, 3, 4, 5, 6, 7, 8)
(1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4)
1
2
3
4

# membership
1 in t1

True

Tuple Functions#

# len/sum/min/max/sorted
t = (1,2,3,4)
len(t)
sum(t)
min(t)
max(t)
sorted(t,reverse=True)

[4, 3, 2, 1]

# count

t = (1,2,3,4,5)

t.count(5)

# index
t.index(5)

Difference between Lists and Tuples#

Syntax
Mutability
Speed
Memory
Built in functionality
Error prone
Usability

a = [1,2,3]
b = a

a.append(4)
print(a)
print(b)

[1, 2, 3, 4]
[1, 2, 3, 4]

a = (1,2,3)
b = a

a = a + (4,)
print(a)
print(b)

(1, 2, 3, 4)
(1, 2, 3)

Sets#

A set is an unordered collection of items. Every set element is unique (no duplicates) and must be immutable (cannot be changed).

However, a set itself is mutable. We can add or remove items from it.

Sets can also be used to perform mathematical set operations like union, intersection, symmetric difference, etc.

Characterstics:

Unordered
Mutable
No Duplicates
Can’t contain mutable data types

Creating Sets#

# empty
s = set()
print(s)
print(type(s))
print(type(s))
# 1D and 2D
s1 = {1,2,3}
print(s1)
# s2 = {1,2,3,{4,5}}
# print(s2)
# homo and hetro
s3 = {1,'hello',4.5,(1,2,3)}
print(s3)
# using type conversion

s4 = set([1,2,3])
print(s4)
# duplicates not allowed
s5 = {1,1,2,2,3,3}
print(s5)
# set can't have mutable items
# s6 = {1,2,[3,4]}
# print(s6)

set()
<class 'set'>
<class 'set'>
{1, 2, 3}
{1, 'hello', (1, 2, 3), 4.5}
{1, 2, 3}
{1, 2, 3}

s1 = {1,2,3}
s2 = {3,2,1}

print(s1 == s2)

True

Accessing Items#

s1 = {1,2,3,4}
s1[0:3]

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[53], line 2
      1 s1 = {1,2,3,4}
----> 2 s1[0:3]

TypeError: 'set' object is not subscriptable

Editing Items#

s1 = {1,2,3,4}
s1[0] = 100

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[54], line 2
      1 s1 = {1,2,3,4}
----> 2 s1[0] = 100

TypeError: 'set' object does not support item assignment

Adding Items#

S = {1,2,3,4}
# add
S.add(5)
print(S)
# update
S.update([5,6,7])
print(S)

{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5, 6, 7}

Deleting Items#

# del
s = {1,2,3,4,5}
# print(s)
# del s[0]
# print(s)
# discard
# s.discard(2)
# print(s)
# remove
# s.remove(4)
# print(s)
# pop
# s.pop()
# print(s)
# clear
s.clear()
print(s)

set()

Set Operation#

s1 = {1,2,3,4,5}
s2 = {4,5,6,7,8}
# s1 | s2
# Union(|)
# Intersection(&)
# s1 & s2
# # Difference(-)
# s1 - s2
# s2 - s1
# # Symmetric Difference(^)
# s1 ^ s2
# # Membership Test
# 1 not in s1
# # Iteration
for i in s1:
  print(i)

Set Functions#

# len/sum/min/max/sorted
s = {3,1,4,5,2,7}
len(s)
sum(s)
min(s)
max(s)
sorted(s,reverse=True)

[7, 5, 4, 3, 2, 1]

# union/update
s1 = {1,2,3,4,5}
s2 = {4,5,6,7,8}

# s1 | s2
s1.union(s2)

s1.update(s2)
print(s1)
print(s2)

{1, 2, 3, 4, 5, 6, 7, 8}
{4, 5, 6, 7, 8}

# intersection/intersection_update
s1 = {1,2,3,4,5}
s2 = {4,5,6,7,8}

s1.intersection(s2)

s1.intersection_update(s2)
print(s1)
print(s2)

{4, 5}
{4, 5, 6, 7, 8}

# difference/difference_update
s1 = {1,2,3,4,5}
s2 = {4,5,6,7,8}

s1.difference(s2)

s1.difference_update(s2)
print(s1)
print(s2)

{1, 2, 3}
{4, 5, 6, 7, 8}

# symmetric_difference/symmetric_difference_update
s1 = {1,2,3,4,5}
s2 = {4,5,6,7,8}

s1.symmetric_difference(s2)

s1.symmetric_difference_update(s2)
print(s1)
print(s2)

{1, 2, 3, 6, 7, 8}
{4, 5, 6, 7, 8}

s1 = {1,2,3,4,5}
s2 = {3,4,5}

s1.issuperset(s2)

True

# copy
s1 = {1,2,3}
s2 = s1.copy()

print(s1)
print(s2)

{1, 2, 3}
{1, 2, 3}

Set Comprehension#

# examples

{i for i in range(1,11)}

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

# examples
{i**2 for i in range(1,11) if i>5}

{36, 49, 64, 81, 100}

Dictionary#

Dictionary in Python is a collection of keys values, used to store data values like a map, which, unlike other data types which hold only a single value as an element.

In some languages it is known as map or assosiative arrays.

dict = { ‘name’ : ‘Fahad’ , ‘age’ : 20 , ‘gender’ : ‘male’ }

Characterstics:

Mutable
Indexing has no meaning
keys can’t be duplicated
keys can’t be mutable items

Create Dictionary#

# empty dictionary
d = {}
d
# 1D dictionary
d1 = { 'name' : 'Fahad' ,'gender' : 'male' }
d1
# # with mixed keys
d2 = {(1,2,3):1,'hello':'world'}
d2
# 2D dictionary -> JSON
s = {
    'name':'Fahad',
     'college':'lms',
     'sem':4,
     'subjects':{
         'AI':50,
         'maths':67,
         'english':34
     }
}
s
# using sequence and dict function
d4 = dict([('name','Fahad'),('age',32),(3,3)])
d4
# duplicate keys
d5 = {'name':'Fahad','name':'asad'}
d5
# mutable items as keys
d6 = {'name':'Fahad',(1,2,3):2}
print(d6)

{'name': 'Fahad', (1, 2, 3): 2}

Accessing items#

my_dict = {'name': 'Jack', 'age': 26}
# []
# my_dict['name']
# get
# my_dict.get('name')

s['subjects']['maths']

Adding key-value pair#

d4 = dict([('name','Fahad'),('age',32),(3,3)])
d4['gender'] = 'male'
d4
d4['weight'] = 72
d4
# update
s['subjects']['AI'] = 75
s

{'name': 'Fahad',
 'college': 'lms',
 'sem': 4,
 'subjects': {'AI': 75, 'maths': 67, 'english': 34}}

Remove key-value pair#

d = {'name': 'Fahad', 'age': 32, 3: 3, 'gender': 'male', 'weight': 72}
# pop
# d.pop('age')
# print(d)
# popitem
# d.popitem()
# print(d)
# del
# del d['name']
# print(d)
# clear
# d.clear()
# print(d)

del s['subjects']['maths']
s

{'name': 'Fahad',
 'college': 'lms',
 'sem': 4,
 'subjects': {'AI': 75, 'english': 34}}

Editing key-value pair#

s['subjects']['AI'] = 80
s

{'name': 'Fahad',
 'college': 'lms',
 'sem': 4,
 'subjects': {'AI': 80, 'english': 34}}

Dictionary Operations#

Membership
Iteration

print(s)

'name' not in s

{'name': 'Fahad', 'college': 'lms', 'sem': 4, 'subjects': {'AI': 80, 'english': 34}}

False

d = {'name':'Fahad','gender':'male','age':20}

for i in d:
  print(i,d[i])

name Fahad
gender male
age 20

Dictionary Functions#

# len/sorted
len(d)
print(d)
sorted(d,reverse=True)
max(d)

{'name': 'Fahad', 'gender': 'male', 'age': 20}

'name'

# items/keys/values
print(d)

print(d.items())
print(d.keys())
print(d.values())

{'name': 'Fahad', 'gender': 'male', 'age': 20}
dict_items([('name', 'Fahad'), ('gender', 'male'), ('age', 20)])
dict_keys(['name', 'gender', 'age'])
dict_values(['Fahad', 'male', 20])

# update
d1 = {1:2,3:4,4:5}
d2 = {4:7,6:8}

d1.update(d2)
print(d1)

{1: 2, 3: 4, 4: 7, 6: 8}

Dictionary Comprehension#

# print 1st 10 numbers and their squares
{i:i**2 for i in range(1,11)}

{1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81, 10: 100}

Data Structures

Contents

Data Structures#

1. Lists#

What are Lists#

Characterstics of a List#

Creating a List#

Accessing Items from a List#

Adding Items to a List#

Editing items in a List#

Deleting items from a List#

Operations on Lists#

List Functions#

List Comprehension#

Disadvantages of Python Lists#

Tuples#

Plan of Learning#

Creating Tuples#

Accessing Items#

Editing items#

Adding items#

Deleting items#

Operations on Tuples#

Tuple Functions#

Difference between Lists and Tuples#

Sets#

Creating Sets#

Accessing Items#

Editing Items#

Adding Items#

Deleting Items#

Set Operation#

Set Functions#

Set Comprehension#

Dictionary#

Create Dictionary#

Accessing items#

Adding key-value pair#

Remove key-value pair#

Editing key-value pair#

Dictionary Operations#

Dictionary Functions#

Dictionary Comprehension#