Indexed Linked List

Indexed Linked List is an improved version of Single Linked List that enable random access (can only found on Array) and fast item splicing (can only found on Linked List). We can use it for prioritized queues where items often got inserted / removed at arbitrary positions. Some popular applications are loading queue manager (sort by priority), delayed tween list (sort by delay), or custom Event Dispatcher (addListeners with priority).

I. THE GENERAL IDEA :

We have a single linked list (to cut memory cost 30% compared to double linked list), every item has a {.next} pointer point to the next item in the list. Every item has a {.priority} property to be used as mandatory sort term, a {.time} stamp for secondary sort term, this way, every item is unique and can be compared to each other without equality worries.

Besides the normal linked list implementation we have another Array {_grid} to keep track of pivots items at some rough space {_gridSize}, that means for every roughly {_gridSize} items in the list we save an item into the {_grid}. This kind of indexing will enable binary search for position of any item in the list which means fast random access to items (fixed (and small) time to reach any item in the list). Of course, this won’t beat Array’s random access, but it’s fast enough for practical use !

II. THE LAZY PIVOT CREATION STRATEGY :

We don’t need to refresh the pivot table for every item insert / remove as it’s not efficient.  As a new pivot can be introduced for every {_gridSize} items added, we only need to refresh the {_grid} for every {_gridSize } items added to the list. Besides that simple check, we can add others checks for special case when new items are always added to the last position (and this seems to be the most popular case in practice) :  we will only need to push new pivots  items into the {_grid} instead of refresh the whole list.

When we iterate through the list using iterStart(), iterNext(), the indexes and pivots will also be updated if needed.

III. THE LAZY DIRTY MARKING / CLEANING STRATEGY :

We divide the _dirty status into 3 states :

  • NONE – no dirty at all, all items’ indexes are correct
  • SIMPLE – items comes after dirty position {_dirty} have the same index offset {_offset}
  • COMPLEX – items comes after _dirty have non-ordered indexes (arbitrary).

So, first thought in your mind : Why should we care about SIMPLE or COMPLEX dirty state instead of just a simple boolean _dirty flag, it’s dirty anyway, what’s the different ? Well, if you have a closer look about SIMPLE you might see that we can know the correct index immediately by a simple check : if the items is before _dirty, its index is correct, if not, the index should be + an offset. So we don’t need to update every _dirty items for every changes and this will improve the performance very much.

Now, second question might raise up : But the SIMPLE case is rare, as we insert/remove two (or more) items into the NONE dirty list, we get COMPLEX dirty and there are no use for SIMPLE at all, right ?  No, it’s not that simple, when a new  item {_new} is insert into the list, we will update the items between {_new} and {_dirty}. After that, we update the _dirty and _offset to the correct values. This way, the list will be at the SIMPLE state almost all the time.

Third question : What if the space between the {_dirty} and {_new} is too large, might be approximated to the length of the whole list ? Isn’t that mean we need to travel through the whole list when that item being inserted ? Well, in the implementation we have a range check, if the number of items need to be updated is more than some specific value {_maxUpdate} we just skip the update and change the _dirty state to COMPLEX. We also have another refined check to keep the list at SIMPLE dirty state for this case : if the {_dirty} or the {_new} is really near to the last item in the list {_last} we will update items from it (the item that is very near to {_last}) to {_last} instead of update the items between {_dirty} and {_new}. We can see that we will never need to update more than {_maxUpdate} items for every item insert / remove

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s