Intro2CS. Tirgul 9

What We’ll Be Seeing Today

Linked lists
Debugger
Ex 9
Student enrollment system

Linked Lists

Separate the logical order of items from their physical order

Important!

The two most common mistakes regarding lists are:
Disconnecting without keeping a

Class Node

5

class Node:
def __init__(self, data=None, next=None):
self.__data = data
self.__next

class Linked List

17

class LinkedList:
def __init__(self, head=None):
self.__head = head
def

class Linked List (cont)

class LinkedList:
def __len__(self):
current = self.__head
count

Reversing a list (O(n) complexity)

class LinkedList:
def rev_list1(self):
current = self.__head
self.__head

Can we do any better? Improved implementation of linked lists

Add:
a length variable

Doubly-linked list with a tail

Sometimes it is convenient that we can

A doubly-linked list with a tail

class Node:
def __init__(self, data, prev=None,

A doubly-linked list with a tail

def add_first(self, node):
if self.__head

A doubly-linked list with a tail

def add_last(self, node):
if self.__tail

A doubly-linked list with a tail

def remove_first(self):
d = self.__head.data

A doubly-linked list with a tail

def remove_last(self):
d =

Linked Lists vs. Python’s List

Debugging with debugger

def mult_nums_in_list(numbers, mult):
for num in numbers:
num *=

Debugging with debugger

def mult_nums_in_list(numbers, mult):
for num in numbers: #should be

Add a break point

Run Debugger

List of Variables

Add variable to be watched

Step over/into/out

Step over

Step over/into/out

Step into

Step over/into/out

Step out

Ex 9

Ex 9 – Playing With Objects

You will only be given a

Ex 9 – Game Loop

We can think that everything happens in

Question from the exam 2015:

29

Q from the exam

30

Q from the exam

31

Q from the exam

32

Q from the exam

33

Q from the exam

34

Q from the exam

35

Stacks and Queues

A stack is a last in, first out (LIFO)

Queues API

Queues (LIFO): What would be the API?
what are the

Implementing Queue

class MyQueue:
def __init__(self):
self.__head = None
self.__tail = None

Adding new item to the queue

def enqueue(self, item):
if self.__tail ==

Removing an item from the queue

def dequeue(self, item):
result = self.__head.data

Student Enrollment System

We want to design a system where students could

Thinking In Interfaces

We need to think about the properties of our

Application Programming Interface

An “Application Programming Interface” (API) is a way for

Student Enrollment System - API

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,

Enrollment System Class

class EnrollmentSystem:
def __init__(self):
self.__courses = {}
self.__students =

Enrollment System Class

class EnrollmentSystem:
def __init__(self):
self.__courses = {}
self.__students = {}
…
def

Enrollment System Class

What about registration?

class EnrollmentSystem:
def __init__(self):
self.__courses = {}

What did we assume so far?

Course
get_id()
is_full()
register(sid)

Student
get_id()
add_course(cid)

Do the EnrollmentSystem care how we

Student Class

class Student:
def __init__(self, student_id):
self.__enrolled_courses = set()
self.__id = student_id
def get_id(self):
return

Course Class

class Course:
def __init__(self, course_id, course_capacity):
self.__enrolled_students = set()
self.__id = course_id
self.__capacity

Putting things together

We want to create an actual program using our

Our main loop

from student import Student
from course import Course
from system import

What’s next?

Well a lot is missing from the system
Actual implementation of