Linked List - History


Linked lists were developed in 1955-56 by Allen Newell, Cliff Shaw and Herbert A. Simon at RAND Corporation as the primary data structure for their Information Processing Language. IPL was used by the authors to develop several early artificial intelligence programs, including the Logic Theory Machine, the General Problem Solver, and a computer chess program. Reports on their work appeared in IRE Transactions on Information Theory in 1956, and several conference proceedings from 1957 to 1959, including Proceedings of the Western Joint Computer Conference in 1957 and 1958, and Information Processing (Proceedings of the first UNESCO International Conference on Information Processing) in 1959. The now-classic diagram consisting of blocks representing list nodes with arrows pointing to successive list nodes appears in "Programming the Logic Theory Machine" by Newell and Shaw in Proc. WJCC, February 1957. Newell and Simon were recognized with the ACM Turing Award in 1975 for having "made basic contributions to artificial intelligence, the psychology of human cognition, and list processing". The problem of machine translation for natural language processing led Victor Yngve at Massachusetts Institute of Technology (MIT) to use linked lists as data structures in his COMIT programming language for computer research in the field of linguistics. A report on this language entitled "A programming language for mechanical translation" appeared in Mechanical Translation in 1958.

LISP, standing for list processor, was created by John McCarthy in 1958 while he was at MIT and in 1960 he published its design in a paper in the Communications of the ACM, entitled "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I". One of LISP's major data structures is the linked list. By the early 1960s, the utility of both linked lists and languages which use these structures as their primary data representation was well established. Bert Green of the MIT Lincoln Laboratory published a review article entitled "Computer languages for symbol manipulation" in IRE Transactions on Human Factors in Electronics in March 1961 which summarized the advantages of the linked list approach. A later review article, "A Comparison of list-processing computer languages" by Bobrow and Raphael, appeared in Communications of the ACM in April 1964.

Several operating systems developed by Technical Systems Consultants (originally of West Lafayette Indiana, and later of Chapel Hill, North Carolina) used singly linked lists as file structures. A directory entry pointed to the first sector of a file, and succeeding portions of the file were located by traversing pointers. Systems using this technique included Flex (for the Motorola 6800 CPU), mini-Flex (same CPU), and Flex9 (for the Motorola 6809 CPU). A variant developed by TSC for and marketed by Smoke Signal Broadcasting in California, used doubly linked lists in the same manner.

The TSS/360 operating system, developed by IBM for the System 360/370 machines, used a double linked list for their file system catalog. The directory structure was similar to Unix, where a directory could contain files and/or other directories and extend to any depth. A utility flea was created to fix file system problems after a crash, since modified portions of the file catalog were sometimes in memory when a crash occurred. Problems were detected by comparing the forward and backward links for consistency. If a forward link was corrupt, then if a backward link to the infected node was found, the forward link was set to the node with the backward link. A humorous comment in the source code where this utility was invoked stated "Everyone knows a flea collar gets rid of bugs in cats".

Read more about this topic:  Linked List

Other articles related to "history":

Spain - History - Fall of Muslim Rule and Unification
... The breakup of Al-Andalus into the competing taifa kingdoms helped the long embattled Iberian Christian kingdoms gain the initiative ... The capture of the strategically central city of Toledo in 1085 marked a significant shift in the balance of power in favour of the Christian kingdoms ...
Xia Dynasty - Modern Skepticism
... The Skeptical School of early Chinese history, started by Gu Jiegang in the 1920s, was the first group of scholars within China to seriously question the traditional story of its early history "the later the time ... early Chinese history is a tale told and retold for generations, during which new elements were added to the front end" ...
Voltaire - Works - Historical
... History of Charles XII, King of Sweden (1731) The Age of Louis XIV (1751) The Age of Louis XV (1746–1752) Annals of the Empire – Charlemagne, A.D ... (1754) Essay on the Manners of Nations (or 'Universal History') (1756) History of the Russian Empire Under Peter the Great (Vol ... II 1763) History of the Parliament of Paris (1769) ...
History of Computing
... The history of computing is longer than the history of computing hardware and modern computing technology and includes the history of methods intended for pen and paper or for chalk and slate, with ...
Casino - History of Gambling Houses
... gambling in some form or another has been seen in almost every society in history ... France and Elizabethan England, much of history is filled with stories of entertainment based on games of chance ... In American history, early gambling establishments were known as saloons ...

Famous quotes containing the word history:

    Perhaps universal history is the history of the diverse intonation of some metaphors.
    Jorge Luis Borges (1899–1986)

    ... in a history of spiritual rupture, a social compact built on fantasy and collective secrets, poetry becomes more necessary than ever: it keeps the underground aquifers flowing; it is the liquid voice that can wear through stone.
    Adrienne Rich (b. 1929)

    Boys forget what their country means by just reading “the land of the free” in history books. Then they get to be men, they forget even more. Liberty’s too precious a thing to be buried in books.
    Sidney Buchman (1902–1975)