deep in the forth mines with hacked together forth, in a hacked together virtual machine, running in a hacked together web-based forth IDE.

the next video approaches

and then if you try to add an element that won't fit... it secretly creates another array 2-3x the size and copies all of your elements over

the problem is — accessing elements means scanning the list until you find the item you want. this is O(n), where the array was O(1). a little worrying for a general purpose data structure everyone is using all of the time (and which people will probably embed in other loops)

you can then play with the links to prepend, append, insert, splice, reverse, or most anything you like — all with quite good performance

the classic answer to this inflexibility is a data structure called a linked list, in which you store pairs of a value and a link to the next record

the snag is that you need to know the element size and array length up front. element size you can get around using pointers, but array length is harder. if your array is hard up against other important data, you can't extend it.

the ability to calculate the location of each item, rather than having to search for it, makes arrays very fast for access and storage. and so long as you know every size up front you can use it to store surprisingly complex types too, like 2d arrays or even trees

in some ways the 'perfect' list is an array.

you take a fixed number of elements of a fixed size and store them one after the other in memory. to access an element you take the start address and add the element size multiplied by the index

new video! this datatype → [1, 2, 3] ← is a bit of a marvel. it can store items of any size, grow to any length, rarely causes performance issues, and almost every modern language has one. what is it, really? and how does it work?

yes i have created my own virtual machine with its own assembly language to implement my own linked lists for the next video