Linked List

Array는 위치 접근이 빠르지만, 중간에 값을 넣거나 빼면 뒤 원소를 밀어야 합니다. 데이터 길이가 자주 변하고, 특정 지점 앞뒤에 항목을 붙였다 떼는 작업이 반복되면 이 이동 비용이 부담이 됩니다. Linked list는 이때 값들을 다시 복사하는 대신 연결만 바꿔 구조를 수정하려는 요구에서 나왔습니다.

초기의 시스템 소프트웨어와 컴파일러, 운영체제 내부 구현에서는 메모리를 한 번에 크게 확보하기 어렵거나 구조 크기가 실행 중에 계속 변하는 경우가 많았습니다. 이런 환경에서는 연속 메모리보다 '필요할 때 노드를 하나 더 만들어 연결한다'는 모델이 더 실용적이었습니다. Linked list는 그 동적 구조 표현의 기본형으로 자리 잡았고, 이후 queue, stack, free list 같은 많은 구조의 내부 구현에도 영향을 줬습니다.

Linked list는 head pointer가 첫 노드를 가리키고, 각 노드는 자신의 값과 next 참조를 가집니다. 원하는 값을 찾으려면 head에서 시작해 next를 따라 한 노드씩 이동해야 합니다. 대신 삽입이나 삭제는 대상 지점의 앞 노드를 알고 있을 때 next 참조만 바꾸면 되므로, 뒤 원소 전체를 옮길 필요가 없습니다. 즉 위치 계산보다 연결 재배선이 중심인 구조입니다.

Linked list와 array의 차이는 저장 방식에서 바로 나옵니다. Array는 연속 공간을 전제로 해 인덱스 접근이 빠르고, linked list는 연결 관계를 전제로 해 재배치가 쉽습니다. 또 linked list는 순서대로 따라가야 하므로 '빠른 탐색' 자체가 핵심인 구조는 아닙니다. 검색 성능과 정렬된 상태 유지가 중요해지면 binary search tree 같은 탐색 트리로 관심이 옮겨갑니다.

Linked list는 큐와 스택의 내부 표현, 메모리 관리용 free list, 충돌 체이닝 버킷, 노드 연결을 자주 바꾸는 파이프라인 구조처럼 '위치를 다시 묶는 작업'이 많은 곳에서 유용합니다. 반대로 화면 목록처럼 n번째 항목을 반복해서 읽거나 캐시 친화적인 순차 순회가 중요한 상황에서는 array가 더 자연스럽습니다. linked list는 빠른 랜덤 접근이 아니라 유연한 연결 수정이 핵심인 구조입니다.