Does anyone know when the list data structure was mentioned in computer programming/algorithms? Who gave birth to this list concept?

  • $\begingroup$ What do you mean by list? Is it this list? $\endgroup$
    – John L.
    May 4 '19 at 21:43

Knuth gives a good overview on the history of lists and linked data structures. From The Art of Computer Programming, Volume I, Section 2.6:

Linked memory techniques were really born when A. Newell, J. C. Shaw, and H. A. Simon began their investigations of heuristic problem-solving by machine.


The first use of linked lists in their modern form seems to have been by Peter Luhn in 1953, when he implemented a chaining-based hash table on the IBM 701 machine.

Linked lists are often misattributed as being due to Newell et al. during their development of the IPL language (an early version of lisp), but that wasn't until 1956. The IPL language did popularize linked lists, however. It just didn't invent them.

A good reference is pages 457 and 458 of Knuth's Art of Computer Programming Vol 1.


List processing is simultaneously three things in the development of computer science. (1) It is the creation of a genuine dynamic memory structure in a machine that had heretofore been perceived as having fixed structure. It added to our ensemble of operations those that built and modified structure in addition to those that replaced and changed content. (2) It was an early demonstration of the basic abstraction that a computer consists of a set of data types and a set of operations proper to these data types, so that a computational system should employ whatever data types are appropriate to the application, independent of the underlying machine. (3) List processing produced a model of designation, thus defining symbol manipulation in the sense in which we use this concept in computer science today.

Computer Science as Empirical Inquiry: Symbols and Search (1975 Alan Turing Award Lecture - Allen Newell and Herbert A. Simon)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.