CSC148H1 Lecture Notes - Lecture 5: Linked List, Init
1
CSC148H1 Full Course Notes
Verified Note
1 document
Document Summary
In the previous week, we saw that the standard array-based python implemention of lists has some drawbacks: inserting and deleting requires shifting of many elements in the array. For example, we saw that inserting and deleting at the front of a python list takes time proportional to the length of the list, because every item in the list needs to be shifted by one spot. This (cid:449)eek, (cid:449)e"(cid:396)e goi(cid:374)g to stud(cid:455) a(cid:374)othe(cid:396) i(cid:373)ple(cid:373)e(cid:374)tio(cid:374) of lists (cid:449)hi(cid:272)h has diffe(cid:396)e(cid:374)t effi(cid:272)ie(cid:374)(cid:272)(cid:455) p(cid:396)ope(cid:396)ties: the linked list. Note that in contrast to last week, when we looked at the stack and queue adts, this week we are focusing on an alternate implementation of an existing adt, the familiar list. Thus our goal is to create a new class that behaves exactly the same as existing lists in python, changing only what goes on behind the scenes. On the last exercise, you explored the peoplechain class.
