As I understand BASIC had line numbers because at the time you had to use a line editor to input your program. It allowed you to do something like this:
20 END
10 PRINT "HELLO WORLD"
This program would print "HELLO WORLD". My question is how did BASIC allow you to enter lines this way? How were they stored in memory? I suppose it was a map of line numbers and pointers to lines themselves which was updated every time you input a line. But this map would have to be sorted before running a LIST/RUN command. Is that so? If not then how exactly did BASIC store commands in the memory?
I guess each Basic implementation used a particular approach.
The Basic I grew up with was a Microsoft Basic running on the MSX computer. According to "The MSX Red Book" which I read avidly at the time, the MS-Basic actually used a linear list.
Each Basic line was stored as a pointer to the next line, followed by its actual line number in binary form, followed by the tokenized version of the line and followed by a null char; something like this:
Address | Content
8000 | 8009 -- next line
8002 | 10 -- this line number
8004 | .... -- opcodes for each instruction in the line
... | ...
8007 | ...
8008 | Null -- terminator
8009 | ... -- the next line
Despite the fact that the lines where a linked list, the Basic interpreter didn't take advantage of that. Each line was physically stored in linear succession.
As you can imagine, inserting and deleting lines in the middle of an existing program represented a lot of work. If new lines where inserted between existing ones the subsequent lines were moved up in memory to make room for the new one(s). Likewise, deleting lines mid-program would cause the subsequent lines being moved down in memory to fulfill the space left by the removed one(s). This moving up and down the memory meant that all those links had to be updated for each line moved.