Lịch sử của các loại cấu trúc dữ liệu điển hình
Công thức “Data Structure + Algorithm = Program” đã quá quen thuộc và trở thành
cẩm nang cho các lập trình viên từ thời kỳ lập trình mã máy (Assembly, …) cho
đến khi các công nghệ hướng đối tượng (object-oriented programming

) và lập
trình trực quan (visual programming) nắm giữ tư tưởng chủ đạo của lập trình. Bài
viết đóng góp sự hiểu biết về lịch sử ra đời và phát triển của các loại cấu trúc dữ
liệu điển hình từ các loại danh sách (lists) cho đến cấu trúc dữ liệu dạng cây (trees)
.
Hy vọng bạn học hiểu phần nào nguyên do và những động lực, cũng như những cái tên giúp khai sinh ra
một trong những thành phần quan trọng nhất của máy tính nói chung và lập trình nói riêng.
Nguồn gốc sự ra đời của danh sách
Danh sách tuyến tính (Linear List)

và các mảng (rectangular arrays)
4
để lưu trữ thông tin ở các vị trí bộ nhớ liên tiếp
(memory locations) đã được sử dụng từ những ngày đầu tiên của máy tính có khả năng lưu trữ chương trình (stored-
program computers) hay trong những chương trình cơ bản đầu tiên để duyệt (traverse) các cấu trúc này - phép toán cơ bản
nhất và buộc phải có trong bất kỳ loại cấu trúc dữ liệu nào. Ví dụ như các công trình của các nhà khoa học máy tính nổi
tiếng như J.von Neumann
4
vào năm 1946, hay Wilkes
4
vào năm 1951 đặc biệt là của Konrad Zuse vào năm 1945. Trong
công trình của mình, Zuse là người đầu tiên phát triển các thuật toán quan trọng làm việc với các danh sách có độ dài thay
đổi (varying lengths). Trước khi các phép toán đánh chỉ số (indexing) ra đời, các phép toán trên danh sách tuần tự
(sequential list) được thực hiện bằng chính các lệnh (instructions) trên ngôn ngữ máy, và những yêu cầu các phép toán số
học như vậy là một trong những động lực tạo ra các máy tính có các chương trình chia sẻ bộ nhớ chứa dữ liệu mà chúng
phải xử lý.

5
, và H.A Simon
5
với các nghiên cứu giải các bài toán heuristic bằng máy tính: đó là
chương trình hỗ trợ cho việc chứng minh các công thức logic toán học bằng cacsh thiết kế một ngôn ngữ xử lý danh sách,
tiền than của các ngôn ngữ xử lý thông tin ngày nay (list-processing) đầu tiên (gọi là IPL-II, IPL là viết tắc của Information
Processing Language) vào mùa xuân năm 1956. Đó là một hệ thống sử dụng các con trỏ (pointers) và các khái niệm quan
trọng như danh sách (thời gian này, khái niệm ngăn xếp (stack) chưa xuất hiện). IPL-III, thiết kế 1 năm sau đó, khái niệm
“đẩy vào” (push down) và “lấy ra” (pop up) mới được thiết kế kèm coi là các phép toán cơ bản quan trọng. Công trình của
Newell, Shaw và Simon đã khích lệ được nhiều người trong việc sử dụng bộ nhớ liên kết, sau đó kỹ thuật này được coi
như một khái niệm lập trình cơ bản (ngày này danh sách liên kết là một trong những kiểu cấu trúc thú vị nhất, xuất hiện
trong hầu hết các sách và ngôn ngữ lập trình), bài toán thực tế đầu tiên được áp dụng do J.W.Carr giải vào năm 1959. Carr
đã chỉ ra rằng danh sách liên kết có thể được xây dựng và xử lý trong các ngôn ngữ lập trình sẵn có mà không cần các thủ
tục phức tạp hoặc các hệ thống biên dịch khác. Đầu tiên, bảng liên kết sử dụng các nút 1 vị trí (one-word node), nhưng
khoảng năm 1959 người ta phát hiện ra sự hữu dụng của các nút trên nhiều vị trí liên tiếp cũng như danh sách “đa-liên kết”
(multilinked) cũng ra đời sau đó. D.T Ross là người đầu tiên thực thi ý tưởng này vào năm 1961, tại thời điểm đó ông ta
dùng khái niệm “plex” thay cho khái niệm “node” được sử dụng rộng rãi sau này, “plex” còn được sử dụng như là một tập
các nút gắn với một thuật toán duyệt (traversal) tương ứng.
Thông thường, ký hiệu chỉ các trường thông tin trong một nút của danh sách thường bao gồm hai loại: trước (precede)
hoặc sau (follow) tên của con trỏ. Vì thế một số viết INFO(P) trong khi một số lại viết P.INFO, hai kiểu ký hiệu này được coi
là tương đương. Ký hiệu này rất thuận lợi khi dịch trực tiếp qua các ngôn ngữ như FORTRAN
5
, COBOL hay tương tự khi
đúng ta định nghĩa INFO và mảng LINK và sử dụng con trỏ P làm chỉ số (index). Hơn nữa nó mang tính tự nhiên và gần gũi
với các ký hiệu toán học thông thường khi mô tả thuộc tính của các nút trong danh sách. Điều này gây ảnh hưởng đến các
nhà thiết kế chương trình dịch, và nó là một phần thú vị của lịch sử ra đời các ngôn ngữ lập trình cũng như cấu trúc dữ liệu
cho chúng. Trong cuốn sách kinh điển của mình, GS Knuth có bàn luận kỹ hơn về chúng.
Ngăn xếp và hàng đợi (Stack and Queue)
Có lẽ những người đầu tiên nhận ra nguyên tắc hoạt động của ngăn xếp (vào-sau-ra-trước, LIFO last-in-first-out) và hàng
đợi(vào-trước-ra-trước, FIFO first-in-first-out) là các nhân viên kế toán (accountants) khi thực hiện việc giảm thiểu các đánh

các công thức đại số biểu diễn dưới dạng mã 3 địa chỉ mở rộng, công trình sau đó được đăng trong hội nghị về tính toán tự
động ở thủ đô Washington DC ở Hoa Kỳ vào năm 1954.
Sau đó, cấu trúc dữ liệu kiểu cây theo nhiều cách được nghiên cứu và phát triển độc lập bởi nhiều nhà khoa học trong
nhiều chương trình và ứng dụng máy tính, nhưng các kỹ thuật cơ bản xử lý cấu trúc cây (không phải là xử lý danh sách
chung chung) thường ít xuất hiện ngoại trừ một số bản đặc tả chi tiết của một số thuật toán cụ thể. Bản nghiên cứu tóm tắt
và tổng kết (survey) đầu tiên với việc nghiên cứu cụ thể các cấu trúc dữ liệu do Iverson và Johnson công bố trên Báo cáo
nghiên cứu của tập đoàn máy tính IBM.
Tóm lại, bài viết tóm lược lịch sử phát triển của cấu trúc dữ liệu dùng trong lập trình máy tính nói chung và hai kiểu cấu trúc dữ liệu
điển hình (cây và danh sách) nói riêng. Hy vọng nó có ích phần nào và gây thú vị cho bạn đọc.