첫 번째 Linked List의 이야기
Source: Dev.to
🙋♂️ 안녕하세요
이 이야기에서는 단순 배열이 제기한 데이터 구조 문제를 해결하기 위해 연결 리스트가 처음 어떻게 사용되었는지 알아볼 것입니다. 시작해봅시다.
서문: 순서 없는 문제
1950년대 초, 컴퓨터는 아직도 진공관과 펀치 카드로 가득 찬 거대한 방이었습니다. 가장 시급한 과제 중 하나는 동적 메모리 관리—실행 중에 컬렉션의 크기가 변할 수 있을 때 아이템들을 어떻게 저장할 것인가 하는 문제였습니다. ENIAC이나 Manchester Mark 1과 같은 초기 기계들은 고정 크기 배열을 사용했으며, 모든 요소는 미리 정해진 메모리 슬롯을 차지했습니다. 프로그램이 예약된 공간보다 더 많은 메모리를 필요로 하면, 프로그램은 충돌하거나 귀중한 메모리를 낭비하게 되었습니다.
RAND Corporation의 젊은 컴퓨터 과학자 Allen Newell(후에 Herbert A. Simon이 합류)에게 이 문제가 찾아왔습니다. 그들은 인간의 문제 해결을 시뮬레이션하는 프로그램, 즉 나중에 Logic Theory Machine이 될 프로젝트를 진행하고 있었습니다. 그들의 알고리즘은 끊임없이 증가하는 논리 명제 리스트를 추적해야 했지만, 런타임에 생성될 명제의 수를 예측할 수 없었습니다.
Chapter 1: 통찰
아이디어를 냅킨에 스케치하던 중, 뉴웰은 chain of boxes를 상상했다. 각 박스는 데이터 조각과 다음 박스로 가는 pointer를 가지고 있었다. “각 박스가 다음 박스가 어디에 있는지 알면, 기존 박스를 옮기지 않고도 새로운 박스를 어디든 추가할 수 있겠군.” 라고 그는 생각했다. 이 개념은 단순했다: 연속된 메모리 블록 대신, 데이터 구조가 주소로 연결된 일련의 노드가 되는 것이다.
그는 이 아이디어를 동료 Clifford Shaw에게 보여주었다. 샤우는 초기 인공지능 프로그램에서 동적 데이터를 다루느라 비슷한 고민을 하고 있었다. 두 사람은 함께 개념을 다듬어, 각 노드가 두 개의 필드를 갖도록 했다—data(실제 값)와 link(다음 노드의 주소). 첫 번째 노드는 head라 불리고, 마지막 노드는 체인의 끝을 나타내는 특수 null 값을 가리키도록 설계했다.
Chapter 2: 첫 번째 구현
1955년, 뉴웰, 쇼, 사이먼은 **RAND “Logic Theory Machine”**용 프로그램을 작성했으며, 이 프로그램은 파생된 정리를 저장하기 위해 노드 체인을 사용했습니다. 정리의 개수를 사전에 알 수 없었기 때문에, 연결 리스트는 새로운 정리가 증명될 때마다 새로운 노드를 할당하고 이전 노드와 연결할 수 있게 해주었습니다. 정리를 삭제하는 것도 마찬가지로 간단했습니다: 이전 노드의 링크를 조정하여 원하지 않는 노드를 건너뛰면 됩니다.
그들의 코드는 IBM 704용 어셈블리 언어로 작성되었으며, 대략 다음과 같이 보였습니다(예시를 위해 단순화됨):
ALLOCATE NEW NODE
STORE THEOREM IN NODE.DATA
SET NODE.LINK = NULL
IF LIST IS EMPTY THEN
HEAD = NODE
ELSE
LAST.LINK = NODE
END IF
LAST = NODE이 솔루션의 우아함은 꼬리에서의 O(1) 삽입과 검색 시 O(n) 순회라는 두 가지 특성에 있었습니다—바로 그들이 필요로 했던 트레이드오프였습니다.
Source: https://example.com/source-link
3장: 출판 및 확산
Newell과 Simon은 1956년 논문 “A Logic Theory Machine”에서 그들의 연구 결과를 발표했습니다. 주요 초점은 자동 정리 증명에 있었지만, 리뷰어들은 새로운 데이터 구조를 주목했습니다. “linked list”라는 용어는 아직 등장하지 않았으며, 저자들은 이를 “chain of records”라고 불렀습니다.
동시에, 당시 대학원생이던 Donald Knuth는 정렬 알고리즘에 관한 박사 논문 작업 중 이 아이디어를 접했습니다. 그는 용어를 정리하여 그의 대표적인 1968년 저서 The Art of Computer Programming에서 “linked list”라는 구절을 만들었습니다. Knuth의 명확한 설명은 신흥 컴퓨터 과학 커뮤니티 전반에 걸쳐 이 개념이 퍼지는 데 크게 기여했습니다.
Chapter 4: 왜 연결 리스트가 중요했는가
연결 리스트는 초기 컴퓨터들의 근본적인 한계를 해결했습니다:
- 동적 크기 – 노드를 추가하거나 제거할 때 전체 메모리 블록을 재할당할 필요가 없었습니다.
- 효율적인 삽입/삭제 – 리스트를 변경하려면 몇 개의 포인터만 업데이트하면 되었으며, 대량의 데이터를 이동시킬 필요가 없었습니다.
- 메모리 활용도 – 사용되지 않는 메모리는 개별 노드를 해제함으로써 회수할 수 있었으며, 메모리가 킬로바이트 단위로 측정되던 시절에는 매우 중요한 장점이었습니다.
이러한 특성 덕분에 연결 리스트는 초기 운영 체제 구성 요소(프로세스 제어 블록, 파일 할당 테이블)와 이후 스택, 큐, 보다 복잡한 트리와 같은 데이터 구조들의 핵심이 되었습니다.
에필로그: 사슬은 계속된다
1950년대 논리‑이론 프로그램에서 시작된 그 겸손한 노드 사슬은, 이제 모든 1학년 컴퓨터‑과학 학생에게 가르쳐지는 기본 개념으로 성장했습니다. 현대 언어들은 포인터 연산을 우아한 추상화 뒤에 숨겨두지만, 핵심 아이디어는 변함없이 데이터의 개별 조각들을 참조로 연결해 유연하고 확장 가능한 사슬을 만드는 것입니다.
따라서 다음에 스택에 아이템을 푸시하거나 파이썬에서 단일 연결 리스트를 순회할 때, 여러분은 반세기 전 앨런 뉴웰과 그의 동료들이 만든 동일한 사고 경로를 걷고 있다는 사실을 기억하세요—링크 하나하나, 노드 하나하나씩, 가장 단순한 연결에서부터 점점 더 큰 구조를 구축해 나가는 과정입니다.
🙋♂️ 안녕