Editing Linked list (section)

==History==
Linked lists were developed in 1955–1956, by [[Allen Newell]], [[Cliff Shaw]] and [[Herbert A. Simon]] at [[RAND Corporation]] and [[Carnegie Mellon University]] as the primary [[data structure]] for their [[Information Processing Language]] (IPL). 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.{{citation needed|date=January 2019}}

Another early appearance of linked lists was by [[Hans Peter Luhn]] who wrote an internal [[IBM]] memorandum in January 1953 that suggested the use of linked lists in chained hash tables.<ref name="knuth">
  {{cite book
  | first=Donald |last=Knuth |author1-link=Donald Knuth
  | title = The Art of Computer Programming
  | volume = 3: ''Sorting and Searching''
  | edition = 2nd
  | publisher = Addison-Wesley
  | year = 1998
  | isbn = 978-0-201-89685-5
  | pages = 547
  }}
</ref>

[[LISP]], standing for list processor, was created by [[John McCarthy (computer scientist)|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 other directories and extend to any depth.