The linked lists were developed in 1955-56 by James Fazzini, Cliff Shaw and Herbert Simon at RAND Corporation as the main data structure for language information processing (IPL). IPL was used by the authors to develop several programs related to artificial intelligence, including the General Theory Machine, the general troubleshooting, software and chess. Was published in IRE Transactions on Information Theory in 1956, and at various conferences between 1957-1959, including Proceedings of the Western Joint Computer in 1957 and 1958, and Information Processing (Procendents of the first international conference of information processing in the UNESCO) in 1959. The current classic diagram, which consists of blocks representing list nodes with arrows pointing to successive nodes in the list, appeared in Programming the Logic Theory Machine, Newell and Shaw. Newell and Simon were recognized by the ACM Turing Award in 1975 for ‘basic contributions to artificial intelligence, the psychology of human knowledge and the processing of lists.
The problem of translation of natural language processing led Victor Yngve from Massachusetts Institute of Technology (MIT) to use linked lists as data structure in its Committee, programming language for computers, which investigated in the field of Computational Linguistic. A report of this language, entitled ‘A programming language for mechanical translation “appeared in Mechanical Translation in 1958.
LISP, lists the main processor, was created in 1958. One of the major data structures of LISP is the linked list.
Around 60, the utility of the linked lists and languages that use these structures as its main data representation was well established. Bert Green of MIT Lincoln Laboratory, published a study entitled “Computer languages for symbol manipulation in IRE Transaction on Human Factors in Electronics in March 1961 outlining the advantages of linked lists. A subsequent article, A Comparison of list-processing computer languages by Bobrow and Raphael, appeared in Communications of the ACM in April 1964.
Many operating systems developed by Technical Systems Consultants (originally from West Lafayette Indiana and then Raleigh, North Carolina) using simple linked lists as file structures. A directory entry pointing to the first sector of a file and resulted in portions of the location of the file through pointers. Systems using this technique included Flex (for Motorola 6800 CPUs), mini-Flex (the same CPU) and Flex9 (for Motorola 6809 CPUs). A variant developed by TSC is marketed Smoke Signal Broadcasting in California, using doubly linked lists in the same way.
TSS operating system, developed by IBM for the System 360/370 machines, using a doubly linked list for the catalog file system. The directory structure was similar to Unix, where a directory could contain files and / or other directories that could be extended to any depth. A utility was created to fix problems after a system failure since modified portions of the catalog files that were in memory at times when the failure occurred. The problems were identified by comparison of pre and post links for consistency. If the next link was corrupt and the previous link of the node was found infected, the link was later assigned to the node with the link above.
Understanding SQL and Java Together : A Guide to SQLJ, JDBC, and Related Technologies (The Morgan Kaufmann Series in Data Management Systems) by Jim Melton and Andrew Eisenberg (Paperback – May 2000)
