Ufdjrw

Why did the rest of the Eastern Bloc not invade Yugoslavia?

Why did the IBM 650 use bi-quinary?

51k Euros annually for a family of 4 in Berlin: Is it enough?

Should I discuss the type of campaign with my players?

Extract all GPU name, model and GPU ram

Using et al. for a last / senior author rather than for a first author

Echoing a tail command produces unexpected output?

At the end of Thor: Ragnarok why don't the Asgardians turn and head for the Bifrost as per their original plan?

Is it true that "carbohydrates are of no use for the basal metabolic need"?

What's the purpose of writing one's academic biography in the third person?

How do I stop a creek from eroding my steep embankment?

Denied boarding although I have proper visa and documentation. To whom should I make a complaint?

Seeking colloquialism for “just because”

How does the particle を relate to the verb 行く in the structure「A を + B に行く」?

Why was the term "discrete" used in discrete logarithm?

Book where humans were engineered with genes from animal species to survive hostile planets

How to call a function with default parameter through a pointer to function that is the return of another function?

porting install scripts : can rpm replace apt?

What is the role of the transistor and diode in a soft start circuit?

Storing hydrofluoric acid before the invention of plastics

Can a non-EU citizen traveling with me come with me through the EU passport line?

Identify plant with long narrow paired leaves and reddish stems

When do you get frequent flier miles - when you buy, or when you fly?

How to bypass password on Windows XP account?

Array-based Linked List: How to deamortize deletion?

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty height:90px;width:728px;box-sizing:border-box;

1

Suppose we implement a linked list using an array. Let's say each element consists of a key and the index of the next item.

Now insertion and deletion are O(1) amortized, if I'm not mistaken. If the array becomes full or too empty, we need to allocate a new one of double or half the size.

We could deamortize insertion by using a resizable array as specified in Resizable Arrays in Optimal Time and Space. In short, instead of one huge array we have smaller arrays, and as the data set grows, smaller arrays are gradually transformed into larger arrays. It has some pretty neat bounds on the running time of each operation.

But now, how might we deamortize deletion?

This is as far as I got: We can maintain a "free-list". Besides the regular "head" index, we would track the first free index, which in turn points to the next free index, and so on. Basically, the structure consists of two intermingled linked lists, namely the data list and the free list.

However, after a lot of deletions, we could be sitting with an array full of "holes". Rebuilding the entire thing to half-size all at once might not be feasible for large data sets.

Can we deamortize deletion?

arrays data-structures linked-list amortization

share|improve this question

asked Mar 8 at 17:32

TimoTimo

3,26822636

add a comment | 

1

Suppose we implement a linked list using an array. Let's say each element consists of a key and the index of the next item.

Now insertion and deletion are O(1) amortized, if I'm not mistaken. If the array becomes full or too empty, we need to allocate a new one of double or half the size.

We could deamortize insertion by using a resizable array as specified in Resizable Arrays in Optimal Time and Space. In short, instead of one huge array we have smaller arrays, and as the data set grows, smaller arrays are gradually transformed into larger arrays. It has some pretty neat bounds on the running time of each operation.

But now, how might we deamortize deletion?

This is as far as I got: We can maintain a "free-list". Besides the regular "head" index, we would track the first free index, which in turn points to the next free index, and so on. Basically, the structure consists of two intermingled linked lists, namely the data list and the free list.

However, after a lot of deletions, we could be sitting with an array full of "holes". Rebuilding the entire thing to half-size all at once might not be feasible for large data sets.

Can we deamortize deletion?

arrays data-structures linked-list amortization

share|improve this question

asked Mar 8 at 17:32

TimoTimo

3,26822636

add a comment | 

Suppose we implement a linked list using an array. Let's say each element consists of a key and the index of the next item.

Now insertion and deletion are O(1) amortized, if I'm not mistaken. If the array becomes full or too empty, we need to allocate a new one of double or half the size.

We could deamortize insertion by using a resizable array as specified in Resizable Arrays in Optimal Time and Space. In short, instead of one huge array we have smaller arrays, and as the data set grows, smaller arrays are gradually transformed into larger arrays. It has some pretty neat bounds on the running time of each operation.

But now, how might we deamortize deletion?

This is as far as I got: We can maintain a "free-list". Besides the regular "head" index, we would track the first free index, which in turn points to the next free index, and so on. Basically, the structure consists of two intermingled linked lists, namely the data list and the free list.

However, after a lot of deletions, we could be sitting with an array full of "holes". Rebuilding the entire thing to half-size all at once might not be feasible for large data sets.

Can we deamortize deletion?

arrays data-structures linked-list amortization

share|improve this question

asked Mar 8 at 17:32

TimoTimo

3,26822636

share|improve this question

asked Mar 8 at 17:32

TimoTimo

3,26822636

share|improve this question

asked Mar 8 at 17:32

TimoTimo

3,26822636

asked Mar 8 at 17:32

TimoTimo

3,26822636

asked Mar 8 at 17:32

TimoTimo

3,26822636