I7: What are lists?

Authoring Inform 7
1

I’ve got to realize that I work quiet a lot with lists while not really knowing what a list itself is. What kind of data structure am I dealing with here, a linked list or something? Arrays? Is there maybe any more in-depth reading material I can dig through?

2

The short answer is that lists are just what they sound like: a sequence of elements. They are similar to arrays but typically lack the random access feature.

I recommend Lists and Lists. It changed my life, and will teach you how powerful such a simple data structure can be.

3

An I7 list is a variable-size array.

4

Would it be possible to use the Glulx acceleration opcodes (@linearsearch, etc.) on I7 lists?

5

In general, no, because Inform’s low-level memory-handling code can split up a block into several memory segments.

6

Couldn’t @linkedsearch be used for that though? (Not saying it could as it’s currently implemented, but that if the implementation was altered…)

7

Yes, if you changed the implementation, it could do something that’s not currently possible. This is always a true statement. :slight_smile:

8

@bcressey
Wow, that was both fun and educational! Thanks for broadening my horizon :smiley:

@zarf
I take that, if you add a new element to a list, Inform creates a new array and copies the entire content of the old array + the new element into it? That would explain why the adding gets more costly the longer the list gets. Or is the underlying algorithm smarter than that?

9

They’re more like a linked list of traditional arrays, which you think of as one long array. You can read all about the technical details here and here. If you’re seeing slowness, it’s probably from the routine BlkSize—there was some discussion on that here.