Intro2CS. Tirgul 9

1. Intro2CS

INTRO2CS
Tirgul 9

2. What We’ll Be Seeing Today

2
Linked lists
Debugger
Ex 9
Student enrollment system

3.

Linked Lists
3
Separate the logical order of items from their
physical order in memory
Each item points to the location of the next item
Dynamically expands list as needed
Linked lists may also be used to implement other
data structures, like queues and stacks
Always remember that when a link to an item is
destroyed – the item can not be reached!

4. Important!

4
The two most common mistakes regarding lists are:
Disconnecting
without keeping a pointer to the head/tail of
the list.
Trying to get the next of the trailing None.

5. Class Node

5
class Node:
def __init__(self, data=None, next=None):
self.__data = data
self.__next = next
def __str__(self):
return str(self.__data)
def get_data(self):
return self.__data
def get_next(self):
return self.__next
def set_data(self,data):
self.__data = data
def set_next(self,next):
self.__next = next

6. class Linked List

1
7
class Linked List
6
class LinkedList:
def __init__(self, head=None):
self.__head = head
def get_head(self):
return self.__head
def is_empty(self):
return self.__head == None
def add(self,new_head):
new_head.set_next(self.__head)
self.__head = new_head

7. class Linked List (cont)

7
7
class LinkedList:
def __len__(self):
current = self.__head
count = 0
while current is not None:
count = count + 1
current = current.get_next()
return count
def r_index(self, item):
return self.index_helper(self.__head, item, 0)
def index_helper(self, head, item, index):
if index >= self.__len__():
return -1
if head.get_data() == item:
return index
return self.index_helper(head.get_next(), item,
index+1)

8. Reversing a list (O(n) complexity)

8
class LinkedList:
def rev_list1(self):
current = self.__head
self.__head = None
while current is not None:
next = current.get_next()
self.add(current)
current = next

9. Can we do any better? Improved implementation of linked lists

9
Add:
a length variable
in init: self.__length = 0
update in add/remove
append?
hold a pointer to the tail
going backwards?
doubly linked list

10. Doubly-linked list with a tail

10
Sometimes it is convenient that we can add and
remove items from both ends of the linked-list (e.g. if
we want to use it both as a stack and a queue)
To support this methods we will need a doublylinked list with both head and a tail

11. A doubly-linked list with a tail

11
class Node:
def __init__(self, data, prev=None, next=None):
self.data = data
self.prev = prev
self.next = next
class DoublyLinkedList:
def __init__(self):
self.__head = self.__tail = None
self.__length = 0

12. A doubly-linked list with a tail

12
def add_first(self, node):
if self.__head is None:
# list was empty
self.__tail = node
else: #connect old head to new node
self.__head.prev = node;
node.next = self.__head
# update head
self.__head = node
self.__length +=1

13. A doubly-linked list with a tail

13
def add_last(self, node):
if self.__tail is None:
# list was empty
self.__head = node
else: #connect old tail to new node
self.__tail.next = node;
node.prev = self.__tail
# update tail
self.__tail = node
self.__length+=1

14. A doubly-linked list with a tail

14
def remove_first(self):
d = self.__head.data
self.__head = self.__head.next
if self.__head is None: # list is now empty
self.__tail = None
else: # disconnect old head
self.__head.prev.next = None
self.__head.prev = None
self.__length -=1
return d

15. A doubly-linked list with a tail

15
def remove_last(self):
d = self.__tail.data
self.__tail = self.__tail.prev
if self.__tail is None: # list is now empty
self.__head = None
else: # disconnect old tail
self.__tail.next.prev = None
self.__tail.next = None
self.__length -=1
return d;
What does this method
assume?
That the list is not empty

16. Linked Lists vs. Python’s List

16
Operation
Linked List
Python’s list
Insert at head
O(1)
O(n)
Insert at middle
O(n), O(1) given a reference
O(n)
Remove from head
O(1)
O(n)
Remove from middle
O(n), O(1) given a reference
O(n)
Find k-th element
O(k)
O(1)
Search unsorted
O(n)
O(n)
Search sorted
O(n)
O(log n)

17. Debugging with debugger

17
def mult_nums_in_list(numbers, mult):
for num in numbers:
num *= mult
return numbers
def add_to_end_of_list(numbers, addition):
for num in numbers:
new_num = num + addition
numbers.append(new_num)
return numbers
print(add_to_end_of_list(mult_nums_in_list([1,2,3],2),2))

18. Debugging with debugger

18
def mult_nums_in_list(numbers, mult):
for num in numbers: #should be for num in range(len(numbers))
num *= mult
# numbers[num] *= mult
return numbers
def add_to_end_of_list(numbers, addition):
for num in numbers:
new_num = num + addition
numbers.append(new_num) # list extends. Endless loop
return numbers
print(add_to_end_of_list(mult_nums_in_list([1,2,3],2),2))

19. Add a break point

19

20. Run Debugger

20

21. List of Variables

21

22. Add variable to be watched

22

23. Step over/into/out

23
Step over

24. Step over/into/out

24
Step into

25. Step over/into/out

25
Step out

26. Ex 9

26

27. Ex 9 – Playing With Objects

27
You will only be given a Screen class that handles
all of the graphics for you
All of the actual design is left to you!
Most of the time games (and programs) are event
driven:
Move right/left if a key pressed.
Fire when requested to.
Reduce HP if got shot.
We will take a more sequential approach.

28. Ex 9 – Game Loop

28
We can think that everything happens in the
same time!
All objects (ship, asteroids, torpedoes) move
one after the other.
Only then we fire/accelerate (if requested)
More in the exercise.
Note: Try to implement it step by step (as
described in the exercise description).

29. Question from the exam 2015:

29

30. Q from the exam

30

31. Q from the exam

31

32. Q from the exam

32

33. Q from the exam

33

34. Q from the exam

34

35. Q from the exam

35

36. Stacks and Queues

36
A stack is a last in, first out (LIFO) data structure
Items
are removed from a stack in the reverse order from
the way they were inserted
A queue is a first in, first out (FIFO) data structure
Items
are removed from a queue in the same order as they
were inserted

37. Queues API

37
Queues (LIFO): What would be the API?
what are the functions required in order to use
it?
class MyQueue:
def __init__(self):
def enqueue(self,item):
def dequeue(self):
def get_size(self):

38. Implementing Queue

38
class MyQueue:
def __init__(self):
self.__head = None
self.__tail = None
self.__size = 0
def get_size(self):
return self.__size
def is_empty(self):
if self.__size > 0:
return False
else:
return True

39. Adding new item to the queue

39
def enqueue(self, item):
if self.__tail == None:
self.__head = Node(item)
self.__tail = self.__head
else:
# adding new item to the end of the list
self.__tail.next = Node(item)
self.__tail = self.__tail.next
self.__size += 1

40. Removing an item from the queue

40
def dequeue(self, item):
result = self.__head.data
self.__head = self.__head.next
if self.__head == None:
self.__tail = None
self.__size -= 1
return result

41. Student Enrollment System

41
We want to design a system where students could
register to courses
What is the most basic expected behavior from such
a system?
List all courses
Enroll into a course
Withdraw from a course

42. Thinking In Interfaces

42
We need to think about the properties of our
enrollment class:
Available courses?
Map students to courses?
Keep track of registered students?
Do we need to think on how we design
students/courses at this stage?

43. Application Programming Interface

43
An “Application Programming Interface” (API) is a
way for us to expose the behavior of our objects
without the actual way it was implemented.
Consider the list construct:
The list object exposes a method called “sort” –
does it matter which sort algorithm is used?
Most of the time what interest us is the final result.

44. Student Enrollment System - API

44
class EnrollmentSystem:
__init__(self)
add_student(self, student):
add_course(self, course)
get_available_courses(self)
register_student(self, student, course_id)
Class Student:
get_id()
add_course(self, cid)
Class Course
get_id()
is_full()
register(self, sid)

45. Enrollment System Class

45
class EnrollmentSystem:
def __init__(self):
self.__courses = {}
self.__students = {}
What are our assumptions?
def add_student(self, student):
# How can we map a student to a student object?
self.__students[ student.get_id() ] = student
def add_course(self, course):
# How can we map a course to a course object?
self.__courses[ course.get_id() ] = course

46. Enrollment System Class

46
class EnrollmentSystem:
def __init__(self):
self.__courses = {}
self.__students = {}
…
def get_available_courses(self):
courses = []
for course_id, course in self.__courses.items():
if not course.is_full():
courses.append( ( course_id, course.get_name() ) )
return courses
What are our assumptions?

47. Enrollment System Class

47
What about registration?
class EnrollmentSystem:
def __init__(self):
self.__courses = {}
What are our assumptions?
self.__students = {}
…
def register_student(self, student, course_id):
if course_id in self.__courses:
registered = self.__courses[ course_id ].register( student.get_id()
if registered:
student.add_course( course_id )
return registered

48. What did we assume so far?

48
Course
get_id()
is_full()
register(sid)
Student
get_id()
add_course(cid)
Do the EnrollmentSystem care how
we implement these methods?

49. Student Class

49
Lets implement our basic student class
class Student:
def __init__(self, student_id):
self.__enrolled_courses = set()
self.__id = student_id
def get_id(self):
return self.__id
def add_course(self, course_id):
self.__enrolled_courses.add( course_id )

50. Course Class

50
class Course:
def __init__(self, course_id, course_capacity):
self.__enrolled_students = set()
self.__id = course_id
self.__capacity = course_capacity
def get_id(self):
return self.__id
def register(self, student_id):
if student_id not in self.__enrolled_students and not self.is_full():
self.__enrolled_students.add(student_id)
return True
return False
def is_full(self):
return self.__capacity == len(self.__enrolled_students)

51. Putting things together

51
We want to create an actual program using our
enrollment system
A user should be able to:
Add courses to the system
Register users to courses

52. Our main loop

52
from student import Student
from course import Course
from system import EnrollmentSystem
def get_user_selection():
return int(input(“Enter selection:”) )
def main_loop():
es = EnrollmentSystem()
while True:
option = get_user_selection()
perform_selction(option, es)
…
def perform_selection(option, es):
if option == 1:
print_courses(es)
elif option == 2:
register_new_student(es)
elif option == 3:
create_new_course(es)
elif option == 4:
register_student_to_course(es)
else:
print(“Please insert a valid option”)

53. What’s next?

53
Well a lot is missing from the system
Actual implementation of the methods
Withdrawing from a course
Removing a course
Course info?
…
We can always come back and extend our system

54. To OOP or not to OOP? – A word on being cautious

54
Not everything should be solved by new objects.
You should always think about the overhead of
working with them.
For example, should you create a class to represent
2D points or could you just use tuples?