CMPT 225 Lecture Notes - Lecture 2: Call Stack, Linked List, Binary Logarithm
17 May 2013
School
Department
Course
Professor
Document Summary
If the stack had 256 things in it, does a lot more (256 times), as it needs to copy all those things into a new array one by one. Does constant amount of work unless it"s full (in which case is linear) Pop function does constant amount of work (just decrements top and returns something) Worth thinking about for every datastructure you create. Functions need space in call stack for variables and line number. Most languages use call stack to implement function calling. Method called, line number and other data pushed onto cs. Functions returned values that were assigned to variables in other functions, but does not change the amount of memory allocated to them. Example - inserting something into a sorted list. Next week"s lab is compulsory, will demonstrate how inefficient our insert is for sortedlist. Order of items in stack is not based on values of items, is based on order in which they were inserted.
