Roku Developer Program

Developers and content creators—a complete solution for growing an audience directly.
cancel
Showing results for 
Show  only  | Search instead for 
Did you mean: 
EnTerr
Level 11

The difference between roList and roArray? [explained]

I just realized tonight there are two different types roList and roArray - and that i don't know what the difference between them is, silly me. Normally when in doubt reading documentation helps but not this time; nothing in the forum too. So here goes, what's the difference between roList and roArray? Why are there two different types that seem to do the same thing?

The matching interfaces ifList and ifArray have bunch of methods that do the same:
ifList           ifArray
------- -------
AddTail(x) = Push(x)
RemoveTail() = Pop()
AddHead(x) = Unshift(x)
RemoveHead() = Shift()
GetTail() = Peek()
GetHead() = a[0]

And not only that but roList besides ifList implements ifArray (as well as all the other lesser interfaces of roArray) to, so all methods from both columns work on it. Curious and curiouser. I know there must have been some inner logic but it does not come to me. Does someone know?
0 Kudos
5 REPLIES 5\
NewManLiving
Level 8

Re: What's the difference between roList and roArray?

The list seems to take on a dual interface of
A linked list (head,tail). Or a stack
( push, pop). There does not appear to
Be any other reason for its duplicity
My Channels: 2D API Framework Presentation: https://owner.roku.com/add/2M9LCVC
Updated: 11-11-2015 - Completed Keyboard interface
The Joel Channel ( Final Beta )
0 Kudos
RokuMarkn
Level 8

Re: What's the difference between roList and roArray?

An roList is a linked list while an roArray is a physically contiguous array. The operations are similar but the performance is different. For example, all of the roList operations you listed are O(1), while roArray.Shift and Unshift are O(n). On the other hand, array access with [] is O(1) for roArray but O(n) for roList. roList generally uses more memory than roArray.

--Mark
EnTerr
Level 11

Re: What's the difference between roList and roArray?

"RokuMarkn" wrote:
An roList is a linked list while an roArray is a physically contiguous array. The operations are similar but the performance is different. For example, all of the roList operations you listed are O(1), while roArray.Shift and Unshift are O(n). On the other hand, array access with [] is O(1) for roArray but O(n) for roList. roList generally uses more memory than roArray.

Now i understand - much obliged for the succinct explanation!

As commentary, some of the corollaries will be:
  • Never loop over big roList with index access (for i=1 to a.count(): ... a ... )

  • In fact, don't use roList, except in a rare event that calls for it; e.g. queue (RemoveHead/AddTail) or dequeue

  • Don't use shift/unshift with big roArray; to implement stack use push/pop
0 Kudos
kbenson
Level 7

Re: What's the difference between roList and roArray?

"EnTerr" wrote:

As commentary, some of the corollaries will be:
  • Never loop over big roList with index access (for i=1 to a.count(): ... a ... )

  • In fact, don't use roList, except in a rare event that calls for it; e.g. queue (RemoveHead/AddTail) or dequeue

  • Don't use shift/unshift with big roArray; to implement stack use push/pop


the GetIndex() method (without an offset) returns the currently indexed item, and advances the pointer to the next item, sort of like Next() in many linked list implementations. That would be the appropriate way to iterate efficiently through an roList.

I only mention it because your original comparison of the ifList and ifArray interfaces didn't mention it, and neither did your commentary, so it may have confused some as to how an roList could be efficiently used.
-- GandK Labs
Check out Reversi! in the channel store!
0 Kudos
EnTerr
Level 11

Re: What's the difference between roList and roArray?

"kbenson" wrote:
the GetIndex() method (without an offset) returns the currently indexed item, and advances the pointer to the next item, sort of like Next() in many linked list implementations. That would be the appropriate way to iterate efficiently through an roList.

I only mention it because your original comparison of the ifList and ifArray interfaces didn't mention it, and neither did your commentary, so it may have confused some as to how an roList could be efficiently used.

I did not say roList cannot be iterated, i was very specific about not using numeric indexing. roList is enumerable, so one can use ifEnum.reset()/next()/isNext(), and by extension for each x in roList.

Sure, you can try iterating with ifList.ResetIndex()/GetIndex() too but this is kinda broken: how would you know when end of list is reached? GetIndex() returns invalid if (a) end of list is reached or (b) if current element=invalid, so those are indistinguishable. That smells to me.

There is also another method RemoveIndex(), which i for the life of me cannot imagine in use. It would erase the "current" element (as per ResetIndex/GetIndex iterator) but how do you know what exactly are you deleting? You cannot "peek" at current element, because GetIndex moves to the next one and then current becomes unreachable previous. So have to delete blind (by resetindex() and getIndex() count to N? that is slow). And there is no counterpart InsertIndex(el) ...

Also, why does ResetIndex() return boolean while reset() is void? I am wary of these 3 methods.
0 Kudos