Tilted Forum Project Discussion Community - View Single Post

n0nsensical · 02-21-2009, 05:09 PM

Okay I just rewrote the answer to part (a) then realized that was exactly what Yakk already said... Heh. The null thing is even worse because then you need to rewrite all your code to check for nulls whenever you iterate or dereference an array (and you WILL forget that little nested for loop that causes your program to randomly crash and burn), and you can't have a valid value equal to null in the array.

For the sorted array it's a little trickier because you need to move things around so it's still dependent on the size of the array. I don't believe it's technically possible to do that for any given sorted array without resorting to even worse hackery which kind of defeats the whole purpose of using one. If you really need to do deletions in O(1) time maybe you are using the wrong data structure.

I would be really curious to find out the instructor's 'answer' to part (b), but I don't imagine cheerios will be back to tell us.

A hash table supports deletion in O(1) time, but by most definitions a hash table is not an array. There are exceptions such as in PHP where an 'array' is actually implemented as a hash table, but a PHP array is quite different from a traditional low-level array.

02-21-2009, 05:09 PM	#12 (permalink)
n0nsensical Junkie Location: San Francisco	Okay I just rewrote the answer to part (a) then realized that was exactly what Yakk already said... Heh. The null thing is even worse because then you need to rewrite all your code to check for nulls whenever you iterate or dereference an array (and you WILL forget that little nested for loop that causes your program to randomly crash and burn), and you can't have a valid value equal to null in the array. For the sorted array it's a little trickier because you need to move things around so it's still dependent on the size of the array. I don't believe it's technically possible to do that for any given sorted array without resorting to even worse hackery which kind of defeats the whole purpose of using one. If you really need to do deletions in O(1) time maybe you are using the wrong data structure. I would be really curious to find out the instructor's 'answer' to part (b), but I don't imagine cheerios will be back to tell us. A hash table supports deletion in O(1) time, but by most definitions a hash table is not an array. There are exceptions such as in PHP where an 'array' is actually implemented as a hash table, but a PHP array is quite different from a traditional low-level array. __________________ "Prohibition will work great injury to the cause of temperance. It is a species of intemperance within itself, for it goes beyond the bounds of reason in that it attempts to control a man's appetite by legislation, and makes a crime out of things that are not crimes. A Prohibition law strikes a blow at the very principles upon which our government was founded." --Abraham Lincoln Last edited by n0nsensical; 02-21-2009 at 06:31 PM.. Reason: i am all fucked up!