I’m not really talking about access as the computer sees it: most of the code I write that processes strings ends up doing things like splitting at new lines an

I’m not really talking about access as the computer sees it: most of the code I write that processes strings ends up doing things like splitting at new lines and stripping off the trailing space of each line. Or getting the length of the string or similar things that require efficient access to a semi-arbitrary offset into the string. For the type of string processing code I find myself writing, linked lists are the wrong data structure because they tend to turn O(n) algorithms into O(n^2) ones: this can be mitigated by things like skip-lists, and is complicated by things like Unicode. But, personally, I tend to think that the biggest issue is not the performance impact of non-local storage of the string’s contents (which can be mitigated by techniques like cdr-coding). The problem is that string processing code, in my experience, tends to assume getting a predetermined offset into the string is relatively low cost.