Inventor of Linked List

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

Linked List is one of the most fundamental Data Structure and it was developed in 1953 by Hans Peter Luhn, Allen Newell, Cliff Shaw and Herbert Simon from IBM and RAND Corporation.

Table of contents:

Who is Inventor of Linked List?
Idea of Linked List in 1953
Implementation of Linked List in 1955 and beyond
Patent on Linked List?
Conclusion

Inventor of Linked List
Background information
Idea on:	1953
Implemented on	1955
Inventors	Hans Peter Luhn, Allen Newell, Cliff Shaw and Herbert Simon
Company associated	IBM, RAND Corporation
Award	Turing Award in 1975
Patented on	2002
Patent Inventor	Ming-Jen Wang
Patent Company	LSI Logic Corporation

Pre-requisite:

Who is Inventor of Linked List?

4 people are credited with the Invention of Linked List. The chronology is as follows:

1953: Idea of Linked List was published by Hans Peter Luhn
1955: Linked List was implemented in a production software by 3 developers: Allen Newell, Cliff Shaw and Herbert Simon

Therefore, the main Inventors of Linked List are:

Hans Peter Luhn
Allen Newell
Cliff Shaw
Herbert Simon

Idea of Linked List in 1953

The idea of Linked List was first proposed by Hans Peter Luhn in 1953. Hans Peter Luhn is the inventor of Hash Map. It was proposed as an approach for Chained Hash Map.

Hans Peter Luhn is an unique figure in Computer Science as he was a Textile Engineer initially and later, joined IBM as a developer and made huge contributions while working on Text based applications.

Implementation of Linked List in 1955 and beyond

Linked lists were developed in 1955 by 3 employees of RAND Corporation namely Allen Newell, Cliff Shaw and Herbert Simon

Linked List was first developed as the internal data structure for a new Information Processing Language at RAND Corporation. The Information Processing Language was used to develop AI programs, General Problem Solver, Chess Program and much more.

The report on the work was published in IRE Transactions on Information Theory in 1956, Proceedings of the Western Joint Computer Conference in 1957 and UNESCO Conference in 1959. This work received the ACM Turing Award in 1975 for contributions to AI. The work involved Linked List.

In 1958, LISP programming language was developed by John McCarthy at MIT. In 1960, a paper was published on the design of LISP at Communications of the ACM and Linked List was a major component of LISP design.

Patent on Linked List?

A Patent on Linked List was issued in 2006 and this is a controversial patent as Linked List is a general Data Structure.

A patent application was submitted by Ming-Jen Wang on 26 September 2002. Ming was an employee of LSI Logic Corporation. The patent was approved on 11 April 2006.

Application number: 10/260,471
Family ID: 32029692
Assignee: LSI Logic Corporation
Inventor: Ming-Jen Wang
Filed: 26 September 2002
Approved: 11 April 2006

The abstract of the concerned patent is as follows:

A computerized list is provided with auxiliary pointers for traversing the list in different sequences. One or more auxiliary pointers enable a fast, sequential traversal of the list with a minimum of computational time. Such lists may be used in any application where lists may be reordered for various purposes.

Find more information on this patent here on USPTO site.

Conclusion

With this article at OpenGenus, you must have the complete idea of how Linked List came into existence and who are the great Inventors behind Linked List.