One of the most common data structure in Flash is Array, which provides a fast way to construct a list of data items with compact memory cost. This data structure is working fine and rather fast, except for some operations, for example, insert / remove items randomly (splice) or pushing things to the beginning of the Arrays (unshift). Because of the compact memory implementation, all the existed items after the insert position will need to be migrated. With o(n) complexity, operated time goes up linearly with the number of items. And it’s just the same for Vector, although Vector is way faster than Array as there are no dense checking and converting between Dense Array & Hash Table (there are more reasons ? ). In short : Array is slowing down by items migration
A rather popular solution is using Linked List – either double or single. Linked list has ability to add and remove items very fast at an arbitrary position as no item is being migrated. Double linked list cost more memory (~ 1.5x ) and a bit slower than single Linked List (which, consume 2x more memory than Array) but it allows traversing in both direction. For some operations, the doubles run faster (~ 2x faster) than single ones. But as we won’t have random access to items by numeric indexes like Arrays, it’s really slow if we need to skip forward / backward to get to some random position. In short : Linked List is slowed down by skipping to specific position Continue reading