Singly-linked list in Lisp
I asked myself why John McCarthy did not use an array. By coding in Lisp for months, I come up with some (maybe not so correct) answers.
I suppose that he wants to support recursion and immutability at the same time without need to copy or clone the whole data structure.
For array, the contiguous unit in the memory is the next element.
Because normally we cannot make sure that contiguous memory of the array is free. In order to add new element, the array has to be modified so it is mutable, in case there are some rooms left in the array; or new array has to be created with the new element.
Singly-linked list is different from array. The existing list can be left unmodified. We can just create a new element with a pointer that points to existing one; so nothing is modified after it has been created.
Even doubly-linked list does not have this property since there is a point-back to new element in the existing list, which has be modified while adding new element.
In order to insert a new list like shown in the figure, for Lisp, we can use the command like: (cons “donkey” existing-list), which can be used as return value of a function.
Usually recursive functions are called more often then non-recursive one because it can be used in place of loop. So it is usually not effective to copy or clone the whole structure every time a recursive function has been called.
In brief, since new singly-linked list with a new element can be constructed without making the existing one become mutable or copying the whole structure. It is suitable to be used in recursive functions, which are tended to be called very often.
