deleting elements in an array...
 

Ok, I'm working on my algorithms homework, and I come across this problem:

now, I'm honestly baffled and the chapter has nothing to say about array element deletion. Because in Data Structures they tought us that array's downside was that they were slow to delete and insert into the middle of the array, because a new array had to be created, and every value had to be copied in, with the correct value added or left out. now, this question implies that is not true, and I have no clue how that could be. Any hints?

You mean a regular array, as in the C++ declaration
?

You don't normally delete elements from an array.
I don't know of any data structure that supports deletion in O(1) time.

I mean a hash table can do that if the set of keys is the same size as the potential set of elements. But that isn't much different then deleting from a regular array.

yeah, i mean a regular array. that's why this has me baffled. 'cuz you don't delete out of an array 'cuz it's a waste of time!

Ha, there was a CS major explaining this to someone in the library this afternoon. I didnt join in because I dont know much about programming, but IIRC, she said just what you did--you cant really delete them, you have to make a new array minus the element you wish to delete, or, if you can, just set the element equal to null.

Creating a new array and copying is an O(n) operation so that can't be it. Arrays don't have null values, unless they are arrays of pointers, which isn't specified.

Question = nonsensical.

Well, I agree that the question doesn't seem to make a lot of sense.

The closest thing I can come to that's a "real" answer (i.e., not just 'set the array element to null') is this:

for(j = i; j < array.length - 1; j++) {
array[j] = array[j + 1];
}
array[array.length] = null;

Although in a worst-case analysis this is in fact O(n), it doesn't depend directly on the length of the array in the same way that copying all the elements does.

Be sure to let us know what the answer is!

i'm thinking hash tables here.

the actual table being a linked list which keeps track of the previous and the next elements.

if the hash table is organized by element #, then u should be able to go into x element and remove it.

same thing with the b part.

well, I went in to ask, but our department is going through acredditation this semester and the entire dept is out for meetings the whole day. :( I am NOT amused. So, your (and my) answer will have to wait until monday.

Shortens the "length" of the array by one, deleting the ith element.

The actual memory allocated to the array might be the same, but 1 less element is used, and the ith element has been deleted/overwritten.

In levels of increasing incorrectness:
1> it can't be done.
2> use markers for "unused value".
3> Implement a hash table instead of an array. Takes practical constant time, theoretical (when you pay attention to the dots on the i's) lg n time.
4> Implement a skip list instead of an array. Takes probabalistic-average lg n time.

If you could solve both problems independently:
a) just set array[i ] to zero/null.
b) use linked lists (pointers). simply drop item i, have item [i-1] point to item [i+1].

To solve both problems at once seems impossible. With a normal array, problem b seems impossible, because sorting an array takes n steps at least. With linked lists, problem a seems impossible, because deleting item i is dependent on the size of n (you have to search for the item).

I got the big olde book of data structures, which tells me that no matter which data structure you use, either a or b depends on the array size n in some way. The most efficient option I saw was a heap (https://users.cs.jmu.edu/bernstdh/we...troduction.php).

Really? 5-year-old programming homework solutions?

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. :lol: 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.

Apparently. For a banned member, no less.

...five YEARS ago!!!

I have to admit. I miss cheerios a lot.

I remember when she got banned, I couldn't figure it out, hell I still don't know.