There are two advantages of lists, however: you can add elements to a list without modifying the original list or ever having to reallocate it, and garbage coll

There are two advantages of lists, however: you can add elements to a list without modifying the original list or ever having to reallocate it, and garbage collection never requires defragmentation as all lists (except NIL) are implemented as exactly two words, the head and a pointer to the tail. If you're processing huge quantities of data or writing games, the speed hit you take from frequent cache misses probably means you should avoid lists whenever you can. You should certainly avoid them in non-garbage collecting languages such as C where you have the additional inconvenience of manual memory management of two word data structures. But those kinds of programs are atypical - most involve frequent user interaction. Almost all languages (including Lisp) have contiguous data structures and these will often fit the data better. Also, lists which aren't built up a cell at a time will be CDR-coded if the language implementation supports that.